Correctness Before Cleverness

The line that looks harmless

Suppose the prompt asks for the first index where a monotonic predicate becomes true. The predicate is false for some prefix of the range and true thereafter. You know binary search, so the implementation appears routine. Then a one-element case fails.

The tempting response is to change < to <=, or mid to mid + 1, until the case passes. That may repair this input while breaking the next one. The comparison was not an isolated typo. It belonged to a model of the search interval, and the code never made that model stable.

Correctness under interview pressure comes from being able to answer a harder question than “Does this look like binary search?” You need to know what each variable means, what remains true after every update, and why the loop’s final state implies the answer.

That reasoning is not ceremony performed after the code. It is what keeps a small change from becoming a guess.

Turn the prompt into a claim

Before choosing an algorithm, settle the parts of the contract that can change the result:

• indexes range from 0 through n - 1;
• the predicate is monotonic;
• n = 0 is valid;
• the result is -1 when no index is true;
• evaluating the predicate has no side effect that changes later evaluations.

These are not generic clarifying questions. Each one supports a line of code. Without monotonicity, discarding half the range is unjustified. Without a defined no-answer result, returning -1 is an invented policy. If predicate calls can change the predicate, the proof describes a different program.

The prompt may guarantee monotonicity. Accept that guarantee and move on. An interview solution should not spend linear time validating the property that makes logarithmic search possible unless invalid input is explicitly part of the task.

Now add a conceptual position at index n. It is not a real element and the predicate will never be called there. It represents “no true index.” The problem becomes: find the boundary between the false prefix and either the true suffix or that sentinel.

Build the loop from its invariant

Use left and right as an inclusive range of possible boundary positions. Initially that range is [0, n]. The invariant is:

The first true index, or the sentinel n if none exists, is somewhere in [left, right].

That statement is precise enough to determine the updates:

left = 0
right = n

while left < right:
    mid = left + floor((right - left) / 2)

    if is_true(mid):
        right = mid
    else:
        left = mid + 1

return -1 if left == n else left

Because left < right, the midpoint is always less than right and therefore less than or equal to n - 1. The predicate is never called on the sentinel.

If is_true(mid) is true, the boundary may be mid or somewhere to its left, so [left, mid] remains possible. Setting right = mid - 1 would wrongly discard mid itself.

If is_true(mid) is false, monotonicity proves that every position through mid is false. The boundary must be to the right, so the next possible position is mid + 1.

The midpoint formula also carries a fixed-width arithmetic decision. Computing (left + right) / 2 can overflow even when both indexes are valid. Computing left + floor((right - left) / 2) avoids that addition. In a language with arbitrary-precision integers the overflow may not exist, but using the safe form keeps the reasoning portable.

Finish the proof, including termination

A loop invariant earns its name only if it survives four questions.

It is true initially because every possible answer, including the sentinel, lies between 0 and n. Each branch preserves it for the reasons above. Each iteration makes the range strictly smaller: either right moves down to mid, or left moves past mid. The loop therefore terminates.

At termination, left == right. The invariant says the answer lies in a range containing one position, so that position is the answer. If it is n, no real index was true; otherwise it is the first true index.

Notice what the proof did. It determined the inequalities and updates, ruled out a predicate call at n, explained the no-answer case, and established that the loop cannot stall. Those are exactly the places where a memorized binary-search template tends to fracture.

Let the boundary cases interrogate the proof

Run the smallest cases before the comfortable sample. For n = 0, the loop does not execute and the sentinel becomes -1. For a single false value, left advances to n. For a single true value, right moves to zero. With all false values, the boundary travels to the sentinel; with all true values, it travels to zero.

Then put the transition at both ends:

• [false, false, false, true] must return 3;
• [false, true, true, true] must return 1.

These cases are useful because each has a job. They are not a ritual list of “edge cases.” Together they challenge initialization, both branches, the sentinel, the final real index, and the first real index. If one fails, trace the candidate range and ask where the invariant stopped being true.

Testing supplies evidence, but examples alone do not prove the algorithm. A handful of passing cases cannot cover every transition position. The invariant explains all of them; the tests check that the implementation actually follows the proof.

Correctness can fail outside the loop

The same discipline applies when there is no obvious search interval. Start by naming what the state represents and who owns it.

Consider two sum when the function must return two distinct indexes. Before processing index i, let the map contain only values from indexes smaller than i:

for each index i:
    needed = target - values[i]
    if needed is present in seen:
        return [seen[needed], i]
    seen[values[i]] = i

