## Microsoft Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
1
of 3 vote

A not so bad solution would be to sort the array (O(n * log n)), then just scan all the elements from start to end to see for repetitions (O(n)). So overall the algorithm complexity is O(n*logn)

If you give specifics about problem like, only positive integer or O(1) space or max integer is already given etc.. then there are better solutions.

Comment hidden because of low score. Click to expand.
0

Only positive integers.
Space required as minimum as possible!

Comment hidden because of low score. Click to expand.
0

Do you know the maximum integer value? Also can the array be changed or is it immutable?

Comment hidden because of low score. Click to expand.
0

No array cant be changed!

Comment hidden because of low score. Click to expand.
0

If its not to be changed, you can create a new byte array, with number of elements = MAX_INT/8, with all elements initialized to 0, all bits are 0's. In this array each bit represents a integer value in your original array. So you make a pass of your original array and set the corresponding bit in the new byte array. The moment you encounter a already set bit during pass, you are done. This is O(n) in time and takes space in bytes equal to max integer value in the array.

Comment hidden because of low score. Click to expand.
0

@ sunday programmer: Nice thought!!

Comment hidden because of low score. Click to expand.
0
of 4 vote

Which company? Does the problem say minimum number or is it just your interpretation?

Comment hidden because of low score. Click to expand.
0

Which idiot downvoted this? This is a perfectly valid question!

People are posting homework on this site, or interpreting the question completely wrong and posting their own version here.

For instance, trying to figure this out in the minimum number of comparison is going to be HARD problem and a moronic interview question.

Comment hidden because of low score. Click to expand.
0

Idiot = Prashant R Kumar.
LOL.

Comment hidden because of low score. Click to expand.
0

I back u up. It is because your question is valid.However, please don't blame on others. =^_^=

Comment hidden because of low score. Click to expand.
0

Its an MS interview question - not my interpretation.

Comment hidden because of low score. Click to expand.
0

Assume we have one more limitation on this question. The duplicate value appear twice in the second half of array. Then the question becomes
the question for finding duplicate in an array. (We consider the second half of array as an new array)

Comment hidden because of low score. Click to expand.
0

@Psycho: Are you absolutely sure the interviewer said _minimum number_ of comparisons? (Not asymptotically optimal, but _minimum number_).

Also, what about the other questions in the interview? Why don't you post them?

And why not indicate the company as Microsoft in the question.

Comment hidden because of low score. Click to expand.
0

Actually my friend sat for microsoft. And told me the same.
I m sure that they say the minimum number of comparison !!

Comment hidden because of low score. Click to expand.
0

I think Hashset and HashTable is now allowed here. In addition, the original array is immutable.

Comment hidden because of low score. Click to expand.
0

@Psycho: So this is hearsay :-)

Perhaps you can ask your friend to recall what exactly was said...

I have seen a lot of candidates interpret statements like "can you do better" to mean "can you find the best possible solution" etc.

And given the way people post questions here, it is not a surprise.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Please explain the problem with simple an example...

Comment hidden because of low score. Click to expand.
0
of 0 vote

My understanding of the problem is, given an array a[1], ..., a[n], only a[i] and a[j] are the same number, while other elements are all distinct. However we don't know the index i, j. The only thing we know is j \in (i, i + arr_size/2]. We need to find both i and j.

I'm thinking of a method using a hash table which may work. For each element in a[i], if there is the same element in the hash table, then we have found this duplicated element, otherwise put a[i] into the hash table. Time complexity should be O(n). This algorithm should work, right?

One problem is that it did not take advantage of the information that the duplicated number must appear in the range (i, i + arr_size/2]. Also, since the range of the number is unknown, the size of hash table could be large if the largest number is very large and the hash function is not well chosen. Hope to see better method.

Comment hidden because of low score. Click to expand.
0

I also try to use the information that "half of the array size" - but till now i m not successful!

Comment hidden because of low score. Click to expand.
0

wat kind of hash table u suggest as there was no range of numbers specified!!!!!!

Comment hidden because of low score. Click to expand.
0

"An unsorted array is given, where there is no specific range in which the elements occur."
Still think you can use hash tables?

Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the array and compareevery element with its next element it takes nlogn+n time

Comment hidden because of low score. Click to expand.
0
of 0 vote

Please correct me if I am wrong or my understanding of problem is wrong. Here is my logic which makes use of the given range. Worst case would be O(n) if i is 0.

void find_dup(int *a, int i, int asize)
{
int n = (i+(asize/2) );
int ele = a[i];
if (n>asize)
printf("invalid range given!");

for (i=i+1; i<n; i++)
{
if (a[i] == ele)
printf ("duplicate ele found @%d", i+1);
}
printf ("No duplicate ele found within given range :%d", n);
}

Please let me know if this deals with the problem.

Comment hidden because of low score. Click to expand.
0

The problem is that we don't know i (if I understand correctly). In this case, the input i of your function will be unknown.

Comment hidden because of low score. Click to expand.
0

Hi Richard,
If only the element @a[i] and size is given, then we cant make use of the range in which case we should go for hashing!!! Or else, we can use of offsetof()?

Comment hidden because of low score. Click to expand.
0

This is also what I'm thinking, use hash table and we have O(n) time complexity. But then we will not be able to use the range information. Maybe this interview problem is weird.... :) Idk

Comment hidden because of low score. Click to expand.
0
of 0 vote

If elements are separated by array.length/2,just make a linear scan and compare elements separated by that distance.

Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i=0;i<A.size/2;i++){
for(int j=i+1;j<i+A.size/2;j++){
if(A[i]==A[j]) return A[i];
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

we can use a hash map here of max size (n/2)........start traversing the array from 0 to (n/2)-1 element and put it into the map. If during this you encounter any element which is already in the map and has appeared once once .. stop .. dats ur answer ..
else from (n/2) index "i" remove the last range element (i - n/2 ) from the hash and insert "i"th element... continue the process untill u find ur answer

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use the hastable as follows. First, travel one round and set H[a[i]] = 0. Use a temporal variable total = 0. Do one more round, by adding to total: total += i * (++H[a[i]]). When we finish, we will have total = 0 + 1 + ... + (n-1) + j where a[i] = a[j], i < j, so we can computer j. Similarly, if we travel from right to left of the array, we can compute i.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.