## Microsoft Interview Question for Software Engineer / Developers

• 1
of 1 vote

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.

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

Definitely

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

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

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

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

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

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).

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;

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

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

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

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.

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

numbers may be negative btw.

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

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

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

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

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

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

Will you be able to solve the problem now?

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

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

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

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

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

How will you add the shift

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..

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..

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

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.

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.

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

Use counting sort. - O(n)

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 points to a, a points to a , a points to a, a points to a and a points to a. Now consider this as a directed graph with a to a as nodes and the points to as directed edges. Start with a 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;

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

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..

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 points to a, a points to a , a points to a, a points to a and a points to a. Now consider this as a directed graph with a to a as nodes and the points to as directed edges. Start with a 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).

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

nice

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

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.

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

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

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

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

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

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.

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

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

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

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

What if k is negative?

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

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.

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.

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

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.

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

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

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

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

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-1st element, a[k]-k+1 element in array

now A=1; and A=6 now A= -6
A=6 and A=3 now A=-3
A=4 and A=2 now A=-2
A=5 and A=6 now A=-6
A=-2 and A[abs(-2)]=4 now A=-4
A=-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.

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-1st element, a[k]-k+1 element in array

now A=1; and A=6 now A= -6
A=6 and A=3 now A=-3
A=4 and A=2 now A=-2
A=5 and A=6 now A=-6
A=-2 and A[abs(-2)]=4 now A=-4
A=-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.

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

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

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

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

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.

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.

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?

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.