Microsoft Interview Question for Software Engineer / Developers






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

Since the range of numbers is less than k,say from zero to k,we need to check only atmost k+1 items in the array.the element at k+1 is sure to differ.So I think so we can obtain O(k)by using hashing method.

- Musheka January 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Definitely

- gevorg January 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Pigeon hole principle FTW ...but numbers s'd be +ve

- Ulquiorra September 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int FindFirstDuplicate(int[] arr,int k)
{
Hashtable hash = new Hashtable();
int i = 0;
for (; i < k + 1; i++)
{
if (hash[arr[i]] == null)
{
hash.Add(arr[i], arr[i]);
}
else
break;
}
return i;
}

- Anonymous June 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution will not be in O(k) as you're not considering the cost of Hash Operations. The best way to do it is implementing Counting Sort which is in linear time and is in O(k).

- Biranchi July 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

k=11 here

int a[]={2,5,3,7,3,9,8,10,1,7,5,6};
int bucket[]=new int[11];

for(int i=0;i<11;i++)
{
bucket[a[i]]++;
if(bucket[a[i]]==2)
{
System.out.println(a[i]);
break;
}
}

- NK May 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

k for your example is not 11 but it's 10 (the max element in set)
Rest looks fine.

- Biranchi July 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Maintain a bit vector of size K. and figure out which is the first repeating one by initializing the vector to all zeros and flipping appropriate bit when ever read a number etc..

2) Hash table. Growing dynamically will save us some space at the cost of efficiency.

- Anonymous January 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

numbers may be negative btw.

- Anonymous January 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this case all numbers can be different. O(k) can be reached only in case if all of them is positive

- gevorg January 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

dont' understand what negative numbers have to do with this. So what if the list has negative numbers?

- Anonymous January 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose i gave you an array and said all numbers are > -k.

Will you be able to solve the problem now?

- Anonymous January 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sure, add a shift first, so that all the elements become positive

- forkloop January 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sure, add a shift first, so that all the elements become positive

- forkloop January 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How will you add the shift

- TheWolfe July 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How to obtain O(k)? ..Everybody understands that O(n) is possible..

- Mike January 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How to obtain O(k)? ..Everybody understands that O(n) is possible..

- Mike January 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess as n>k and the maximum possible number is k. So either the first k elements will be distinct or some repeating elements will occur already. So at k+1 th item we are bound to find a repeating element. So O(k) elements have to be checked (as we encounter j-th item check the hash table for a 1 or 0).

credit goes to Musheka.

- Anonymous January 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Mike: O(k) means O(n) only here, in general the meaning is O(x) where 'x' is the number of elements and in the above question

approximately we have 'k' numbers.

- vaibhav Garg January 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use counting sort. - O(n)

- Anonymous January 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I will explain with an example.
Let n=5, k=4 and the array is: a[] = {2,3,2,1,4} (Let us consider array index starts from 1)
Now we can use the array elements as the pointer to the array itself. Like a[1] points to a[2], a[2] points to a[3] , a[3] points to a[2], a[4] points to a[1] and a[5] points to a[4]. Now consider this as a directed graph with a[1] to a[5] as nodes and the points to as directed edges. Start with a[5] and travel the directed graph. You are sure to find a loop. (Figure out why?)
So, its like tail and a cycle. Now the problem is to simply find the beginning node of cycle, which is a duplicate integer.

Pseudo code:
i = n;
j = n;
while (i != j)
{
i = a[i];
j = a[a[j]]; // This is like detecting loop in a linked list
}
j = n;
while (i != j)
{
i = a[i];
j = a[j];
} //This while loop finds the first node of the loop
return i;

- spsneo January 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the issue is that creating the array of pointers requires you to scan the entire array of length n , thus the complexity is O(n) + O(k) .. which is O(n). correct me if i am wrong..

- Anonymous February 26, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I will explain with an example.
Let n=5, k=4 and the array is: a[] = {2,3,2,1,4} (Let us consider array index starts from 1)
Now we can use the array elements as the pointer to the array itself. Like a[1] points to a[2], a[2] points to a[3] , a[3] points to a[2], a[4] points to a[1] and a[5] points to a[4]. Now consider this as a directed graph with a[1] to a[5] as nodes and the points to as directed edges. Start with a[5] and travel the directed graph. You are sure to find a loop. (Figure out why?)
So, its like tail and a cycle. Now the problem is to simply find the beginning node of cycle, which is a duplicate integer.

Pseudo code:
i = n;
j = n;
while (i != j)
{
i = a[i];
j = a[a[j]]; // This is like detecting loop in a linked list
}
j = n;
while (i != j)
{
i = a[i];
j = a[j];
} //This while loop finds the first node of the loop
return i;


Order of this algo O(n) and space requirement is O(1).

- spsneo January 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice

- Anonymous January 29, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how does this work? if the elements happened to be the same as in the indexes your loops would just be reoccuring and go nowhere.

- Mac January 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

try to run the program with an example. You will understand it.

- spsneo January 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont think ur algo works for this example:
{2,2,3,3}, n = 4; k =3 It will return 3 and not 2

- TripleH January 31, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah you are true. I am sorry. I gave the algo to find just any repeating element. I was asked the question to find just any one repeating element.

