Tech Interview Question-Is my approach correct?

Answer 1

If I get question correctly you can solve this in O(n) time.

1. find two same elements using "hash" of size N
2. set one of this elements to 0.
3. make sum of elements and substract from calculated sum and you have the missing/replaced element (sum of elements is (2M+N-1)*(N)/2

EDIT:

Explanation of 1. point (find two same elements using "hash" of size N)

1. If you do not not know M find it (finding smallest element is O(n) , just one loop)
2. Alocate array h of size N and set elements to 0 (can be type BOOL )
3. go trough table and check 1 at apropriate location off h
4. if it is 1 then you have colission, else set 1.

code for last part:

for(i=0;i<N;i++)
{
    if(h[a[i]-M] == 1) return i;
    h[a[i]-M] == 1;
}

Answer 2

This is a classical interview "riddle". It is in fact quite easy to solve in O(n) using the trick ralu described.

One of the things we teach in Data Structures 1, is that when your domain is limited, it might be possible to use that for a function better than O(nlogn) [obviously, sorting a domain without any additional knowledge cannot be done in less than that]. So when you know your domain - a little red light bulb should be turned on in your head somewhere :-)

I think that you should have immediately pointed out the question about the duplicates. It would make it clear that the question is not well formed. Otherwise, he just thought that you're slow (although it is in fact his fault...).

I also think that questions 4,5 are good questions. They show what experience an applicant has, and how the applicant thinks. So it may be possible that you failed the interview because of something you said there.

Answer 3

Since no limits are specified on the amount of memory you are allowed to use, there is an O(N) solution: initialize an array A of size N to all zero. Look at each element b in the list and mark A[b - M] = 1. Then walk A and return c if A[c] == 0.

Answer 4

@Rulu
Can you elaborate more on point 3. If I am understanding it correctly, then taking the difference between the sum of elements and the expected sum according to the formula would only give the difference between the original element and the element with which it was replaced.

For example, if the numbers are 3,4,5,6,7 (Sum is 25) and let us say I replace 6 with 4 so the new array is 3,4,5,4,7 (Sum is 23). The difference 2 is not the answer we are looking for.

Answer 5

It's absolutely impossible for anyone here to answer your question properly. You're writing this up after the fact in a clear manner.

• perhaps you rambled in your interview or did not express yourself quite as clearly as in this question!
• perhaps you didn't ask the right questions quickly enough
• perhaps you weren't quite as quick on the uptake after being given pointers (or not as quick as your competitors)
• perhaps the interviewer didn't like the fact that you started writing code before thinking through the problem

I have given umpteen interviews where I have felt that the person I am interviewing knows the answer to the question I'm asking. They just can't tell me: they're flustered or jumbled in their thinking. Some people's thought processes clearly run ahead of their mouths and they jump about confusingly. I'll wager a few of them go away and construct perfect answers like yours...

I can't tell you whether you did these things; perhaps your interviewer was being unreasonable. I know I've had interviews which didn't go so well for what I felt was no fault of my own. But at the moment, I find myself thinking things like:

• could I put this person in front of a user?
• is (s)he joining the dots of this quickly enough?
• have they just waded right in without thinking it through?
• how do they compare to the person I saw an hour ago?

Answer 6

O(nlogn) Solution Using B trees:..

Assuming we construct a binary tree as the array is made too ...since the complexity to construct an bin tree is O(n). Another assumption is that any element equalor lesser than is placed to the left of the binary tree.

Here we check each element in the array for its left node to be the same as the parent node for each subtree. To traverse the tree takes a time of O(logn). We try to find a duplicate for each of the n elements. Hence overall time is O(nlogn).

O(n) Solution using B trees and recursion:

We can construct a btree like mentioned above and using the same assumptions. Check for each left child to be same as parent . Do the same with both children . The stopping condition for the recursion is if child is NULL. Hence each node is checked once . So the total time taken is O(n).