Complete Annotated Coding Interviews

Five rounds, five changes in trust

Two candidates can submit the same correct function and leave different impressions. One has made the contract, proof, and trade-offs available for inspection. The other has left the interviewer to guess whether the code was derived, remembered, or reached by luck.

That difference does not come from narrating every keystroke. It appears at a few hinge moments: a boundary question before code, an invariant before a loop, a test chosen for the likely failure, a disciplined response to a contradiction, or the decision to stop designing once the contract is met.

The five rounds in this chapter use familiar problems so that the algorithms do not obscure those moments. Read the exchanges as performances, not scripts. Notice when the interviewer has enough evidence to trust the work—and when that trust has to be supplied by prompting.

The strong round: one question changes one line

Given a list of intervals, merge all overlapping intervals and return the merged intervals sorted by start time.

def merge_intervals(intervals):
    if not intervals:
        return []

    ordered = sorted(intervals, key=lambda interval: interval[0])
    merged = []

    for start, end in ordered:
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)

    return merged

The code is ordinary. The strength of the round lies in how little remains implicit. The endpoint question changes a comparison. The mutation question changes the ownership behavior. The invariant explains why the loop need not search the whole result. The tests are not a generic collection of edge cases; each protects a claim the candidate has already made.

Notice also what the candidate does not do. There is no speech during each assignment, no proof longer than the algorithm, and no attempt to impress the interviewer with a more exotic data structure. Visible reasoning is selective.

The borderline round: knowledge supplied on request

Return the k most frequent integers from a list. Output order does not matter, k is valid, and tied values may be returned in any order.

from collections import Counter
import heapq

def top_k_frequent(nums, k):
    counts = Counter(nums)
    heap = []

    for value, count in counts.items():
        heapq.heappush(heap, (count, value))
        if len(heap) > k:
            heapq.heappop(heap)

    return [value for count, value in heap]

Nothing here is technically weak. The candidate knows the variables, the alternative, the heap invariant, and the consequence of a stronger output contract. The borderline signal comes from ownership: each important part of the reasoning appears only after the interviewer asks for it.

A stronger opening would have taken one sentence:

“I’ll count in O(n), then choose between sorting m distinct counts in O(m log m) and keeping a size-k heap in O(m log k); if k is expected to be small, I’ll use the heap.”

The lesson is not to talk more. It is to lead with the reason for the chosen structure instead of its name.

Correct code, concealed recurrence

Given a non-empty binary tree whose node values may be negative, return the maximum sum of a path. A path may begin and end at any nodes but follows parent-child links.

def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if not node:
            return 0

        left = max(0, gain(node.left))
        right = max(0, gain(node.right))

        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best

The implementation is correct, but “the code handles it” asks the interviewer to certify understanding from familiar syntax. The recurrence needs a precise name. An upward gain begins at the current node and may be extended by its parent. It can therefore contain at most one child branch. A complete path may have the current node as its highest point and use both child branches.

The missing explanation could have been brief:

Now the revealing tests follow from the explanation. A root 1 with children 2 and 3 must return 6, proving that a finished path may use both sides. A single node -3 must return -3, proving that zero does not masquerade as an empty path. A tree rooted at -10 with children 9 and 20, where 20 has children 15 and 7, must return 42, proving that the best path need not touch the root.

Private reasoning is especially costly in recursive problems. The surface code can look polished while the state definition is wrong. The interviewer needs to hear the distinction that makes the recurrence correct, not a tour of the recursive calls.

The wrong first answer and the strong recovery

Given a grid of 0s and 1s, return the size of the largest connected component of 1s. Connectivity is up, down, left, and right. Empty input returns zero, and the function must not mutate the grid.

The candidate chooses a breadth-first search from each unseen 1, with a separate visited set because the caller retains ownership of the grid. The first implementation accidentally includes diagonal neighbor offsets.

[
  [1, 0, 1],
  [0, 1, 0],
  [1, 0, 1],
]

from collections import deque

def largest_component(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    best = 0

    for start_row in range(rows):
        for start_col in range(cols):
            if grid[start_row][start_col] != 1:
                continue
            if (start_row, start_col) in visited:
                continue

            size = 0
            queue = deque([(start_row, start_col)])
            visited.add((start_row, start_col))

            while queue:
                row, col = queue.popleft()
                size += 1

                for dr, dc in directions:
                    next_row = row + dr
                    next_col = col + dc
                    in_bounds = (
                        0 <= next_row < rows and 0 <= next_col < cols
                    )
                    if not in_bounds:
                        continue
                    if grid[next_row][next_col] != 1:
                        continue
                    if (next_row, next_col) in visited:
                        continue

                    visited.add((next_row, next_col))
                    queue.append((next_row, next_col))

            best = max(best, size)

    return best

The first answer was wrong. The recovery is nevertheless strong because the candidate does not become random or defensive. They state the expected result, classify what an overly large answer could mean, connect the peculiar input to the most likely state, make one change, and preserve the contradiction as a test. A senior signal can survive a bug when control of the investigation remains visible.

The unfinished answer hidden inside an architecture

Return whether two strings are anagrams. Comparison is case-sensitive; spaces and punctuation count as characters; ordinary language-level character iteration is acceptable.

The candidate has noticed real complexities of text processing. None belongs to the stated contract. The unfinished framework offers less evidence than this complete function:

from collections import Counter

def is_anagram(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)

Counting takes expected O(n) time and O(k) additional space for k distinct characters. Sorting both strings would also be defensible at O(n log n) time, especially if brevity and available library behavior make it the clearer choice. Tests should protect the actual contract: "listen" and "silent" are a positive case; "rat" and "car" are not; "a b" and "ab " are anagrams because spaces count; and "aA" and "Aa" are anagrams without any case folding.

Overengineering is not merely an aesthetic fault in a timed round. It spends the available time, hides the rule among invented extension points, and may leave no behavior to evaluate. Production judgment means matching the design to the promise in front of you, then identifying where a real change would enter.

Read the hinge, not the verdict

The labels on these rounds are outcomes, not personality types. The borderline candidate knew the heap argument. The quiet candidate wrote the correct recurrence. The candidate with the initial bug showed the strongest recovery. A different interviewer or time limit could change the eventual decision.

What transfers is the location of the hinge:

• In merge intervals, one endpoint question determined the comparison and its regression test.
• In top-k frequency, the choice became credible only when n, m, and k made the trade-off explicit.
• In maximum path sum, two meanings of “best” had to be separated before the recursion could be trusted.
• In the grid, the failing input pointed directly to the neighbor policy.
• In the anagram problem, stopping at a complete small solution was the design decision.

Use the cases for rehearsal by pausing at those moments. Before reading the candidate’s next line, answer the interviewer yourself. Then vary the rule: make intervals half-open, require deterministic top-k ordering, allow an empty tree, permit diagonal adjacency, or introduce one genuine normalization policy. The useful follow-up is the one that reveals whether you know which part of the solution owns the changed requirement.

The coding-round chapters have now supplied a workflow, a standard of correctness, implementation habits, testing, debugging, and review. A complete round does not display those subjects one after another like a checklist. It uses them when the work demands them. The reader—and the interviewer—should be able to see why the next move is safe.

Related reading

• Chapter 32: The Coding-Round Workflow
• Chapter 33: Correctness Before Cleverness
• Chapter 35: Testing in the Interview
• Chapter 36: Debugging Live
• Chapter 39: Arrays and Strings