Tech Interview Question-Is my approach correct?
algorithm
Solution
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.
Problem
Recently I was interviewed by a Software Company. I didnt make it through the first round itself. Maybe I was too slow in forming ideas or solving problems and wasnt good enough for the company that i interviewed for. I would like to have a second opinion about my interview and I cant find anyone better than the stackoverflow community. So this interview was a basic one - Introduction - Why you have applied for this position? - One Techincal Question(Details Below) - Whats the Worst software you have used? Why? Improve - Whats the Best Software you have used? why Improve? Original Technical Question(As asked by the interviewer) Given a Range of numbers M.....M+N-1 I contruct an array of size N and replace one of the element in that array with a number. How will you find what element is replaced? I asked him to repeat the question once more as I thought the input was not sufficient to solve the problem. He repeated the statement ditto Q. Then I asked him Is the array you got from the range of number in sorted order? Interviewer: Its not necessary Q Do we know the array before we replace an Element? Interviewer: No Then i started Writing some pseudo code(while doing loud thinking). I immediately realized that It wont work if the original array had duplicates. So I was stuk for a while thinking how the hell am gonna solve this.Then finally I asked questions that mattered Q How do you choose the elements from the Range to form the array? Interviewer: I have a range of number M, M+1, M+2....M+N-1. A number is picked only once. And I form an array of size N.(Which essentially means no Duplicates and all elements in the range get picked) Q What about the number you replace it with? Does it lie in the same range? Interviewer: Yes it does. Then everything became clear This was what he meant: Q I have a range of numbers starting from M , like M,M+1,M+2,M+3...M+N . I form an array of Size N, such that each element gets picked only once and the original array does not have any duplicates. I replace one of the elements in the array with a number in the same range. Find out what I picked from the range to replace? This is equivalent to finding duplicates in array. Here after replacement there will be only one pair of duplicates We can easily find that out in O(N^2) time or O(nlogn) time. I gave him both the algorithms. In the end I couldnt resist asking him "How did I perform in that question? He said Well you took a lot of time in answering. Clearly he was not satisfied with my approach to this question. What do you think I should have done differently while answering this question?