Debugging

coreCommon atGoogleStripeAnthropicMetaAmazonRead firstTesting and verificationPractise in the Sandbox →

Debug like a scientist, not a gambler: reproduce the failure, minimize the input, form one hypothesis, bisect the code or the data to test it, and verify the fix with the original case and the old tests. The sharpest tool is the loop invariant: the first step where it turns false is where the bug is.

The idea in plain words

When a test fails in an interview, the tempting move is to stare at the code and change things until it passes. That is guess-and-check, and under pressure it burns ten minutes and often adds a second bug.

The alternative is a short, repeatable method. Think of it as narrowing down a search space:

• The failing input is too big to reason about, so shrink it until every element matters.
• The code is too long to suspect all at once, so cut it in half with a print or an assert, and ask which half went wrong.
• You have one idea about the cause. Test that idea, not a fix.

A loop invariant makes “which half went wrong” precise. It is a statement that should be true every time the loop reaches a certain point, like “a[0..i] is sorted” or “best is the max of what I’ve seen.” If you know the invariant, you don’t need to understand the whole run. You need the first step where it’s false. The bug is in the code that ran just before.

See it

Four buggy textbook functions. Step through each one and watch the hand-trace table fill in. At each checkpoint (◆), compare the variables with the invariant. Flag the first step where it’s false. Each function breaks in a different way, matching the four ways a loop can be wrong.

Find the bug: where does the invariant break?

step and flag

buggy function

Running maxInsertion sortReverse in placeBinary search

inputa = [2, 5, 1, 4]invariantAt the end of pass i, the prefix a[0..i] is sorted.your jobStep forward. When you reach the first checkpoint (◆) where the invariant is false, press Flag this step.

1def insertion_sort(a):

2 for i in range(1, len(a)):

3 key = a[i]

4 j = i - 1

5 while j > 0 and a[j] > key:

6 a[j + 1] = a[j]

7 j -= 1

8 a[j + 1] = key

9 return a

2

5

1

4

0123

i

⚑ Flag this step

Hand-trace table

step	line	i	key	j	j > 0	a[0..i]	a[j] > key	check
1	2	1

Pass 1: insert a[1] into the sorted prefix a[0..0].

↺◀▶ Play▶1 / 22

Give up: show the checksBug type: try to name it before you look. Initialisation, maintenance, bounds, or termination?

The four bugs line up with the classic proof of a loop (CLRS, ch. 2):

Bug type	The invariant…	Example above
Initialisation	is false before the first pass	best = 0 with all-negative input
Maintenance	holds, then one pass breaks it	insertion sort with j > 0
Bounds	holds while the loop runs in range, then the loop overshoots	reversing with range(n)
Termination	stays true, but the loop stops making progress	binary search with lo = mid

When to reach for it

The situation…	Start with…
a test fails and you don’t know why	Reproduce with the exact input, then minimize it.
the failing input is big (random test, long string)	Shrink it automatically or by hand: delete half, does it still fail?
the output is wrong but nothing crashes	A hand trace with a variable table, checking the invariant at each pass.
the code is long, or has several phases	Bisect: print or assert at the midpoint. Is the state right there?
it worked before your last change	Diff: what changed? Undo half of it. (In real repos, git bisect does this over commits.)
it hangs	Print the loop variables once per pass. Look for one that stops changing.
it crashes with an index error	Print the index and the length right before the access. Then ask which bound is wrong.

How it works

1. Reproduce. Get a failing input you can run on demand. Write it as a test. If it’s random, record the seed.
2. Minimize. Shrink the input while it still fails: remove elements, shorten strings, move numbers toward 0. Stop when every remaining piece matters.
3. Hypothesize. Say one specific cause out loud: “I think the inner loop never compares index 0.” A hypothesis predicts something you can check.
4. Bisect. Test the prediction at a midpoint: print the state, assert the invariant, or trace by hand. Each check halves where the bug can be.
5. Fix the cause, not the symptom. Change the line that broke the invariant. Don’t add an if for the one input that failed.
6. Verify. Re-run the minimized case, the original case, and every earlier test. Add the minimized case to your table so it stays fixed.

Hand-tracing with a variable table

A hand trace is a table: one column per variable, one row per step. Here is insertion sort with the buggy while j > 0 on [2, 5, 1, 4], at the end of each outer pass:

pass i	key	j after inner loop	a after pass	a[0..i] sorted?
1	5	0	[2, 5, 1, 4]	yes
2	1	0	[2, 1, 5, 4]	no

The table shows the bug without any guesswork. In pass 2 the inner loop stopped at j = 0, so key landed at index 1 instead of 0. The only line that decides where it stops is the while condition.

Rules that make traces fast:

