Best coding interview question of all time.

Question: Given an array of N+1 integers containing elements in range [1, N]. Find any one duplicate number.

This question itself is self explanatory but I have experienced that candidates asks clarification questions which is actually a good thing.

Some of the common clarification questions are.

• Candidate: Can you provide an example?
• Interviewer: [4, 3, 1, 1, 2].
• Candidate: Will there be only one repeated number?
• Interviewer: Actually there can be more ex: [4,3,3,1,1,2].
• Candidate: Are we sure that repeated number will always be present?
  - This is bad clarification question! why?
  - As we already know that size of array is N+1 but no of distinct elements it can have is N, So by pigeonhole principle we can say that it will definitely have repeated elements.
• Interviewer: Is it possible to have an array of size N+1 containing elements in range [1, N] to not have any repeated number?

Now candidate understood the problem he will start thinking about the solution and might also feels that it a pretty easy problem to solve.

Next conversation

• Candidate: Brute force solution would be to check for every number if it again present in the array or not.
  - Every candidate does that, to start with brute force solution. My take on this is start with some level of optimal solution.
• Interviewer: Can we do better? (Or he might ask about time complexity and then ask this question.)
• Candidate: We can use HashMap and maintain count of each element of the array, as soon as we found an element whose count is more than 1 we found our answer.
  - Yay! we found an O(N) solution but still this is a very trivial solution. Ideally candidate could have provided this solution first and saved some time.
• Interviewer: What is the time and space complexity of this solution?
• Candidate: Time complexity O(N) Space complexity O(N).

Till here all good now come a followup questions.

• Interviewer: Can we solve this problem without using additional space?
• Candidate: We can sort the given array and then we will repeated elements adjacent to each other and we can easily find that.
• Interviewer: But this will increase the time complexity to O(NLogN). Is there anything else we can do.

At this point I have seen that some candidates starting thinking that its a math problem, like we can find some of elements of array and some of elements from [1 to N] is N*(N+1)/2 etc etc. Actually they are getting confused with another problem similar to find but the question is completely different. The question is. Given that array will have only 1 number repeated twice and elements are in range [1, N] and every other element occur only once. find missing and repeated element.

In this problem we cannot apply sum of elements strategy as we don’t know how many elements are repeated and how many times they are repeated.

Most of the candidates get stuck at this point.

Hint: On the line of HashMap strategy, instead of using HashMap can we use array index itself to mark elements?

• Candidate: Ok ok I got it! As the elements are in range [1, N] and array size is N+1 I can use array index to mark if element is present of not by using element as index and making element at that index negative. Can I write code to explain this? Or take an example?
• Interviewer: Explain with an example.
• Candidate:
  - arr = [4, 1, 3, 2, 5, 4, 5, 5]
  - take 4 and go to 4th index and make that number negative
  - arr = [4, 1, 3, 2, -5, 4, 5,5]
  - We also need to take absolute value.
  - next process 1, arr = [4, -1, 3, 2, -5, 4, 5, 5]
  - next process 3, arr = [4, -1, 3, -2, -5, 4, 5, 5]
  - next process -2, arr = [4, -1, -3, -2, -5, 4, 5, 5]
  - next process -5, arr = [4, -1, -3, -2, -5, -4, 5, 5]
  - next process -4, arr = [4, -1, -3, -2, -5, -4, 5, 5] abs(-4) = 4 and 4th index is already negative means that number 4 is encountered 2nd time So 4 is the answer.
• Interviewer: Can you write the code.
• Candidate: yes.

Here is the code

Candidate might feels that he nailed it. But interview is not over yet. Here comes another followup question.

• Interviewer: What if given array is immutable?
• Candidate: Ohh, We are not allowed to modify input array?
• Interviewer: Yes.
• Candidate: What if after modifying the array I revert all the changes, Can I do that?
• Interviewer: No, Given array itself is not mutable and you also cannot used additional space.

Most of the candidate gives up at this point. But some asks more questions.

• Candidate: Are we looking for an O(N) solution?
• Interviewer: For now only major constraint is that array is immutable and we need solution better than O(N²). Can we solve this with O(NLogN) time complexity?
• Candidate: This is a searching problem logN complexity generally comes in binary search or divide and conquer. But the given array is not sorted.

Hint: Can we apply binary search to this problem. Though our input array is not sorted but our search space [1, N] is sorted. Also if we are looking to solve this problem with O(N*LogN) complexity we can still perform O(N) operations on our array LogN times.

Very few candidates get this hint.

• Candidate: Okay got it. I think I can binary search for a duplicated number. For example, I go through the list and count the number of integers between 1 and N/2. If the count is greater than the number of possible integers in that range, then I know there’s a duplicate in that range. Otherwise, a duplicate must exist in the range of N/2+1 to N. Once I know which half of the range the duplicate is in, I can recurse and binary search in that half, then keep repeating the process until I’ve found a duplicated number. The time complexity is O(n*log n) and the space complexity is O(1).
• Implementation

Time complexity O(NLogN) Space complexity O(1)

• Interviewer: Excellent!
• Interviewer: I have one more followup question.
• Candidate: (In his mind Now what! are you not satisfied yet) Yes tell me.
• Interviewer: Can we solve this with O(N) time complexity if there is only one repeated number.
• Candidate: (In his mind I don’t think so). Yeah sure let me try.

Most of the candidates get frustrated at this point and Now they realised that how this simple problem turned out very difficult.

Almost everyone needs hint at this point.

Hint: Do you know about hare and tortoise or slow fast pointer technique?

• Candidate: Yes, it’s used to detect cycle in linked list and also helps in finding starting point of the loop.
• Interviewer: Good. If you observe closely in this problem also there’s a loop.
• Candidate: How?
• Interviewer: If you consider array as linkedList and every index points to the index which is equal to value at that index.
• Candidate: Let me take an example.

Consider example array = [2, 6, 4, 1, 3, 1, 5]

0th index points to 2nd, then 2nd points to 4th and so on.

• Candidate: Okay I got it now.
• Interview: Can you write code for this.
• Candidate: Here is the code.

Time complexity: O(N) Space complexity O(1) and array is immutable.

This solution won’t work if we have multiple repeated numbers.

• Interviewer: I have another followup question.
• Candidate: (Gets angry) I’m done with this interview.
• Interviewer: But my question is.. How soon can you join this company :)

This is great interview question because

• The candidate’s general competence with algorithms, space/time complexity, etc.
• The candidate’s ability to respond to different constraints and handle various trade-offs. This is something engineers deal with all of the time, and it’s a critical skill to have.
• The candidate’s creativity. Each constraint forces a person to start from scratch and think of a completely new approach — a great test of creativity.
• The candidate’s attitude toward complexity. Some candidates get permanently stuck because they start off by trying to come up with the O(n*log n) time / O(1) space solution. They assume that using a hash or comparing all elements of the list to all other elements is not what you’re looking for, and so they don’t mention the easy solutions (but also can’t figure out the harder solutions). This is a yellow flag that the candidate tends to overcomplicate things (I’ll typically ask subsequent interviewers to watch out for this tendency).
• The candidate’s passion for learning and challenges. Some people get excited when you throw in harder and harder constraints, others get dejected and/or lazy.

Thanks for reading

Happy coding!!!