Correctness, invariants, edge cases and testing

Why it matters

A solution with an untested boundary bug can leave a weaker impression than a slightly slower one that the candidate tested and justified. Interviewers look for whether you verify your own work: do you know why the code is right, can you find its edge cases before they do, and can you debug calmly when a test fails? The same habits make production code trustworthy: invariants become assertions, edge-case lists become test suites, and brute-force references become oracles for randomized and property-based tests.

Core ideas

Specification first. Before coding, write down the input domain and what the output must satisfy, including awkward cases: empty input, duplicates, negative numbers, ties, no valid answer. Many bugs are really disagreements about the specification.

Loop invariants. An invariant is a statement that is true before every iteration. Three facts make it useful: it holds initially (initialization), one iteration preserves it (maintenance), and when the loop stops it implies the result (termination). For lower-bound binary search on a half-open range [lo, hi): every index below lo holds a value smaller than the target, and every index at or above hi holds a value at least the target. It holds for lo = 0, hi = n; each branch preserves it; when lo == hi, the answer is lo. That sentence settles the usual questions (lo < hi or lo <= hi, hi = mid or mid - 1) without guessing. Also name a termination measure, something that strictly decreases, such as hi - lo.

Induction for recursion. Assume the recursive calls are correct on smaller inputs and show the current call combines them correctly; separately check the base cases and that every call makes progress toward one. It is the same argument as an invariant, organized differently.

Boundary cases by partition. Split the input space into classes, test one value per class plus its boundaries, and choose cases that exercise every branch. Arrays: sizes 0, 1 and 2, all equal, sorted, reverse sorted. Numbers: zero, negatives, and the extremes of the type. Graphs: disconnected, self-loop, single vertex. Strings: empty, one character, all identical.

Hand simulation. Trace a small input with a table of variables per iteration, reading the code you actually wrote rather than the code you meant. Pick an input that finishes in a minute but is not trivial, such as five elements with a duplicate.

Brute-force cross-check. Write the obviously correct slow version (try every pair, subset or split), generate many small random inputs and compare. When they disagree, shrink the input by removing elements while the failure persists; small counterexamples explain bugs quickly.

import random

def cross_check(fast, slow, trials=2000):
    for _ in range(trials):
        xs = [random.randint(-3, 3) for _ in range(random.randint(0, 7))]
        if fast(list(xs)) != slow(list(xs)):
            return xs              # a failing input; shrink it next
    return None

Property-based thinking. Check properties that must hold for every input rather than only specific outputs: a sort's output is ordered and is a permutation of its input; an encode-decode round trip returns the original; a reported shortest path is no longer than any path you construct. Libraries such as Hypothesis generate inputs and shrink failures automatically.

Debugging. Reproduce the failure with the smallest input, form a hypothesis about which invariant breaks, and check exactly that point with an assertion or a print. Random edits waste time and often add a second bug.

Common misconceptions

• "Passing the given examples means it is correct." Examples rarely cover empty inputs, duplicates or extremes; derive your own cases from the input classes.
• "Invariants are only for formal proofs." One sentence about what your variables mean is what lets you choose loop bounds and conditions without trial and error.
• "Random testing proves correctness." It finds bugs but cannot show their absence; pair it with an argument.
• "Debugging means adding prints everywhere." Minimize the input first, then check one hypothesis at a time.
• "Edge cases belong at the end of the interview." Asking about them up front shapes the design and avoids rewrites.

How to approach it

In an interview, clarify edge cases while restating the problem, state the invariant as you write each loop, and after coding trace one normal case and one boundary case aloud before saying you are done. If something fails, say what you suspect and check that. In practice, keep a log of every bug with its class (off-by-one, wrong initialization, missed empty case, overflow) and review it weekly so that recurring mistakes become visible and can be targeted. Self-testing is expected at every level; mid and senior candidates are also expected to propose a test plan and reason about failure modes beyond the happy path.