• Trace the smallest failing input, not the prompt’s example.
• Write down only the variables the invariant mentions.
• Check the invariant at the same point in every pass (end of the body is usual).

Asserting the invariant in code

When a hand trace is too slow, let the computer check the invariant on every pass. Here is a lower-bound binary search with the invariant asserted at the top of the loop. A wrong update fails on the first pass where it matters, with lo and hi in the message, instead of returning a wrong index at the end.

Python

lower_bound.py

def lower_bound(xs: list[int], target: int) -> int:
    """First index i with xs[i] >= target (len(xs) if none). xs must be sorted."""
    lo, hi = 0, len(xs)  # search space is the half-open range [lo, hi)
    while lo < hi:
        # 1. Invariant, checked on every pass: everything left of lo is < target,
        #    everything from hi on is >= target. Bugs show up here first, not at the end.
        assert all(x < target for x in xs[:lo]), (lo, hi)
        assert all(x >= target for x in xs[hi:]), (lo, hi)
        mid = lo + (hi - lo) // 2
        if xs[mid] < target:
            lo = mid + 1  # 2. mid is too small, so the answer is strictly right of it
        else:
            hi = mid      # 3. mid might be the answer: keep it (hi = mid - 1 would lose it)
    return lo             # 4. lo == hi: the boundary itself


if __name__ == "__main__":
    xs = [1, 3, 3, 5, 8]
    assert lower_bound(xs, 3) == 1    # first of the duplicates
    assert lower_bound(xs, 4) == 3    # between values
    assert lower_bound(xs, 0) == 0    # before everything
    assert lower_bound(xs, 9) == 5    # after everything
    assert lower_bound([], 7) == 0    # empty
    print("ok")

TypeScript

lower_bound.ts

import assert from "node:assert/strict";

const DEBUG = true; // flip off once it works: the checks below are O(n) per pass

/** First index i with xs[i] >= target (xs.length if none). xs must be sorted. */
export function lowerBound(xs: readonly number[], target: number): number {
  let lo = 0, hi = xs.length; // search space is the half-open range [lo, hi)
  while (lo < hi) {
    if (DEBUG) {
      // 1. Invariant, checked on every pass: left of lo is < target, from hi on is >= target.
      assert.ok(xs.slice(0, lo).every((x) => x < target), `left side broke at lo=${lo}`);
      assert.ok(xs.slice(hi).every((x) => x >= target), `right side broke at hi=${hi}`);
    }
    const mid = lo + Math.floor((hi - lo) / 2);
    if (xs[mid] < target) lo = mid + 1; // 2. mid is too small: answer is strictly right of it
    else hi = mid; // 3. mid might be the answer: keep it (hi = mid - 1 would lose it)
  }
  return lo; // 4. lo === hi: the boundary itself
}

const xs = [1, 3, 3, 5, 8];
assert.equal(lowerBound(xs, 3), 1); // first of the duplicates
assert.equal(lowerBound(xs, 4), 3); // between values
assert.equal(lowerBound(xs, 0), 0); // before everything
assert.equal(lowerBound(xs, 9), 5); // after everything
assert.equal(lowerBound([], 7), 0); // empty
console.log("ok");

C#

lower_bound.cs

using System.Diagnostics;

int[] xs = [1, 3, 3, 5, 8];
Check(LowerBound(xs, 3) == 1, "first of the duplicates");
Check(LowerBound(xs, 4) == 3, "between values");
Check(LowerBound(xs, 0) == 0, "before everything");
Check(LowerBound(xs, 9) == 5, "after everything");
Check(LowerBound([], 7) == 0, "empty");
Console.WriteLine("ok");

// First index i with xs[i] >= target (xs.Length if none). xs must be sorted.
static int LowerBound(int[] xs, int target)
{
    int lo = 0, hi = xs.Length;   // search space is the half-open range [lo, hi)
    while (lo < hi)
    {
        // 1. Invariant, checked on every pass: left of lo is < target, from hi on is >= target.
        //    Debug.Assert compiles away in Release builds, so it costs nothing in production.
        Debug.Assert(xs[..lo].All(x => x < target), $"left side broke at lo={lo}");
        Debug.Assert(xs[hi..].All(x => x >= target), $"right side broke at hi={hi}");
        int mid = lo + (hi - lo) / 2;
        if (xs[mid] < target) lo = mid + 1;   // 2. mid is too small: answer is strictly right of it
        else hi = mid;                        // 3. mid might be the answer: keep it
    }
    return lo;                                // 4. lo == hi: the boundary itself
}

static void Check(bool ok, string name) { if (!ok) throw new Exception($"failed: {name}"); }

Cheap in production, expensive in debug

