Why "it passes the samples" proves so little
Generated code tends to look like a solution and to handle the examples in the prompt, because those are what it was given. What it handles less reliably are the cases nobody wrote down, and the cost of operations hidden inside convenient calls. An interviewer who asks for complexity and a breaking input is checking whether you can audit code rather than accept it.
Here is a typical answer to "merge overlapping intervals", which passes the four-interval sample in most problem statements.
def merge(intervals):
intervals.sort()
merged = []
while intervals:
start, end = intervals.pop(0)
if merged and start <= merged[-1][1]:
merged[-1][1] = end
else:
merged.append([start, end])
return merged
Reading the structure, then pricing each line
Complexity analysis starts with the shape: one sort, then one loop that runs n times. That reads as O(n log n), and a candidate who stops there has been fooled by the structure.
Now price each line inside the loop. intervals.pop(0) removes the first element of a Python list, which shifts every remaining element down one place. The Python documentation says it directly: lists incur O(n) memory movement for pop(0) and insert(0, v). Across the loop that is (n − 1) + (n − 2) + … + 1, about n²/2 moves. The real bound is O(n²). At 100,000 intervals that is roughly five billion element moves, from a line that looks like a cheap dequeue.
The same habit catches a family of hidden costs that recur in generated code.
| Line inside a loop | Real cost per call | Typical fix |
|---|
Python lst.pop(0) or lst.insert(0, x) | O(n) shift | collections.deque, or iterate instead |
x in lst, lst.remove(x), lst.index(x) | O(n) scan | A set or dict alongside the list |
s += piece on strings | Copies the string built so far | "".join(parts); PEP 8 advises against relying on in-place concatenation |
Slicing a[1:] in a recursive call | O(n) copy per level | Pass an index |
sorted(...) inside the loop | O(n log n) per iteration | Sort once, or keep a heap |
Java list.get(i) on a LinkedList | O(i) walk | Iterate, or use ArrayList |
Java String += in a loop | Copies all characters so far | StringBuilder |
"Breaks" has two meanings, and a strong answer offers both. Complexity analysis gives you the first; reading for missing cases gives you the second. The performance break targets the cost you found: the worst case for pop(0) is simply the largest allowed n, since every iteration shifts the whole remaining list whether or not anything merges. Name the size where the quadratic term starts to dominate the time limit.
The correctness break comes from asking what the samples did not contain. They had overlapping neighbours, but no interval inside another. Try [[1, 10], [2, 3]]. The second interval starts inside the first, so the code overwrites the end with 3 and returns [[1, 3]], losing most of the first interval. The fix is max(merged[-1][1], end). Then run through the edges a worst-case-minded tester always checks: an empty list, one interval, duplicates, touching intervals such as [1, 2] and [2, 3], and negative coordinates.
There is a third finding a careful reader adds. The function sorts and empties the caller's list. After merge(meetings), meetings is []. That breaks any caller that uses its input again.
def merge(intervals):
merged = []
for start, end in sorted(intervals):
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-][], end)
:
merged.append([start, end])
merged
Checking against a slow oracle
Reading finds the bugs you can imagine. A randomised comparison finds the ones you cannot, and it checks correctness while your complexity analysis checks cost, so you want both. Write a deliberately naive version that repeatedly merges any two overlapping intervals until nothing changes, so it is too simple to be wrong, and compare the two on many small inputs.
import random
for _ in range():
= [(random.sample((), )) _ (random.randint(, ))]
merge([iv[:] iv ]) == merge_slow(),
Small ranges matter more than large ones here, because they make collisions, nesting and touching intervals common. Against the original version this assertion fires within the first few dozen cases, and it hands you a concrete breaking input to show the interviewer. The copy in the call is itself a lesson: a test harness that shares mutable input with the code under test can report the wrong failure. Note what the generator never produces, here zero-length intervals such as [4, 4], and test those by hand.
Trusting the loop count over the line cost
The answer that loses marks counts loops, announces O(n log n), and offers "a very large input" as the breaking case. It reads the structure the assistant chose and never asks what each call costs, or which shapes of input the samples left out. Worst-case reasoning is about the operation and the input together.
What scores is the specific chain: this line, this documented cost, this total, this input that triggers it, and a separate input that returns a wrong answer. That is complexity analysis applied as an audit, and it is the same skill whether a colleague, a library or an assistant wrote the code. When the bound you claim needs defending against a doubting interviewer, defending an amortised bound covers that argument.
Price every line inside the loop, not just the loop. Then aim one input at the cost you found and another at the case the samples never showed.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).