Testing in the Interview

Five minutes, one finished function

The interval-merging code from the previous chapter is on the screen. It sorts a copy of the input, scans from left to right, and merges closed intervals when the next start is less than or equal to the current end. Five minutes remain. The interviewer asks, “How would you test it?”

It is tempting to answer with categories: happy path, empty input, duplicates, negative values, malformed input, large input. That list is easy to remember and hard to use. It does not say which cases matter for this implementation, what their answers should be, or what a failure would teach you.

A test earns scarce interview time when it can distinguish the promised solution from a plausible wrong one. For this function, the relevant promises are already visible:

• touching endpoints merge because the intervals are closed;
• output is ordered even when input is not;
• the active interval covers every overlapping interval processed so far;
• empty input is accepted; and
• sorting does not reorder the caller’s list.

Those promises are a better source of tests than a memorized edge-case catalog. They turn testing into a compact correctness argument.

Derive the cases from the code

Start with the smallest case that exercises the ordinary path. Say the expected answer before running it:

input:    [[1, 3], [2, 6], [8, 10]]
expected: [[1, 6], [8, 10]]

This establishes the output shape and the basic merge. It proves very little about the decisions most likely to be wrong. A useful next question is:

What nearby implementation could pass this case and still violate the contract?

Several answers appear immediately. A function can initialize incorrectly, forget to sort, use < where the closed-interval contract requires <=, or replace the active end instead of retaining its maximum. Each wrong implementation suggests a small counterexample.

The table is not a universal template. It is the proof outline for this one implementation. If the prompt defined half-open intervals, the touching case would expect two intervals. If the input were guaranteed to arrive sorted, the unsorted case would be outside the contract. Test selection follows the decisions you actually made.

Some familiar edge cases do not belong

Negative endpoints sound like an edge case, but they create no new behavior here. Python compares negative integers with the same ordering rules as positive integers, and the algorithm has no sentinel that could collide with zero. One negative case may reassure you; it is weaker than the nested case, which challenges a real state update.

The same judgment applies to the rest of the usual catalog.

• Duplicate intervals are useful if equality affects the merge rule; otherwise they cover the same branch as an ordinary overlap.
• Extreme values matter when arithmetic can overflow, a sentinel can collide with valid data, or recursion or allocation approaches a limit. This scan only compares endpoints.
• Malformed intervals matter only if the prompt puts validation in scope. If valid intervals are guaranteed, say so and spend the time on the algorithm.
• A giant input is rarely a useful live test. Complexity analysis establishes the O(n log n) sorting cost more clearly than watching a large literal run.
• Adversarial cases are valuable only after you can name what they are adversarial to: a comparator, update order, ownership boundary, invariant, or complexity claim.

“I considered it and excluded it” is often a better engineering answer than performing every item in a ritual.

Test ownership as well as output

The function also promised not to reorder the caller’s list. Output-only tests cannot prove that. Keep a snapshot and inspect the input after the call:

intervals = [[8, 10], [1, 3], [2, 6]]
before = [interval[:] for interval in intervals]

assert merge_intervals(intervals) == [[1, 6], [8, 10]]
assert intervals == before

This is a contract test, not defensive ceremony. It checks the ownership decision that motivated sorted(intervals, ...) instead of intervals.sort(). If the function were allowed to reorder its input, the second assertion would add no value.

Stateful prompts require the same attention to lifetime. A cache, iterator, parser, data structure, class field, or default mutable argument may behave correctly once and fail on the second call. Test a sequence rather than a single operation:

add(1)
add(1)
count(1) -> 2

That sequence distinguishes a multiset from an incorrect set-backed implementation. For a reusable solver object, two independent calls can reveal a result list or visited set that was never reset. The diagnostic question is not merely “Does it have state?” but “How long is this state supposed to live?”

Decide what equality means

Exact expected output is best when the contract determines one answer. The interval function promises increasing start order, so a direct equality check is honest.

Other prompts allow several correct answers. A graph traversal may permit different visit orders; grouped anagrams may permit different group and item orders; a top-k problem may leave ties unspecified. Comparing one arbitrary serialization would test a requirement the prompt never made.

Choose an oracle that matches the contract:

• normalize only the dimensions whose order is irrelevant;
• check properties such as coverage, non-overlap, membership, or frequency; or
• compare an optimized solution with a simpler brute-force solution on small inputs.

For merged intervals, useful properties are that the result is ordered and non-overlapping and covers exactly the same points as the input. For random arrays, a straightforward quadratic solution can serve as an independent oracle for an optimized one. Random input without a property or an oracle is only a stream of examples whose answers you do not know.

Expected first, execution second

State the expected answer before you run or trace a case. Otherwise the output on the screen can quietly become the answer you meant to get.

The statement need not be elaborate:

“For [[1, 10], [2, 3]], I expect [[1, 10]]. This checks that the active end never moves backward while intervals still overlap.”

Now the case has a job, an oracle, and a connection to the invariant. The interviewer can correct a misunderstood contract before you diagnose code against the wrong expectation.

When time is short, selection matters more than volume. For the interval function, a credible three-case finish is the representative input, touching endpoints, and a nested interval. Mention the empty and ownership cases you would run next. If initialization felt risky while you coded, substitute the single-interval case. The best set is sensitive to the implementation in front of you.

Testing can also happen before the function is complete. Write down the touching and nested expectations when you settle the endpoint policy and loop invariant. During implementation, trace the nested case through the update. After implementation, run the smallest set that challenges the finished code. This keeps the correctness argument alive instead of postponing it until the last minute.

Keep the failure

Suppose the nested case returns [[1, 3]] instead of [[1, 10]]. Do not move to a friendlier input. The failure has identified a precise contradiction: the active interval no longer covers all processed overlapping intervals.

Say what is known:

“The nested case fails: expected [[1, 10]], got [[1, 3]]. I am keeping that input because it isolates the update of current_end.”

At this point testing has done its work. It selected the case, established the expected result, and exposed the broken promise. Debugging begins when you inspect the state that produced the mismatch, form a hypothesis, and repair the responsible line. After the repair, rerun the same input before expanding the test set. A failure becomes a regression test because it records something the previous reasoning missed.

Practice choosing, not listing

Take three solutions you already know: a sliding window, a breadth-first search, and a backtracking function. For each one, write no more than five tests. Beside every case, name the contract clause, invariant, ownership rule, or plausible bug it challenges. Remove any case whose job is already done by a smaller one.

Then make one deliberate mistake in each solution. Let a window boundary move backward, mark a BFS node visited on dequeue, or store a mutable path without copying it. Find the smallest input that distinguishes the faulty version from the correct one. State the expected result before running it, fix the cause, and rerun that input.

The habit to carry into an interview is compact: read the decisions in the code, challenge the riskiest ones with small counterexamples, and know the answer before execution. A test set is not a tour of possible inputs. It is a short attempt to prove the code wrong.

Related reading

• Chapter 21: Thinking Aloud Without Narrating Noise
• Chapter 24: Recovering When Stuck
• Chapter 30: Interview-Language Fluency
• Chapter 34: Writing Senior-Level Interview Code
• Chapter 36: Debugging Live