These checks are O(n) per pass, so the search becomes O(n log n). That is fine while debugging. C#’s Debug.Assert compiles away in Release builds; Python’s assert is skipped under python -O; in TypeScript, guard the checks with a flag.

Minimizing a failing input

Shrinking is mechanical, so write it once. This is a simplified form of Zeller’s delta debugging: try deleting a chunk, keep the deletion if it still fails, and halve the chunk size when nothing more can go.

Python

minimize.py

from collections.abc import Callable


def minimize(xs: list[int], fails: Callable[[list[int]], bool]) -> list[int]:
    """Shrink a failing input: keep removing chunks while the bug still reproduces."""
    assert fails(xs), "start from an input that actually fails"
    chunk = len(xs) // 2
    while chunk >= 1:
        i, shrunk = 0, False
        while i < len(xs):
            candidate = xs[:i] + xs[i + chunk:]   # 1. try deleting xs[i : i+chunk]
            if fails(candidate):
                xs, shrunk = candidate, True      # 2. still fails: keep the smaller input
            else:
                i += chunk                        # 3. that chunk mattered: move past it
        if not shrunk:
            chunk //= 2                           # 4. nothing removable at this size: go finer
    return xs


def buggy_max(xs: list[int]) -> int:
    best = 0  # bug: should start at xs[0]; wrong when every value is negative
    for x in xs:
        best = max(best, x)
    return best


if __name__ == "__main__":
    def fails(ys: list[int]) -> bool:  # the bug reproduces if the answer is wrong
        return len(ys) > 0 and buggy_max(ys) != max(ys)

    found_by_fuzzer = [-5, -3, -8, -4, -7, -6, -9, -2]
    small = minimize(found_by_fuzzer, fails)
    assert len(small) == 1 and fails(small)  # 8 values -> 1: the bug in one line
    assert not fails([4, -2, 7, -9])         # any positive value hides the bug
    print("ok")

TypeScript

minimize.ts

import assert from "node:assert/strict";

/** Shrink a failing input: keep removing chunks while the bug still reproduces. */
export function minimize(xs: number[], fails: (ys: number[]) => boolean): number[] {
  assert.ok(fails(xs), "start from an input that actually fails");
  let chunk = Math.floor(xs.length / 2);
  while (chunk >= 1) {
    let i = 0, shrunk = false;
    while (i < xs.length) {
      const candidate = [...xs.slice(0, i), ...xs.slice(i + chunk)]; // 1. try deleting a chunk
      if (fails(candidate)) {
        xs = candidate; // 2. still fails: keep the smaller input
        shrunk = true;
      } else {
        i += chunk; // 3. that chunk mattered: move past it
      }
    }
    if (!shrunk) chunk = Math.floor(chunk / 2); // 4. nothing removable at this size: go finer
  }
  return xs;
}

function buggyMax(xs: number[]): number {
  let best = 0; // bug: should start at xs[0]; wrong when every value is negative
  for (const x of xs) best = Math.max(best, x);
  return best;
}

const fails = (ys: number[]) => ys.length > 0 && buggyMax(ys) !== Math.max(...ys);
const foundByFuzzer = [-5, -3, -8, -4, -7, -6, -9, -2];
const small = minimize(foundByFuzzer, fails);
assert.ok(small.length === 1 && fails(small)); // 8 values -> 1: the bug in one line
assert.ok(!fails([4, -2, 7, -9])); // any positive value hides the bug
console.log("ok");

C#

minimize.cs

int[] foundByFuzzer = [-5, -3, -8, -4, -7, -6, -9, -2];
int[] small = Minimize(foundByFuzzer, Fails);
if (small.Length != 1 || !Fails(small)) throw new Exception("expected a 1-element repro"); // 8 -> 1
if (Fails([4, -2, 7, -9])) throw new Exception("a positive value should hide the bug");
Console.WriteLine("ok");

// The bug reproduces if the answer is wrong.
static bool Fails(int[] ys) => ys.Length > 0 && BuggyMax(ys) != ys.Max();

// Shrink a failing input: keep removing chunks while the bug still reproduces.
static int[] Minimize(int[] xs, Func<int[], bool> fails)
{
    if (!fails(xs)) throw new ArgumentException("start from an input that actually fails");
    int chunk = xs.Length / 2;
    while (chunk >= 1)
    {
        int i = 0;
        bool shrunk = false;
        while (i < xs.Length)
        {
            int[] candidate = [.. xs[..i], .. xs[Math.Min(i + chunk, xs.Length)..]]; // 1. delete a chunk
            if (fails(candidate)) { xs = candidate; shrunk = true; } // 2. still fails: keep it
            else i += chunk;                                        // 3. that chunk mattered
        }
        if (!shrunk) chunk /= 2;                                    // 4. go finer
    }
    return xs;
}

