I'd written the BFS in about eight minutes. The interviewer ran the example I'd traced and said "ok, but how do you know this is right for any input?" My instinct was to point at the code. Pointing wasn't an argument. The silence stretched, and the realisation landed: nobody had ever taught me how to answer that question.
The interview ended without an offer. The post-mortem felt strange because the algorithm was correct, and there was still no way to say why in a form the interviewer could check.
What changed for me
- Tracing one input is testing, not proving. Most engineers, including a past version of me, don't notice the difference.
- Interviewers want a loop invariant, the property that's true at the start of every iteration.
- The full method is two checks: state and verify the invariant, then check initialization, termination, and edge cases.
- Different patterns produce differently shaped invariants, but the two step structure stays constant.
- The skill is separate from problem solving. It needs its own practice before it becomes reflexive.
Quick disclosure before I get into this: I built Codeintuition, a structured learning platform for coding interviews. This post is the retrospective version of the lesson that BFS interview should have taught me years earlier.
Where my approach was breaking
The default habit looks reasonable from the outside. You write the algorithm. You walk through it on the example the interviewer suggested. You get the right answer. You stop. If they ask a follow up, you trace a slightly harder example. If they push harder, you start guessing about edge cases.
None of that is an argument. It's a sequence of tests. Each test confirms one input. The interviewer's question was about every input.
The gap is small in description and large in practice. A trace shows the algorithm worked once. A correctness argument has to give the interviewer a reason it works always. That bridge is where the interview lives, and most prep material skips it.
The discrete math course you took in college covered induction proofs with formal notation. It's easy to dismiss as academic and move on. What that misses is that the idea (a property that holds every iteration) is exactly what the interview wants. The interview just asks for it as 90 seconds of clear English instead of a paper proof.
What I started doing differently
The first habit was simple. Before tracing any input, write down what's supposed to be true at the start of each iteration. One sentence.
The hard part is that for a few weeks, the sentence wouldn't always come. That alone is the diagnostic. If you can't state the invariant, you solved the problem by pattern matching, not by understanding what made the algorithm work.
The second habit, after stating the invariant, is to check the boundaries separately. What happens before the loop runs. What happens when the loop exits. What happens on an empty input. What happens on a single element. What happens on the maximum size.
The two step method is short. The change in interview outcomes is not.
| Step | What I used to do | What works |
|---|
| Before tracing | Pick an example and run it | State the invariant in one sentence, then trace 3 to 4 iterations |
| At the loop end | Say "and that gives the right answer" | Confirm the invariant plus the loop's exit condition together force the right output |
| On boundaries | Mention "edge cases" if asked | List initialization, termination, and at least three degenerate inputs explicitly |
What that looked like on the next problem
A few months later, the same kind of BFS question came up on a different graph problem. This time the invariant came first.
from collections import deque
def shortest_path(graph, start):
distances = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in distances:
distances[neighbor] = distances[node] + 1
queue.append(neighbor)
return distances
The argument went something like this: the invariant is that when a node is dequeued, its recorded distance equals the shortest path from the start. The reason it holds is FIFO ordering on a graph with equal edge weights. Any node enqueued later has been reached by a path of the same length or longer, so the first time you see a node is via the shortest path to it.
Then the boundaries. Initialization: only the start node sits in distances with value 0, which is the shortest path from the start to itself. Termination: the loop exits when the queue is empty, meaning every reachable node has been dequeued with its correct distance. Edge cases: a graph with one node returns {start: 0} immediately. A disconnected graph returns distances only for nodes reachable from the start. A self-loop is fine because the check if neighbor not in distances runs before enqueueing.
The interviewer didn't follow up with "but how do you know it's right for any input?" The argument had already covered that.
Why this works (the bit worth digging into later)
The two step method generalises because the structure is the same across every algorithm class. Only the shape of the invariant changes. Sliding window tracks a running variable. Two pointers tracks a search range. Binary search tracks a range too, but a different one. BFS tracks a relationship between dequeue order and shortest path. DP tracks an entire table of subproblem solutions.
The verification framework is invariant plus boundaries, in that order, regardless of pattern.
This connects to a broader idea in computer science formalism: the loop invariant is a logical statement that, combined with the loop's exit condition, gives you the postcondition you wanted to prove. The interview version drops the formal symbols and keeps the structure. Same skeleton, different vocabulary.
What I'd tell someone in the same spot
Three concrete things matter most:
- Pick a problem you've solved. Set a timer for 60 seconds. Try to state the loop invariant in one sentence. If the sentence doesn't come, that's the most important diagnostic in your prep, and more problems won't fix it.
- Take a correct algorithm. Write down an invariant that sounds plausible but is subtly wrong. Find the iteration where it breaks. This trains the gap between invariants that describe what the code does and invariants that guarantee correctness.
- Pair correctness reasoning with mental dry running. The dry run gives you a trace. The invariant gives you the claim to verify against the trace. Practising them apart leaves a hole that interview pressure exposes.
If you want a worked walkthrough of the BFS distance invariant before solving a graph problem with it, the BFS lesson walks through why FIFO ordering plus equal edge weights forces the shortest path property to hold.
I originally posted this on my own blog, a slightly longer version that walks through the two step method on sliding window, binary search, and DP, with an FAQ on nested loops where each loop needs its own invariant.
What's a problem where you understood the algorithm but couldn't say why it was right when someone asked, and what was the missing sentence you wished you'd had?