Looking up before inserting prevents an element from pairing with itself. It still allows [3, 3] to satisfy a target of 6, because the second 3 finds the first one’s index. “Use a hash map” is only a pattern; the ordering of the two operations is the correctness argument.

Presence must also be tested explicitly. If a language treats zero, false, or an empty string as falsey, a truthiness check can confuse a stored value with absence. The same ambiguity appears when a sentinel such as -1, 0, or null is also valid data. Prefer a containment check, an optional result, or a separate presence flag whose states cannot collide.

Mutation creates an ownership proof

Backtracking exposes another kind of invariant. The active path should contain exactly the choices on the current recursion branch. A choice is pushed before descent and popped after return. When a complete path is stored, the result collection needs a copy:

def search(next_choice):
    if path is complete:
        answers.append(copy(path))
        return

    for each available choice:
        path.append(choice)
        search(choice after this one)
        path.pop()

Without the pop, state leaks into sibling branches. Without the copy, every stored answer may refer to the same list and change as later branches mutate it. Copying on every recursive call would be correct but more expensive than necessary. The ownership rule—one mutable working path, copied only when its value crosses into stored results—shows where mutation is safe.

Input mutation needs the same explicitness. Sorting the caller’s array in place, marking a grid to avoid a visited set, or caching results in a global map may all be legitimate. They are incorrect when the contract promises the input remains reusable, when state survives into the next test, or when a helper’s side effect is hidden from the caller.

Representation is part of the contract

Many failures blamed on “edge cases” are really disagreements about what the data means.

Duplicates may represent interchangeable values, separate indexes, repeated events, or multiplicity that must be counted. A set erases multiplicity. A map from value to one index erases all but one identity. Neither structure is wrong in isolation; each becomes wrong when it forgets information the result requires.

Strings are especially easy to underspecify. “Character” might mean a byte, a language runtime’s code unit, a Unicode code point, or a user-perceived grapheme cluster. Case-insensitive comparison may also require a normalization and case-folding policy. Most interview prompts intend the runtime’s ordinary iteration model, and it is unhelpful to turn each string problem into a Unicode seminar. But if the task concerns user-visible length, international identifiers, truncation, or normalization, the unit changes the correct algorithm. State it.

Numeric representation has similar boundaries. Sums and products can overflow even when individual inputs fit their declared type. Negating the minimum signed integer may overflow. A comparator implemented as a - b may overflow and reverse an ordering. Use a wider type, checked arithmetic, or direct comparison when the input limits make those failures reachable.

Nullability belongs to the domain model, too. Decide whether null means an invalid input, an absent answer, an empty collection, or a legitimate element. Those meanings demand different code. A guard clause that silently maps all of them to the same return value does not simplify the contract; it discards it.

Invalid input is a policy decision

“Handle invalid input” is not a complete requirement. The function might reject malformed data, skip bad records, coerce them, return an error value, or rely on validation at an outer boundary. Each policy changes observable behavior.

In an algorithm round, separate two questions:

1. What validity does the prompt guarantee?
2. If invalid input is in scope, what response does the caller need?

If intervals are guaranteed to have start < end, state the assumption and keep validation out of the core loop. If the function is an ingestion boundary for untrusted records, validation is part of correctness and should happen before partially mutating output. Senior judgment appears in choosing the right boundary, not in adding the maximum number of guards.

Optimize the argument, not just the code

An optimization is safe when it preserves a contract you can still name. If sorting is replaced by a heap, decide whether output order remains arbitrary or becomes observable. If a set replaces a count map, confirm that multiplicity no longer matters. If recursion becomes iteration, identify the stack state that must now be represented explicitly. If copying is removed, say who owns the shared value.

When the faster approach is difficult to defend and the constraints permit a simpler one, the simpler solution is often the stronger interview answer. This is not a preference for slow code. It is a refusal to claim a performance improvement before establishing which behavior it must preserve.

Practice correctness reasoning by taking a familiar solution and withholding the code for two minutes. Write one sentence that describes the valid state at the top of its main loop or recursive call. Derive the update from that sentence. Name the quantity that makes progress. Then choose the smallest inputs that challenge each part of the argument.

The aim is not to recite a formal proof in every round. It is to make the proof available when a comparison is disputed, a test fails, or an optimization changes the representation. Cleverness becomes useful once you know what it is forbidden to break.

Related reading

• Chapter 24: Recovering When Stuck
• Chapter 30: Interview-Language Fluency
• Chapter 31: Complexity and Constraint Analysis
• Chapter 32: The Coding-Round Workflow
• Chapter 34: Writing Senior-Level Interview Code
• Chapter 35: Testing in the Interview