My favorite interview question to ask is:

Given a collection (list, array, vector) of integers, with n+1 integers in the range [1,n], find a duplicate.

What makes a question great?

First, I like this question because it's easy. When I asked this question all candidates came up with an answer in a few minutes. Even people without programming experience can solve this problem — try asking it to a non-engineer friend, using colors instead of numbers: "if you have 8 color markers, but only 7 colors, how do you find a duplicate pair?"

I think it's important to start a coding interview with an easy warmup question. Interviewing is stressful, and this question will put candidates at ease. They start the interview confident and relaxed. If you regularly interview candidates I strongly recommend you to start with a simpler version of the question you intend to ask. This will most likely give you better signal on the candidates.

Second, I also like this question because it has many solutions. If the candidate's solution prioritizes time, ask them for a different solution that prioritizes space, and vice-versa. This is a good way to test if the candidate understands algorithmic complexity, and to get a sense of their knowledge of data structures and algorithms. I usually like to discuss a couple solutions with the candidate before having them starting to write code.

Finally, I like this question because it can be optimized several times, and some of these optimizations will throw off even really good candidates. One of the things I'm looking for in candidates is how well they can learn from feedback, and this question has a few great opportunities to get that signal.

Initial solution

Most candidates will start with a brute-force solution comparing all numbers, or use a hash map to check for seen numbers.

Brute-force solution

The brute force solution simply compares all pairs of numbers:

def find_duplicate(numbers: List[int]) -> int:
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] == numbers[j]:
                return numbers[i]

    raise Exception("Invalid input")

I usually tell candidates that they can assume the input is valid if they ask, but assuming it without asking is a red flag.

This solution is quadratic in time, due to the nested for loops, and constant in space. If the candidate writes this solution I ask them to optimize for time, which usually leads to the next solution:

Hash map

This solution uses a hash map (or set) to keep track of the numbers that have been seen:

def find_duplicate(numbers: List[int]) -> int:
    seen = set()
    for number in numbers:
        if number in seen:
            return number
        seen.add(number)

    raise Exception("Invalid input")

Adding to the hash map and checking for membership is O(1), so the solution is linear in time and linear in space. If this is the candidate's first solution I'll ask them for a solution that uses constant space.

A better solution

Once we have discussed the two solutions above, I'll ask the candidate for a solution in constant space and better than quadratic time. Most candidates quickly realize that they can sort the numbers, and then scan the sorted collection looking for identical adjacent numbers:

def find_duplicate(numbers: List[int]) -> int:
    numbers.sort()                              # O(n log n)
    for i in range(1, len(numbers)):            # O(n)
        if numbers[i - 1] == numbers[i]:
            return numbers[i]

    raise Exception("Invalid input")

The time complexity is now O(n log n), and the space is constant. Note that if the candidate uses sorted() instead of the method .sort() I usually point out that they're creating a new list, and that they should sort in place using the method instead of the function.

Once the candidate has coded this solution, I ask them if they can make it faster.

Can we sort faster than O(n log n)?

After being asked to optimize this solution, many candidates will try to come up with a completely different solution, often with some kind of clever trick. Some candidates will start looking at ways to use XOR to find the duplicate number, which doesn't work in this problem because we don't know the distribution of numbers; they could all be the same number, eg.

When that happens, I try to bring them back to their previous solution and ask about its bottleneck: "why is it O(n log n)?" They mention that sorting the data is the bottleneck, and that the fastest sorting algorithms have time complexity O(n log n).

I then ask, "do you know what algorithm Python uses for sorting?" Most people don't know, so I tell them that Python uses an algorithm called Timsort[archived], named after Tim Peters of the Zen of Python[archived]. Even though it was created for Python, timsort has been ported to Java, Swift, V8 and other programming languages. I explain to them that Timsort usually does better than O(n log n), because it was designed for real-world data: usually data will be partially sorted, and the algorithm exploits these sorted subsequences to sort the data.

"Now", I say, "given that the data we're trying to sort is not random, but instead consists of numbers that can be from 1 to n, can we sort it faster than O(n log n) time?"

I don't know if the solution is obvious to you, but from my experience most candidates have a hard time at this point. Some will try to come up with their own sorting algorithms and end up reinventing bubble sort. Others will simply get stuck. So I usually tell the candidate we're going to take a step back, and I ask them: "given a list with all the numbers from 1 to n, how can we sort it in linear time?" I write a simple example on the whiteboard:

