Convincing me your algorithm is correct
“You have written an algorithm. How do you convince me it is correct without running it on every input?”
What this tests
- Whether the candidate has a vocabulary of proof techniques: invariants, induction, exchange arguments, reduction to a known result.
- Whether they can pick the right technique for the algorithm's shape (loop → invariant, recursion → induction, greedy → exchange).
- Ability to state a precise invariant, not a vague one, and to check initialization, maintenance, and termination.
- Understanding that tests demonstrate presence of bugs, not absence.
Strong answer
Testing shows the algorithm works on the inputs tried; a proof shows it works on all of them. A strong candidate matches proof technique to code shape. Loops → invariants. State a property that holds before the first iteration, is preserved by each iteration, and at termination implies the result. For Binary Search: "the target, if present, lies in [lo, hi]" — true initially, preserved by each discard because of sortedness, and when lo > hi the range is empty so the target is absent. For Two Pointers (Opposite Ends): "every solution pair lies within [l, r]". For Kadane's Algorithm: "cur is the maximum sum of a subarray ending at i". An invariant that cannot be stated precisely is a signal the algorithm might be wrong.
Recursion and DP → induction. Assume the recursive calls return correct answers for smaller inputs and show the combination is correct; the base case anchors it. For DP, the induction is over the topological order of states: "dp[i] is correct assuming dp[j] is correct for all j it depends on". Greedy → exchange argument. Show any optimal solution can be transformed into the greedy one without losing optimality; if the exchange cannot be made, look for the counterexample that the failed exchange suggests. Graph algorithms → structural lemmas. BFS layers equal distances by induction on distance; Dijkstra's correctness rests on the lemma that the minimum tentative node has its final distance, which holds only with non-negative weights.
They also use reduction: "this is exactly interval scheduling, whose greedy is known optimal", which transfers a known proof. And they complement the proof with disciplined edge-case enumeration — empty input, single element, all equal, extreme values, the boundary of every < vs <= — because a proof covers the algorithm while edge cases catch the gap between the algorithm and the code. Finally, they say what they are *not* sure of: "I believe the invariant holds when duplicates are present, let me check the <= branch." That honesty is itself evidence of correctness-oriented thinking.
Green flags · Red flags
- States a precise loop invariant and checks initialization, maintenance, and termination.
- Uses induction for recursion and DP, with an explicit base case.
- Sketches an exchange argument for a greedy choice.
- Reduces to a known problem with a known proof when possible.
- Separates "the algorithm is correct" from "the code implements the algorithm" and tests the latter with edge cases.
- Names termination as part of correctness (each iteration shrinks a measure).
- Flags the specific spot they are least sure of.
- Says "it passed the examples, so it is correct".
- Offers a vague invariant like "the answer so far is right" with no mention of what that means.
- Cannot say why the loop terminates.
- Believes an argument for a greedy is unnecessary because "it is obviously optimal".
- Confuses proving correctness with proving complexity.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
lo < hi, hi = mid).dp[i][j] means. Is it correct?