A mock interview, start to finish

Here is one interview, from the first question to the last test, the way a strong candidate handles it.

The problem

Interviewer: Given a list of integers, return the length of the longest run of consecutive numbers. For [100, 4, 200, 1, 3, 2] the answer is 4, because of 1, 2, 3, 4. The numbers can be in any order.

1. Understand. "So the numbers do not have to be next to each other in the list, just consecutive in value? Can there be duplicates? Negative numbers? How long can the list be? And for an empty list, I return 0?" (Yes; yes, duplicates count once; yes; up to 10⁵; yes.)

2. Examples. "[100, 4, 200, 1, 3, 2] gives 4. With duplicates, [1, 2, 2, 3] gives 3. A single number gives 1."

3. Brute force. "I could sort the list and walk through it, counting runs and skipping duplicates. That is O(n log n). Is that acceptable, or should I aim for O(n)?" (Can you do O(n)?)

4. Optimize. "Put everything in a set, so I can ask 'is x + 1 there?' in O(1). The trick is to start counting only at the start of a run: a number x where x − 1 is not in the set. From there, count upward. Each number is then counted once, in one run, so the whole thing is O(n), even though there is a loop inside a loop."

5. Code (still talking):

def longest_run(nums):
    present = set(nums)
    best = 0
    for x in present:
        if x - 1 not in present:          # x starts a run
            length = 1
            while x + length in present:
                length += 1
            best = max(best, length)
    return best

print(longest_run([100, 4, 200, 1, 3, 2]))
print(longest_run([1, 2, 2, 3]))
print(longest_run([]))

6. Test. "Let me trace [100, 4, 200, 1, 3, 2]. 100: 99 is not in the set, so it starts a run of length 1. 4: 3 is in the set, so skip; it is not a start. 1: a start; 2, 3, 4 are there, length 4. The edge cases: the empty list gives 0, since the loop never runs; duplicates disappear in the set. Time O(n), space O(n) for the set."

Notice what made this strong: questions before code, a stated brute force, the idea explained before it was coded, the complexity argued (not just claimed), and testing without being asked.

When you are stuck

• Say what you are thinking, even half-formed ideas. Interviewers give hints to people who talk.
• Try a smaller example, or a special case (all numbers equal, sorted input).
• Go through the patterns of this course: hash map? two pointers? sorting? a heap? BFS? DP?
• A working slow solution beats an unfinished fast one. Code the brute force, then improve it.

The behavioural round

You will be asked about yourself: a time you disagreed with a teammate, a project you are proud of, a mistake you made. Prepare four or five true stories, and tell each with STAR:

• Situation: the background, in one or two sentences.
• Task: what you had to do.
• Action: what you did (say "I", not only "we").
• Result: what happened, with numbers if you have them, and what you learned.

Your CV

One page. Projects with links (GitHub, a live demo) and what each one does; for each, a line on what you built and with which tools; contest results and online-judge ratings if you have them; contributions to open source (the Open-Source Contribution course shows how to make one). No photo and no long objective statement; check the spelling twice.

A preparation plan

• Weeks 1 to 4: one or two pattern lessons a week from this course, and their practice problems. Then 3 to 5 problems a week of each pattern on an online judge.
• Weeks 5 to 8: mixed problems against a timer (45 minutes each), out loud. One mock interview a week with a friend, taking turns as interviewer.
• Every week: review every problem you could not solve, and write down which pattern solved it. Recognising the pattern is most of the battle.

Mark lesson complete