- spsneo January 31, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Declare an bucket of size k. Then insert the element into appropriate bucket.

initialize bucket to zero

for(i = 0 ; i < n; i++)
{
bucket[inputarray[i]] ++;
if(bucket[inputarray[i]] == 2)
return the element, position and continue to find next repeating element
}

Time: Linear

- Sumanth Lingala February 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thats linear in O(n)... u need O(k)... what if u have a huge input, say n=2^k... O(n) isn't O(k)
checking first k sounds fine

- anonym February 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What if k is negative?

- Rob February 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

well in that case, you'll map the min number in the set to 0.
So if the set is {-10, -9, -6, -7, -8}, map -10 to 0. So every other element is compared with the +10th position.

- Biranchi July 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

let me rephrase the answer ... first create an array of k length.
now scan only till the first k+1 elements,(worst case), of the given array of length n whenever we get a new value , set the corresponding index in the array of length k to 1.(if it is zero). If the index already has value 1, display it , that is our answer.

assumption .
1) all nos. should be positive and within the range 1-k.

- Max Payne February 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can optimize your answer by replacing array of k length to an 32bit integer array of k/32. Set a bit to 1 corresponding to the value < k. And when you find a bit which already has been set to 1, then you have a first repeative value. Order is still same but memory usage is optimize in terms of array size reduced from k to k/32. Interviewers always look for your attempt to solve the question.

- Anonymous March 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

but our worst case is O(k+1). Interviwever is looking for O(k)?!?! Any answers??
Im not sure if we get credit if we modify the problem

- breeze February 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(k)=O(k+1) doesn't matter

- Anonymous March 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

one better approach can be using k bit number for finding that number is repeating or not instead of bucket or some other data structure

- Anonymous March 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

code is -(considering array contains only positive numbers)

for(i=0;i<k+1;i++){
if(A[abs(A[i])])<0) return abs(A[i]); //1st duplicate, abs is absolute function

A[abs(A[i])]*=(-1);

}




let k=6 , k<n

A= 1,6,4,5,2,6,3,..........
A[0]-1st element, a[k]-k+1 element in array

now A[0]=1; and A[1]=6 now A[1]= -6
A[1]=6 and A[6]=3 now A[6]=-3
A[2]=4 and A[4]=2 now A[4]=-2
A[3]=5 and A[5]=6 now A[5]=-6
A[4]=-2 and A[abs(-2)]=4 now A[2]=-4
A[5]=-6 and A[abs(-6]<0 therefore return 6

time complexity=O(k+1) and very much inplace solution .

The only point is the first K+1 numbers may get negated and the array is modified. In that case after finding the duplicate we can traverse the array again for the first k+1 no.s and make the negative numbers positive.

- Priyanka Chatterjee July 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

code is -(considering array contains only positive numbers)

for(i=0;i<k+1;i++){
if(A[abs(A[i])])<0) return abs(A[i]); //1st duplicate, abs is absolute function

A[abs(A[i])]*=(-1);

}




let k=6 , k<n

A= 1,6,4,5,2,6,3,..........
A[0]-1st element, a[k]-k+1 element in array

now A[0]=1; and A[1]=6 now A[1]= -6
A[1]=6 and A[6]=3 now A[6]=-3
A[2]=4 and A[4]=2 now A[4]=-2
A[3]=5 and A[5]=6 now A[5]=-6
A[4]=-2 and A[abs(-2)]=4 now A[2]=-4
A[5]=-6 and A[abs(-6]<0 therefore return 6

time complexity=O(k+1) and very much inplace solution .

The only point is the first K+1 numbers may get negated and the array is modified. In that case after finding the duplicate we can traverse the array again for the first k+1 no.s and make the negative numbers positive.

- Priyanka Chatterjee July 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice answer..!!!!

- Anonymous August 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just a random thought! Instead of hashing why can we not xor each element? worst case would be that at the k+1th element we are bound to get repetition.so O(k). The moment you get answer 0 record the last number xored..it's the first repeated vale..save and exit

- Guest November 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

stupid.
xor will come zero when all number will repeat previously occurred. how will you do it. 3 2 2 ...

- pankaj January 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For each ith element set a[a[i]-1] to -ve. One u get the 1st -ve elt that's the repetition.

- Avenger April 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I thought of this one. Not sure how good it is.
The OP says that there are n elements. The n elements are less than k. k is the value of the number in the array. so it means that all the n elements in the array are less than the value k(this is my understanding of the problem).
Now to solve the problem.
Traverse through the first k-1 elements in the array.
1) you could have found a repeating element by then.
2) if you haven't jump to the position k+1(don't go to the kth element). you can find the match for any one of the element before(as all the elements are less than the value k and occur only once until then). if the k+1 th element is not a match from any of the elements before then you can say that the kth element is repeating.

I am not sure that i am really clear. but you can work this out with an example.

- Mino De Raj November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What if we have nonintegers and/or negative values? Say k = 0, and the array is, say [-1.1, -1.2, -1.3, -1.4, -1.5, -1.6, -1.7, -1.8, -1.9, -1.1, ...]. Then we need O(n) time, right?

- Anonymous June 21, 2019 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More