Testing & Debugging Algorithms
An algorithm that is wrong on one input in ten thousand is wrong. It will pass every example in the problem statement, pass the three cases you tried by hand, pass code review, and fail in production on a Tuesday with an input nobody will ever reconstruct. Interview problems are designed by people who know exactly which input that is, and the hidden tests contain it.
This lesson is the discipline that catches those inputs before anyone else does. It is step 7 of the method expanded to a full page, and it rests on one idea: you do not test an algorithm by thinking harder about it; you test it by building a second, independent source of truth and comparing. A hand-computed answer, a brute-force implementation, a mathematical property, the standard library: each is an oracle, and testing is the act of running your code against an oracle on inputs you did not choose.
Why this exists: algorithm bugs are different
Ordinary application bugs tend to be loud. A null dereference crashes; a missing field throws; a wrong URL returns 404. You find out quickly and the stack trace points at the line. Algorithm bugs are different in three ways that make the normal testing habits insufficient.
They are silent. A binary search that returns index 4 when the answer was index 5 does not crash. A Kadane that returns 0 for an all-negative array does not throw. Nothing in the program knows the answer is wrong, because the program is the thing that was supposed to know. The only way to detect a silent wrong answer is to have a second way of computing the right one.
They live on rare inputs. Most algorithm bugs are boundary bugs: the empty input, the single element, the window that reaches the end, the target equal to the largest element, two intervals that touch exactly. Random "happy path" testing almost never produces these inputs, which is why the edge-case checklist below is organised by input type and why randomised testing needs a generator biased toward small sizes and extreme values.
They are proved, not observed. You cannot run an algorithm on all inputs, so the final argument that it is correct is a proof: an invariant, an induction, an exchange argument. Testing does not replace the proof; it checks that the code matches the proof. The most productive debugging question is therefore not "which line is wrong?" but "which step of the proof does the code violate?" When you find the input on which the invariant first fails to hold, you have found the bug.
The history is short. Random testing against a specification was popularised by QuickCheck (Claessen and Hughes, ICFP 2000) and has been ported to every language. Delta debugging, the systematic shrinking of a failing input, is from Zeller and Hildebrandt (IEEE TSE 2002). Competitive programmers independently developed "stress testing" (brute force, candidate, generator, loop) because a wrong submission costs penalty time and the judge's feedback is a single word. The recipe on this page is that practice, written down.
Pattern triggers: when a problem demands which test
The literal features of a problem that tell you which testing tool to reach for.
| The problem has… | Reach for | Because |
|---|---|---|
| A simple or brute force you can write in five minutes | Randomised stress test against the brute force | The cheapest oracle that covers inputs you would never think of |
Indices, ranges, lo/hi, left/right | The off-by-one discipline: half-open ranges, loop-condition check, trace on sizes 0, 1, 2 | Nearly every index bug is at a boundary |
| A loop that is supposed to maintain something ("the window is valid", "the heap holds active meetings") | Assertions on the invariant inside the loop | Turns a silent wrong answer into a loud failure at the first bad step |
| Recursion | Tests at depth 0, 1, 2 and an induction-shaped argument | Base case and the inductive step are the only two places a recursive bug can be |
| Sorting, searching, parsing, arithmetic that the standard library also does | Differential testing against the library | The library is a free, battle-tested oracle |
| A hash map or quicksort in a hostile setting (contest, public API) | Adversarial inputs: anti-hash tests, sorted and organ-pipe arrays | Average-case guarantees do not hold against an adversary |
| A claimed complexity | Complexity-ratio harness: time at , , | Confirms the claim empirically before the judge or the customer does |
| Integers near , products, sums of many elements | Overflow cases: INT_MAX, INT_MIN, -INT_MIN | The classic silent bug in C++, Java and JavaScript bit operations |
| Floating point anywhere | Tolerance-based comparison, never == | in binary |
Negative numbers and % or / | Test -7 % 3 and -7 / 2 explicitly | Languages disagree on the sign of the result |
| Strings | Empty, one character, spaces, case, non-ASCII | Strings have more boundaries than arrays |
| Graphs | Disconnected, self-loop, multi-edge, single node, no edges | Each one breaks a different assumption of the traversal |
Intuition & first principles: a test is a claim plus an oracle
Every test has the shape "on input , the output should be ". The hard part is never the input; it is knowing . There are four ways to know it, and a complete testing strategy uses all four.
- Hand computation. You work out yourself. Precise but expensive, so you spend it on the smallest inputs and the boundary cases, where it matters most and where the algorithm is most likely to differ from your mental model.
- A brute-force oracle. You write the dumbest correct program and let it compute . Cheap per input, covers thousands of random inputs, finds the inputs you would never think of. Its weakness is that the brute force may share a misunderstanding with the candidate (both read the specification wrong); hand computation on a few cases guards against that.
- A property. You do not know , but you know something that must be true of it: a sort's output is a permutation of its input and is non-decreasing;
decode(encode(x)) == x; the number of rooms is at least the maximum number of simultaneously overlapping meetings. Properties are weaker than exact answers but they are available when no brute force exists. - A reference implementation. The standard library's sort, the language's big-integer arithmetic, a previous version of your own code, or a competitor's accepted solution. This is differential testing.
flowchart LR
I["Input x<br/>(checklist or generator)"] --> C["Candidate"]
I --> O1["Oracle 1: hand-computed y"]
I --> O2["Oracle 2: brute force"]
I --> O3["Oracle 3: property of y"]
I --> O4["Oracle 4: library / reference"]
C --> V{"Agree?"}
O1 --> V
O2 --> V
O3 --> V
O4 --> V
V -->|"no"| F["Failing input → shrink → trace"]
The rest of this lesson is these four oracles and the machinery around them: how to pick inputs (checklists, generators), how to make failures loud (assertions), how to make a failure understandable (shrinking), and how to go from a failing input to the wrong line (debugging).
The edge-case checklist, by input type
Use this list in step 2 of the method (writing examples) and again in step 7 (testing). The habit to build: before you run anything, write down which items on the list apply and what the expected output is for each. The expected output is the part people skip, and it is the part that catches bugs.
Arrays
| Case | What it breaks | Expected behaviour to decide |
|---|---|---|
Empty [] | Code that reads a[0] before checking; loops that assume one iteration | Return 0, -1, [], or throw? Decide in step 1 |
One element [x] | Fast/slow pointers, binary search with hi = n - 1, "compare with neighbour" logic | The single element is both min and max, both first and last |
Two elements [x, y] | Off-by-one in mid, swaps, "middle" definitions | mid = 0 with (0 + 1) / 2; is that the left or right middle? |
All equal [5,5,5,5] | Binary search on rotated arrays; quicksort partitions; "strictly greater" comparisons | Duplicates collapse the "sorted half" test |
| Already sorted / reverse sorted | Quicksort with first-element pivot (); algorithms whose worst case is sorted input | Should still be within the claimed complexity |
| Many duplicates | Two-pointer dedupe, "next greater" with ties, set-based counting | Decide > versus >= for every comparison |
| Negatives | Kadane with best = 0, prefix sums assumed monotone, abs tricks | The all-negative array is the canonical test |
| Zeros | Products (product-except-self), division, "truthy" checks in Python and JS | One zero versus two zeros are different cases |
| Max and min values | INT_MAX + 1, INT_MIN negated, (lo + hi) overflow | Use the language's actual limits, not round numbers |
| Length exactly at the constraint | Recursion depth, at , stack allocation | Run it once at full size |
| Answer at index 0, at index , not present | Binary search termination, "first/last occurrence" logic | Three separate tests |
k = 0, k = 1, k = n, k > n | Sliding windows of size k, top-k heaps, k-th element | Each has a different degenerate path |
Strings
Empty string; a single character; all the same character; the alphabet boundary ('a', 'z', and whichever character your count array does not index); leading, trailing and repeated spaces; mixed case when the problem says case-insensitive; digits inside words; a non-ASCII character ("é", an emoji) when the alphabet is unspecified, because len("é") and the number of code units differ by language; the pattern longer than the text in string matching; the pattern equal to the text; and a palindrome of even and odd length.
Trees
Null (empty tree); a single node; a root with one child on the left only and on the right only; a chain (every node has one child, depth , which is the recursion-depth test); a perfect binary tree of depth 3 (15 nodes, exercises the balanced path); negative values if the tree is a BST, because people compare against 0 by accident; duplicate values if the BST definition allows them; and the target at the root, at a leaf, and absent.
Graphs
No edges (every node is its own component); a single node; a disconnected graph (two components, so a single DFS from node 0 misses half the graph); a self-loop (breaks "neighbour is not parent" cycle detection in undirected graphs); multi-edges between the same pair (breaks the same check and double-counts degrees); a cycle (infinite loop without a visited set); a directed acyclic graph that is a chain (topological sort has one valid order) versus one with many valid orders (topological sort has several; your test must accept any); a complete graph (edge count , adjacency-matrix memory); and node ids that are 1-based in the input and 0-based in your arrays.
Numbers
0; 1; ; the smallest and largest representable values; a value such that an intermediate computation overflows even though the result fits (abs(INT_MIN), a * b / c where a * b overflows); even and odd (the middle element differs); and for anything parameterised by ; a perfect square and the integer just below it for sqrt; negative numerators for % and /.
Intervals
Touching intervals [1,3],[3,5] (overlap or not depends on open/closed convention; decide and test both ways); nested [1,10],[2,3]; identical [1,3],[1,3]; a single interval; unsorted input; an interval that swallows several later ones; intervals of zero length [4,4]; and negative coordinates.
The three sizes
If you have time for only three tests of an array algorithm, run sizes 0, 1 and 2. Size 0 catches the unguarded read, size 1 catches every "compare with the neighbour" assumption, and size 2 catches the mid computation and the final loop iteration. Most index bugs die at .
Off-by-one hunting
Off-by-one errors are not random. They come from three specific confusions, and each has a discipline that removes it.
Half-open ranges. Represent every range as [lo, hi): lo included, hi excluded. Then the length is hi - lo with no +1; the empty range is lo == hi; adjacent ranges [a, b) and [b, c) share no element and need no -1 to abut; splitting at mid gives [lo, mid) and [mid, hi) with nothing lost and nothing duplicated. Python slices, C++ iterators, Java's subList and Arrays.copyOfRange, and JavaScript's slice are all half-open, so following the convention makes your code agree with the library. The only place a closed range is natural is when the problem statement hands you one ([start, end] inclusive); convert at the boundary.
The while (lo < hi) versus while (lo <= hi) discipline. These are two different binary searches with two different invariants, and mixing their parts is the most common binary search bug.
while (lo <= hi)searches a closed range[lo, hi]for an exact match. Bothlo = mid + 1andhi = mid - 1are correct becausemidhas been examined and excluded. Exit means "not found". Returningloafter the loop gives the insertion point.while (lo < hi)searches for a boundary (the firsttruein a monotone predicate) over[lo, hi]where the answer is guaranteed to exist in the range. Updates arelo = mid + 1(mid is false, exclude it) andhi = mid(mid is true, keep it: it might be the answer). Exit meanslo == hiis the answer. Usinghi = mid - 1here skips the answer; usinglo = midwithmid = (lo + hi) / 2loops forever whenhi = lo + 1.
The check for the second form: with lo = 0, hi = 1, mid = 0. If the update on the "move right" branch is lo = mid, nothing changes and the loop never ends. If you need lo = mid, round mid up: mid = lo + (hi - lo + 1) / 2. Write the invariant above the loop ("answer is in [lo, hi]"), and check both updates preserve it.
Index versus count. n elements have indices 0..n-1; the last index is n - 1; the number of elements between indices i and j inclusive is j - i + 1; the number of windows of size k in an array of n is n - k + 1; a prefix-sum array has n + 1 entries so that prefix[j] - prefix[i] is the sum of [i, j) with no special case for i = 0. When you write +1 or -1 in index arithmetic, say in a comment which of these facts it comes from. If you cannot, it is probably wrong.
Invariants and assertions as executable documentation
An invariant is a statement about the program state that is true at a specific point every time execution passes it. "At the top of the loop, s[left..right) has at most k distinct characters." "After partitioning, everything in [lo, i) is less than the pivot." "The heap contains exactly the end times of meetings that have started and not ended." The correctness proof of an algorithm is a list of invariants and arguments that each step preserves them.
An assertion is an invariant written as code: assert len(counts) <= k. It costs one line and converts a silent wrong answer into a loud failure at the first step where the proof and the code disagree. That localisation is what you are buying: instead of "the output was 3, expected 4", you get "the invariant failed at iteration 7 with state …".
Where to put them:
- Preconditions at the top of a function:
assert k >= 0,assert all(a[i] <= a[i+1] for i in range(n-1))for a function that requires sorted input (expensive; see below). - Loop invariants at the top of the loop body, in terms of the state variables.
- Postconditions before
return: the result is in range, the output has the right length, the sum of the parts equals the whole. - "Unreachable" branches:
assert False, "unreachable"in theelseyou believe cannot execute. When it executes, you have learned something.
Cheap versus expensive. An assertion inside an loop is free. An assertion inside an loop makes the algorithm , which is fine for testing on small inputs and unacceptable in production or on the full-size test. Convention: keep cheap assertions always; wrap expensive ones in a debug flag (if DEBUG: assert is_sorted(a)) or a function you can switch off.
Disabling in production. Python's assert is removed entirely under python -O, which is why you must never put side effects in an assertion and never use assert to validate user input. Java's assert is disabled unless the JVM runs with -ea, so Java code that relies on it silently loses its checks; competitive programmers and most production code use an explicit if (!cond) throw new AssertionError(...) or a check() helper instead. C++'s assert compiles to nothing when NDEBUG is defined, which most release build configurations do. JavaScript has node:assert, which is never stripped. Know what your build does before you trust an assertion.
Mechanics: brute-force comparators and randomised stress testing
The core recipe. You need four pieces and a loop.
- A brute force. The dumbest correct program. Enumerate every candidate, check every one, no cleverness. It is allowed to be or because it only runs on tiny inputs. Its only job is to be obviously correct; if you find yourself optimising it, stop.
- A candidate. The solution you want to trust.
- A generator. A function from a random seed to an input. Small sizes (1 to 8 elements) and small value ranges (say to ) so that boundary conditions and duplicates occur constantly. The generator must be deterministic given its seed so a failure can be reproduced.
- A comparator. Usually
candidate(x) == brute(x). When the answer is not unique (any valid topological order, any index of a duplicate), the comparator must check validity rather than equality.
The loop: for iteration , generate an input, run both, compare. On the first mismatch, stop and print the input and both outputs. Then shrink: try to make the failing input smaller while it still fails, so that you can trace it by hand.
flowchart TD
G["Generator<br/>seed → small random input"] --> C["Candidate"]
G --> B["Brute force"]
C --> M{"Outputs<br/>agree?"}
B --> M
M -->|"yes"| N["Next iteration<br/>(until budget exhausted)"]
N --> G
M -->|"no"| S["Shrink: drop elements,<br/>move values toward 0,<br/>keep any change that still fails"]
S --> R["Minimal failing input<br/>→ hand trace → bug"]
Shrinking is delta debugging in miniature. Given a failing input, try a set of simplifications: remove one element; replace a value by one closer to zero; replace a substring by a shorter one; replace a subtree by a leaf. For each simplification, re-run the comparator. If the simplified input still fails, keep it and continue from there; if it passes, revert and try the next simplification. Stop when no simplification keeps the failure. The result is a locally minimal failing input: usually one to three elements, which is small enough to trace by hand in under a minute. The full delta debugging algorithm (Zeller and Hildebrandt 2002) removes chunks of decreasing size rather than single elements, which matters for inputs of thousands of elements; for stress-testing algorithms, element-at-a-time is enough because inputs are already small.
Trace table: a stress-test session
The candidate is a deliberately buggy Kadane's algorithm for maximum subarray sum, initialised with best = 0 and current = 0 (the version that resets to zero whenever the running sum goes negative). It is correct whenever the array has a non-negative element and wrong on every all-negative array. The generator uses the 32-bit linear congruential generator from the implementation section with seed 12345, lengths 1 to 8, values in . Every number here was produced by running the harness.
| iteration | random array | brute | candidate | verdict |
|---|---|---|---|---|
| 1 | [3, -9] | 3 | 3 | match |
| 2 | [10, 10] | 20 | 20 | match |
| 3 | [-5, -4, 10] | 10 | 10 | match |
| 4 | [-6, -9, 8, -4] | 8 | 8 | match |
| 5 | [-4, -1, -2, -3, -10, -5] | 0 | mismatch |
Five iterations. A hand-written test suite with "a normal array, a mixed array, a single element" would have passed. Then shrinking, from [-4, -1, -2, -3, -10, -5]:
| shrink step | attempt | candidate input | brute | candidate | outcome |
|---|---|---|---|---|---|
| 1 | drop a[0] = -4 | [-1, -2, -3, -10, -5] | 0 | still fails, keep | |
| 2 | drop a[0] = -1 | [-2, -3, -10, -5] | 0 | still fails, keep | |
| 3 | drop a[0] = -2 | [-3, -10, -5] | 0 | still fails, keep | |
| 4 | drop a[0] = -3 | [-10, -5] | 0 | still fails, keep | |
| 5 | drop a[0] = -10 | [-5] | 0 | still fails, keep | |
| 6 | drop a[0] = -5 | [] | — | — | empty is outside the domain, skip |
| 7 | a[0]: | [-4] | 0 | still fails, keep | |
| 8 | a[0]: | [-3] | 0 | still fails, keep | |
| 9 | a[0]: | [-2] | 0 | still fails, keep | |
| 10 | a[0]: | [-1] | 0 | still fails, keep | |
| 11 | a[0]: | [0] | 0 | 0 | passes, revert |
| 12 | drop a[0] = -1 | [] | — | — | empty is outside the domain, skip |
| 13 | a[0]: | [0] | 0 | 0 | passes, revert |
Minimal failing input: [-1], expected , got 0. At this point the bug is obvious without a debugger: the candidate's answer cannot be below zero, so it is treating "take nothing" as a legal subarray. The fix is to initialise best and current with a[0] and iterate from index 1, which the correct kadane in the implementation does.
The session also illustrates the role of the generator's parameters. With values in and length up to 8, the probability that a random array is all-negative is high enough that the failure appeared on iteration 5. With values in and length 1000, which is how beginners write generators, the probability is and the stress test would run forever reporting success. Small inputs find bugs; large inputs find performance problems. Run both, separately.
Property-based testing
A property is a predicate on (input, output) pairs that every correct implementation satisfies. Property-based testing generates random inputs and checks the property; it is stress testing where the oracle is a property instead of a brute force. The canonical examples:
- Round trip:
decode(encode(x)) == x,parse(format(x)) == x,unzip(zip(a, b)) == (a, b). - Idempotence:
sort(sort(a)) == sort(a),normalise(normalise(s)) == normalise(s). - Permutation plus order:
sorted(a)has the same multiset asaand is non-decreasing. - Commutativity / equivalence of two paths:
union(a, b) == union(b, a);kth_largest(a, k) == sorted(a)[n-k]. - Bounds: the number of meeting rooms is at least the maximum overlap at any start time and at most the number of meetings.
- Metamorphic relations: if you append a very large element to an array, the maximum subarray sum increases by at least that element; if you double every weight, the shortest path doubles.
Libraries exist in every language: Hypothesis for Python, jqwik for Java (and the older junit-quickcheck), fast-check for JavaScript and TypeScript, RapidCheck for C++. They contribute three things over a hand-written loop: generators for structured data (lists of a type, trees, strings matching a regex), automatic shrinking that is smarter than element-at-a-time, and a database of previously failing inputs that is re-run first on the next test run. Hypothesis in particular is worth learning: @given(st.lists(st.integers())) on a test function gives you a stress test with shrinking in two lines.
You do not need the library to use the idea. The implementation section's harness is a property-based test whose property is "candidate equals brute force"; replace the comparator with any of the properties above and you have the rest. What the library buys you is time and better shrinking; what the discipline buys you is the habit of asking "what must be true of the answer?", which is the same question the correctness proof asks.
Differential testing against the standard library
When the standard library implements the same function, it is an oracle you already trust. Your merge sort against sorted; your binary search against bisect_left; your big-number multiplication against Python's integers; your atoi against int() on the inputs where both are defined; your string matcher against str.find; your heap against heapq; your shortest path against networkx in a test environment. Differential testing is stress testing where the brute force is someone else's production code.
Two cautions. The library's specification may differ from yours at the edges (Python's int(" 42 ") accepts surrounding whitespace, LeetCode's atoi accepts only leading spaces; str.find returns , your function may return None), so the comparator must restrict to the common domain. And when the library disagrees with you, the library is right far more often than not, but not always: the famous counterexample is Java's Arrays.binarySearch, which overflowed on (low + high) / 2 for arrays over elements until it was fixed in 2006, nine years after the code was written. Joshua Bloch's write-up of that bug is the best short essay on why boundary testing matters.
Testing recursive code
Recursive code has exactly two places to be wrong: the base case and the inductive step. Test them separately.
Base cases first, in isolation. Call the function directly on the empty input, the single node, depth 0. If height(None) returns 0 and height(leaf) returns 1 (or 0, depending on your convention, which you have written down), the base is right. Most "recursion returns the wrong answer" bugs are an off-by-one in the base case that propagates up.
Induction-shaped tests. The inductive step says "if the recursive calls are right, the combination is right". Test the combination on inputs where you know the sub-results: a tree with two leaves, an array of three elements, a string of two characters. Then one level deeper. If sizes 0, 1, 2 and 3 are right, and the recursion only calls itself on strictly smaller inputs, the induction gives you every size; see Recursion & Induction for the argument made precise.
Depth. Run once at the maximum input size in the shape that maximises depth (a chain for a tree, a sorted array for a naive quicksort). Python dies at a depth of 1000 by default; Java and C++ at a few thousand to a few tens of thousands frames depending on frame size and stack configuration. If the maximum depth is proportional to and can be , the recursion must become iteration or the recursion limit must be raised and the stack enlarged, and both of those are things you need to have tested.
Memoised recursion. Test with memoisation disabled first (small ); a memoisation bug (wrong key, state missing a dimension) produces plausible wrong answers that are hard to tell from a logic bug. Then enable it and check the answers are unchanged and the call count drops.
Testing with adversarial inputs
Average-case analysis assumes the input is not chosen by someone who has read your code. Contests and public APIs violate that assumption.
Anti-quicksort. A quicksort that picks the first or last element as the pivot degrades to on sorted and reverse-sorted input. With median-of-three it degrades on the "organ pipe" and other crafted inputs. McIlroy's "A Killer Adversary for Quicksort" (1999) shows how to construct a worst case for any deterministic quicksort by observing its comparisons. The defence is a random pivot, or introsort (fall back to heapsort when depth exceeds ), which is what the C++ standard library does. The test: run your sort on a sorted array, a reverse-sorted array, an all-equal array, and an organ pipe [1,2,…,n/2,…,2,1] at and time it.
Anti-hash. A hash map's depends on keys spreading across buckets. Java's HashMap with String keys, C++'s std::unordered_map with the default std::hash<long long> (an identity function in libstdc++), and Python's dict with integer keys all have inputs that collide into one bucket and make every operation . On Codeforces, anti-hash test cases that target unordered_map with the default hash are added to contests routinely and turn solutions into time-limit failures. The defences are a custom hash with a random seed, a tree map, or sorting instead of hashing; see the anti-hash section of Hash Tables. Java 8 and later convert long bucket chains to red-black trees, which caps the damage at per operation for Comparable keys.
Worst-case shapes for everything else. The chain for a tree algorithm; the complete graph for an adjacency-list algorithm; the string "aaaa…a" with pattern "aaa…ab" for a naive string match; intervals that all overlap for a sweep; a DP with the state space at its maximum. For each algorithm you write, you should be able to name the input shape that is its worst case, and you should run it once.
Performance testing: does the code match the claimed complexity?
A complexity claim is a testable prediction: if the algorithm is , doubling doubles the time; if , doubling quadruples it; if , the ratio is slightly above 2 and decreases slowly toward 2 as grows. The test is to time the function at , and and compute the ratios. Taking the base-2 logarithm of the ratio gives an estimate of the exponent: 1.0 for linear, 2.0 for quadratic, around 1.1 for at practical sizes.
Three rules make the measurement meaningful:
- Take the minimum of several runs, not the mean. Noise (garbage collection, a background process, CPU frequency changes) only ever adds time, so the minimum is the best estimate of the true cost.
- Warm up JIT-compiled languages (Java, JavaScript) by running the function a few times before timing; the first runs include compilation.
- Make large enough that each run takes at least a few milliseconds, otherwise timer resolution and fixed overheads dominate the ratio. At the same time, must be small enough that still fits in time and memory.
The harness in the implementation section does all three and asserts that a known linear function measures near exponent 1 and a known quadratic function near exponent 2. Use it on your own code by passing your function and a reasonable . The Complexity Analysis lesson explains what to expect when the measured exponent disagrees with the analysis (cache effects, which the memory lesson covers, and allocation costs are the usual reasons), and the capstone is built around this measurement.
The ladder: hand tests → stress → property → adversarial
| Rung | What you do | Finds | Cost | Misses |
|---|---|---|---|---|
| Provided examples | Run the statement's sample cases | Gross misunderstanding | Minutes | Everything else; the samples are chosen to be understandable, not hard |
| Edge-case checklist | Hand-write the boundary inputs for the input type, with expected outputs | Boundary bugs: empty, size 1 and 2, extremes, k degenerate | 10 minutes | Interactions between features (duplicates and negatives) |
| Hand trace | Execute the algorithm in a table on one small input | Mismatch between your mental model and the code | 5 minutes | Inputs you did not trace |
| Randomised stress vs brute force | Generator, brute, candidate, loop, shrink | Logic bugs on inputs you never imagined; produces a minimal reproducer | 15 minutes to write once; seconds to run | Bugs shared by brute and candidate; performance |
| Property-based | Stress with a property instead of a brute force | Specification violations when no brute force exists | Same as stress | Properties you did not state |
| Differential | Compare with a library or reference | Everything the reference gets right | Minutes | Edges where specifications differ |
| Adversarial | Hand-craft worst-case shapes | Complexity blow-ups, hash collisions, recursion depth | 10 minutes | Correctness bugs |
| Complexity ratio | Time at , , | Wrong complexity class; accidental | 5 minutes | Constant factors; small- behaviour |
Each rung is cheap relative to what it finds, and each finds things the others do not. In an interview you get the first three; in a contest the first four plus adversarial; in production code all of them, and the stress test becomes a permanent test in the suite with its seed fixed.
Correctness: what a passing stress test proves
A stress test that passes 10,000 iterations does not prove the code correct. It proves that the candidate agrees with the brute force on 10,000 inputs drawn from the generator's distribution. The gap between that and correctness has three parts, and you should be able to name them.
Coverage of the generator. If the generator never produces an all-negative array, no number of iterations finds the Kadane bug. The generator's parameters (small sizes, small values, high duplicate rate, explicit inclusion of extremes) are what determine which bugs are reachable. A useful habit: after the random loop, run the edge-case checklist explicitly as well, because random generation reaches "empty" and "all equal" only with the right biases.
Independence of the oracle. If brute force and candidate both misread the specification, they agree on wrong answers. Hand-computed examples from the problem statement break this symmetry; so does a second brute force written a different way.
The probabilistic bound. If a fraction of the generator's inputs trigger the bug, the chance that iterations all miss it is . For and , that is ; for it is . A hundred iterations is not a stress test. A thousand usually is, for bugs the generator can reach at all; ten thousand costs nothing when the inputs are small. The bound says nothing about bugs with under the generator, which is why adversarial inputs are a separate rung.
What the stress test does give you is a decisive, reproducible counterexample when the code is wrong, and that is the thing worth the most in practice: a minimal failing input converts debugging from a search into a trace.
Complexity of testing itself
The brute force runs in its own complexity, so the generator's maximum size must keep it fast: for an brute force, for , for . Ten thousand iterations of an brute at is operations, well under a second in any language. Shrinking makes at most comparator calls for an input of length and value magnitude in the element-at-a-time version, which is trivial at these sizes. The complexity harness runs the function under test seven times each at three sizes, so budget about the cost at ; choose so that the whole thing finishes in a second or two. None of this is a concern in practice; the concern is the opposite, writing generators so large that the brute force becomes the bottleneck.
Implementation
(a) Stress-test harness: Kadane versus brute force
Four pieces: a deterministic PRNG (a 32-bit linear congruential generator with the Numerical Recipes constants; the same sequence in all four languages, so the failing iteration is the same everywhere), a generator, the brute force, two candidates (correct and buggy), the loop and the shrinker. The tests assert that the correct Kadane survives 1,000 iterations, that the buggy one fails on iteration 5 with exactly the array in the trace table, and that shrinking reduces it to [-1].
The PRNG uses the high 16 bits of its state. The low bits of a power-of-two-modulus LCG have short periods (the lowest bit alternates, the lowest three bits cycle with period 8), so state % 8 would produce array lengths that cycle instead of varying. This is a real bug that was found while writing this page; it is also a reminder that the test generator is code and needs testing.
from typing import Callable
class Lcg:
"""32-bit linear congruential generator. Deterministic; same sequence in every language."""
def __init__(self, seed: int) -> None:
self.state = seed & 0xFFFFFFFF
def next_int(self, lo: int, hi: int) -> int:
"""Integer in [lo, hi]. Uses the high 16 bits: the low bits of an LCG are weak."""
self.state = (self.state * 1664525 + 1013904223) & 0xFFFFFFFF
return lo + (self.state >> 16) % (hi - lo + 1)
def random_array(rng: Lcg, max_len: int, lo: int, hi: int) -> list[int]:
n = rng.next_int(1, max_len)
return [rng.next_int(lo, hi) for _ in range(n)]
def brute_max_subarray(a: list[int]) -> int:
"""O(n^2): every (i, j), running sum. Obviously correct, deliberately slow."""
best = a[0]
for i in range(len(a)):
total = 0
for j in range(i, len(a)):
total += a[j]
best = max(best, total)
return best
def kadane(a: list[int]) -> int:
best = current = a[0]
for x in a[1:]:
current = max(x, current + x)
best = max(best, current)
return best
def kadane_buggy(a: list[int]) -> int:
"""The classic mistake: best starts at 0, so an all-negative array returns 0."""
best = current = 0
for x in a:
current = max(0, current + x)
best = max(best, current)
return best
Solver = Callable[[list[int]], int]
def find_failure(candidate: Solver, seed: int, iterations: int) -> tuple[int, list[int]] | None:
rng = Lcg(seed)
for it in range(1, iterations + 1):
a = random_array(rng, 8, -10, 10)
if candidate(a) != brute_max_subarray(a):
return it, a
return None
def shrink(candidate: Solver, a: list[int]) -> list[int]:
"""Greedy delta debugging: drop elements, then move values toward 0; keep what still fails."""
def fails(b: list[int]) -> bool:
return len(b) > 0 and candidate(b) != brute_max_subarray(b)
changed = True
while changed:
changed = False
i = 0
while i < len(a):
b = a[:i] + a[i + 1:]
if fails(b):
a, changed = b, True
else:
i += 1
for i in range(len(a)):
while a[i] != 0:
b = a.copy()
b[i] -= 1 if a[i] > 0 else -1
if fails(b):
a, changed = b, True
else:
break
return a
if __name__ == "__main__":
assert find_failure(kadane, 12345, 1000) is None
failure = find_failure(kadane_buggy, 12345, 1000)
assert failure == (5, [-4, -1, -2, -3, -10, -5]), failure
assert shrink(kadane_buggy, failure[1]) == [-1]
assert kadane([-1]) == -1 and kadane_buggy([-1]) == 0
print("stress harness ok")
import java.util.Arrays;
import java.util.function.ToLongFunction;
public class StressHarness {
/** 32-bit linear congruential generator. Deterministic; same sequence in every language. */
static final class Lcg {
private long state;
Lcg(long seed) { state = seed & 0xFFFFFFFFL; }
/** Integer in [lo, hi]. Uses the high 16 bits: the low bits of an LCG are weak. */
int nextInt(int lo, int hi) {
state = (state * 1664525L + 1013904223L) & 0xFFFFFFFFL;
return lo + (int) ((state >>> 16) % (hi - lo + 1));
}
}
static int[] randomArray(Lcg rng, int maxLen, int lo, int hi) {
int n = rng.nextInt(1, maxLen);
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = rng.nextInt(lo, hi);
return a;
}
/** O(n^2): every (i, j), running sum. Obviously correct, deliberately slow. */
static long bruteMaxSubarray(int[] a) {
long best = a[0];
for (int i = 0; i < a.length; i++) {
long total = 0;
for (int j = i; j < a.length; j++) {
total += a[j];
best = Math.max(best, total);
}
}
return best;
}
static long kadane(int[] a) {
long best = a[0], current = a[0];
for (int i = 1; i < a.length; i++) {
current = Math.max(a[i], current + a[i]);
best = Math.max(best, current);
}
return best;
}
/** The classic mistake: best starts at 0, so an all-negative array returns 0. */
static long kadaneBuggy(int[] a) {
long best = 0, current = 0;
for (int x : a) {
current = Math.max(0, current + x);
best = Math.max(best, current);
}
return best;
}
record Failure(int iteration, int[] input) {}
static Failure findFailure(ToLongFunction<int[]> candidate, long seed, int iterations) {
Lcg rng = new Lcg(seed);
for (int it = 1; it <= iterations; it++) {
int[] a = randomArray(rng, 8, -10, 10);
if (candidate.applyAsLong(a) != bruteMaxSubarray(a)) return new Failure(it, a);
}
return null;
}
static boolean fails(ToLongFunction<int[]> candidate, int[] b) {
return b.length > 0 && candidate.applyAsLong(b) != bruteMaxSubarray(b);
}
static int[] without(int[] a, int idx) {
int[] b = new int[a.length - 1];
for (int i = 0, j = 0; i < a.length; i++) if (i != idx) b[j++] = a[i];
return b;
}
/** Greedy delta debugging: drop elements, then move values toward 0; keep what still fails. */
static int[] shrink(ToLongFunction<int[]> candidate, int[] a) {
boolean changed = true;
while (changed) {
changed = false;
int i = 0;
while (i < a.length) {
int[] b = without(a, i);
if (fails(candidate, b)) { a = b; changed = true; } else i++;
}
for (i = 0; i < a.length; i++) {
while (a[i] != 0) {
int[] b = a.clone();
b[i] -= a[i] > 0 ? 1 : -1;
if (fails(candidate, b)) { a = b; changed = true; } else break;
}
}
}
return a;
}
static void check(boolean cond, String msg) { if (!cond) throw new AssertionError(msg); }
public static void main(String[] args) {
check(findFailure(StressHarness::kadane, 12345, 1000) == null, "kadane should pass");
Failure f = findFailure(StressHarness::kadaneBuggy, 12345, 1000);
check(f != null && f.iteration() == 5, "buggy should fail on iteration 5");
check(Arrays.equals(f.input(), new int[]{-4, -1, -2, -3, -10, -5}), Arrays.toString(f.input()));
check(Arrays.equals(shrink(StressHarness::kadaneBuggy, f.input()), new int[]{-1}), "shrink to [-1]");
check(kadane(new int[]{-1}) == -1 && kadaneBuggy(new int[]{-1}) == 0, "minimal case");
System.out.println("stress harness ok");
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <optional>
#include <utility>
#include <vector>
// 32-bit linear congruential generator. Deterministic; same sequence in every language.
class Lcg {
std::uint32_t state;
public:
explicit Lcg(std::uint32_t seed) : state(seed) {}
// Integer in [lo, hi]. Uses the high 16 bits: the low bits of an LCG are weak.
int nextInt(int lo, int hi) {
state = state * 1664525u + 1013904223u; // unsigned: wraps mod 2^32 by definition
return lo + static_cast<int>((state >> 16) % static_cast<std::uint32_t>(hi - lo + 1));
}
};
using Solver = std::function<long long(const std::vector<int>&)>;
std::vector<int> randomArray(Lcg& rng, int maxLen, int lo, int hi) {
int n = rng.nextInt(1, maxLen);
std::vector<int> a(n);
for (int& x : a) x = rng.nextInt(lo, hi);
return a;
}
// O(n^2): every (i, j), running sum. Obviously correct, deliberately slow.
long long bruteMaxSubarray(const std::vector<int>& a) {
long long best = a[0];
for (std::size_t i = 0; i < a.size(); ++i) {
long long total = 0;
for (std::size_t j = i; j < a.size(); ++j) {
total += a[j];
best = std::max(best, total);
}
}
return best;
}
long long kadane(const std::vector<int>& a) {
long long best = a[0], current = a[0];
for (std::size_t i = 1; i < a.size(); ++i) {
current = std::max<long long>(a[i], current + a[i]);
best = std::max(best, current);
}
return best;
}
// The classic mistake: best starts at 0, so an all-negative array returns 0.
long long kadaneBuggy(const std::vector<int>& a) {
long long best = 0, current = 0;
for (int x : a) {
current = std::max<long long>(0, current + x);
best = std::max(best, current);
}
return best;
}
std::optional<std::pair<int, std::vector<int>>> findFailure(const Solver& candidate, std::uint32_t seed, int iterations) {
Lcg rng(seed);
for (int it = 1; it <= iterations; ++it) {
std::vector<int> a = randomArray(rng, 8, -10, 10);
if (candidate(a) != bruteMaxSubarray(a)) return std::make_pair(it, a);
}
return std::nullopt;
}
// Greedy delta debugging: drop elements, then move values toward 0; keep what still fails.
std::vector<int> shrink(const Solver& candidate, std::vector<int> a) {
auto fails = [&](const std::vector<int>& b) { return !b.empty() && candidate(b) != bruteMaxSubarray(b); };
bool changed = true;
while (changed) {
changed = false;
std::size_t i = 0;
while (i < a.size()) {
std::vector<int> b = a;
b.erase(b.begin() + static_cast<long>(i));
if (fails(b)) { a = b; changed = true; } else ++i;
}
for (i = 0; i < a.size(); ++i) {
while (a[i] != 0) {
std::vector<int> b = a;
b[i] -= a[i] > 0 ? 1 : -1;
if (fails(b)) { a = b; changed = true; } else break;
}
}
}
return a;
}
int main() {
assert(!findFailure(kadane, 12345, 1000).has_value());
auto f = findFailure(kadaneBuggy, 12345, 1000);
assert(f.has_value() && f->first == 5);
assert((f->second == std::vector<int>{-4, -1, -2, -3, -10, -5}));
assert((shrink(kadaneBuggy, f->second) == std::vector<int>{-1}));
assert(kadane({-1}) == -1 && kadaneBuggy({-1}) == 0);
std::cout << "stress harness ok\n";
return 0;
}
import assert from "node:assert/strict";
/** 32-bit linear congruential generator. Deterministic; same sequence in every language. */
class Lcg {
private state: number;
constructor(seed: number) {
this.state = seed >>> 0;
}
/** Integer in [lo, hi]. Uses the high 16 bits: the low bits of an LCG are weak. */
nextInt(lo: number, hi: number): number {
// state * 1664525 < 2^53, so plain doubles are exact here; then reduce mod 2^32.
this.state = (this.state * 1664525 + 1013904223) % 4294967296;
return lo + (Math.floor(this.state / 65536) % (hi - lo + 1));
}
}
type Solver = (a: number[]) => number;
function randomArray(rng: Lcg, maxLen: number, lo: number, hi: number): number[] {
const n = rng.nextInt(1, maxLen);
return Array.from({ length: n }, () => rng.nextInt(lo, hi));
}
/** O(n^2): every (i, j), running sum. Obviously correct, deliberately slow. */
function bruteMaxSubarray(a: number[]): number {
let best = a[0];
for (let i = 0; i < a.length; i++) {
let total = 0;
for (let j = i; j < a.length; j++) {
total += a[j];
best = Math.max(best, total);
}
}
return best;
}
function kadane(a: number[]): number {
let best = a[0];
let current = a[0];
for (let i = 1; i < a.length; i++) {
current = Math.max(a[i], current + a[i]);
best = Math.max(best, current);
}
return best;
}
/** The classic mistake: best starts at 0, so an all-negative array returns 0. */
function kadaneBuggy(a: number[]): number {
let best = 0;
let current = 0;
for (const x of a) {
current = Math.max(0, current + x);
best = Math.max(best, current);
}
return best;
}
function findFailure(candidate: Solver, seed: number, iterations: number): [number, number[]] | null {
const rng = new Lcg(seed);
for (let it = 1; it <= iterations; it++) {
const a = randomArray(rng, 8, -10, 10);
if (candidate(a) !== bruteMaxSubarray(a)) return [it, a];
}
return null;
}
/** Greedy delta debugging: drop elements, then move values toward 0; keep what still fails. */
function shrink(candidate: Solver, input: number[]): number[] {
let a = input.slice();
const fails = (b: number[]) => b.length > 0 && candidate(b) !== bruteMaxSubarray(b);
let changed = true;
while (changed) {
changed = false;
let i = 0;
while (i < a.length) {
const b = a.slice(0, i).concat(a.slice(i + 1));
if (fails(b)) { a = b; changed = true; } else i++;
}
for (i = 0; i < a.length; i++) {
while (a[i] !== 0) {
const b = a.slice();
b[i] -= a[i] > 0 ? 1 : -1;
if (fails(b)) { a = b; changed = true; } else break;
}
}
}
return a;
}
assert.equal(findFailure(kadane, 12345, 1000), null);
const failure = findFailure(kadaneBuggy, 12345, 1000);
assert.deepEqual(failure, [5, [-4, -1, -2, -3, -10, -5]]);
assert.deepEqual(shrink(kadaneBuggy, failure![1]), [-1]);
assert.equal(kadane([-1]), -1);
assert.equal(kadaneBuggy([-1]), 0);
console.log("stress harness ok");
To reuse the harness on another problem, replace bruteMaxSubarray and the candidate, adjust randomArray to produce the right input shape (two arrays, a string, a list of intervals), and keep everything else. The shrinker's two moves (drop an element, move a value toward zero) are right for arrays of integers; for strings, drop a character and replace a character by 'a'; for intervals, drop an interval and shorten one.
(b) Complexity-ratio harness
Times a function at , , with warm-up and best-of-7, and reports the estimated exponent in , computed as . The self-test checks a known loop and a known loop. The acceptance bands are deliberately wide (linear in , quadratic in ) because timing on a shared machine is noisy; a real regression (quadratic where linear was claimed) lands far outside them.
import math
import time
from typing import Callable
def best_of(fn: Callable[[int], int], n: int, repeats: int = 7) -> float:
"""Minimum wall time over `repeats` runs. Noise only adds time, so min is the best estimate."""
best = math.inf
for _ in range(repeats):
t0 = time.perf_counter()
fn(n)
best = min(best, time.perf_counter() - t0)
return best
def growth_exponent(fn: Callable[[int], int], n0: int) -> float:
"""Estimate b in T(n) ~ c * n^b from timings at n0, 2n0, 4n0."""
fn(n0) # warm-up (matters for JIT languages; harmless here)
t1 = best_of(fn, n0)
t4 = best_of(fn, 4 * n0)
return math.log2(t4 / t1) / 2
def linear_work(n: int) -> int:
total = 0
for i in range(n):
total += i & 7
return total
def quadratic_work(n: int) -> int:
count = 0
for i in range(n):
for j in range(i + 1, n):
if (i ^ j) & 3 == 0:
count += 1
return count
if __name__ == "__main__":
lin = growth_exponent(linear_work, 200_000)
quad = growth_exponent(quadratic_work, 300)
print(f"linear exponent ~ {lin:.2f}, quadratic exponent ~ {quad:.2f}")
assert 0.5 < lin < 1.6, lin
assert 1.5 < quad < 2.6, quad
print("complexity harness ok")
import java.util.function.LongUnaryOperator;
public class ComplexityHarness {
/** Minimum wall time over `repeats` runs, in nanoseconds. */
static long bestOf(LongUnaryOperator fn, long n, int repeats) {
long best = Long.MAX_VALUE;
for (int r = 0; r < repeats; r++) {
long t0 = System.nanoTime();
sink += fn.applyAsLong(n);
best = Math.min(best, System.nanoTime() - t0);
}
return best;
}
static volatile long sink = 0; // keeps the JIT from discarding the work
/** Estimate b in T(n) ~ c * n^b from timings at n0 and 4n0, after warming up the JIT. */
static double growthExponent(LongUnaryOperator fn, long n0) {
for (int i = 0; i < 5; i++) sink += fn.applyAsLong(n0); // warm-up
double t1 = bestOf(fn, n0, 7);
double t4 = bestOf(fn, 4 * n0, 7);
return Math.log(t4 / t1) / Math.log(2) / 2;
}
static long linearWork(long n) {
long total = 0;
for (long i = 0; i < n; i++) total += i & 7;
return total;
}
static long quadraticWork(long n) {
long count = 0;
for (long i = 0; i < n; i++)
for (long j = i + 1; j < n; j++)
if (((i ^ j) & 3) == 0) count++;
return count;
}
static void check(boolean cond, String msg) { if (!cond) throw new AssertionError(msg); }
public static void main(String[] args) {
double lin = growthExponent(ComplexityHarness::linearWork, 4_000_000);
double quad = growthExponent(ComplexityHarness::quadraticWork, 3_000);
System.out.printf("linear exponent ~ %.2f, quadratic exponent ~ %.2f%n", lin, quad);
check(lin > 0.5 && lin < 1.6, "linear exponent out of band: " + lin);
check(quad > 1.5 && quad < 2.6, "quadratic exponent out of band: " + quad);
System.out.println("complexity harness ok");
}
}
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <functional>
static volatile std::int64_t sink = 0; // keeps the optimiser from discarding the work
// Minimum wall time over `repeats` runs, in seconds.
double bestOf(const std::function<std::int64_t(std::int64_t)>& fn, std::int64_t n, int repeats) {
double best = 1e300;
for (int r = 0; r < repeats; ++r) {
auto t0 = std::chrono::steady_clock::now();
sink += fn(n);
double dt = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();
if (dt < best) best = dt;
}
return best;
}
// Estimate b in T(n) ~ c * n^b from timings at n0 and 4n0.
double growthExponent(const std::function<std::int64_t(std::int64_t)>& fn, std::int64_t n0) {
sink += fn(n0); // warm-up (page faults, caches)
double t1 = bestOf(fn, n0, 7);
double t4 = bestOf(fn, 4 * n0, 7);
return std::log2(t4 / t1) / 2;
}
std::int64_t linearWork(std::int64_t n) {
std::int64_t total = 0;
for (std::int64_t i = 0; i < n; ++i) total += (i & 7) + (sink & 1); // read sink: no closed form
return total;
}
std::int64_t quadraticWork(std::int64_t n) {
std::int64_t count = 0;
for (std::int64_t i = 0; i < n; ++i)
for (std::int64_t j = i + 1; j < n; ++j)
if (((i ^ j) & 3) == 0) ++count;
return count;
}
int main() {
double lin = growthExponent(linearWork, 8'000'000);
double quad = growthExponent(quadraticWork, 4'000);
std::printf("linear exponent ~ %.2f, quadratic exponent ~ %.2f\n", lin, quad);
if (!(lin > 0.5 && lin < 1.6)) { std::printf("linear exponent out of band\n"); return 1; }
if (!(quad > 1.5 && quad < 2.6)) { std::printf("quadratic exponent out of band\n"); return 1; }
std::printf("complexity harness ok\n");
return 0;
}
import assert from "node:assert/strict";
import { performance } from "node:perf_hooks";
let sink = 0; // keeps the JIT from discarding the work
/** Minimum wall time over `repeats` runs, in milliseconds. */
function bestOf(fn: (n: number) => number, n: number, repeats = 7): number {
let best = Infinity;
for (let r = 0; r < repeats; r++) {
const t0 = performance.now();
sink += fn(n);
best = Math.min(best, performance.now() - t0);
}
return best;
}
/** Estimate b in T(n) ~ c * n^b from timings at n0 and 4n0, after warming up the JIT. */
function growthExponent(fn: (n: number) => number, n0: number): number {
for (let i = 0; i < 5; i++) sink += fn(n0); // warm-up
const t1 = bestOf(fn, n0);
const t4 = bestOf(fn, 4 * n0);
return Math.log2(t4 / t1) / 2;
}
function linearWork(n: number): number {
let total = 0;
for (let i = 0; i < n; i++) total += i & 7;
return total;
}
function quadraticWork(n: number): number {
let count = 0;
for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (((i ^ j) & 3) === 0) count++;
return count;
}
const lin = growthExponent(linearWork, 4_000_000);
const quad = growthExponent(quadraticWork, 3_000);
console.log(`linear exponent ~ ${lin.toFixed(2)}, quadratic exponent ~ ${quad.toFixed(2)}`);
assert.ok(lin > 0.5 && lin < 1.6, `linear exponent out of band: ${lin}`);
assert.ok(quad > 1.5 && quad < 2.6, `quadratic exponent out of band: ${quad}`);
assert.ok(sink !== 0);
console.log("complexity harness ok");
An function measures around 1.1 to 1.2 at these sizes, which is distinguishable from both 1 and 2. If a function you believe is linear measures 1.4 or higher, the usual causes are cache misses once the data stops fitting in L2 (see How Data Structures Live in Memory), allocation inside the loop, or a hidden operation such as list.insert(0, x) or string concatenation in a loop.
Debugging techniques
When a test fails, you have an input and a wrong output. These are the moves, roughly in the order to try them.
Reproduce with the smallest input. Shrink first (by hand or with the harness). Every other technique is ten times faster on three elements than on three hundred.
Print the state table. Add one print per loop iteration, printing every state variable, and lay the output out as a table. This is exactly the trace table that every lesson in this course includes, produced by the code instead of by hand. Then compute the same table by hand from the algorithm's description and find the first row where they differ. That row is the bug, and the column that differs is the variable.
Check the base case first. For recursion: call the function directly on the smallest input. For loops: check the state before the first iteration (initial values) and after the first iteration. Half of all algorithm bugs are in initialisation (best = 0 instead of best = a[0], lo = 1 instead of lo = 0, an empty heap when the first element should already be in it).
Re-derive the invariant. Write down what should be true at the top of the loop. Add it as an assertion. Run. The assertion fails at the first iteration where the code departs from the proof, which is far earlier and far more informative than the wrong final answer.
Binary-search the bug with assertions. In a long function, place an assertion halfway through that checks the intermediate state; if it passes, the bug is in the second half, otherwise the first. Repeat. This is assertions to find the line, and it works on a 200-line solution where reading does not.
Rubber duck. Explain the code, line by line, to someone or something that cannot help. The act of translating code into sentences forces you to state what each line is for, and the line whose purpose you cannot state is the one that is wrong. In an interview the interviewer is the duck, and talking through the code is both debugging and communication.
Suspect the comparison operators. When the answer is off by one, or wrong only on duplicates or only on touching intervals, the bug is a < that should be <= or the reverse. Find every comparison in the function and ask for each: what happens when the two sides are equal?
Suspect the data, then change one thing. Print the input as parsed (1-based indices, a trailing newline, edges added in one direction only: many "algorithm bugs" are input bugs). Then make one hypothesis, one change, one rerun. Changing two things and seeing the test pass tells you nothing about which one mattered.
Common bug catalogue, with fixes
| Bug | Symptom | Fix |
|---|---|---|
(lo + hi) / 2 overflows in C++, Java and C | Wrong mid, often negative, on arrays over elements or on value ranges near INT_MAX when binary searching on the answer | lo + (hi - lo) / 2, or (lo + hi) >>> 1 in Java (unsigned shift) |
best = 0 initialisation in a maximisation | Returns 0 on all-negative input | Initialise with the first element, or with -infinity |
| Mutating a collection while iterating over it | Skipped elements, ConcurrentModificationException in Java, undefined behaviour in C++, silently wrong in Python | Iterate over a copy, collect changes then apply, or iterate by index backwards when removing |
| Shallow copy of nested structure | Modifying a "copy" changes the original; a DP table of rows that are all the same list ([[0]*m]*n in Python) | [[0]*m for _ in range(n)]; copy.deepcopy; in JS structuredClone or map per row |
| Floating-point equality | 0.1 + 0.2 == 0.3 is false; a geometry test fails on one input in a million | Compare with a tolerance, or compute in integers (scale by , cross-multiply fractions) |
| Recursion without a visited set on a graph with cycles | Stack overflow or infinite loop on the first cyclic input | Mark visited before recursing; for DP on a DAG, memoise |
| Inconsistent comparator | Sort produces garbage, or throws "Comparison method violates its general contract" in Java | Make the comparator a strict weak ordering: antisymmetric, transitive, cmp(a, a) == 0; never compare by subtraction of large ints (overflow) |
| Stale cache or memo key | Memoised function returns the answer for a previous call with a different hidden parameter | Include every parameter that affects the result in the key; clear the memo between test cases |
| 1-based input, 0-based arrays | Off by one everywhere; a[n] out of bounds | Subtract 1 at the input boundary and nowhere else, or allocate n + 1 and ignore index 0 consistently |
| Modulo of a negative number | -7 % 3 is 2 in Python but -1 in C++, Java and JavaScript | ((x % m) + m) % m in the C-family languages; in Python it is already non-negative for positive m |
| Integer overflow in a sum or product | Wrong answer only on large inputs; negative total from positive numbers | Use 64-bit (long, long long, Python is arbitrary precision; JavaScript needs BigInt beyond ) |
| Reusing a global between test cases | First test passes, second fails | Reset every mutable global, or avoid globals |
while (lo < hi) with lo = mid | Infinite loop when hi == lo + 1 | Round mid up, or use lo = mid + 1 with the predicate inverted |
| Returning the index instead of the value, or the length instead of the index | Right algorithm, wrong answer on every test | Re-read step 1 of the method; add a postcondition assertion on the return type and range |
Language-specific traps
Python. The default recursion limit is 1,000 frames (sys.setrecursionlimit raises it, but the C stack can still overflow at a few tens of thousands; convert deep recursion to iteration). A default argument is evaluated once: def f(x, memo={}) shares memo across all calls, which is a stale-cache bug waiting for the second test case; use None and create inside. [[0] * m] * n makes n references to one list. is compares identity, not value; == on floats has the usual problem. Integer division // floors toward negative infinity, so -7 // 2 == -4, which differs from every C-family language. Slicing never raises on out-of-range bounds, which hides index bugs.
Java. Integer division truncates toward zero (-7 / 2 == -3) and % takes the sign of the dividend. == on Integer objects compares references; it happens to work for values in because of the integer cache and fails above that, which is the textbook "works on small tests, fails on large" bug. Math.abs(Integer.MIN_VALUE) is negative. int overflow wraps silently; use long for sums and Math.multiplyExact when you want an exception. Arrays.sort(int[]) is a dual-pivot quicksort with a known adversary (Codeforces anti-Java-sort tests exist); sort Integer[] or a List (Timsort, guaranteed) when the input may be adversarial. assert is off by default. String concatenation in a loop is ; use StringBuilder.
C++. Signed integer overflow is undefined behaviour, so int sums that exceed do not reliably wrap; the optimiser may assume they never happen and delete your overflow check. Use long long or unsigned types for anything that might wrap, and compile tests with -fsanitize=undefined,address. Uninitialised local variables hold garbage, not zero: int best; followed by best = max(best, x) is a bug that passes on your machine and fails on the judge. Iterators and references into a std::vector are invalidated by push_back when it reallocates; iterating with an index is safe, iterating with a range-for while pushing is not. std::unordered_map with the default hash is attackable (see the adversarial section). std::sort with a comparator that is not a strict weak ordering (<= instead of <) is undefined behaviour and does crash in practice. Array indexing out of bounds does not throw; it reads adjacent memory and the program continues with a wrong answer.
JavaScript / TypeScript. [10, 9, 1].sort() gives [1, 10, 9] because the default comparator converts to strings; always pass (a, b) => a - b. == coerces (0 == "", "1" == 1); use ===. All numbers are doubles: integers are exact only up to , so products of two 32-bit values can lose precision; bitwise operators truncate to 32 bits ((1 << 31) is negative, 2**32 | 0 is 0). Use BigInt for anything that may exceed , and Math.trunc rather than | 0 for large values. Object keys are strings, so obj[1] and obj["1"] collide and obj[0.1 + 0.2] is the key "0.30000000000000004"; use Map for non-string keys and never use a float as a key. Array(n) creates holes, not zeros; new Array(n).fill(0) or Array.from({length: n}, () => 0). Default recursion depth is around 10,000 frames in V8 (it depends on frame size), lower than C++ and Java.
Real-world uses: where these techniques run in production
Fuzzing. Randomised stress testing with a crash-or-not oracle, at scale, is fuzzing. AFL (Zalewski, 2013), libFuzzer and Google's OSS-Fuzz project run generators against parsers, compressors, image decoders and cryptographic libraries around the clock and have found thousands of security bugs; the shrinking step is called "test case minimisation" there. The property being tested is usually just "does not crash or trip a sanitiser", which is why fuzzing finds memory-safety bugs rather than logic bugs.
Differential testing of compilers and databases. Csmith (Yang et al., PLDI 2011) generates random C programs and compares the output of different compilers or optimisation levels; it found over 300 bugs in GCC and LLVM. SQLite's test suite compares SQLite's results against other SQL engines on generated queries and is one of the reasons SQLite is trusted enough to ship in every phone; the project's "How SQLite Is Tested" document describes 100% branch coverage and billions of test cases per release. SQLancer applies the same idea to PostgreSQL, MySQL and others with properties such as "a query and its partition into three disjoint predicates return the same rows".
Jepsen. Kyle Kingsbury's Jepsen tests distributed databases by generating random concurrent operations, injecting network partitions, and checking the history against a consistency model using a checker (Knossos, Elle). It is property-based testing where the property is linearizability or snapshot isolation, and it has found consistency bugs in most major databases. The consensus and vector clocks pages describe the properties being checked.
Assertions and benchmarks in production. Storage engines check invariants such as log-sequence-number ordering on every write, because a silent violation means data loss; see Write-Ahead Logging. Performance-sensitive libraries run the complexity-ratio idea in CI and fail the build when the exponent moves; the benchmarks page covers stable measurement.
Pitfalls & edge cases of testing itself
- A weak generator. Large values and large sizes produce almost no boundary conditions. The Kadane bug appears in 5 iterations with values in and length up to 8, and essentially never with values in and length 1000.
- A broken generator. Low bits of an LCG cycle;
rand() % nis biased; a generator that never produces duplicates cannot find duplicate bugs. Test the generator: print 20 outputs and look at them. - Brute force shares the bug. Both implementations read the specification wrong (both treat touching intervals as overlapping when the problem says otherwise). Guard with hand-computed cases from the statement.
- Non-unique answers compared with equality. "Any valid order" or "any index of the target" will produce false mismatches. Write a validity checker instead of comparing outputs.
- Flaky timing tests. A complexity test with narrow bands fails randomly in CI. Use minimum-of-several, wide bands, and sizes large enough for milliseconds.
- Assertions with side effects, or assertions used as input validation, disappear in optimised builds along with their effects.
- Testing the brute force's performance. The brute force is for correctness on tiny inputs; never run it at full size.
- Stopping at the first passing run. A stress test is a permanent fixture, not a one-time ritual. Keep it in the test suite with its seed fixed; raise the iteration count when the code changes.
Variations
Mutation testing inverts the question: instead of asking whether tests find bugs, inject bugs (flip a < to <=, change a constant) and check that at least one test fails. A test suite that survives mutations is weak. Tools: mutmut and cosmic-ray (Python), PIT (Java), Stryker (JavaScript).
Metamorphic testing uses relations between outputs of related inputs when no oracle exists for a single input: shortest_path(g, s, t) <= shortest_path(g, s, u) + shortest_path(g, u, t); reversing the input array does not change the maximum subarray sum; adding a constant to every element adds it to the minimum.
Model checking and symbolic execution explore inputs exhaustively up to a bound instead of randomly. TLA+ for protocols, KLEE for C programs, bounded exhaustive testing (every array of length up to 6 over values : inputs) for algorithms. Exhaustive small-input testing is underused: for many algorithms, every input of size at most 6 over a 3-value alphabet is a complete test of every branch.
Snapshot (golden-file) testing records the output once and compares against it later: useful for regressions, useless for finding the first bug, since the golden file is whatever the code produced.
Practice ladder: problems famous for their edge cases
Each problem is easy to state and famous for the inputs it hides. Before coding, write the edge cases you expect from the checklist; after coding, run them and a stress test. The point is the testing, not the algorithm.
1. Plus One — carries
Plus One (LeetCode 66). Increment a number given as a digit array. Hides: a trailing 9 ([1,9]), all 9s ([9,9,9] grows the array), the single digit [9], and [0].
Hint
Walk from the right; if the digit is below 9, increment and return; otherwise set to 0 and continue. If you fall off the left end, prepend 1.
Solution
def plus_one(digits: list[int]) -> list[int]:
i = len(digits) - 1
while i >= 0:
if digits[i] < 9:
digits[i] += 1
return digits
digits[i] = 0
i -= 1
return [1] + digits # every digit was 9
assert plus_one([1, 2, 3]) == [1, 2, 4]
assert plus_one([1, 9]) == [2, 0]
assert plus_one([9]) == [1, 0]
assert plus_one([9, 9, 9]) == [1, 0, 0, 0]
assert plus_one([0]) == [1]
print("ok")
time, extra space except in the all-9s case. A differential test: compare against list(map(int, str(int("".join(map(str, d))) + 1))) on random digit arrays.
2. Sqrt(x) — binary search bounds and overflow
Sqrt(x) (LeetCode 69). Integer square root, rounded down. Hides: x = 0 and x = 1; mid * mid overflowing 32-bit for x near INT_MAX (use mid <= x / mid or 64-bit); the perfect square versus one below it (x = 16 vs x = 15); hi starting at x versus x / 2 + 1.
Hint
Find the largest m with m * m <= x. With while lo < hi and lo = mid on success, round mid up: mid = (lo + hi + 1) // 2. Differential-test against math.isqrt on every x up to a few thousand and on 2**31 - 1.
Solution
import math
def my_sqrt(x: int) -> int:
lo, hi = 0, x
while lo < hi: # invariant: answer in [lo, hi]
mid = (lo + hi + 1) // 2 # round up, because lo = mid below
if mid * mid <= x:
lo = mid
else:
hi = mid - 1
return lo
for x in list(range(0, 2000)) + [2147395599, 2147483647]:
assert my_sqrt(x) == math.isqrt(x), x
print("ok")
. In Java or C++, mid * mid must be long; in Python integers do not overflow, which is why the Python solution looks simpler than it is.
3. Reverse Integer — overflow without 64-bit
Reverse Integer (LeetCode 7). Reverse the digits of a signed 32-bit integer, returning 0 on overflow. Hides: the reversed value overflowing while the input does not (1534236469 → 9646324351 → 0), INT_MIN (whose negation overflows), trailing zeros (120 → 21), and negative numbers' % behaviour in C-family languages.
Hint
Build the result digit by digit; before each result = result * 10 + d, check result > INT_MAX // 10 (or equal with d > 7). Work on the absolute value only if you handle INT_MIN separately, or work with the sign carried through.
4. Merge Intervals — touching and nested
Merge Intervals (LeetCode 56). Hides: touching intervals ([1,4],[4,5] merge), nested ([1,10],[2,3]), an interval swallowing several, a single interval, and unsorted input. Property test: the output is sorted, non-overlapping, and covers exactly the same set of integer points as the input.
Hint
Sort by start; extend the last merged interval while the next start is at most its end (<= for touching). Compare against a brute force that marks covered points on a number line.
5. Search in Rotated Sorted Array — which half is sorted
Search in Rotated Sorted Array (LeetCode 33). Hides: no rotation at all, rotation by exactly one, arrays of size 1 and 2 ([3,1], [1,3]), the target at the pivot, and the comparison that decides which half is sorted when mid == lo.
Hint
At each step one of [lo, mid] and [mid, hi] is sorted; decide which with a[lo] <= a[mid] (the <= handles lo == mid), then check whether the target lies in the sorted half's value range.
Solution
def search_rotated(a: list[int], target: int) -> int:
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
if a[lo] <= a[mid]: # left half sorted (<= handles lo == mid)
if a[lo] <= target < a[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if a[mid] < target <= a[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 3) == -1
assert search_rotated([1], 0) == -1
assert search_rotated([1], 1) == 0
assert search_rotated([3, 1], 1) == 1
assert search_rotated([1, 3], 3) == 1
assert search_rotated([], 5) == -1
print("ok")
. Stress test this against a.index(target) if target in a else -1 over every rotation of range(1, n+1) for and every target in : that is exhaustive, not random, and takes a few milliseconds.
6. Find Minimum in Rotated Sorted Array II — duplicates defeat the sorted-half test
Find Minimum in Rotated Sorted Array II (LeetCode 154). Like the previous problem but with duplicates allowed. Hides: a[mid] == a[hi] gives no information about which half holds the minimum ([3,3,1,3] vs [1,3,3,3]), so the worst case is ; [2,2,2,0,1]; all equal.
Hint
Compare a[mid] to a[hi]: greater means the minimum is right of mid; smaller means it is at mid or left; equal means you can only discard hi itself (hi -= 1), which is safe because a[mid] still holds the same value.
Solution
def find_min_with_duplicates(a: list[int]) -> int:
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > a[hi]:
lo = mid + 1
elif a[mid] < a[hi]:
hi = mid
else:
hi -= 1 # a[hi] is duplicated at mid; dropping it loses nothing
return a[lo]
assert find_min_with_duplicates([2, 2, 2, 0, 1]) == 0
assert find_min_with_duplicates([1, 3, 5]) == 1
assert find_min_with_duplicates([3, 3, 1, 3]) == 1
assert find_min_with_duplicates([1, 1, 1]) == 1
assert find_min_with_duplicates([10, 1, 10, 10, 10]) == 1
print("ok")
average, worst case (all equal), and the worst case is unavoidable: with [1,1,1,1,0,1,1,1]-style inputs no comparison-based method can do better than linear.
7. String to Integer (atoi) — the parsing checklist
String to Integer (atoi) (LeetCode 8). Parse an integer the way C's atoi does. Hides: leading spaces but not other whitespace, a sign with no digits ("+"), a sign after spaces, digits followed by garbage ("1337c0d3"), garbage first ("words 987" → 0), "0-1", leading zeros, and clamping to the 32-bit range in both directions.
Hint
Skip spaces, read one optional sign, read digits while they are digits, clamp after each digit (not at the end: the intermediate value may already overflow in a fixed-width language). Differential-test against Python's int() on inputs that both accept.
8. Divide Two Integers — the overflow problem in full
Divide Two Integers (LeetCode 29). Integer division without *, / or %. Hides: INT_MIN / -1 overflows (clamp to INT_MAX), INT_MIN / 1, negative operands' truncation toward zero, and the doubling step overflowing when the divisor is large.
Hint
Work with negative numbers (the negative range is one larger) or with 64-bit intermediates; subtract the largest shifted multiple of the divisor repeatedly. Test every combination of {INT_MIN, -1, 0, 1, INT_MAX} as dividend and divisor (excluding division by zero).
9. Valid Number — the state machine nobody gets right first time
Valid Number (LeetCode 65). Decide whether a string is a valid decimal or scientific-notation number. Hides: ".", ".1", "1.", "1e", "e1", "1e1.5", "+.8", "-", " 1", "1 ", "1e+5", "46.e3". It is the canonical argument for writing a state machine (or a grammar) instead of a chain of ifs, and for exhaustive testing over all strings of length at most 4 over the alphabet {1, ., e, +, -}: strings, which you can check against a reference regular expression.
Hint
Grammar: [sign] (digits [. [digits]] | . digits) [e [sign] digits]. Implement it as a DFA with states {start, sign, integer, dot-after-int, dot-no-int, fraction, e, e-sign, exponent}; the accepting states are integer, dot-after-int, fraction, exponent.
10. Median of Two Sorted Arrays — partition boundaries
Median of Two Sorted Arrays (LeetCode 4). Median of the merge of two sorted arrays in . Hides: one array empty, both of size 1, all of one array smaller than all of the other, even versus odd total length, duplicates across arrays, and the partition index landing at 0 or at the array's length (sentinels of ). Stress-test against sorted(a + b) with the median computed directly; with sizes up to 5 and values in the test is close to exhaustive.
Hint
Binary search the partition of the shorter array; the longer array's partition follows from the total. The partition is correct when every element left of both partitions is at most every element right of both. Use sentinels so that empty sides compare correctly.
Common mistakes & interview follow-ups
"How would you test this?" The expected answer has structure, not a list of random cases. "First the provided examples. Then the boundary cases for this input type: empty, one element, two elements, all equal, the answer at index 0 and at the end, k = 0 and k = n. Then I'd write the brute force, which I already described, and compare the two on a few thousand small random arrays. If I had a failing case I'd shrink it and trace it." Saying "I'd write unit tests" is not an answer.
"What edge case would break your solution?" Have one ready, and have the fix ready. If you cannot name an input your code mishandles, you have not thought about your code hard enough; if you can and have handled it, say so.
"Your code returns the wrong answer on this input." Do not start editing. Trace the input through the code, out loud, one state table row at a time, until the first row that disagrees with what the algorithm should do. Then change one thing. Interviewers plant a failing case to see whether you debug systematically or thrash.
"How confident are you that it is correct?" Give the argument: the invariant, why each step preserves it, and which tests you ran. "I tested it on three examples" is a low-confidence answer; "the loop maintains that the window has at most k distinct characters, each index enters and leaves once, and I traced the example where the window must shrink twice" is a high-confidence one.
"What would you do if this had to run on a billion elements?" Mention the performance test: measure at , , to confirm the complexity class before scaling, then look at constants, memory and whether the data fits in RAM.
Common mistakes: testing only the happy path; writing the brute force at full size and waiting; a generator with huge values that never produce boundaries; comparing outputs with equality when any valid answer is acceptable; "fixing" a bug by special-casing the failing input rather than finding the invariant it violated; and declaring that a test passing once means the code is correct.
Quick quiz
1. A stress test runs 100 iterations and passes. The bug triggers on 1% of generated inputs. How likely is it that the test missed it?
Answer
, so roughly a 37% chance. Run thousands of iterations, not hundreds; small inputs make each iteration essentially free.
2. Why does the complexity harness take the minimum of several runs instead of the mean?
Answer
Timing noise (GC, other processes, frequency scaling) only ever adds time. The minimum is the run with the least noise and the best estimate of the true cost; the mean is biased upward by the noise.
3. while (lo < hi) { mid = (lo + hi) / 2; if (ok(mid)) lo = mid; else hi = mid - 1; }. What is wrong?
Answer
When hi == lo + 1, mid == lo, and if ok(mid) holds then lo = mid changes nothing: infinite loop. Round up, mid = lo + (hi - lo + 1) / 2, or restructure as hi = mid / lo = mid + 1 with the predicate inverted.
4. Your Kadane passes 10,000 random iterations with values in and length 1,000. Is it correct on all-negative arrays?
Answer
Unknown. The chance a random array of 1,000 values in that range is all-negative is ; the generator never produced the case. Shrink the generator's size and value range, and add the all-negative case to the checklist explicitly.
5. Name the single most useful assertion to add to a loop when debugging.
Answer
The loop invariant, at the top of the body. It fails at the first iteration where the code departs from the proof, which localises the bug to one step and one variable.
Further reading / sources
- Koen Claessen and John Hughes, "QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs", ICFP 2000. The origin of property-based testing.
- Andreas Zeller and Ralf Hildebrandt, "Simplifying and Isolating Failure-Inducing Input", IEEE Transactions on Software Engineering 28(2), 2002. Delta debugging; the shrinking recipe formalised.
- Andreas Zeller, Why Programs Fail: A Guide to Systematic Debugging, 2nd ed. (Morgan Kaufmann, 2009). The scientific method applied to debugging.
- Joshua Bloch, "Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken", Google Research blog, 2006. The
(low + high) / 2overflow. - M. Douglas McIlroy, "A Killer Adversary for Quicksort", Software: Practice and Experience 29(4), 1999.
- Xuejun Yang, Yang Chen, Eric Eide, John Regehr, "Finding and Understanding Bugs in C Compilers", PLDI 2011 (Csmith).
- D. Richard Hipp, "How SQLite Is Tested", sqlite.org.
- Hypothesis documentation, jqwik, fast-check, RapidCheck.
- Codeforces blog, "Blowing up unordered_map, and how to stop getting hacked on it" (neal, 2018), for anti-hash tests.
- CLRS, 4th ed., Section 2.1 (loop invariants) and Problem 2-4; Jon Bentley, Programming Pearls, 2nd ed., Column 4 ("Writing Correct Programs") and Column 5 ("A Small Matter of Programming"), which test binary search exactly the way this page recommends.
Previous lesson: How to Solve Any Problem: The Method · Next lesson: Capstone: Benchmark Your Language · Module: Foundations · Course: DSA: Zero to Mastery
Related: Complexity Analysis · Recursion & Induction · Your Language's Data Structures · Hash Tables · Sorting & Searching · Benchmarks