2 4 1 3

Eventually candidates will realize you can simply swap numbers, placing them at their expected position. If the number that it was swapped with ended up in the wrong position, swap it as well, until it's swapped with one that also falls in the right position. When that happens, proceed to the next number:

2 4 1 3
4 2 1 3  # 2 <-> 4
3 2 1 4  # 4 <-> 3
1 2 3 4  # 3 <-> 1

In code:

def linear_sort(numbers: List[int]) -> List[int]:
    for i in range(len(numbers)):
        number_at_position = numbers[i]
        expected_number_at_position = i + 1
        while number_at_position != expected_number_at_position:
            j = numbers[number_at_position - 1]
            numbers[i], numbers[j] = numbers[j], numbers[i]

    return numbers

To analyze the time complexity of the solution we need to realize that every swap puts one number in the correct position, so there are at most n swaps, making it linear.

Once the candidate has written this solution I remind them that we're not interested in sorting, but finding duplicates. How can we use the sort function to find a duplicate in linear time? A good candidate will see that they can try to sort the data, and simply check if the two numbers are identical when swapping them. In that case, they found a duplicate:

def find_duplicate(numbers: List[int]) -> int:
    for i in range(len(numbers)):
        number_at_position = numbers[i]
        expected_number_at_position = i + 1
        while number_at_position != expected_number_at_position:
            j = numbers[number_at_position - 1]
            if numbers[i] == numbers[j]:
                return numbers[i]
            numbers[i], numbers[j] = numbers[j], numbers[i]

    raise Exception("Invalid input")

Candidates who can come up with this solution are usually proud that they were able to sort faster than O(n log n).

Other solutions

For really strong candidates I usually throw in a new requirement: what if we want a solution in constant space and that does not modify the input?

We've already seen a solution that fits this criteria: it's the first one we wrote! The downside of that solution is that it's quadratic, so I ask candidates if they can make it slightly faster. This is a much harder problem, and since we usually don't have a lot of time left at this point I usually just ask the candidate to discuss the problem without writing any code. I'm mostly interested in figuring out their thought process.

If the candidate is stuck, I point out that we're looking for a solution that is O(n log n) in time, and I ask them what do algorithms that have that time complexity usually have in common. Most will realize that they are divide-and-conquer algorithms, reducing the problem space by half at each step. Candidates will usually try to come up with an algorithm that splits the array in half, but they quickly realize that it wouldn't work since the duplicate numbers could fall in separate sub-arrays.

"What if instead of dividing the problem space, you divided the solution space?"

The solution is to first determine if the duplicate number is between [1, n/2] or (n/2, n]. This can be done by scanning the array and counting how many numbers are in each subdomain. One of the halves will necessarily have more than n/2 numbers, so it must contain a duplicate. Note that the other half could still contain a duplicate, even though it has less than n/2 numbers! But that's OK, because we know for sure the half with more than n/2 numbers has a duplicate.

If we repeat the process, we do log n passes, and each one requires scanning n elements in the list. We use two numbers for storage, so the solution runs in constant space and O(n log n) time.

To be clear: I don't expect any candidates to come up with this solution on their own! When I ask this iteration of the question I'm already satisfied with their skills, so I'm happy with giving enough hints to see if they can come up with this solution.

Finally, there's a solution to this problem that uses constant space, linear time, and does not modify the input[archived]. The solution is clever and elegant, but I can't imagine any candidate coming up with the solution unless they've seen it before. In fact, this is the reason why I don't ask this question anymore: the only time I had a candidate write this solution was during a phone interview where they went silent for a while. I'm pretty sure they searched for the solution online, since they quickly wrote the solution but couldn't explain it (they never mentioned the words "graph" or "linked lists", eg). When I asked why the time complexity was linear they answered: "it is, trust me".

After the interview I found a few solutions online, and retired the question. The good thing is that now I can talk about it.

Final thoughts

There it is, my favorite interview question. It starts easy, but has enough depth and breadth to give a lot of signal from candidates. Do you have a favorite interview question? If you can, please share it with me. You can do that by writing a blog article and sending a webmention[archived] to my blog, or by commenting on anywhere where this post has been published (linked below).