static int BuggyMax(int[] xs)
{
    int best = 0; // bug: should start at xs[0]; wrong when every value is negative
    foreach (int x in xs) best = Math.Max(best, x);
    return best;
}

What it costs

Method	Cost	Cuts the search by
Staring and changing things	unbounded	nothing reliable
Minimizing the input	1-3 min by hand, seconds with a shrinker	n elements down to a few
Hand trace with invariant checks	1-2 min on a minimized input	finds the first failing pass
Bisecting with prints or asserts	one run per check	half the code per check: log₂ of the length

Bisection is binary search over the program. A 64-line function needs at most 6 well-placed checks to find the line where state first goes wrong.

Variations you’ll meet

• Print debugging vs a debugger. In an interview editor, prints are often all you have. Print the state at a checkpoint, labelled, once per pass: print(f"i={i} lo={lo} hi={hi}"). A debugger (pdb, node --inspect, Visual Studio) is the same idea with breakpoints.
• Rubber-duck debugging. Explain the code line by line, out loud, to the interviewer. Saying “and here j is always at least 1” is often when you hear the bug.
• Wolf fence. Put a check halfway, see which side the bug is on, repeat. The name comes from finding a wolf in Alaska by building fences: bisection again.
• Data bisection. If a batch of 1000 records fails, run the first 500. This is minimization when you can’t edit individual values.
• Heisenbugs. Bugs that change when observed, usually from shared mutable state, iteration order of a hash map, or timing. Look for aliasing first: two names for one list.

Pitfalls

• Fixing the symptom. if xs == [2, 5, 1, 4]: ... or a special case for one input. The invariant is still broken for the next input.
• Changing two things at once. If the test passes, you don’t know which change fixed it, or whether the other one broke something else.
• Debugging a big input. Minimize first. It feels slower and is almost always faster.
• Trusting your mental model over the output. If the print says j = 0, then j is 0. Re-read the line that set it.
• Not re-running the old tests. A fix for the new case often breaks an earlier one (especially an edge case).
• Mutation while iterating. Removing from a list or map while looping over it skips elements or throws.

In the interview

• When a test fails, narrate the method: “Let me find the smallest input that fails… [2, 5, 1]. I’ll trace it. My invariant is that a[0..i] is sorted after each pass.”
• State a hypothesis before you change code: “I think key never reaches index 0, because the loop stops at j > 0.”
• After the fix, re-run the small case and the earlier tests out loud.
• If the interviewer hands you a failing case, thank them, minimize it, and follow the same steps. They are grading the method as much as the fix.
• Under time pressure, a clean hypothesis and the right line to change is worth more than a frantic fix.

Check yourself

Check yourself

pick one

A random test fails on a 40-element list. What should you do first?

ARead the whole function again carefullyBShrink the input while it still fails, then trace the small versionCAdd a special case that returns the expected output for that listDRewrite the function with a different approach

Check yourself

pick one

A binary search loops forever on some inputs. Its invariant 'if the target exists, it is in a[lo..hi]' holds on every pass. What kind of bug is it?

AInitialisation: lo and hi start in the wrong placeBTermination: some update does not shrink the range (for example lo = mid)CThere is no bug if the invariant always holds

Check yourself

pick one

You fix a bug and the failing test now passes. Which step is still missing?

ANothing: the test passesBRe-run the earlier tests and add the minimized case to the tableCRemove the debug prints and submit

Practice on your own

Each of these textbook functions is easy to get subtly wrong. Write it, write an oracle, break it on purpose, then find the break with an invariant:

• Partition an array around a pivot (Lomuto scheme). Invariant: everything left of i is ≤ pivot.
• Merge step of merge sort. Invariant: out is sorted and holds the smallest len(out) items.
• Remove all occurrences of x from an array in place, returning the new length.
• Iterative in-order traversal of a binary tree with an explicit stack.
• Evaluate a postfix expression with a stack (what happens on "1 +"?).

Go deeper

• Andreas Zeller, Why Programs Fail (2nd ed., 2009), and The Debugging Book: Delta Debugging, the scientific method for bugs and automatic input minimization.
• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), §2.1: loop invariants with initialisation, maintenance and termination.
• Jon Bentley, Programming Pearls (2nd ed.), column 4, and Joshua Bloch, “Nearly all binary searches and mergesorts are broken” (2006): why even famous code needs invariants and boundary tests.
• David J. Agans, Debugging: The 9 Indispensable Rules: “make it fail”, “divide and conquer”, “change one thing at a time”.

Related

Testing and verificationOracles and random inputs that find the failing case.

Edge casesWhere most minimized failures end up.

Binary searchThe canonical home of invariant and termination bugs.

Class design and invariantsInvariants for objects, not just loops.