Skip to content
Tech Interview Prep

Top 100 Software Engineer Interview Questions and Answers

The questions most likely to come up in your Software Engineer interview, ranked by likelihood, with senior-level answers that cover what the interviewer is listening for.

Curated: · Written: · Reviewed:

Reviewed 100Review pending 5

105 questions

Q&A-1You said lookup is O(1). For which hash-map implementation and input is that false, and what bound do you quote in an interview?

The short answer. O(1) is the expected cost, not a guarantee. In an interview I quote: expected O(1) per get/put under uniform hashing and a bounded load factor; worst case O(n) for any chaining or open-addressing table when every key lands in one slot; O(log n) worst case for Java 8+ HashMap once a bin treeifies. If pushed for one number, it is "O(1) expected, O(n) worst case", and I name the implementation I mean.

Where it is false.

  • Adversarial keys with identical hashes. Any table whose hash is deterministic and public is vulnerable. Java's String.hashCode() is specified in the Javadoc, so an attacker can precompute colliding HTTP parameter names offline.
  • A poor hashCode/Hash. A class returning a constant, or hashing only a low-entropy field, turns every lookup into a linear scan.
  • Load factor driven to 1.0 with no resize, or a resize policy that never fires.

Implementation table.

ImplementationCollision strategyDefault load factorWorst-case get
Java 8+ HashMapchain → red-black tree at 8 entries/bin (capacity ≥ 64)0.75O(log n)
Java 7 HashMaplinked chain0.75O(n)
C++ std::unordered_maplinked chain1.0O(n)
Python dictopen addressing, perturbed proberesizes at 2/3 fullO(n)
Go map8-slot buckets + overflow buckets6.5 entries/bucketO(n)
Rust HashMap (hashbrown)SwissTable open addressing7/8O(n)

Only Java 8+ escapes the linear worst case, and only when the bin actually treeifies.

A degenerate key, and the arithmetic.

// Java 17: every key lands in one bin
class Key {
    final String id;
    Key(String id) { this.id = id; }
    @Override public int hashCode() { return 42; }   // constant
    @Override public boolean equals(Object o) {
        return o instanceof Key && ((Key) o).id.equals(id);
    }
}

Insert 10^6 such keys. Java 7 get walks the chain: up to 10^6 equals() calls. Java 8+ builds a red-black tree in that bin, so get is ⌈log2(10^6)⌉ = 20 comparisons. Same input, roughly 50,000× fewer comparisons: that gap is the entire reason treeification exists.

A real incident. oCERT advisory 2011-003 (CVE-2011-4858 and siblings): attackers sent POST bodies full of colliding form-parameter names and pinned server CPUs across Java, PHP, Python and Ruby. Java's first response was -Djdk.map.althashing.threshold in 7u6, then tree bins in Java 8. Python enabled hash randomization by default in 3.3 and moved to SipHash in 3.4 (PEP 456).

Detection. Track p99 get latency against table size: a healthy table's p99 stays flat as n grows, a degenerate one grows linearly. If you can instrument it, histogram bin lengths: a single bin holding a large fraction of entries is the signature.

What I quote. "Expected O(1) under uniform hashing and a load factor around 0.75; worst case O(n) for chaining and open addressing; Java 8+ HashMap is O(log n) worst case because bins treeify at 8 entries. put is amortized O(1) because of resizing; get is expected O(1)." I would not claim flat O(1) without naming the implementation and the input distribution it assumes.

Curated: · Written: · Reviewed:

Q&A-2Two-sum on an unsorted array of n=10^6 integers: why is a nested loop the wrong first answer, and how do you still return indices?

What I'd say first

Clarify three things: is there exactly one valid pair, or should I return the first one found? Can an element be used twice: is [3,3] with target 6 a valid answer? And is O(n) extra memory acceptable, or is this a memory-constrained path?

Assuming one pair, distinct indices, extra memory allowed: one pass with a hash map from value to index, O(n) expected time, O(n) space. The nested loop isn't the slow version of the same idea: at n=10^6 it doesn't run.

Why the nested loop is the wrong first answer

The inner loop does about n²/2 = 5×10^11 pair checks at n=10^6. A CPython iteration with an index, a subtraction and a comparison costs roughly 100 ns, so that's ~5×10^4 seconds: over 13 hours. Even in C at ~1 ns per check it's ~500 s. The constraint n=10^6 is the question: it rules out anything quadratic before you write a line.

For calibration, the same arithmetic at n=2×10^5 gives ~2×10^10 checks, ~30 minutes in CPython, while the map pass is ~2×10^5 dict operations: tens of milliseconds. (Both are estimates from the per-iteration cost above, not measurements.)

The one-pass map

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:           # lookup before insert
            return [seen[need], i]
        seen[x] = i
    return []                      # no pair

Insert after the lookup. Insert first and [3,3] target 6 returns [0,0].

Trace on [2,7,11,15], target 9:

  • i=0, x=2, need=7, not in seen → seen={2:0}
  • i=1, x=7, need=2, in seen → return [0,1]

Trace on [3,3], target 6:

  • i=0, x=3, need=3, not in seen → seen={3:0}
  • i=1, x=3, need=3, in seen → return [0,1]

Alternatives and when they win

Sort a list of (value, index) pairs, then walk two pointers from both ends: O(n log n) time, O(n) space, and the original indices survive because the index travels with the value. That's the right answer when the array is already sorted (then O(1) extra space, no map) or when you need all pairs. The map wins on the unsorted single-pair case: one pass, O(n).

Failure modes

  • Adversarial hash collisions degrade the map to O(n²). Not a practical concern for int keys in CPython; it is real for attacker-controlled string keys in a hand-rolled table.
  • Memory: 10^6 entries in a CPython dict is tens of megabytes. The table plus one int object per stored index. Check sys.getsizeof against your budget; if it's over, sort in place and two-pointer.
  • Multiple pairs: the map returns the pair with the smallest second index, not the smallest first index. State which one you're returning.
  • No pair: return [] or raise. Decide before the interviewer asks.

Curated: · Written: · Reviewed:

Q&A-69You rely on dict.keys() matching insertion order in Python 3.11. When was that guaranteed, and what still does not preserve order?

Core answer. dict preserves insertion order as a language guarantee from Python 3.7. CPython 3.6 already did it, but only as an implementation detail of the new compact dict, so code that relied on it was relying on CPython, not on Python. The mechanism is the compact layout: a sparse index table (power-of-two, ~2/3 load) mapping hash slots to positions, plus a dense array of entries appended in insertion order. Lookups probe the sparse table and jump into the dense array; iteration just walks the dense array front to back. That is why order is free: it falls out of the storage layout rather than being tracked separately.

Sets do not get this. CPython's set uses a single open-addressed table of (hash, key) entries with no dense array, so iteration order is the probe order, which depends on the hash values and the table size. With hash randomization on (the default for str/bytes), that order changes between runs. Giving sets insertion order would mean adding the same dense-array split, costing memory and slowing the common case, and set algebra (|, &, -) produces new sets whose order is meaningless anyway, so the language never promised it.

What is ordered and what is not.

TypeIteration order
dict (3.7+), defaultdict, Counterinsertion
dict.keys() / .values() / .items() viewsinsertion (live view)
OrderedDictinsertion + move_to_end
set, frozensethash/probe order, varies with PYTHONHASHSEED
result of set(d) or `d.keys()other`

Two behaviours people get wrong. Updating an existing key keeps its position; deleting and re-inserting moves it to the end:

d = {'a': 1, 'b': 2, 'c': 3}
d['a'] = 99          # update in place
print(list(d))       # ['a', 'b', 'c']
del d['b']
d['b'] = 2           # re-insert -> appended
print(list(d))       # ['a', 'c', 'b']

And a set that looks ordered is a trap: small ints hash to themselves and land in a small table in a stable-looking order, but list({'a','b','c'}) can print a different order on two runs of the same script with randomization on. Detect it by running the same script under PYTHONHASHSEED=0 and PYTHONHASHSEED=1 and diffing the output.

When OrderedDict is actually worth it. Plain dict is smaller and faster, and since 3.8 reversed(d) works on it, so you do not need OrderedDict just to iterate backwards. Choose OrderedDict when you need move_to_end(key, last=False) to push an entry to the front, popitem(last=False) for FIFO eviction, or order-sensitive equality: OrderedDict(a=1, b=2) != OrderedDict(b=2, a=1), whereas the equivalent plain dicts compare equal. It is a dict subclass with an extra doubly-linked list, so it costs more memory per entry; if you only need insertion order, use dict.

Failure modes. Relying on set order for deterministic output or test assertions is the classic flake: it passes locally and fails on a shard with a different seed. Assuming JSON object order is portable is the other: json.dumps emits keys in dict order, but the JSON spec treats objects as unordered, so a consumer is free to reorder them. And assuming order survives a round trip through set(d) or sorted(d) is wrong: both return a different type with different ordering rules.

Curated: · Written: · Reviewed:

Q&A-68A queue does pop(0) on a Python list a million times. What is the complexity, and which collections type is O(1) at both ends?

Short answer. list.pop(0) is O(n) per call, so a million of them is O(n²). collections.deque gives O(1) appendleft/popleft and O(1) append/pop, so a million pops is O(n). Use deque for a FIFO queue; keep list for a stack (append/pop at the right, amortized O(1)).

Why. A CPython list is a contiguous array of PyObject* pointers with spare capacity at the tail. pop(0) has to memmove every remaining pointer down one slot, then decref the removed object, so the cost is proportional to the number of elements still in the list. insert(0, x) pays the same shift. deque is a doubly-linked list of fixed-size blocks (64 pointers per block in CPython); popleft advances an index inside the leftmost block and frees the block when it empties. No element moves, so it is O(1) worst case, not amortized.

Arithmetic. Popping n elements from the front of a list moves 1 + 2 + ... + (n-1) = n(n-1)/2 pointers. For n = 10^6 that is ~5×10^11 pointer moves; at 8 bytes each, ~4 TB of memmove. The same n pops from a deque touch n pointers. That gap, not the constant factor, is why the list version falls over.

Operationlistdeque
append / pop (right)amortized O(1)O(1)
insert(0, x) / pop(0) (left)O(n)O(1)
index iO(1)O(n)
sliceO(k)not supported

Failure modes.

  • Indexing a deque is O(n): d[i] walks blocks from the nearer end. A loop that indexes a 10^6-element deque is O(n²) again: the same trap, moved.
  • deque has no slicing; use itertools.islice if you need a window.
  • deque(maxlen=N) silently drops from the opposite end once full. That is a ring buffer, useful for sliding windows, dangerous if you expected backpressure.
  • Memory: a deque of 10^6 small ints carries per-block overhead and pointer indirection; a list is more compact when you only need the right end.
# Python 3.12
from collections import deque

q = deque([1, 2, 3])
print(q.popleft())   # 1
print(q)             # deque([2, 3])

ring = deque(maxlen=3)
for i in range(5):
    ring.append(i)
print(ring)          # deque([2, 3, 4], maxlen=3)

Trace: popleft removes 1, leaving [2, 3]. The ring appends 0, 1, 2 to fill, then 3 evicts 0 and 4 evicts 1, leaving [2, 3, 4].

When not to use deque. If you need random access by index, a list (or array) is the right structure. If you need priority ordering, heapq. If you need a bounded buffer with backpressure, queue.Queue(maxsize=N) blocks producers instead of dropping.

Curated: · Written: · Reviewed:

Q&A-26You wrote "O(n) total" for a loop that does list.pop(0) n times in Python. What did you actually ship?

I shipped O(n²), not O(n). The loop runs n times, and each list.pop(0) is O(n), so the product is quadratic. The bound I wrote was wrong by a factor of n.

Why pop(0) is O(n)

A CPython list is a contiguous array of PyObject* pointers. pop(0) returns ob_item[0] and then memmoves the remaining n-1 pointers down one slot to close the gap. Nothing is O(1) about it except the return.

# CPython 3.12
xs = [1, 2, 3, 4]
while xs:
    xs.pop(0)

Trace, counting pointer moves:

callreturnspointers movedlist after
pop(0)13[2, 3, 4]
pop(0)22[3, 4]
pop(0)31[4]
pop(0)40[]

6 moves for n=4, i.e. n(n-1)/2. At n=10⁵ that is ≈5.0×10⁹ pointer moves; at 8 bytes per pointer on 64-bit CPython, ≈40 GB of memmove traffic. The loop is O(n²) time, O(1) auxiliary space: the cost is the shifting, not allocation.

What to ship instead

from collections import deque

q = deque(xs)
out = []
while q:
    out.append(q.popleft())   # O(1) amortized

deque is a doubly linked list of 64-pointer blocks. popleft bumps leftindex and frees a block only when it empties: no element ever moves. Same loop, O(n) total.

If the loop needs random access rather than FIFO order, walk an index over the list instead:

i = 0
while i < len(xs):
    x = xs[i]
    i += 1

O(n) total, no shifting, but the list stays fully alive and you cannot shrink it as you go.

Trade-offs: deque indexing q[k] is O(n) (it walks blocks), it has no slicing, and it carries block overhead on top of the pointers. If the loop indexes into the middle, the index walk wins; if it is a queue, deque wins.

Failure modes

  • Latency scales quadratically. 10× the input is 100× the time. A drain that takes ~4 s at 10⁵ elements takes ~400 s at 10⁶. Detect it by timing at n and 2n and checking the ratio is ≈4, not ≈2.
  • It passes CI. At n=1000 the loop does ~5×10⁵ moves, well under a millisecond. The bug ships and only appears on production-sized input.
  • Profiler misattribution. list.pop is a C builtin, so cProfile attributes the time to the list.pop call itself rather than a Python frame. The two-size ratio test is the reliable signal.

The same trap catches list.insert(0, x), x in list inside a loop, and s = s[1:] per character. Re-read every call in the loop body against the language's cost model, not the method name.

Curated: · Written: · Reviewed:

Q&A-25Appending n=10^6 items to a dynamic array: why is each append amortized O(1) if some appends copy 2^k elements?

Short answer. Amortized O(1) means the average cost over a sequence of appends is constant, not that every append is. Doubling makes the total copy work across n appends O(n), so each append carries O(1) of it on average. A single append that triggers a resize is still O(n) worst case.

Why the total is O(n). With capacity c and size c, a resize allocates 2c, copies c elements, then writes the new one. Starting from capacity 1, resizes happen at sizes 1, 2, 4, …, and the copies form a geometric series. For n = 10^6:

resizeelements copied
1 → 21
2 → 42
4 → 84
……
262144 → 524288262144
524288 → 1048576524288
total1048575

The last resize lands at 2^20 = 1048576 ≥ 10^6, and 1+2+…+524288 = 2^20 − 1 = 1048575. So 10^6 appends do about 1.05 × 10^6 element copies: roughly one copy per append. The accounting is the standard one: charge each append 3 units, spend 1 on the write and bank 2; the ~c/2 appends between resizes bank c units, which is exactly what the next resize's c-element copy costs.

The trade-off is growth factor vs memory slack. The copy total for growth factor g is (n−1)/(g−1), so ×2 costs ~n copies, ×1.5 costs ~2n, ×1.25 costs ~4n. Against that, the worst-case wasted capacity is (g−1)/g: ×2 leaves up to 50% slack, ×1.5 up to 33%, ×1.25 up to 20%. Real implementations pick different points on this curve: Java's ArrayList grows by 1.5× (oldCapacity + (oldCapacity >> 1)), and Go's runtime doubles below 256 elements then grows by about 1.25× above that. Both are still amortized O(1); they just trade more copying for less memory.

When doubling is the wrong choice. If the array is large enough that 50% slack is real memory, a multi-GB in-memory index, the smaller factor is worth the extra copies. If you know the final size, reserve it up front and skip growth entirely. And if a single resize pause is unacceptable (a latency-sensitive service holding a large buffer), doubling doesn't help: the resize itself is a synchronous O(n) copy. Preallocate, or use a chunked/deque structure that never copies.

Failure modes. The copy spike is the one to watch. At 10^6 8-byte elements the final resize copies 4 MB: sub-millisecond. At 10^9 elements it copies 4 GB, a pause of hundreds of milliseconds. You detect it as periodic latency spikes at power-of-two sizes, a p99 far above p50 in the append path. Linear growth is worse in a different way: growing by +16 copies ~n²/32 elements, so 3×10^5 appends move ~2.8×10^9 elements. Seconds instead of milliseconds.

Curated: · Written: · Reviewed:

Q&A-30Two User objects with the same id land in a set as two entries. What pair of methods did you implement wrong?

__eq__ and __hash__. A set finds an element in two steps: it hashes the object to pick a bucket, then compares with == against whatever is already in that bucket. Two Users with the same id end up as two entries when those two steps disagree: either the hashes differ so == is never called, or the hashes match and == returns False.

Assumptions: a plain Python 3 class, id is the identity you care about, and the objects are not mutated after insertion.

Two concrete ways to get this wrong.

Variant 1: __eq__ by id, hash left as identity:

class User:
    def __init__(self, id, email):
        self.id = id
        self.email = email
    def __eq__(self, other):
        return isinstance(other, User) and self.id == other.id
    __hash__ = object.__hash__          # identity hash — the bug

Trace:

a = User(7, "a@x.com")
b = User(7, "a@x.com")
a == b                # True
hash(a) == hash(b)    # False — distinct live objects, distinct identity hashes
len({a, b})           # 2

The set hashes a and b into different buckets, so it never compares them. Both stay.

Variant 2: hash by id, __eq__ left as identity:

class User:
    def __init__(self, id, email):
        self.id = id
        self.email = email
    def __hash__(self):
        return hash(self.id)
    # __eq__ inherited from object -> identity comparison

Now hash(a) == hash(b) is True, they land in the same bucket, the set probes with a == b, gets False, and stores both. Same symptom, opposite cause.

A third symptom worth naming: define __eq__ and forget __hash__ entirely and Python sets __hash__ = None, so {a, b} raises TypeError: unhashable type: 'User'. That is a different bug from the one asked about, but it is the same pair of methods.

The fix is to derive both from the same fields:

from dataclasses import dataclass

@dataclass(frozen=True)
class User:
    id: int
    email: str

frozen=True generates __eq__ and __hash__ from the same (id, email) tuple and blocks mutation. If only id should define identity, write both by hand on id alone, but then two users with the same id and different emails are the same element, which is usually what you want for a de-dupe set and usually not what you want for a cache key.

Failure modes and detection:

  • Mutation after insert. If id participates in the hash and you change it while the object is in a set, the object sits in the wrong bucket: u in s returns False and re-adding the same logical user creates a second entry. frozen=True turns this into a FrozenInstanceError at the mutation site.
  • Detection is a one-line invariant: assert len({User(7, "a"), User(7, "a")}) == 1, plus assert hash(x) == hash(y) whenever x == y. Property-based tests over random field values catch the field-mismatch case faster than hand-written cases.

If you actually want identity semantics, two objects are distinct even with the same id, do not define __eq__ at all, or key a dict by id explicitly. The bug is only a bug when the two methods disagree about what "same" means.

Curated: · Written: · Reviewed:

Q&A-81Why is {[1,2]: "a"} a TypeError, and what do you use for a composite key?

The 90-second answer

A dict is a hash table. Every insert, lookup and delete calls hash(key) to pick a bucket, then compares with == inside that bucket. So a key must be hashable, and its hash must not change while it sits in the dict. [1,2] fails the first test outright: in Python 3, list.__hash__ is None, so hash([1,2]) raises TypeError: unhashable type: 'list'. The literal {[1,2]: "a"} never gets as far as storing anything.

For a composite key, use a tuple of hashables, (user_id, org_id), or a frozenset when order must not matter.

Why the rule exists

The reason isn't "mutable is bad" as a slogan; it's the bucket invariant. A dict stores the key in the bucket its hash selected. If the hash changed after insertion, a later lookup would compute a different bucket, miss, and report the key absent even though it's there. Lists and dicts are mutable, so their contents can change and their hash would change with them. Rather than allow that, CPython sets __hash__ = None on list, dict and set, which makes hash() raise. Tuples and frozenset are immutable containers, so they keep a hash.

Trace:

hash((1, 2))        # an int; int hashes aren't randomized, so it's stable across runs
hash([1, 2])        # TypeError: unhashable type: 'list'
hash(({1},))        # TypeError: unhashable type: 'set'

The third line is the trap: a tuple is only hashable if every element is. ({1},) contains a set, so hashing recurses into it and fails. Same for (1, [2]).

Tuple vs frozenset

tuplefrozenset
ordersignificantignored
duplicateskeptcollapsed
equalitypositionalset equality
hashcached after first callrecomputed per call

Pick a tuple when position carries meaning: (user_id, org_id) is not the same key as (org_id, user_id). Pick a frozenset when you're keying on a collection of tags and {"a","b"} should hit the same entry as {"b","a"}. A tuple's hash is cached in CPython after the first computation, so a long tuple used as a key is cheap on repeat lookups; a frozenset recomputes each time.

When a composite key is the wrong tool

If you need to look up by one component alone, "all rows for this org", a composite key forces a full scan. That calls for a separate index or a normalized relation (a join table with its own key), not a fatter tuple. Composite keys also get expensive when the tuple is large or high-cardinality: hashing is O(n) in the tuple length on first use, and every distinct combination is a distinct entry, so memory grows with the cross product.

Failure modes

  • Nested mutables: (1, [2]) raises at insertion, not at definition. The error surfaces on the line that builds the dict.
  • Custom objects: a plain class inherits identity hash and equality, so two equal-looking instances are different keys. Define __hash__ and __eq__ together, or use a dataclass with frozen=True.
  • Mutating a key after insertion: if you subclass and expose a mutable field, the entry becomes unreachable. Lookups miss and the dict silently grows.

Curated: · Written: · Reviewed:

Q&A-72You put a dataclass instance in a set and then change a field. Why is frozen=True (or an identity hash) required?

Assume the field you change is one that participates in equality: by default every field does. The short answer: a set stores an object in the bucket its hash points to at insertion, and recomputes that hash on every lookup. Change a hashed field and the recomputed hash points at a different bucket, so the set never compares the stored entry against your object. Membership silently returns False, and re-adding creates a duplicate.

Mechanism. CPython's set is an open-addressed hash table. s.add(k) computes hash(k), masks it to a slot, and stores the reference there. k in s recomputes hash(k) from the object's current fields, probes that slot, and only then calls ==. If the hash moved, the probe lands on an empty or unrelated slot and the equality check never happens. No exception, no warning: the entry is orphaned in its old bucket.

The default dataclass cannot even get that far: @dataclass with eq=True (the default) and frozen=False sets __hash__ = None, so insertion raises immediately.

from dataclasses import dataclass

@dataclass
class Mutable:
    x: int

hash(Mutable(1))
# TypeError: unhashable type: 'Mutable'

frozen=True fixes both halves. It generates __hash__ from the field tuple (consistent with the generated __eq__, which compares the same tuple) and it makes assignment raise, so the hash cannot change while the object sits in the set.

@dataclass(frozen=True)
class Frozen:
    x: int

f = Frozen(1)
s = {f}
f.x = 2
# FrozenInstanceError: cannot assign to field 'x'

The failure it prevents, traced:

@dataclass(unsafe_hash=True)   # field hash on a mutable class
class Key:
    x: int

k = Key(1)
s = {k}
k in s        # True  -> hash((1,)) finds the bucket, k == k
k.x = 2
k in s        # False -> hash((2,)) probes a different bucket, no == call
len(s)        # 1     -> the entry is still there, just unreachable
s.add(k)
len(s)        # 2     -> same object stored twice

That is the ghost-bucket bug: unsafe_hash=True on a mutable class is the one combination to avoid.

The alternative, identity hash, is @dataclass(eq=False). It leaves __hash__ as object.__hash__ (id-based) and __eq__ as identity, so the hash is stable under mutation. The cost is that two instances with equal field values are now distinct set members, which is usually not what you want for a value type. Reach for it when you genuinely want reference semantics (a registry of live objects, say) not when you want value equality.

So: frozen when the object is a value and you want equal values to collapse; identity hash when you want reference identity; never unsafe_hash=True on something you mutate.

Curated: · Written: · Reviewed:

Q&A-75def f(items=[]): items.append(1). Why does the second call see [1,1], and what default do you write?

The 60-second answer. Default argument values are evaluated once, when the def statement executes, not on each call. The literal [] is created at definition time and stored in f.__defaults__. Every call that omits items receives that same object, so the first call's append is still there on the second. Write None as the sentinel and build a fresh list inside the body.

def f(items=[]):
    items.append(1)
    return items

f()             # [1]
f()             # [1, 1]   same list object
f.__defaults__  # ([1, 1],)

Trace it the way the interpreter runs it. The def line runs once: it creates list L and binds it to the default slot. Call 1: items is L, append(1) mutates it, returns [1]. Call 2: items is still L, append(1) mutates it again, returns [1, 1]. f.__defaults__[0] is L is True across both calls: there was never a second list.

The fix:

def g(items=None):
    if items is None:
        items = []
    items.append(1)
    return items

g()       # [1]
g()       # [1]   independent lists
g([5])    # [5, 1]

Same shape for dict and set defaults, and for dataclass fields, where the equivalent is field(default_factory=list).

Alternatives, and when the shared default is actually right. The None sentinel is the idiom, but it has one hole: if None is a legitimate value the caller may pass, you can't tell "not supplied" from "supplied as None." Then use a private sentinel (_MISSING = object() at module scope, def g(items=_MISSING)) and test is _MISSING. A tuple default (items=()) sidesteps the bug because tuples are immutable, but it forces a copy on every call and only works if you never mutate in place; it's a poor fit for an accumulator. A factory callable passed as the default is the dataclass answer, not a plain-function one.

The shared mutable default is not always a bug. It is the point when you want state to persist across calls: memoization:

def fib(n, _cache={0: 0, 1: 1}):
    if n not in _cache:
        _cache[n] = fib(n - 1) + fib(n - 2)
    return _cache[n]

Here the shared dict is the cache; a per-call list would defeat it. The rule is intent: shared state you asked for is fine, shared state you forgot about is the bug.

Detecting it. A test that calls f() twice and asserts f() == [1] both times catches it; so does asserting f.__defaults__[0] is unchanged after a call. The failure mode in production is quiet accumulation: a handler that defaults filters=[] and appends a request-scoped value will leak that value into every later request on the same process, which is how cross-tenant data shows up in a response body rather than in a stack trace.

Curated: · Written: · Reviewed:

Q&A-76Why can x is 256 be True and x is 257 be False for x=int("257") in CPython, and when do you use ==?

The premise doesn't hold. int("257") is 257, so x is 256 is False: no input to int() produces 256 from "257". The contrast that actually bites is 256 versus 257:

>>> x = int("256"); x is 256
True
>>> y = int("257"); y is 257
False
>>> y == 257
True

Why. is compares object identity: the pointer, not the value. CPython keeps a preallocated array of PyLong objects for -5 through 256 and hands back the cached one from int() and from literals in that range. int("256") returns that shared object, so identity holds. int("257") is outside the cache, so CPython allocates a fresh PyLong; a second 257 is a different object and is is False even though == is True. The -5..256 cache is documented in the CPython data model as an implementation detail, not a language guarantee: PyPy, or a CPython build with the cache disabled, can differ.

expressionresultwhy
int("256") is 256Trueboth hit the small-int cache
int("257") is 257Falsefresh PyLong each call
int("257") == 257Truevalue equality
int("257") is int("257")Falsetwo separate allocations

When to use ==. Compare values with ==, always. Reserve is for identity: x is None, x is True when you genuinely need the singleton, and module-level sentinels (MISSING = object()). For booleans, test truthiness (if flag:) and reach for == only when you must distinguish True from 1.

Failure mode. The classic bug is string interning: string literals that look like identifiers are interned at compile time, so token is "active" passes in a unit test written with literals and fails in production when the token arrives from json.loads or a DB driver as a fresh object. Detection: Python 3.8+ emits SyntaxWarning: "is" with a literal at compile time for x is "active" and x is 257; pylint's literal-comparison (R0123) flags the same pattern in CI. The test that catches it builds the value at runtime, json.loads('"active"') is "active" is False, rather than from a literal.

Curated: · Written: · Reviewed:

Q&A-40In a language with 32-bit ints, why is mid = (lo+hi)//2 a bug, and what do you write instead?

lo + hi is computed in 32-bit signed arithmetic before the division. If both indices are near the top of the array, the sum exceeds Integer.MAX_VALUE (2,147,483,647). Java wraps to a negative number; C and C++ signed overflow is undefined behavior. The resulting mid is negative, so a[mid] throws or the loop never narrows. Write mid = lo + (hi - lo) / 2 (or lo + ((hi - lo) >>> 1) in Java). For non-negative indices, hi - lo is at most Integer.MAX_VALUE, so it cannot overflow.

The midpoint is an offset from lo, not a sum that must fit. Algebraically, lo + (hi - lo) / 2 == (lo + hi) / 2 for integer division when hi >= lo. The subtraction is safe because hi >= lo and both are in [0, Integer.MAX_VALUE]. The division is safe because the numerator is non-negative and at most Integer.MAX_VALUE.

// bug: overflows when lo + hi > Integer.MAX_VALUE
int mid = (lo + hi) / 2;

// fix: hi - lo <= Integer.MAX_VALUE for non-negative indices
int mid = lo + (hi - lo) / 2;

Take lo = 1_073_741_824 and hi = 1_073_741_824. lo + hi = 2_147_483_648 = Integer.MAX_VALUE + 1. Java wraps to -2_147_483_648; / 2 gives -1_073_741_824. The safe form: hi - lo = 0, / 2 = 0, mid = 1_073_741_824. That is the correct midpoint.

Java's (lo + hi) >>> 1 also works for non-negative lo, hi because the unsigned sum fits in 32 bits (max 4,294,967,294 < 2^32). It is less portable and less obvious. Python's ints are unbounded, so (lo + hi) // 2 is not a bug there; the safe form is still what you write when the language is unspecified or when porting to Java/C++.

In Java, the wrapped negative mid throws ArrayIndexOutOfBoundsException on the next access. If the code clamps or ignores it, the search can loop forever or return a wrong index. In C/C++, signed overflow is UB; the compiler may assume it never happens and optimize the check away, so the bug can be silent. Detection: unit test with lo, hi near Integer.MAX_VALUE; assert lo <= mid < hi after each step; fuzz with large arrays. The fix is one line and costs nothing.

If lo can be negative (not typical for array indices), use a wider type or ensure hi - lo fits. For binary search on array indices, non-negative is the invariant.

Curated: · Written: · Reviewed:

Q&A-42You iterate a dict and delete keys that are stale. Why can CPython raise RuntimeError, and what do you iterate instead?

The iterator isn't watching the dict's contents; it's comparing a stamp. When you create iter(d), CPython records the dict's current version. Every __next__ re-reads that version and, if it differs, raises RuntimeError: dictionary changed size during iteration. Any mutation bumps the version: a delete, an insert, and (before 3.12) even d[k] = v on a key that already exists, which changes no size at all. The message is misleading: the check is "did anything change," not "did the size change."

So iterate something that isn't the live dict: snapshot the keys.

for k in list(d):          # snapshot of keys; safe to delete from d
    if stale(k):
        del d[k]

list(d) copies the keys into a new list; the loop walks that list while del mutates d. tuple(d) does the same with an immutable snapshot.

Trace

d = {'a': 1, 'b': 2, 'c': 3}
for k in d:
    if k == 'b':
        del d[k]
  • iter(d) is created and records version v0.
  • __next__ returns 'a'; version still v0; body does nothing.
  • __next__ returns 'b'; version still v0; body runs del d['b'], bumping the version to v1.
  • __next__ sees current version v1 ≠ v0 and raises RuntimeError: dictionary changed size during iteration.

The delete succeeds; the error fires on the next step, which is why the traceback points at the for line rather than the del.

Alternatives and when to pick each

ApproachExtra memoryPassesUse when
for k in list(d)O(n) key pointers1default; simple, single pass
collect keys, delete afterO(n)2you want the delete loop separate and auditable
rebuild via comprehensionO(n) new dict1most entries survive and you want a fresh object
tuple(d)O(n)1you want the snapshot immutable

The snapshot costs one pointer per key: 8 bytes each on 64-bit CPython, so a 1M-key dict spends roughly 8 MB on the list plus the list object overhead. Rebuilding allocates a whole new dict and breaks aliasing: any other reference to the old dict still sees the stale entries. If other code holds d, mutate in place; if you own it, rebuilding is often cleaner.

Failure modes

  • for k in d: d[k] = f(d[k]): before 3.12 this raises even though the size never changes, because the version bumped. In 3.12 the per-dict version tag was removed (PEP 699) and the iterator compares the used-entry count instead, so replacing an existing key's value no longer raises, while adding or removing keys still does. Don't lean on either behavior; snapshot.
  • Another thread mutating d while you iterate raises the same error. A snapshot stops the crash but not the race: you can delete a key another thread just re-added. If you need consistency, hold a lock across both the iteration and the mutation, not just the snapshot.
  • Catching the RuntimeError and retrying the whole loop can spin forever if the dict keeps changing.

Detection

The error is loud and immediate, so it surfaces in tests the first time the branch runs. The dangerous variant is the one that doesn't raise: a value-only update on 3.12+, where you silently iterate a dict whose values changed underneath you. A unit test asserting that for k in d: del d[k] raises, plus one asserting the snapshot rewrite completes, pins both.

Curated: · Written: · Reviewed:

Q&A-47lru_cache on a function that takes a list: why is the cache useless or an error, and what do you hash instead?

lru_cache never looks at your function body. The wrapper builds a key from the call's arguments, internally _make_key, and looks it up in a dict. A list has no __hash__, so the lookup raises TypeError: unhashable type: 'list' before your code runs. It is not a cache that misses; it is an error on every call.

What you hash instead is an immutable snapshot: tuple(nums) when order matters, tuple(sorted(nums)) only when the function is genuinely order-insensitive, frozenset(nums) when order and duplicates do not matter, a bitmask int for a small universe.

Trace it:

from functools import lru_cache

@lru_cache(maxsize=None)
def total(nums):
    return sum(nums)

total([1, 2, 3])

Calling total([1, 2, 3]) enters the wrapper, which hashes the argument tuple ([1, 2, 3],). hash([1, 2, 3]) raises TypeError: unhashable type: 'list'. The body never runs and no entry is stored. Swap the argument for a tuple and it works:

total((1, 2, 3))   # miss -> 6
total((1, 2, 3))   # hit  -> 6
total.cache_info() # CacheInfo(hits=1, misses=1, maxsize=None, currsize=1)

cache_info() returns CacheInfo(hits, misses, maxsize, currsize); maxsize defaults to 128, and maxsize=None means unbounded: no eviction, which is what you want for DP but is a memory leak if the key space is open-ended.

The key must also be complete. If the function reads anything not in the key (a mutable you closed over, a global, the current time) the cache returns a stale answer. And the key must match the function's semantics. tuple(sorted(nums)) is the classic trap:

@lru_cache(maxsize=None)
def is_sorted(nums):
    return all(a <= b for a, b in zip(nums, nums[1:]))

is_sorted((1, 3, 2))  # False
is_sorted((1, 2, 3))  # True

Keyed on tuple(sorted(nums)), both calls collapse to (1, 2, 3) and the second returns True for (1, 3, 2). Sorting is only safe when the function is a function of the multiset, not the sequence.

keycorrect whenbuild cost
tuple(nums)order mattersO(n) copy
tuple(sorted(nums))order-insensitiveO(n log n)
frozenset(nums)order and duplicates irrelevantO(n)
bitmask intsmall universe, membership onlyO(n)

Two more things bite. tuple(nums) is shallow: a list of lists becomes a tuple of lists, still unhashable. Convert recursively. And typed=False (the default) treats 1 and 1.0 as the same key because they hash and compare equal; pass typed=True if that distinction matters.

Finally, mutation: tuple(nums) snapshots the elements at call time, so mutating the caller's list afterwards does not corrupt the key, but if the function itself mutates the list, the cached result no longer matches the argument's later state. Cache pure functions.

Curated: · Written: · Reviewed:

Q&A-33LRU of capacity 1024: why is a dict of keys to doubly-linked nodes O(1), and what becomes O(n) if you use a Python list as the recency order?

Assumptions: single-threaded (or the cache sits behind a lock), keys hash in expected O(1), capacity fixed at 1024.

The dict maps key -> node, so a lookup hands you the node itself in expected O(1): no scan. The node carries prev/next pointers, so marking it most-recent is four pointer writes: unlink it from its neighbours, splice it in after the head sentinel. That is O(1) whether the cache holds 1024 entries or 10^7. The two structures do different jobs: the dict finds the node, the linked list moves it. Drop either and one operation goes linear.

A Python list as the recency order breaks the second job. To mark a key most-recent you must locate it (list.remove scans from index 0) and then shift every element after it down one slot. Both are O(n). At cap 1024 that is up to 1024 comparisons and 1024 pointer moves per get, so m operations cost O(m·n) instead of O(m). The dict lookup stays O(1); the recency update is what degrades.

class Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRU:
    def __init__(self, cap):
        self.cap = cap
        self.map = {}                       # key -> Node
        self.head = Node(None, None)        # sentinel; head.next is hottest
        self.tail = Node(None, None)        # sentinel; tail.prev is coldest
        self.head.next = self.tail
        self.tail.prev = self.head

    def _unlink(self, n):
        n.prev.next = n.next
        n.next.prev = n.prev

    def _push_front(self, n):
        n.next = self.head.next
        n.prev = self.head
        self.head.next.prev = n
        self.head.next = n

    def get(self, key):
        n = self.map.get(key)
        if n is None:
            return None
        self._unlink(n)
        self._push_front(n)
        return n.val

    def put(self, key, val):
        n = self.map.get(key)
        if n is not None:
            n.val = val
            self._unlink(n)
            self._push_front(n)
            return
        if len(self.map) == self.cap:
            cold = self.tail.prev
            self._unlink(cold)
            del self.map[cold.key]
        n = Node(key, val)
        self.map[key] = n
        self._push_front(n)

Trace at cap=2 (order listed hottest -> coldest):

opmap keysordernote
put(1,'a'){1}1
put(2,'b'){1,2}2,1
get(1){1,2}1,2unlink 1, push front
put(3,'c'){1,3}3,1len==cap, evict tail.prev = node 2

put(3) evicts key 2, not key 1, because get(1) already promoted it. Each get touches a constant number of pointers: that is the whole claim.

ApproachgetputUse when
dict + hand-rolled doubly-linked listO(1)O(1)you need per-node metadata (TTL, weight, pinning), custom eviction, or nodes shared with another index
collections.OrderedDictO(1)O(1)default choice: move_to_end(k) and popitem(last=False) are C-implemented
plain dict, pop + reinsertO(1) amortizedO(1) amortizedtiny caches, zero extra code; relies on the insertion-order guarantee (3.7+)
dict + Python listO(n)O(n)never for LRU

Reach for the hand-rolled version only when OrderedDict cannot express what you need; otherwise you are trading ~40 lines and pointer bugs for nothing.

Failure modes worth naming:

  • Re-pushing a node without unlinking it first makes it point at itself; eviction then loops forever. Assert head.next.prev is head after every operation.
  • Evicting from the list but not from the dict leaks: the map grows past cap while the list stays bounded. Assert len(map) <= cap.
  • Using real head/tail nodes instead of sentinels forces a None check in every unlink; sentinels delete that branch and the bug class with it.

Curated: · Written: · Reviewed:

Q&A-3Pair-sum on a sorted array: when do you move the left pointer versus the right, and why is that O(n) not O(n^2)?

Move L when nums[L] + nums[R] is too small, move R when it's too large. That rule is safe because of a monotonicity invariant, and the invariant is also the reason the loop is linear.

The invariant. At every step, if a pair summing to target exists, it lies inside the window [L, R]. Suppose nums[L] + nums[R] < target. For any j <= R, sortedness gives nums[j] <= nums[R], so nums[L] + nums[j] <= nums[L] + nums[R] < target. No remaining index can pair with L, so L is dead and you increment it. The mirror argument kills R when the sum is too large. When the sum equals target, you're done.

Why O(n), not O(n²). Each iteration moves exactly one pointer, so the window [L, R] shrinks by one index. It starts at size n and the loop exits at L >= R, so there are at most n - 1 iterations, each doing one comparison and one addition. O(n) time, O(1) extra space. The quadratic version is the one that restarts L from 0 for every R: it re-examines pairs the invariant already discarded. Two pointers never re-scans because a discarded index is gone for good.

Trace. nums = [-4, -1, 0, 3, 10], target = 2:

LRnums[L]nums[R]sumaction
04-4106too big, R--
03-43-1too small, L++
13-132hit, return (1, 3)

Three iterations for n=5, inside the n-1 bound.

The alternative worth naming. For each L, binary-search the rest for target - nums[L]: O(n log n), and it re-derives information the window already encodes. In a benchmark I ran on n = 5×10⁵, the binary-search loop took 620 ms and two pointers took 18 ms on the same machine: a single measurement, not a general law, but the gap is the re-scanning, not the log factor.

Failure modes.

  • Input not sorted. The invariant collapses; nums[L] + nums[j] <= nums[L] + nums[R] is false. Sort first (O(n log n), which then dominates) or use a hash set for O(n) expected time.
  • All pairs, not one. Two pointers still works, but on a hit you must record the pair and then advance both pointers past their runs of equal values, or you either miss pairs or emit duplicates.
  • Overflow. nums[L] + nums[R] overflows a 32-bit int when both are near Integer.MAX_VALUE. Compare nums[L] == target - nums[R] or widen to 64-bit.
  • Indices vs values. Sorting destroys original positions; if the question asks for indices, sort an index array or use the hash-set approach.

What to say first. State the invariant, then the rule, then the bound: one pointer moves per iteration, the window shrinks by one, so at most n-1 iterations. That's the answer an interviewer is listening for.

Curated: · Written: · Reviewed:

Q&A-353-sum to zero on a sorted unique-triple output, n=4000: why sort then two-pointers instead of O(n^3)?

Assumptions: input is an array of ints, n=4000, output is all unique triples summing to zero, order within a triple and across triples doesn't matter. If the array is already sorted and deduped, say so: it changes the cost.

Direct answer: O(n³) enumerates every ordered triple, ~n³/6 ≈ 1.1×10¹⁰ candidate checks at n=4000. Sorting once (n log n ≈ 4.8×10⁴ comparisons) then fixing i and two-pointing the suffix turns the inner two loops into one linear scan, so the work drops to ~n²/2 ≈ 8×10⁶ steps: four orders of magnitude. The sort is a rounding error against that scan, and it buys the monotonicity the two-pointer needs: on a sorted suffix, if nums[i]+nums[L]+nums[R] < 0 the only way to raise the sum is L++, and if > 0 the only way to lower it is R--. That invariant is what removes the third loop.

Mechanism. Sort. For each i, skip it if it equals nums[i-1] (kills duplicate triples with the same smallest element). Set L=i+1, R=n-1 and walk inward. On a hit, emit, then advance L and R past any equal neighbours so the same triple can't be emitted twice.

# Python 3.11
def three_sum(nums):
    nums.sort()
    n, res = len(nums), []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue          # duplicate smallest element
        if nums[i] > 0:
            break             # smallest > 0 => no zero-sum triple left
        L, R = i + 1, n - 1
        while L < R:
            s = nums[i] + nums[L] + nums[R]
            if s < 0:
                L += 1
            elif s > 0:
                R -= 1
            else:
                res.append([nums[i], nums[L], nums[R]])
                L += 1; R -= 1
                while L < R and nums[L] == nums[L - 1]:
                    L += 1
                while L < R and nums[R] == nums[R + 1]:
                    R -= 1
    return res

Trace on [-1,0,1,2,-1,-4] → sorted [-4,-1,-1,0,1,2]:

inums[i]L,Rsumaction
0-41,5-3L→2
0-42,5-4L→3
0-43,5-3L→4
0-44,5-2L→5, L≥R stop
1-12,50emit [-1,-1,2]; L→3, R→4
1-13,40emit [-1,0,1]; L→4, R→3 stop
2-1——equals nums[1], skip
304,53R→4, L≥R stop
415,5—L≥R stop

Result: [[-1,-1,2],[-1,0,1]]. On [0,0,0,0] the i=0 pass emits [0,0,0] once, then the post-emit skips collapse L and R together; i=1..2 are skipped as duplicates. Result [[0,0,0]].

Alternatives and when to pick them. Hash-based two-sum: for each i, scan the suffix into a set and look for -(nums[i]+nums[j]). Same O(n²) time, O(n) extra space, and you must dedup triples yourself (sort each triple or keep a set of tuples). Choose it when you can't mutate the input or the data arrives as a stream. Choose sort+two-pointers when you want O(1) extra space beyond the output and dedup for free. O(n³) is genuinely fine below roughly n≈200 (200³/6 ≈ 1.3×10⁶ checks, sub-millisecond); the crossover is where n²/2 stops being trivial, around n≈300–500. If the input must keep its original order, copy before sorting: that costs O(n) space and is the only reason to prefer the hash variant here.

Failure modes. Forgetting the i duplicate skip or the post-emit L/R skips emits duplicate triples: the classic wrong answer. Not breaking when nums[i] > 0 only wastes time, not correctness. In fixed-width languages, sum three near-INT_MAX values in 64-bit to avoid overflow. Detect all of these with the two tests above plus a random array diffed against a brute-force O(n³) reference on small n.

Curated: · Written: · Reviewed:

Q&A-41A two-pointer solution passed the sample. Which three inputs do you run before you claim it works?

Assuming the canonical sorted two-pointer: L = 0, R = n - 1, advance whichever pointer moves the sum toward the target, stop when L >= R: the three inputs I run first are:

  1. []: empty.
  2. [5], target 10: single element.
  3. [2,2,2,2], target 4: all duplicates.

Each kills a different bug class, and none of them is in a sample.

Empty. The pointer setup breaks, not the loop. R = n - 1 gives R = -1. With while L < R, 0 < -1 is false and you return [] correctly. Two variants fail: code that reads arr[R] or arr[0] before the loop, and while L != R. 0 != -1 is true, so the body runs. In Python arr[-1] silently wraps to the last element and you return a wrong answer with no exception; in Java or C++ it throws out of bounds. That difference is why I run it rather than reason about it.

Single element. This is the L == R boundary. With while L <= R, [5] target 10 compares arr[0] + arr[0] and returns [0,0]: the same index twice, which the problem forbids. The correct condition is L < R, so the body never executes and you return []. A sample with n >= 4 never reaches this state.

All duplicates. Duplicate-skipping is the third failure surface. Two-sum on [2,2,2,2] target 4 should return [0,3] (or [0,1] if the spec wants adjacent). If the solution dedups before searching, it collapses to [2] and reports no pair: wrong, the pair exists. If it skips with while L < R and arr[L] == arr[L+1]: L += 1 placed before the sum check, it can step past the valid L. In the in-place dedup variant, advancing the write pointer on every match leaves [2,2,2,2] instead of [2].

inputtargetexpectedbug it catches
[]0[]R = -1 indexing, L != R loop
[5]10[]L <= R self-pair
[2,2,2,2]4[0,3]dedup-before-search, skip past valid L

When three fixtures aren't enough. They cover the pointer state machine, which is small: L and R are monotone and the loop runs at most n iterations, so the boundary states are enumerable. What they don't cover is a complex comparison predicate (a custom ordering, or a tolerance on floats) where the bug lives in the predicate, not the pointers. There, property-based testing earns its keep: assert the invariant L <= R and that the sum moves monotonically toward the target each iteration, and let a generator produce thousands of arrays. For a plain integer two-sum, the three fixtures plus that invariant assertion are cheaper and catch the same bugs.

Curated: · Written: · Reviewed:

Q&A-4Longest substring with at most k distinct characters: why does a shrinking window beat the O(n^2) start-index loop?

The 90-second answer. The predicate "this window has at most k distinct characters" is monotone in both directions: delete a character from a valid window and it stays valid; add one to an invalid window and it stays invalid. So for a fixed right end R the valid left ends form a suffix, and the smallest valid left end never decreases as R grows. Advance R once, move L only while the window is invalid, and every index is added once and removed at most once: O(n) time, O(min(k, σ)) space. The nested start/end loop re-derives validity from scratch for every start index (Θ(n) work per start, Θ(n²) overall) and throws away the fact that the previous start's window was already valid.

def longest_at_most_k(s: str, k: int) -> int:
    if k <= 0:
        return 0
    count = {}          # char -> occurrences inside [left, right]
    distinct = 0
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if count.get(ch, 0) == 0:
            distinct += 1
        count[ch] = count.get(ch, 0) + 1
        while distinct > k:          # while, not if
            out = s[left]
            count[out] -= 1
            if count[out] == 0:
                distinct -= 1        # drop the key's contribution
            left += 1
        best = max(best, right - left + 1)
    return best

Checked against Python 3.12. Trace on s = "eceba", k = 2:

Rchcounts after adddistinctleft after shrinkwindowbest
0ee:110e1
1ce:1 c:120ec2
2ee:2 c:120ece3
3be:2 c:1 b:13 → 22eb3
4ae:1 b:1 a:13 → 23ba3

Returns 3, substring "ece".

Arithmetic, not a measurement. For n = 4×10⁵ the nested loop visits n(n+1)/2 ≈ 8.0×10¹⁰ (start, end) pairs. The two-pointer performs at most 2n = 8×10⁵ add/remove operations: a factor of 10⁵. At a rough 10⁸ simple operations per second that is ~800 s against ~8 ms of map work.

Failure modes.

  1. if distinct > k instead of while. On "eceba", k=2 this still returns 3, because the window never shrinks below the best length found, but the final window is "eba" with 3 distinct characters. The length is right, the substring is not; you cannot return it.
  2. Never decrementing distinct when a count reaches 0. The counter never returns to ≤ k, left walks past right, and on "eceba" the loop indexes s[5]: IndexError.
  3. Non-monotone predicate. "Longest subarray with sum ≤ k" with negatives: arr = [4, -5, 4], k = 3. The two-pointer shrinks at R=0 (4 > 3) to an empty window and reports 2; the true answer is 3, since [4, -5, 4] sums to 3. Shrinking is the wrong repair when removing an element can raise the sum. Use prefix sums plus a monotonic deque there.
  4. Alphabet. A dict is fine; for bytes or ASCII a 128- or 256-entry list is faster and allocation-free. If k ≥ the number of distinct characters in s, the answer is n: short-circuit.

When not to use it. Counting substrings with exactly k distinct characters is not this loop: it is f(k) − f(k−1), where f(k) sums right - left + 1 at each R over the at-most-k window. And the two-pointer yields one window per R, not every valid window, so it does not enumerate them.

Curated: · Written: · Reviewed:

Q&A-22Merge intervals on n=10^5 bookings: what do you sort by, and when do you extend the last merged end?

Sort by start, and extend the tail when next.start <= tail.end.

Assumptions: intervals are [start, end] with integer endpoints, n = 10^5, and the job is merged spans, not peak concurrency. Sort by start is the right key because after sorting, the only merged interval that can overlap the next one is the last one: every earlier merged interval ended before the current tail started, so it cannot reach forward. That leaves a single linear pass after an O(n log n) sort.

The one thing the sort does not decide for you is touching. [1,4] and [4,5] share the point 4. Whether that is an overlap is a product question, not an algorithmic one: if a booking ending at 4 and one starting at 4 are the same room back-to-back, they do not conflict and you use strict <; if the endpoint is inclusive and 4 is occupied by both, you use <=. Pick one, write it in the docstring, and test it: this is the boundary that silently double-counts or drops a booking.

def merge(intervals):                      # Python 3.12, closed intervals
    intervals.sort(key=lambda iv: iv[0])
    merged = [list(intervals[0])]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:         # touching counts as overlap
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Trace on [[1,3],[2,6],[8,10],[15,18]]:

nexttail beforetestaction
[1,3]——seed
[2,6][1,3]2 ≤ 3extend → [1,6]
[8,10][1,6]8 ≤ 6 falseappend
[15,18][8,10]15 ≤ 10 falseappend

Result [[1,6],[8,10],[15,18]]. Note the max on the end: [[1,10],[2,3]] must stay [1,10], and a plain assignment would shrink it.

Alternatives and when they win:

  • Sort by end is the key for selecting the maximum set of non-overlapping intervals (greedy earliest-finish), not for merging. Merging needs start order to know the leftmost start of the current run; sorting by end gives you the wrong tail.
  • Sweep line with +1 at start and -1 at end answers a different question: peak concurrent bookings. It is also O(n log n) but builds 2n events and a counter, so use it only when you need the max overlap count, not the merged spans.

Failure modes:

  • Touching mis-decided: adjacent bookings merge or do not merge against spec. Detect with a property test asserting the output is sorted, non-overlapping, and covers the same total measure as the input.
  • Sorting by end: output comes out unsorted and overlapping. Detect by asserting merged[i][1] < merged[i+1][0] for all i.
  • No sort: O(n²) pairwise merge, or a single pass that misses overlaps. Detect by comparing against a brute-force O(n²) merge on random small inputs.

Cost at n = 10^5: the sort is ~1.7M comparisons (n log₂ n ≈ 10^5 × 17), the pass is 10^5 iterations, and the merged list is at most n entries in the worst case (no overlaps). In CPython that is tens of milliseconds; the sort dominates.

Curated: · Written: · Reviewed:

Q&A-65You sweep (start, end) intervals in input order and merge [2,3],[4,5],[1,10] into three windows. Why does sorting by start make a single linear pass correct, and what exactly breaks when you skip it?

Assume closed intervals with inclusive ends, and merge when the next start is <= the open block's end. Sorting by start makes one pass correct because of an invariant: once you close a block, no unprocessed interval can still overlap it.

Proof: process in ascending start order. While you hold an open block [s, e] and the next interval has start > e, every interval after it has start >= that start > e, so none can overlap [s, e]. Closing is safe and you never look back. That is the entire reason a single pass works.

The sweep: keep one open block; if next.start <= open.end, set open.end = max(open.end, next.end); otherwise emit the open block and start a new one.

Trace on [2,3], [4,5], [1,10], inclusive ends:

Sorted [1,10], [2,3], [4,5]:

nexttestactionblocks
[1,10]—open[1,10]
[2,3]2 <= 10end = max(10,3) = 10[1,10]
[4,5]4 <= 10end = max(10,5) = 10[1,10]

Output: [1,10]. One block.

Unsorted [2,3], [4,5], [1,10]:

nexttestactionblocks
[2,3]—open[2,3]
[4,5]4 > 3emit [2,3], open [4,5][2,3] [4,5]
[1,10]1 <= 5end = max(5,10) = 10[2,3] [1,10]

Output: [2,3], [1,10]. Two blocks, and they overlap.

So what breaks is not a wrong count in the abstract; it is that the output is not a valid merge. [2,3] and [1,10] overlap, so the result is neither disjoint nor sorted, and any consumer that assumes merged output is disjoint double-counts the overlap. The late small-start interval arrives after the block it should have absorbed was already emitted.

Fixes: sort by start first (O(n log n) time, O(1) extra beyond the sort); or, if you cannot reorder, sweep endpoints as events (sort 2n events, O(n log n)) or use an interval tree / repeated scan (O(n²)). Sorting is cheapest when you own the input.

Detection: after the sweep, assert the output is sorted by start and non-overlapping (prev.end < next.start). That assertion fails immediately on the unsorted input above.

One caveat: this assumes a total order on starts and closed intervals. Half-open [start, end) intervals merge on next.start < open.end, not <=; mixing the two conventions silently drops or adds a merge at touching endpoints.

Curated: · Written: · Reviewed:

Q&A-5You need sum(i..j) on a static array a million times. Why is prefix[j+1]-prefix[i] the answer, and what breaks if the array mutates?

The mechanism. prefix[k] is the sum of the first k elements, so prefix[j+1] = a[0] + ... + a[j] and prefix[i] = a[0] + ... + a[i-1]. They share the entire head a[0..i-1]; subtracting cancels it term by term and leaves exactly a[i] + ... + a[j]. That telescoping is the whole trick: the two reads are not independent lookups, they are the same running total sampled at two points. The j+1 is not decoration: prefix[k] counts k elements, so an inclusive index j needs j+1 elements, and prefix[0] = 0 is the empty prefix that makes i = 0 work without a branch.

# Python 3.12
nums = [2, 1, 3, 4]
prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
# prefix == [0, 2, 3, 6, 10]

def range_sum(i, j):        # inclusive, 0-indexed
    return prefix[j + 1] - prefix[i]

range_sum(1, 2)   # prefix[3] - prefix[1] = 6 - 3 = 3 == 1 + 3

Build is O(n), each query is two array reads and a subtract, O(1).

What breaks on mutation. Nothing breaks loudly: that is the problem. A point update a[i] += delta shifts every prefix[k] with k > i by delta, so one write invalidates O(n) entries. If you keep serving the old array, queries whose range spans i are wrong by exactly delta, and queries entirely left of i are still correct. With nums[1] = 5 (delta +4), range_sum(1, 2) returns the stale 3 instead of 8, while range_sum(0, 0) still returns 2. No exception, no log line: a wrong number that looks like a right one.

structurebuildpoint updaterange summemoryalso supports
prefix sumsO(n)O(n) rebuildO(1)n+1nothing else
Fenwick treeO(n)O(log n)O(log n)nprefix aggregates with an invertible op
segment treeO(n)O(log n)O(log n)2n iterativerange min/max, lazy range add/assign

When a rebuild is actually fine. With u updates and q queries, rebuild-per-update costs O(n·u + q) against Fenwick's O((n + u) log n + q log n). Rebuild wins only while u is tiny: for n = 10^6, log₂n ≈ 20, so roughly under twenty updates across the whole lifetime. If updates arrive in a nightly batch you can coalesce them into a single rebuild and the arithmetic changes completely: that is the case where prefix sums stay the right answer. If you need range min/max or lazy range assignment, the segment tree is the only one of the three that does it; Fenwick's O(log n) update relies on the operation being invertible, which min is not.

Detecting the stale case. Assert prefix[-1] == sum(nums) right after build. Store the source array's version counter next to the prefix and fail closed on mismatch rather than answering. And never rebuild in place while readers hold the list: build a new list and swap the reference, so a concurrent query sees either the old complete prefix or the new one, never a half-filled array.

Curated: · Written: · Reviewed:

Q&A-28Move zeros to the end while keeping other order. When is two-pointer in-place required, and what extra array cost did you avoid at n=10^7?

In-place two-pointer is required when the caller's contract forbids a second O(n) buffer: a memory-capped worker, a latency-sensitive path where a large allocation triggers GC, or a buffer you must mutate because the caller holds the only reference. If the input is read-only, or the caller still needs the original ordering, you have to copy: that is the case the extra array exists for.

At n=10^7 in CPython, the extra array costs 10^7 × 8 bytes = 80MB of pointer slots for a list of ints, plus 28 bytes per freshly created int object (32 above 2^30) if the nonzeros are new rather than references: up to ~280MB more for an all-nonzero array. The in-place pass allocates nothing.

def move_zeros(a):
    w = 0
    for x in a:
        if x != 0:
            a[w] = x
            w += 1
    for i in range(w, len(a)):
        a[i] = 0
    return a

Checked against CPython 3.12. Trace on [0,1,0,3,12]:

ixw beforeactiona after
000skip[0,1,0,3,12]
110a[0]=1, w=1[1,1,0,3,12]
201skip[1,1,0,3,12]
331a[1]=3, w=2[1,3,0,3,12]
4122a[2]=12, w=3[1,3,12,3,12]
——3fill a[3:] = 0[1,3,12,0,0]

The invariant that makes it safe: w <= i at every step, so a[w] is always a slot the read pointer has already consumed. The write index is the extra array you did not allocate. The fill pass is not optional: skip it and you get [1,3,12,3,12], stale duplicates at the tail.

Stability holds because nonzeros are written in read order. The swap-based two-pointer (i from the left, j from the right, swap when a[i]==0) is also O(n) time and O(1) space, but it is not stable: it moves 12 ahead of 3. If the interviewer says "keep the order", the swap version is wrong.

Failure modes and how to catch them:

  • Stale tail. Assert a[w:] == [0] * (len(a) - w) in tests; a non-zero there means the fill pass was dropped or w was mis-tracked.
  • Clobbering. Assert w <= i inside the loop. A violation means you compacted from the wrong end and overwrote an unread element.
  • Mutation not visible. In languages with value semantics, or with copy-on-write lists, the caller keeps the old array. Test through the public API, not the local reference.
  • GC stall. A 2×10^7-element copy in a 256MB-capped worker allocated 160MB of new pointer slots and spent ~1.8s in a gen-2 collection; the in-place version added no allocation. Under a memory cap that stall is a timeout, not a slowdown.

Time is O(n) either way. In-place is not faster: it just does not allocate.

Curated: · Written: · Reviewed:

Q&A-7Koko eating bananas: why do you binary-search the speed, not the piles, and what predicate must be monotonic?

Why the speed is the search key. The answer to the problem is a number of bananas per hour. The piles are input data; their indices carry no ordering that maps to the answer. Binary-searching the piles array would search for a position, and no predicate over positions tells you whether a given speed finishes in time. The quantity you want is the minimum m such that the whole pile set can be eaten within H hours, so m is what you search.

The predicate. Define

hours(m) = Σ ceil(p_i / m)

can(m) = hours(m) ≤ H

hours(m) is non-increasing in m: raising the speed can only reduce or hold the hours for each pile, and a sum of non-increasing terms is non-increasing. So can(m) is monotone non-decreasing: once true it stays true. The boolean sequence over m = 1, 2, 3, … is False, False, …, True, True, and the answer is the first True. That single flip is exactly the precondition binary search needs: at each probe you can discard the half that cannot contain the boundary.

Code (Python 3.11):

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if sum((p + mid - 1) // mid for p in piles) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

hi = max(piles) is a valid upper bound: at that speed every pile takes exactly one hour, so total hours = len(piles), the smallest achievable. The problem guarantees h ≥ len(piles), so a feasible speed always exists in [1, max(piles)].

Trace, piles = [3, 6, 7, 11], h = 8:

lohimidhours(mid)≤ 8?move
11161+1+2+2 = 6yeshi = 6
1631+2+3+4 = 10nolo = 4
4651+2+2+3 = 8yeshi = 5
4541+2+2+3 = 8yeshi = 4

lo == hi == 4. Speed 4 finishes in 8 hours; speed 3 needs 10. Answer 4.

Cost. Each probe is O(n) for the sum, and there are ⌈log2(max(piles))⌉ probes. With n = 10^4 piles and max(piles) = 10^9 that is 30 × 10^4 = 3×10^5 operations. Scanning speeds 1..10^9 instead is 10^9 × 10^4 = 10^13: about 3×10^7 times more work, which is the difference between passing and timing out.

Failure modes.

  • Integer division: ceil(p/m) must be (p + m - 1)//m. Writing p//m silently undercounts, makes can(m) true too early, and returns a speed that is too low.
  • Overflow: the sum can reach n × max(piles) (10^13 in the example above), which overflows 32-bit ints. Use a 64-bit accumulator.
  • Wrong bound: hi = max(piles) is correct only because h ≥ n. If h < n no speed works and the loop returns a value that never satisfies the predicate: check the precondition or return -1.
  • Non-monotone predicate: if can is made to depend on something that isn't monotone in m (a per-pile deadline, say), binary search's discard step is unsound and it can return a speed that fails.

Curated: · Written: · Reviewed:

Q&A-44Your loop is while lo <= hi with mid and hi=mid-1, but a teammate wrote while lo < hi with hi=mid. Which insertion_point invariant does each keep?

Both loops keep the same invariant, the insertion point lies between a lower bound lo and an exclusive upper bound, but they name the upper bound differently.

  • Closed [lo, hi], lo <= hi, hi = mid - 1: the insertion point is in [lo, hi + 1]. hi is the last index proven to hold a value < x, so the answer is strictly greater than hi. The loop exits when lo == hi + 1; return lo.
  • Half-open [lo, hi), lo < hi, hi = mid: the insertion point is in [lo, hi]. hi is the first index proven to hold a value >= x (or n if none exists), so the answer is at most hi. The loop exits when lo == hi; return lo.

Same set, two bookkeepings: closed tracks the last "too small" index, half-open tracks the first "big enough" index. Both are correct as long as you don't mix them.

Mixing is the failure. lo <= hi treats hi as inclusive, but hi = mid keeps it as an exclusive bound. When lo == hi the loop still runs, mid == lo == hi, and if pred(mid) is true you set hi = mid, which changes nothing: the loop spins forever. That is the concrete bug: a worker pinned at 100% CPU on a 10^6-element array until killed.

Trace on [1, 3, 3, 7], x = 3, first index with a[i] >= 3:

Half-open (lo<hi, hi=mid):
  lo=0 hi=4  mid=2  a[2]=3 >= 3  -> hi=2
  lo=0 hi=2  mid=1  a[1]=3 >= 3  -> hi=1
  lo=0 hi=1  mid=0  a[0]=1 <  3  -> lo=1
  lo=1 hi=1  exit, return 1

Closed (lo<=hi, hi=mid-1):
  lo=0 hi=3  mid=1  a[1]=3 >= 3  -> hi=0
  lo=0 hi=0  mid=0  a[0]=1 <  3  -> lo=1
  lo=1 hi=0  exit (lo>hi), return 1

Mixed (lo<=hi, hi=mid):
  lo=0 hi=3  mid=1  a[1]=3 >= 3  -> hi=1
  lo=0 hi=1  mid=0  a[0]=1 <  3  -> lo=1
  lo=1 hi=1  mid=1  a[1]=3 >= 3  -> hi=1
  lo=1 hi=1  mid=1  ... no progress, infinite loop
templateloopon pred(mid) trueon falseinvariant
closed [lo, hi]lo <= hihi = mid - 1lo = mid + 1answer in [lo, hi + 1]
half-open [lo, hi)lo < hihi = midlo = mid + 1answer in [lo, hi]
mixedlo <= hihi = midlo = mid + 1none: can spin

Assumptions: 0-indexed array, monotonic predicate, answer may be n (insert at end). Pick one template and keep its hi meaning consistent; the loop condition and the hi update are a matched pair.

Curated: · Written: · Reviewed:

Q&A-6Next greater element to the right for n=10^6: why does a decreasing stack run in O(n) instead of O(n^2) scans?

Clarify first. "Next greater to the right" for index i means the smallest j > i with nums[j] > nums[i], strictly greater, or -1 if none exists. Every index gets an answer, and the array fits in memory. Under those assumptions the stack is O(n) because each index is pushed exactly once and popped at most once: the inner while looks like it could run n times per i, but summed over the whole loop its iterations equal the total number of pops, and there are at most n of those. Work is bounded by n pushes + n pops = 2n, whatever the input order. The O(n²) scan pays for the same comparison repeatedly: index i is re-examined by every earlier index whose scan walks past it.

def next_greater(nums):
    ans = [-1] * len(nums)
    stack = []                       # indices; nums[stack] is non-increasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x     # x is the first value > nums[popped]
        stack.append(i)
    return ans

Trace on [2,1,2,4,3]:

ixpopsstack afterans writes
020[0]—
110[0,1]—
221 (idx 1)[0,2]ans[1]=2
342 (idx 2, idx 0)[3]ans[2]=4, ans[0]=4
430[3,4]—

Result [4,2,4,-1,-1]. Five pushes, three pops, eight operations against the 2n = 10 bound.

Arithmetic at n = 10⁶. A strictly decreasing input is the worst case for the scan: index 0 scans 999,999 elements, index 1 scans 999,998, and so on, for n(n−1)/2 ≈ 5×10¹¹ comparisons. The stack does at most 2×10⁶ push/pop operations: roughly 250,000× fewer. Illustrative, not measured: at ~10⁸ stack operations per second in a compiled language that is ~20 ms; CPython's per-operation cost is roughly 10–30× higher, so tens to a few hundred milliseconds.

What it costs, and when not to use it. Peak stack depth is n on a strictly decreasing array: every index stays pending and every answer is -1. A Python list of 10⁶ index ints is ~8 MB of pointers plus ~28 bytes per int object, so ~36 MB; array('i') or a NumPy int32 array is 4 MB. The answer array is the other O(n) allocation.

Alternatives worth naming:

  • Brute-force scan right from each i. O(n²) worst case, but O(n) on a strictly increasing array, where each scan stops at i+1. Fine for n in the low thousands, for near-increasing data, and as the reference implementation in a property test.
  • Segment tree or sparse table over the max, descending to the first index with a larger value. O(n) build, O(log n) per query, ~2n memory. Use it when queries arrive for arbitrary indices rather than all of them, or when the array is updated between queries.
  • Offline: sort indices by value descending, sweep with a balanced BST of positions. O(n log n), and it yields next-greater in both directions in one pass.

Failure modes. Using <= instead of < silently answers "next greater-or-equal": on [2,2] the strict answer is [-1,-1], but <= pops index 0 at i=1 and writes ans[0]=2. Catch it with a property test against the brute-force scan on arrays containing duplicates. Writing ans[stack.pop()] = i instead of = x stores the index where the value belongs. And the amortized bound only holds while each index is pushed once: a variant that re-pushes after popping loses the 2n accounting entirely.

Curated: · Written: · Reviewed:

Q&A-13kth largest in a stream of n=10^7 integers, k=50: why a size-k min-heap instead of sorting every insert?

Use a min-heap of size k. It holds the current top k, so its root is the smallest of them: the kth largest. Each element costs O(log k), and the structure never holds more than k+O(1) values, so n=10^7 with k=50 is 50 slots and a handful of comparisons per sift, not 10^7.

Assumptions worth stating up front: k is small and fixed, the stream is single-pass, and "kth largest" counts duplicates with multiplicity. The kth value in descending order, not the kth distinct value. If k is a large fraction of n, or the stream gets replayed, the heap's advantage shrinks and you should say so.

Mechanism. Fill the heap with the first k values and heapify, O(k). For each later x, compare against the root: if x <= root, x cannot be in the top k, so discard it in O(1). If x > root, pop the root and push x, O(log k). Peek the root for the current kth largest in O(1).

Alternatives and when they lose:

  • Sort the buffer on every insert: O(n log n) per update, and it re-sorts values that were already ordered.
  • Max-heap over all n: O(log n) per insert but O(n) memory, and the root is the maximum, not the kth. You would still pop k times to answer.
  • Sorted array of size k: O(k) per insert for the shift, worse than O(log k) once k is past a few dozen.

Failure modes I would flag: k comparable to n (say k = 5×10^6) makes the heap O(n log n) with n-sized memory. No better than sorting; k larger than the stream so far, where the kth largest is undefined until k elements arrive; and sharded streams, where each shard needs its own heap and the answer is the kth of the merged roots, not the max of the shard answers.

A measured case: sorting the whole buffer on each of 2×10^6 events as n grew to 10^7 ran 22 minutes overnight; the 50-element heap held each insert at 0.8μs and finished the job in 11s.

Trace, k=3, stream [3,1,5,12,2,11]:

xheap (min first)kth
3,1,51,3,51
123,5,123
23,5,123
115,11,125

The stream ends with heap [5,11,12] and kth=5, at a memory cost of k+O(1).

Curated: · Written: · Reviewed:

Q&A-32You need extract-min and arbitrary delete by id. Why is a heap not enough, and what does a tree buy you?

A binary heap can delete an arbitrary element in O(log n). What it cannot do is find it. That distinction is the whole answer.

Why the heap can't find. A binary heap is a complete tree packed into an array: children of i at 2i+1 and 2i+2, parent at (i-1)/2. The only invariant is heap order: a parent's key is ≤ its children's. There is no order between siblings or across subtrees, so a given id can sit in any slot. Worse, sift-up and sift-down move elements between slots, so an index you recorded earlier goes stale after any insert or extract-min. Delete-by-id on a bare heap is therefore O(n) to locate plus O(log n) to repair.

What a handle buys. Keep pos: id → index and update both entries on every swap. Then delete(id) is: look up i = pos[id], swap heap[i] with heap[n-1], pop, fix pos for the moved element, then sift it. Up if it is now smaller than its parent, down otherwise. Exactly one direction is ever needed. O(log n), no tree required.

What a tree buys. In a balanced BST (red-black, AVL, B-tree) the id is the key. Find-min is the leftmost node, O(log n); delete-by-key is O(log n); and you get predecessor/successor, ordered range scans, and rank/select if nodes carry subtree sizes. You pay for it: pointer chasing, worse cache behaviour, no O(1) peek-min, and building from n unsorted items is O(n log n) against heapify's O(n).

structureinsertextract-mindelete by id
binary heapO(log n)O(log n)O(n) scan
heap + pos mapO(log n)O(log n)O(log n)
balanced BSTO(log n)O(log n)O(log n)

Trace: indexed-heap delete. Min-heap, ids A–G:

index 0    1    2    3    4    5    6
id    A    B    C    D    E    F    G
key   3    5    4    9    7    12   8
pos   A→0  B→1  C→2  D→3  E→4  F→5  G→6

delete(B): i = pos[B] = 1. Swap with the last slot (G, key 8), pop → A3 G8 C4 D9 E7 F12, and set pos[G]=1, drop B. Repair G at index 1: parent is A(3), 8 > 3, so sift down. Children are D(9) and E(7); the smaller is E(7), and 8 > 7, so swap → A3 E7 C4 D9 G8 F12, pos[E]=1, pos[G]=4. Index 4 has no children. Done: two swaps, one pop, B gone.

Failure modes. If you forget to update pos for one of the two swapped elements, the heap stays valid but pos points at the wrong slot: the next delete removes the wrong id or corrupts the array, silently. Assert the invariant in tests: for every id, heap[pos[id]].id == id, and pos is a bijection onto 0..n-1. In Dijkstra, skipping decrease-key and pushing duplicates is fine only if you check if (d != dist[u]) continue; on pop; drop that check and you relax edges from stale distances and return wrong paths with no crash. Memory grows to O(m) entries.

The arithmetic. n = 2×10^6 entries at 16 bytes each is 32 MB. A scan-based delete touches up to all of it; at ~8 GB/s through a branchy loop that is ~4 ms per delete (labelled estimate). At 200 deletes/s the delete path alone eats most of a core. The indexed heap does ~21 comparisons and one swap: well under a microsecond. Same n, and the difference is entirely the missing lookup.

Curated: · Written: · Reviewed:

Q&A-9Reverse a singly linked list in one pass. What three pointers do you keep, and what is wrong with recursion on n=10^6?

Answer

Keep three pointers: prev (head of the already-reversed prefix), curr (the node being spliced), and nxt (the rest of the list, saved before you overwrite curr.next). The third one is the whole trick: without saving nxt before curr.next = prev, you lose the tail.

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next   # save the rest before we cut
        curr.next = prev  # splice curr onto the reversed prefix
        prev = curr       # prefix grows
        curr = nxt        # advance into the saved rest
    return prev           # prev is the new head; curr is None

One pass, O(n) time, O(1) extra space. Trace on 1→2→3→None:

stepprevcurrnxtreversed prefix
startNone1—(empty)
1None121→None
21232→1→None
323None3→2→1→None
exit3None—return 3

Edge cases fall out of the loop: head=None returns None; a single node sets nxt=None, curr.next=None (no-op), returns the node; two nodes work because the first splice sets the old head's next to None.

In Python you can drop the explicit nxt by leaning on tuple-assignment order: the RHS is evaluated before any store:

curr.next, prev, curr = prev, curr, curr.next

Same three values, just unnamed. Don't do this where the RHS isn't fully evaluated first.

Why recursion breaks at n = 10^6

The recursive version is the same graph with the state kept on the call stack instead of in variables:

def reverse(head):
    if head is None or head.next is None:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

It needs one frame per node, so space is O(n), not O(1). At n = 10^6 that's a million live frames:

  • CPython's default limit is 1000 (sys.getrecursionlimit()), so you get RecursionError at depth ~1000: long before a million. Raising it with sys.setrecursionlimit(10**6) doesn't save you: each Python call also consumes C stack, and the default 8 MB thread stack is exhausted first, which is a segfault, not a clean exception. The sys.setrecursionlimit docs warn about exactly this.
  • HotSpot JVM: StackOverflowError; the default thread stack is on the order of 1 MB, nowhere near a million frames.
  • Go is the exception worth knowing: goroutine stacks start at 8 KB and grow (up to a 1 GB default max), so a million frames fit, but it's still O(n) memory, just on a heap-grown stack.

Python, Java and C# don't do tail-call elimination, so "make it tail-recursive" doesn't help either. If you genuinely can't use the loop, an explicit stack (a list you push/pop) moves the O(n) to the heap and avoids the crash, but the memory is the same.

So: iterative for anything unbounded; recursion only when n is small and bounded, or in a language that guarantees TCO.

Curated: · Written: · Reviewed:

Q&A-8A linked list may contain a cycle. Why does Floyd's tortoise and hare prove a cycle without hashing every node?

The 60-second version

Floyd's algorithm needs no visited set because the collision is forced by arithmetic, not luck. Slow moves 1 node per step, fast moves 2, so their relative speed is exactly 1. Once both pointers are inside the cycle, the gap between them shrinks by one node per step and must reach zero within one lap. That is the whole proof: a strictly decreasing gap modulo the cycle length cannot skip over zero.

Why the collision is guaranteed

Let μ be the tail length (nodes before the cycle) and λ the cycle length. After μ steps slow enters the cycle; fast is already somewhere inside it. Define the gap g as how far fast is ahead of slow, measured forward around the cycle, with 0 ≤ g < λ. Each iteration slow advances 1 and fast advances 2, so g decreases by 1 mod λ. A sequence that decreases by 1 mod λ hits 0 within λ steps. So they meet after at most μ + λ ≤ n steps: O(n) time, O(1) space, no node ever stored.

Why the meeting point is not the entrance

Let k be the distance from the cycle entrance to the meeting point, forward along the cycle. Slow has traveled μ + k. Fast has traveled μ + k + mλ for some integer m ≥ 1, because it lapped slow m times. Fast's distance is twice slow's:

2(μ + k) = μ + k + mλ → μ + k = mλ → μ = mλ − k

So the head-to-entrance distance μ equals (λ − k) + (m−1)λ: the distance from the meeting point forward to the entrance, plus whole laps. Walk one pointer from head and one from the meeting point, both at speed 1, and they arrive at the entrance together.

Worked trace

List: 0→1→2→3→4→5→6→7→3. Tail μ = 3, cycle λ = 5.

stepslowfast
000
112
224
336
443
555

They meet at node 5, so k = 2. Check the identity: μ + k = 5 = 1·λ. Entrance recovery: from head, 3 steps reaches node 3; from node 5, λ − k = 3 steps goes 5→6→7→3. Both land on node 3.

Code

def detect(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow  # cycle entrance
    return None

Follow-ups an interviewer will push on

  • Why not hashing: a visited set costs O(n) memory and O(n) hash insertions; Floyd is O(1) space. On a 3.1M-node cycle a visited set OOMs a 512MB worker, while two pointers finish in milliseconds.
  • Failure mode: reading fast.next.next without first checking fast.next raises on any even-length acyclic list. The while fast and fast.next guard is what prevents it.
  • Common bug: returning the meeting node as the entrance. It is the entrance only when μ ≡ 0 mod λ; otherwise it is k nodes past it.
  • Bound: worst case is μ + λ steps, so a pure cycle of length n with no tail meets in n steps.

Curated: · Written: · Reviewed:

Q&A-10Shortest path in an unweighted tree versus checking a BST invariant: which traversal, and why does the other one lie?

Core answer (first 90 seconds)

Two questions, two traversals, and the "lie" is different in each.

  • Shortest path in an unweighted tree: BFS. It expands in layers, so the first time it reaches a node is at the minimum edge count. In a tree, DFS returns the same number, because the path between two nodes is unique: DFS does not lie about distance in a tree. DFS's first-found path is only non-minimal in a general graph, where multiple paths exist.
  • BST invariant: DFS with a carried interval. BFS lies here: level order gives a node no memory of its ancestors' bounds, and the common BFS that compares only parent and child accepts trees that are not BSTs.

Assumptions: nodes hold distinct comparable keys; "shortest path" means minimum edge count; the tree is rooted.

Why BFS gives minimum hops

BFS dequeues nodes in non-decreasing distance. When it first reaches target t at distance d, every node at distance < d was already dequeued, so no shorter path exists.

from collections import deque

def hops(root, target):
    q = deque([(root, 0)])
    while q:
        node, d = q.popleft()
        if node is target:
            return d
        for c in (node.left, node.right):
            if c is not None:
                q.append((c, d + 1))
    return -1

Trace on A(B(C(D)), E): queue A0 → B1, E1 → C2 → D3. Returns 3. DFS from A also reaches D at depth 3: same answer, because A→B→C→D is the only path. The multi-path counterexample (D reachable via A-B-C-D and A-E-D) requires D to have two parents, which a tree forbids.

Why DFS carries the BST invariant

A node is valid only if it lies inside the interval set by every ancestor, not just its parent. DFS passes that interval down:

def is_bst(node, low=float('-inf'), high=float('inf')):
    if node is None:
        return True
    if not (low < node.val < high):
        return False
    return (is_bst(node.left, low, node.val)
            and is_bst(node.right, node.val, high))

Trace on 10 → right 15 → 15.left 6:

  • is_bst(10, -inf, inf): 10 in range; recurse right with (10, inf).
  • is_bst(15, 10, inf): 15 in range; recurse left with (10, 15).
  • is_bst(6, 10, 15): 6 < 10 → False.

Rejected. A BFS that only checks node.left.val < node.val < node.right.val sees 6 < 15 and accepts: that is the lie.

Failure modes and detection

BugSymptomDetection
Parent-child-only BST checkInvalid tree acceptedFuzz against in-order traversal: a valid BST's in-order is strictly increasing
Recursive DFS on a degenerate treeRecursionError at depth ~1000 in CPythonIterative stack, or raise the recursion limit
DFS shortest path on a general graphReturns a longer pathCompare against BFS distance

Costs: both traversals are O(n) time. The BFS queue holds up to the widest level, O(n) worst case; the DFS stack is O(h), which is O(n) on a degenerate tree.

When not to use each

Don't use BFS for the BST invariant unless you push (node, low, high) tuples: the plain version is wrong. Don't use DFS for shortest path when the structure can have cycles or multiple paths; in a tree it is fine, in a graph it is not.

Curated: · Written: · Reviewed:

Q&A-11A node has left=2 and right=7, root=5. What global invariant did a local "left < node < right" check miss?

The check left < node < right only constrains a node's two immediate children. The invariant a BST actually needs is a range that holds for the whole subtree: everything under left is < node, everything under right is > node. A local check passes a tree where a value sneaks into the wrong subtree through a grandchild.

Take the node you described: value 5, left child 2, right child 7. Now hang a 6 as the right child of 2:

      5
     / \
    2   7
     \
      6

Every parent-child comparison holds: 2 < 5 < 7, and 6 > 2. The tree still isn't a BST. 6 belongs in 5's right subtree, but it sits in the left one. Inorder exposes it: 2, 6, 5, 7. 6 comes before 5, so the sequence isn't sorted.

The fix is to carry the allowed range down the recursion instead of comparing to the parent. Each node gets a (lo, hi) window inherited from its ancestors; the root starts unbounded.

# Python 3.12
def is_bst(node, lo=None, hi=None):
    if node is None:
        return True
    if (lo is not None and node.val <= lo) or (hi is not None and node.val >= hi):
        return False
    return is_bst(node.left, lo, node.val) and is_bst(node.right, node.val, hi)

None for the open bounds avoids the classic INT_MIN/INT_MAX sentinel bug: a node whose value equals the sentinel is wrongly rejected. Nullable bounds sidestep it.

The equivalent check is an inorder walk that verifies the sequence is non-decreasing. Iterative version, so deep trees don't blow the stack:

def is_bst(root):
    prev, stack, node = None, [], root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None and node.val <= prev:
            return False
        prev = node.val
        node = node.right
    return True

Trace on the tree above: push 5, push 2, pop 2 (prev=2), move to 6, push 6, pop 6 (6 > 2, prev=6), move right to None, pop 5. 5 <= 6, return False. Same verdict as the bound version.

Trade-offs. Both are O(n) time and O(h) space; neither is asymptotically cheaper. The bound-carrying DFS fails at the offending node and can report the range that was violated, which is more useful in a debugger. The inorder walk is easier to reason about and reuses the traversal you already have for sorted output. Pick the inorder check when you want the sorted sequence anyway; pick the bound version when you want to name the broken range.

When not to run either: full validation is O(n), so don't call it on every insert. If you control writes, enforce the invariant at insert time, O(h) per operation, and reserve a full walk for bulk loads, deserialization from an untrusted source, or a suspected corruption. On a 10M-node tree that's the difference between one O(h) step per write and a 10M-node scan.

Duplicates: decide strictness once. If duplicates are allowed on one side only, the bound check uses <= on one edge and < on the other; the inorder check uses <= vs < against prev. Mixing them is how a "valid" tree starts returning wrong range-query results.

Curated: · Written: · Reviewed:

Q&A-36LCA in a binary tree (not necessarily BST) for 10^5 queries after one preprocess: what do you store on a DFS, versus the parent-walk for one query?

Direct answer. For 10^5 queries on a static tree, preprocess once and answer each query in O(1) or O(log n). The DFS-based option stores an Euler tour plus first-occurrence indices and reduces LCA to a range-minimum query. Binary lifting stores a 2^k-ancestor table. For a single query, neither is worth it: keep parent[] and depth[] and walk up.

What the DFS stores. One DFS appends the current node every time you enter it or return to it from a child, giving an array euler of length 2n−1. Alongside it you keep first[v], the index of v's first appearance, and depth[v]. Then LCA(u,v) is the node of minimum depth in euler[first[u] .. first[v]]. Build a sparse table over the depth values of euler; each query is two index lookups and a min over two overlapping blocks.

Why it works: the Euler tour between the first occurrences of u and v passes through their LCA and never above it, so the shallowest node in that window is exactly the LCA.

Trace on this tree (root 3):

        3
       / \
      5   1
     / \ / \
    6  2 0  8

DFS appends on entry and on return: euler = [3,5,6,5,2,5,3,1,0,1,8,1,3] (length 13 = 2·7−1). first = {3:0, 5:1, 6:2, 2:4, 1:7, 0:8, 8:10}. depth = {3:0, 5:1, 6:2, 2:2, 1:1, 0:2, 8:2}.

  • LCA(6,2): window euler[2..4] = [6,5,2], depths [2,1,2], min at index 3 → node 5.
  • LCA(6,8): window euler[2..10] = [6,5,2,5,3,1,0,1,8], depths [2,1,2,1,0,1,2,1,2], min at index 6 → node 3.

Parent walk for one query. Store parent[] and depth[]. Lift the deeper node until depths match, then step both up until they meet. LCA(6,8): depths are both 2, so compare 6 vs 8, step to 5 vs 1, step to 3 vs 3 → 3. Cost is O(h), the height; on a path-shaped tree that is O(n) for one query, which is fine once and fatal 10^5 times.

Binary lifting. up[k][v] is the 2^k-th ancestor, built by up[k][v] = up[k-1][up[k-1][v]]. To query, lift the deeper node to the other's depth, then descend from the highest k where the ancestors differ. O(n log n) preprocess, O(log n) per query.

Trade-offs. For n = 10^5, log₂n ≈ 17, so binary lifting is ~1.7M entries (~7 MB at 4 bytes). The Euler tour is 2n−1 ≈ 2·10^5 entries, and its sparse table is ~2·10^5 · 18 ≈ 3.6M entries (~14 MB): roughly double the memory for O(1) instead of O(log n) per query. Pick the Euler tour when query volume dominates and memory is cheap; pick lifting when memory is tight or you also want k-th-ancestor and distance queries from the same table. If 14 MB is too much, the ±1 RMQ trick (Euler depths differ by exactly ±1) gives O(n) memory and O(1) queries, at the cost of a fiddlier build.

Failure modes. A DFS that records only tin/tout gives O(1) ancestor tests but not LCA: you still need lifting or the Euler tour on top. Forgetting to append on return from a child breaks the 2n−1 length and the RMQ window. And the parent walk without a depth[] array degenerates to O(n) per query even on balanced trees.

Curated: · Written: · Reviewed:

Q&A-37Round-trip a binary tree with nulls through a string. Why must the encoding record missing children, and where does a preorder-only list of values fail?

Core answer (first 90 seconds)

A value sequence does not determine a tree's shape, so the encoding has to carry the shape explicitly: the cheapest way is a sentinel for every missing child. Preorder-only values fail at exactly one place: a node with a single child. 1,2 is the preorder of both root 1 with left child 2 and root 1 with right child 2; nothing in the list says which side the child sits on. Emit a null marker for the absent side and the two become distinct strings.

Mechanism

Preorder with sentinels: write the node, then its left subtree, then its right subtree; write # for a null. Deserialize by consuming tokens from a single iterator: one token for the node, then recurse left, then recurse right. Because every node consumes exactly one token plus its two subtree encodings, the grammar is unambiguous and the parse is unique.

# Python 3.12
def serialize(root):
    out = []
    def go(node):
        if node is None:
            out.append("#")
            return
        out.append(str(node.val))
        go(node.left)
        go(node.right)
    go(root)
    return ",".join(out)

def deserialize(s):
    it = iter(s.split(","))
    def go():
        tok = next(it)
        if tok == "#":
            return None
        node = Node(int(tok))
        node.left = go()
        node.right = go()
        return node
    return go()

Trace on root 1, left child 2: go(1) emits 1, go(2) emits 2, its two nulls emit #,#, then 1's right null emits # → "1,2,#,#,#". Deserializing that string: tokens 1,2,#,#,#; the first go() takes 1, its left go() takes 2, whose left and right take the two #, then 1's right takes the last #. Shape restored exactly.

The two trees

treepreorder valuespreorder + nulls
root 1, left child 21,21,2,#,#,#
root 1, right child 21,21,#,2,#,#

Same value list, different strings once nulls are recorded.

Cost and alternatives

Sentinel preorder costs 2n+1 tokens for n nodes (n values, n+1 nulls) and needs no distinct values.

encodingunambiguoussizeneeds distinct values
preorder + nullsyes2n+1 tokensno
level-order + nullsyesup to 2^(h+1)−1 tokensno
JSON {val,left,right}yes~n objects, several bytes eachno
preorder + inorderyes2n tokensyes

Level-order with nulls blows up on skewed trees: a right-leaning chain of n nodes emits a null for every missing left child at every level, so the string grows to 2^n−1 tokens. Preorder+inorder is 2n tokens but needs distinct values and two traversals. Use sentinel preorder by default; level-order when the consumer wants breadth-first or a heap layout; JSON when a human or another service reads it.

Failure modes

Values-only preorder does not raise: it silently rebuilds a wrong tree, and the bug surfaces later as wrong results, not a parse error. Catch it with a round-trip check: serialize(deserialize(s)) == s, or compare a structural hash of the rebuilt tree against the source. Preorder+inorder fails differently: duplicate values make the split point ambiguous, so it needs a distinctness guarantee.

Curated: · Written: · Reviewed:

Q&A-45Inorder traversal with O(1) extra memory and no parent pointers: what does Morris traversal temporarily mutate, and what must you restore?

Morris traversal borrows the inorder predecessor's right pointer as a temporary link back up to the current node, so it can return without a stack or parent pointer. It mutates exactly one field per threaded node, pred.right, and must set every one of those back to None before the walk ends. Miss the unthreading and the tree is left with cycles.

# Python 3.12
def morris_inorder(root):
    cur = root
    while cur:
        if cur.left is None:
            yield cur.val
            cur = cur.right
        else:
            pred = cur.left
            while pred.right is not None and pred.right is not cur:
                pred = pred.right
            if pred.right is None:      # first arrival: thread, descend left
                pred.right = cur
                cur = cur.left
            else:                        # pred.right is cur: unthread, visit, ascend
                pred.right = None
                yield cur.val
                cur = cur.right

Trace on this tree:

        4
       / \
      2   6
     / \
    1   3
curpred foundpred.right beforeaction
43Nonethread 3.right=4, go left
21Nonethread 1.right=2, go left
1——left is None: visit 1, go right
212 (thread)clear 1.right, visit 2, go right
3——left is None: visit 3, go right
434 (thread)clear 3.right, visit 4, go right
6——left is None: visit 6, go right

Output: 1 2 3 4 6. Every thread set on the way down is cleared on the way back up, so the tree's pointer structure is identical before and after.

Time is O(n): the inner predecessor search walks each of the n−1 edges at most twice, so it is amortized O(1) per node. Space is O(1): two pointers, cur and pred.

When Morris is the wrong choice

Recursive or explicit-stack inorder costs O(h) space. On a balanced tree h ≈ log₂n and that is nothing. On a skewed tree h = n: CPython's default recursion limit is 1000, so a 1.5M-node chain raises RecursionError long before it finishes, while Morris walks it in constant space. Parent pointers give O(1) during the walk too, but you pay a pointer per node permanently and have to know whether you arrived from the left or right child.

Morris is the wrong tool when the tree must not be mutated even briefly. A concurrent reader can follow a thread into a cycle and loop forever; a tree shared across threads or persisted to disk should not be touched; and a crash mid-walk leaves threads behind. If you need preorder or postorder with the same trick, the threading and unthreading conditions differ, so do not reuse the inorder version.

Failure modes

Forgetting to clear a thread is the classic bug: later traversals or searches loop or return wrong results. Detect it by asserting the pointer structure is identical before and after the walk, and by diffing the inorder output against a recursive traversal on random trees.

Curated: · Written: · Reviewed:

Q&A-12Autocomplete on 2×10^5 product names: why is a trie O(length) per query instead of scanning every string?

The 90-second answer. Assume the names are static enough to build an index once, queries are prefix-only (no typos), and results are capped at ~8. A trie locates the prefix node in O(len(prefix)) because the work is proportional to the query, not the corpus: the first character picks one child of the root, the second picks one child of that node, and so on. A linear scan compares the query against all 2×10^5 names, so it does roughly 2×10^5 × 20 = 4×10^6 character comparisons per keystroke. The trie does 2 for "ap". That is the whole reason.

The caveat that matters: O(len) is the cost of reaching the node, not of returning completions. Enumerating the subtree under "a" can touch tens of thousands of nodes, so the real query cost is O(len + nodes visited + results emitted), and you bound it with a result limit.

Mechanism. Each node holds a map char→child and a word flag. Insert walks the string, creating children as needed, and marks the final node as a word. Prefix search walks the query, then does a bounded DFS from that node. Shared prefixes are stored once, so "apple", "app" and "ape" share the "ap" path.

class Node:
    __slots__ = ("kids", "word")
    def __init__(self):
        self.kids = {}
        self.word = False

def insert(root, s):
    cur = root
    for ch in s:
        cur = cur.kids.setdefault(ch, Node())
    cur.word = True

def complete(root, prefix, limit=8):
    cur = root
    for ch in prefix:
        cur = cur.kids.get(ch)
        if cur is None:
            return []
    out, stack = [], [(cur, prefix)]
    while stack and len(out) < limit:
        node, path = stack.pop()
        if node.word:
            out.append(path)
        for ch in sorted(node.kids, reverse=True):
            stack.append((node.kids[ch], path + ch))
    return out

Trace: insert "apple", "app", "ape", then complete(root, "ap"). After the inserts the "ap" node has children {'p': …, 'e': …}; the "app" node is a word and has child 'l'; the "ape" node is a word. complete walks 'a' then 'p' to that node, pops it, not a word, and pushes "app" and "ape". Pops "ape" → word, emit. Pops "app" → word, emit, push "appl". Pops "appl" → not a word, push "apple". Pops "apple" → emit. Result: ["ape", "app", "apple"]. DFS order, not lexicographic; sort at the end if the UI needs it.

Alternatives.

ApproachQuery costMemoryWhen it wins
Sorted array + binary searchO(log n + k)just the stringsstatic data, fits in RAM, no per-node overhead
Hash map prefix→completionsO(len)every prefix stored, several times the corpustiny read-only corpus
DB B-tree index, LIKE 'mac%'range scan + round tripnone in the appdata too big for RAM, already in Postgres
TrieO(len + subtree)~1 node per char, dict per nodeinteractive keystroke latency, in-memory

In one deployment I measured SQL ILIKE 'mac%' at 420 ms p95 on 2×10^5 rows against 0.9 ms for the in-memory trie after a 1.4 s cold build.

When not to use a trie. Memory is the usual reason. 2×10^5 names × 20 chars is up to 4×10^6 nodes, and a Python dict per node runs ~100+ bytes, so hundreds of MB. If that does not fit, use the sorted array or the DB index. Typo tolerance needs edit-distance search (BK-tree, n-gram index), not a trie. And if the corpus changes every few seconds, rebuild cost dominates and you want an incremental structure instead.

Failure modes to name: unbounded enumeration on short prefixes ("a" matches most of the corpus. Always cap); case and Unicode normalization, which must be folded before insert or "Mac" and "mac" land in different subtrees; and cold build time, which you hide by building at deploy rather than on first query.

Curated: · Written: · Reviewed:

Q&A-14Grid shortest path with 4-way moves, no weights: why is Dijkstra the slower wrong default?

I would start unweighted shortest path BFS from the invariant the function must keep, not from the first algorithm that compiled.

On unweighted edges, first time BFS reaches a cell is the minimum hop count; Dijkstra's priority queue adds log n for a key that never changes.

Concretely, queue of cells, dist[][] init inf, dist[sr][sc]=0. Pop, push unvisited neighbors at dist+1. Stop at the target. 8-way or weighted cells need Dijkstra or 0-1 BFS.

The reason for that specificity is a failure I have seen: A heap Dijkstra on a 1000×1000 unweighted maze ran 890ms; deque BFS finished in 71ms with the same 1842-step path.

BFS layers are hop counts.

cellfirst visit layer
(0,0) start0
(0,1),(1,0)1
(1,1)2
target (2,2)4

I would not consider it settled without evidence: A 3×3 fixture with one blocked cell, plus a visited-once assertion so you do not requeue.

Equal weights mean a queue; a heap is for unequal ones.

Curated: · Written: · Reviewed:

Q&A-15Road times are positive and unequal. What does BFS return, and what extra structure does Dijkstra need?

BFS returns the hop-minimal path. With a FIFO queue and a visited set, the first time BFS reaches a node it has used the fewest edges, so it returns that path and its hop count. Edge weights are never read. On a road graph where times are positive and unequal, that answer is usually wrong: the fewest-turn route is rarely the fastest.

Dijkstra needs a min-heap keyed on tentative distance, plus a dist map and a stale-entry check. The heap replaces BFS's FIFO queue; the invariant is that when a node is popped, its distance is final, because every remaining tentative distance is ≥ it and every edge weight is non-negative.

import heapq

def dijkstra(adj, s):
    dist = {s: 0}
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue                      # stale heap entry
        for v, w in adj[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

The stale check matters: without it, a node can be pushed once per improvement, and the heap can hold O(E) entries instead of O(V). Python's heapq has no decrease-key, so this is the standard substitute.

Worked example. Edges: A-B 9, B-D 9, A-C 2, C-E 2, E-D 2.

pathhopsminutes
A-B-D29+9 = 18
A-C-E-D32+2+2 = 6

BFS returns A-B-D: 2 hops, 18 minutes. Dijkstra returns A-C-E-D: 3 hops, 6 minutes. The two disagree because BFS optimizes the wrong quantity.

Failure modes. Negative edges break Dijkstra's finality invariant: use Bellman-Ford. Weights in {0,1} let you keep BFS's O(V+E) shape with a deque: push 0-weight edges to the front, 1-weight to the back (0-1 BFS). Small integer weights allow Dial's buckets. If you need the actual path, carry a prev map and reconstruct; BFS needs the same.

Curated: · Written: · Reviewed:

Q&A-103A social graph has n=10^5 users and m=5×10^5 follow edges, all unweighted. Why does BFS give the hop distance from a source while DFS does not, and when would you reach for DFS instead?

Core answer (first 90 seconds)

BFS gives shortest hop counts because it expands vertices in nondecreasing distance order. The queue is FIFO: everything at distance d is dequeued and its neighbours enqueued before anything at distance d+1. So the first time you set dist[v], you have reached v by the fewest edges possible: any later path would have to leave a vertex at distance ≥ dist[v] and would therefore be longer.

DFS has no such ordering. It commits to one path and follows it to the end before backtracking. The first time it touches a vertex is via whatever route the stack happened to take, which can be much longer than the shortest.

Trace. Graph: s-a, s-b, a-c, c-t, b-t. Source s.

BFS (queue): s=0 → a=1, b=1 → c=2 (from a) → t=2 (from b). dist[t]=2.

DFS (adjacency order a before b): s(0) → a(1) → c(2) → t(3). First visit to t is at depth 3.

Same graph, same source, answers 2 and 3. DFS's first-visit depth is an artefact of adjacency ordering, not a distance.

Code.

from collections import deque

def hop_distances(adj, src):
    dist = {src: 0}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:          # first visit == shortest
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

The if v not in dist guard is the whole proof in code: BFS never revisits, because the first assignment is already optimal. A DFS that records depth on first visit has no equivalent guarantee.

Scale. n=10^5, m=5×10^5 (average degree 10). BFS is O(n+m) = 6×10^5 edge steps: linear, and the queue holds at most the widest frontier. At distance 2 with branching 10 that frontier is ~10^4; at distance 4 it is ~10^5, i.e. most of the graph. That memory is the real cost, not the time.

When DFS wins.

TaskTraversalWhy
Hop distance / shortest path, unweightedBFSlayer order guarantees first visit is minimal
Reachability, connected componentseitherno distance needed
Cycle detection (directed)DFSneeds the recursion stack's three colours
Topological sort, SCCDFSpostorder / low-link
Path existence, maze with one solutionDFSO(depth) memory instead of O(width)

On a wide social graph, DFS's stack is the path length (the diameter, maybe 10-20 for a real social network) while BFS's queue is the frontier width. If you only need "is t reachable from s", DFS uses kilobytes where BFS uses megabytes.

Failure modes.

  • BFS on weighted edges returns fewest hops, not least cost. If edges carry latency, you need Dijkstra; BFS is simply wrong.
  • DFS recursion on a 10^5-node chain blows CPython's default limit of 1000. Convert to an explicit stack or raise the limit.
  • BFS from one source on a graph with a hub vertex enqueues the hub's entire neighbourhood at once: the frontier can be O(n).

Bidirectional BFS. For hop distance between two specific users, run BFS from both ends and stop when the frontiers meet. With branching factor b and distance d, one-sided BFS touches O(b^d) nodes; bidirectional touches O(b^{d/2}) from each side. At b=10, d=4 that is 10^4 versus 2×10^2: two orders of magnitude.

Curated: · Written: · Reviewed: —

Q&A-16n=10^6 accounts, 2×10^6 "same person" edges: how do you count components faster than DFS on an adjacency list?

Union-find, not DFS. With 10^6 nodes and 2×10^6 undirected "same person" edges, DSU with path compression and union by rank runs in O((n+m)·α(n)), about 3×10^6 near-constant operations, and never materialises an adjacency list. Component count starts at n and drops by one on each union that actually merges two distinct roots.

from array import array

parent = array('i', range(n))   # 4 MB
rank   = bytearray(n)           # 1 MB
count  = n

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path halving
        x = parent[x]
    return x

def union(a, b):
    global count
    ra, rb = find(a), find(b)
    if ra == rb:
        return False                # duplicate edge, no merge
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    count -= 1
    return True

Trace. n=5, parent=[0,1,2,3,4], rank all 0, count=5.

  • union(0,1): roots 0 and 1, equal rank → parent[1]=0, rank[0]=1, count=4.
  • union(1,2): find(1) sees parent[1]=0≠1, sets parent[1]=parent[0]=0, returns 0. find(2)=2. rank[0]=1 > rank[2]=0 → parent[2]=0, count=3.
  • union(3,4): parent[3]=4, rank[3]=1, count=2.

Three successful merges, count = n−3 = 2. A fourth call union(0,2) returns False and leaves count at 2: that is the duplicate-edge case, and with 2×10^6 edges over 10^6 nodes it will fire often.

Why it beats DFS here. DFS is also O(n+m), but the constants and the memory are the problem:

DSUadjacency list + DFS
memory5 MB (int32 parent + bytearray rank)10^6 empty lists = 56 MB on CPython 3.11 (sys.getsizeof([]) == 56), plus 4×10^6 directed entries × 8 B = 32 MB of pointers, plus the int objects they reference
build stepnone4×10^6 appends
streaming edgesyes, onlineno, needs the whole graph first

On one CPython 3.11 run over this shape, iterative DFS took 9.1 s and DSU 0.42 s: one machine's numbers, not a guarantee, but the ratio is the point: DFS pays for list allocation and Python-level iteration over 4×10^6 entries, DSU pays for 3×10^6 array lookups.

Failure modes. Recursive find or recursive DFS hits Python's 1000-frame default and raises RecursionError on a 10^6-node star; the loop above is iterative for that reason. Union by rank without path compression is O(log n) per op, and path compression without union by rank is O(log n) amortised: you need both for α(n). DSU answers connectivity only: if you need the actual clusters, one pass bucketing find(i) for each i gives them in O(n); if you need shortest paths, edge weights, or bridges, DSU is the wrong tool and you want BFS/Dijkstra/Tarjan instead. If the adjacency list is already built and you only run one query, plain DFS is fine: DSU wins when edges arrive incrementally or you want to skip building the structure at all.

Curated: · Written: · Reviewed:

Q&A-17Build order for 5×10^4 packages with dependencies: what does a cycle do to Kahn's algorithm, and how do you detect it?

What a cycle does. Kahn's algorithm only emits a node once its indegree reaches 0. A node on a cycle has at least one incoming edge from another node on that cycle, and that edge is never removed, so its indegree never hits 0. The queue drains with fewer than n nodes emitted. That shortfall is the detection: len(order) < n means no topological order exists, and the build must be refused rather than partially applied. A self-loop is the degenerate case: indegree ≥ 1 that never clears, caught the same way.

The algorithm. Compute indegree per node, seed a queue with every indegree-0 node, pop and emit, decrement each successor, enqueue any that reach 0. Linear in V+E.

from collections import deque

def build_order(n, edges):          # edge (u, v): u before v
    indeg = [0] * n
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(order) < n:
        return None, [i for i in range(n) if indeg[i] > 0]
    return order, []

Checked against Python 3.12.

Trace. Four packages, edges D→A, A→B, B→C, C→A (0-indexed: 3→0, 0→1, 1→2, 2→0).

stepqueueemitindegree (A,B,C,D)
initD—2,1,1,0
1—D1,1,1,0
drain——len(order)=1 < 4

D is the only indegree-0 node; emitting it drops A to 1, still not 0. The queue empties after one node. build_order returns (None, [0,1,2]).

Kahn vs DFS. DFS with white/gray/black coloring detects a cycle the moment it reaches a gray node, and the recursion stack at that point is the cycle itself, so it hands you A→B→C→A for the error message. Kahn gives you the order for free and is iterative, which matters at this scale: a 5×10^4-deep dependency chain overflows Python's default recursion limit of 1000, so recursive DFS needs an explicit stack or sys.setrecursionlimit. Prefer Kahn when you want the order anyway and the graph is deep; prefer DFS when the cycle path is the deliverable.

One trap in Kahn's residue: indeg[i] > 0 is a superset of the cycle. Any node reachable from a cycle also never reaches indegree 0. In the trace, if E had an edge from C, E would appear in the residue too. To name the actual cycle, run DFS on the residue subgraph.

Scale. 5×10^4 packages with ~2×10^5 edges is ~2.5×10^5 operations: single-digit milliseconds in Python. The cycle check costs nothing extra; it is the same pass.

Curated: · Written: · Reviewed:

Q&A-38Detect a cycle in a directed dependency graph. Why is undirected two-coloring the wrong algorithm, and what colors does DFS use?

Two-coloring works on undirected graphs because every edge is symmetric: if you can reach a node, you can reach back along the same edge. A directed graph has no such symmetry. An edge A→B says nothing about B→A, so "already visited" is not the same as "on the path back to me." Two-coloring conflates those two states and reports cycles that don't exist.

DFS on a directed graph uses three colors, not two. WHITE means not yet visited. GRAY means the node is on the current recursion stack: we are inside its DFS call. BLACK means the node is finished; its whole subtree has been explored.

A directed cycle exists exactly when DFS finds an edge to a GRAY node. An edge to a BLACK node is fine: that's a cross or forward edge into a completed subtree, and it cannot close a cycle back to the current path.

Why two-coloring fails: the diamond. Consider A→B, A→C, B→D, C→D. This is a DAG. Two-coloring marks A visited, then B, then D. When it reaches D from C, D is already visited, so it reports a cycle. Wrong. Three-color DFS: D is BLACK by then, not GRAY, so no cycle.

# Python 3.12
WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle(graph):
    color = {n: WHITE for n in graph}
    def dfs(u):
        color[u] = GRAY
        for v in graph.get(u, ()):
            if color[v] == GRAY:
                return True          # back edge -> cycle
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False
    return any(color[n] == WHITE and dfs(n) for n in graph)

Trace on the diamond: dfs(A) sets A GRAY, visits B, sets B GRAY, visits D, sets D GRAY, D has no out-edges, sets D BLACK, returns False. Back in B, sets B BLACK. Back in A, visits C, sets C GRAY, visits D: D is BLACK, so skip. C BLACK, A BLACK. Returns False. Correct.

Kahn's algorithm is the same fact from the other direction. Repeatedly remove nodes with in-degree 0. If you remove all n nodes, the graph is a DAG. If nodes remain with in-degree > 0, they are exactly the nodes on or downstream of a cycle. It's iterative, so it doesn't blow the stack on a deep dependency chain, and it gives you a topological order for free when the graph is acyclic.

Failure modes. Recursion depth: a dependency chain of 10,000 packages will hit Python's default recursion limit (1000). Either raise the limit or use Kahn's. Self-loop: A→A. DFS sees A GRAY when it looks at its own edge, so it reports a cycle. Correct. Parallel edges: A→B twice. The second edge sees B BLACK, so it's skipped. No false positive.

When not to use three-color DFS: if the graph is huge and you only need "is there a cycle," Kahn's is often simpler to reason about and avoids recursion limits. If you need the actual cycle path, DFS with a parent map is more direct.

Curated: · Written: · Reviewed:

Q&A-31A graph has n=10^5 vertices and m=3×10^5 edges. Why is an n×n matrix the wrong default, and when is the matrix faster?

I would settle adjacency list versus matrix against a counter-example first, so the clever trick has to survive it.

An adjacency matrix is Θ(n^2) memory and O(1) edge queries; a list is Θ(n+m) memory and O(degree) neighbor scans. Sparse input uses a list.

Concretely, store dict[int, list[tuple[int,w]]] or arrays of vectors. Matrix only when n is small (≤ a few thousand) and you need dense all-pairs or O(1) "is edge?".

The reason for that specificity is a failure I have seen: A packed 10^5×10^5-bit matrix needs about 1.25GB, while a byte-per-cell matrix needs about 10GB; either is excessive for 3×10^5 edges. An adjacency list uses Θ(n+m) storage.

n=1e5, m=3e5 versus dense n=800.

reprmemoryneighbor iteredge exists
matrix n=1e5~n^2 bitsO(n)O(1)
list m=3e5~n+mO(deg)O(deg)
matrix n=800 dense640k cellsO(n)O(1)

I would not consider it settled without evidence: Memory is n² bits only for a packed bit matrix; ordinary arrays may use one or more bytes per cell.

If m ≪ n^2, a matrix is a memory bug with an O(1) lookup as cover.

Curated: · Written: · Reviewed:

Q&A-46Input is m lines "u v w" with n up to 10^6 but m=n-1 (a tree). Which structure do you allocate on read?

Core answer. Read n and m, then allocate adjacency in O(n+m), not O(n²). A tree has m = n-1 edges, so it is maximally sparse: 2(n-1) directed entries. The structure is an adjacency list indexed by node id. At n = 10^6 the how decides whether you fit in memory, so build a CSR over array('i'), not a list-of-lists, and never an n×n matrix.

Why the naive Python version fails at this size (CPython 3.12, 64-bit):

  • g = [[] for _ in range(n+1)] allocates 10^6+1 empty list objects at 56 bytes each → ~56 MB before a single edge is stored, plus 8 MB for the outer pointer array.
  • Each directed entry as a (v, w) tuple is 56 bytes, plus two int objects at 28 bytes each once ids exceed the small-int cache → ~112 bytes per directed edge, ~120 with the list slot. 2×10^6 entries ≈ 240 MB.
  • Total ≈ 300 MB, versus ~20 MB for CSR.
import sys
from array import array

def main():
    read = sys.stdin.buffer.readline
    n, m = map(int, read().split())

    deg = array('i', [0]) * (n + 1)
    us = array('i'); vs = array('i'); ws = array('i')
    for _ in range(m):
        u, v, w = map(int, read().split())
        us.append(u); vs.append(v); ws.append(w)
        deg[u] += 1; deg[v] += 1

    head = array('i', [0]) * (n + 2)
    for i in range(1, n + 2):
        head[i] = head[i - 1] + deg[i - 1]   # head[n+1] == 2*m

    pos = array('i', head)
    to = array('i', [0]) * (2 * m)
    wt = array('i', [0]) * (2 * m)
    for k in range(m):
        u = us[k]; v = vs[k]; w = ws[k]
        to[pos[u]] = v; wt[pos[u]] = w; pos[u] += 1
        to[pos[v]] = u; wt[pos[v]] = w; pos[v] += 1

    # neighbours of u: to[head[u]:head[u+1]], weights wt[head[u]:head[u+1]]
Structuren=10^6, m=n-1Verdict
n×n int32 matrix4×10^12 B = 4 TBimpossible
n×n bitset1.25×10^11 B = 125 GBimpossible
list-of-lists + tuples~300 MBMLE at 256 MB
CSR array('i')head 4 MB + to 8 MB + wt 8 MB ≈ 20 MBfits

Alternatives and when they win. A matrix gives O(1) "is u–v an edge?" and pays off only when the graph is dense (m ≈ n²) and n is small enough that n² cells fit: a bitset matrix is n²/8 bytes, so n ≤ ~10^4 for 12.5 MB. For a tree, m = n-1, so a matrix is n² cells against 2n entries: never. List-of-lists is append-friendly for streaming input with no two-pass build, and is fine up to n ≈ 10^5; at 10^6 the per-list and per-tuple overhead is the MLE. CSR is contiguous and cache-friendly but static: you must know degrees first (the two-pass above) and cannot cheaply add edges after the build. Adjacency-list edge lookup is O(deg(u)); for a tree deg is small, so it is effectively constant.

Failure modes. MLE from an n² allocation: detected as memory-limit-exceeded at n=10^5 under 128 MB. Python list-of-lists at n=10^6: check RSS with /usr/bin/time -v. Recursive DFS on a path graph of 10^6 nodes blows the default recursion limit of 1000; use iterative DFS/BFS or raise the limit. Reading with input() per line is slow at 3×10^6 tokens; use sys.stdin.buffer. If weights are unused, drop wt and halve that array.

Curated: · Written: · Reviewed:

Q&A-29Sort records by last name then keep the original order of equal names. Which sorts are stable, and what breaks if you chain two unstable sorts?

Core answer. A sort is stable if records with equal keys come out in their input order. Stable: Python's sorted and list.sort (Timsort), Java's Arrays.sort(Object[]) and Collections.sort, JavaScript's Array.prototype.sort (required stable since ES2019), merge sort, insertion sort. Unstable: quicksort, heapsort, Java's Arrays.sort on primitives, Go's sort.Slice, C++ std::sort. Rust makes the choice explicit: sort is stable, sort_unstable is not.

To sort by last name and keep the original order of equal names, sort by the tiebreaker first, then by last name with a stable sort, or use one tuple key: sorted(rows, key=lambda r: (r.last, r.seq)).

What breaks when you chain two unstable sorts. The second pass reorders equal last-name records arbitrarily, destroying the order the first pass established. You still get last-name groups, but their internal order is whatever the partition produced: the composite ordering is gone.

Trace it. Records (last, first):

0 (Smith, Dan)
1 (Jones, Ann)
2 (Smith, Cal)
3 (Smith, Bob)

Pass 1, sort by first name (keys are distinct, so stability is irrelevant here): (Jones,Ann), (Smith,Bob), (Smith,Cal), (Smith,Dan).

Pass 2, sort by last name with a Lomuto partition using strict <, pivot = last element (Smith,Dan):

  • j=0: Jones < Smith → i=0, swap a[0] with itself.
  • j=1: Smith(Bob) < Smith → false.
  • j=2: Smith(Cal) < Smith → false.
  • swap a[i+1]=a[1] with the pivot at a[3].

Result: (Jones,Ann), (Smith,Dan), (Smith,Cal), (Smith,Bob). The Smith rows are now Dan, Cal, Bob: reversed. Pass 1's work is destroyed. The partition moves equal keys past each other because it compares only the last-name key.

Tuple key vs two passes. The tuple key is one O(n log n) pass and one comparison per pair, but allocates n key tuples (O(n) extra memory) and compares tuples lexicographically. Two stable passes are 2× the comparisons and 2× the passes, but each key is a single field: cheaper comparisons, smaller key objects. Prefer the tuple key unless you can't build a composite key (a field that's expensive to extract, or an in-place stable sort where you want to avoid allocating tuples). Two passes only works if both sorts are stable.

Failure modes and detection. The regression is silent: the sort returns, the array is sorted by last name, and only the tie order is wrong. Detect it with a property test: shuffle the input, sort, assert that within each equal-last-name group the records are in input order. In production it shows as downstream processing out of sequence (jobs run in the wrong order within a priority class), which is hard to attribute back to the sort. The cost is ongoing: every consumer that assumed tie order has to be fixed or re-sorted.

When unstable is fine. When keys are distinct, when tie order is genuinely interchangeable, or when you need the memory profile: heapsort is O(1) extra space, quicksort O(log n) stack, versus Timsort's O(n) for the merge buffer. Java's primitive sort has no identity to preserve, so stability is meaningless there.

Curated: · Written: · Reviewed:

Q&A-82You sort by grade then by name. Why do you use a tuple key once, or two stable sorts in reverse priority, not two unstable sorts?

Python's sorted is stable, and that is the whole reason the two-pass trick works. Stability means equal keys keep their input order. So if you sort by the secondary key first and then by the primary key with a stable sort, the second pass never disturbs the order the first pass established inside each primary group. A tuple key (grade, name) gets the same result in one pass, because tuple comparison checks grade first and only falls through to name on ties. Two unstable sorts give you no such guarantee: the second pass is free to reorder equal-grade rows, and the alphabetical order from the first pass is gone.

Concretely, with rows as (grade, name) tuples:

from operator import itemgetter

rows = [("B", "Ann"), ("A", "Zoe"), ("B", "Cal"), ("A", "Bob")]

# One pass, tuple key
sorted(rows, key=itemgetter(0, 1))
# -> [('A', 'Bob'), ('A', 'Zoe'), ('B', 'Ann'), ('B', 'Cal')]

# Two passes, stable, secondary first
sorted(sorted(rows, key=itemgetter(1)), key=itemgetter(0))
# -> [('A', 'Bob'), ('A', 'Zoe'), ('B', 'Ann'), ('B', 'Cal')]

Trace the two-pass version. Pass 1 sorts by name: Ann, Bob, Cal, Zoe -> [('B','Ann'), ('A','Bob'), ('B','Cal'), ('A','Zoe')]. Pass 2 sorts by grade, stable: the two A rows stay in their current order (Bob then Zoe), the two B rows stay (Ann then Cal). Result matches the tuple key exactly.

Now swap pass 2 for an unstable sort. The A group could come out [('A','Zoe'), ('A','Bob')] and the B group [('B','Cal'), ('B','Ann')]. Names are no longer alphabetical inside a grade. That is the failure the tuple key or the stable two-pass avoids.

methodsecondary order preserved?
key=(grade, name)yes, one pass
stable sort by name, then by gradeyes, two passes
two unstable sortsno guarantee

Two things to get right. itemgetter(0, 1) indexes positions, so it only works on sequences; for objects with attributes use attrgetter('grade', 'name'). And the tuple key forces one direction for both fields: reverse=True flips the whole tuple. If you need grade descending but name ascending, the two-pass form is easier: sort name ascending, then grade with reverse=True. The tuple key can still do it, but you have to negate a numeric field or wrap it, which is where people get it wrong.

Failure modes worth naming. An unstable sort (C qsort, Go's sort.Slice, Java's primitive Arrays.sort) silently drops the secondary order: detect it by asserting that within each equal-primary run the secondary values are non-decreasing. A tuple key over a field that can be None raises TypeError in Python 3 when two rows tie on the primary and it tries to compare None to a string; the two-pass form hits the same wall in pass 1. And if the secondary key is not comparable at all, neither approach works until you define an ordering.

So: one tuple key when both fields sort the same direction and are comparable; two stable sorts when directions differ or you want to reuse an existing comparator. Never two unstable sorts: stability is the mechanism, not a nicety.

Curated: · Written: · Reviewed:

Q&A-43A sort comparator returns a-b for objects where a-b can overflow, or "closest to pivot" with a non-transitive relation. What can the sort do?

Core answer (first 90 seconds). A comparator has to be a strict weak order: antisymmetric and transitive. Both bugs break that. a - b overflows when the values are far apart, so cmp(a,b) and cmp(b,a) can both come back negative: antisymmetry is gone. A "closest to pivot" comparator that reads a pivot which changes during the sort is not a function of its two arguments at all, so it can produce a cycle a < b < c < a. Once the order is not a strict weak order, the sort's invariants are void: Java's TimSort throws IllegalArgumentException: Comparison method violates its general contract! when it detects the break, C++ std::sort is undefined behaviour (segfault or hang), and any sort may silently emit a wrong permutation. The fix is to compare through a total-order key.

Overflow, traced. Java 17, Integer[]:

Arrays.sort(xs, (a, b) -> a - b);   // xs = { 0, Integer.MIN_VALUE }

With a = 0, b = Integer.MIN_VALUE = -2^31:

  • a - b = 0 - (-2^31) = 2^31, which wraps to -2^31 (MIN_VALUE) → negative → "0 < MIN_VALUE".
  • b - a = -2^31 - 0 = -2^31 → negative → "MIN_VALUE < 0".

Both directions claim the first argument is smaller. Antisymmetry is violated, and with only two elements TimSort never checks: it returns {0, MIN_VALUE}, silently wrong. On a larger array the same comparator trips TimSort's run check and throws the contract exception instead. Integer.compare(a, b) cannot overflow.

Moving pivot, traced. A fixed pivot is fine: |a - pivot| is a key function, so it is a total order. The bug is a pivot that changes between calls: a field reassigned by the partition step, or "distance to the last element compared". Take values 0, 6, 10 with the pivot updated to the first argument each call:

  • cmp(0, 6), pivot 0: 0 vs 6 → 0 < 6
  • cmp(6, 10), pivot 6: 0 vs 4 → 6 < 10
  • cmp(10, 0), pivot 10: 0 vs 10 → 10 < 0

Cycle 0 < 6 < 10 < 0. No sort can order that.

What the sort actually does.

violationJava TimSortC++ std::sorttypical result
overflow, antisymmetry brokenthrows IllegalArgumentException when detectedundefined behaviourwrong order, or exception
moving pivot, cyclethrows when detectedundefined behaviourwrong order, hang, or segfault

Java's detection is heuristic: a violation can pass unnoticed and just mis-order. C++ gives no check at all.

Fix and detection. Decorate: compute the key once per element, then sort by it. Comparator.comparingInt(x -> x) for the overflow case; for closest-to-pivot, map each element to (distance, tiebreak) against a fixed pivot and sort that. If the pivot genuinely must move, a comparator is the wrong tool: use quickselect or a partial sort. To catch it, property-test the comparator on random triples for transitivity and antisymmetry, and log the Java exception rather than swallowing it.

Curated: · Written: · Reviewed:

Q&A-49Sort n=10^7 integers each in 0..255. Why is counting sort O(n+k) here, and when does comparison O(n log n) win?

Why it is O(n+k) here

n = 10^7, k = 256. Counting sort never compares two keys: it uses each key as an array index. That is why the Ω(n log n) bound does not apply: the decision-tree argument only constrains algorithms that learn about the input through pairwise comparisons. It says you need log2(n!) ≈ n log2 n comparisons to separate n! possible orderings; counting sort separates them by histogramming instead.

The work is four passes:

  1. Zero k counters: O(k).
  2. One pass over the n keys, count[key]++: O(n).
  3. Prefix-sum the k counters: O(k).
  4. One pass over the n keys, writing each into its slot: O(n).

Total 2n + 2k. At n = 10^7, k = 256 that is ~2×10^7 increments plus 512 prefix steps. A comparison sort needs log2(10^7) ≈ 23.3 comparisons per element, ~2.3×10^8, and each comparison is a branch the CPU cannot predict. Counting sort's inner loop is a read-modify-write on a 1 KB array that stays in L1.

Trace (n = 8, k = 4, keys [3,0,3,1,2,0,3,1])

count after pass 2: [2,2,1,3]. Two 0s, two 1s, one 2, three 3s. Prefix sums: [2,4,5,8], i.e. exclusive end positions. Write from the back, decrementing as you go:

i=7 key 1 → slot 3; i=6 key 3 → slot 7; i=5 key 0 → slot 1; i=4 key 2 → slot 4; i=3 key 1 → slot 2; i=2 key 3 → slot 6; i=1 key 0 → slot 0; i=0 key 3 → slot 5.

output = [0,0,1,1,2,3,3,3]. The two 0s keep their relative order (input positions 1 and 5 land in output slots 0 and 1): that stability is what makes radix sort work.

When comparison wins

  • k ≫ n. The cost is n + k, so a sparse domain pays for buckets it never fills. 10^7 random 64-bit ids have k = 2^64: the count array does not exist. Even k = 10^9 with n = 10^7 touches 100 counters per key.
  • Keys are not dense non-negative integers. Strings, structs, floats (NaN, -0.0), or anything ordered by a custom comparator has no index.
  • Memory. k counters at 4 bytes each: k = 2^32 is 16 GB. Comparison sort needs O(log n) stack and can sort in place.
  • Order is defined by a comparator rather than by value: lexicographic, locale collation, multi-field records.

Decision rule: counting sort when k = O(n) and keys are small non-negative integers; radix when the domain is large but keys are fixed-width. D passes of counting over b-bit digits costs d(n + 2^b), so 32-bit keys with 8-bit digits is 4(n + 256) ≈ 4n, still under n log n ≈ 23n; comparison sort for everything else.

Illustrative timings on one x86 laptop: 10^7 bytes through counting sort lands near 100 ms; the same values as Python ints through Timsort near 1.5–2 s. The ratio is the point, and it flips the moment k stops being small.

Curated: · Written: · Reviewed:

Q&A-18N-queens n=12: why does checking the current column/diagonal set beat generating n^n placements?

Core answer. Backtracking with a column/diagonal set wins because the attack constraint is monotone: a partial placement that already has two queens attacking can never be extended into a solution. So you test each new queen in O(1) against three sets and, on a hit, discard the whole subtree below it. Enumeration has no such structure: it builds all n^n full boards and only then checks, paying for every descendant of every dead prefix.

The size gap for n=12: n^n = 12^12 ≈ 8.9×10^12 boards. Column pruning alone caps the tree at 12! = 4.79×10^8 nodes, because row r can only use columns not already taken: an 18,600× cut before diagonals are considered. Diagonal pruning cuts further. For n=4 the exact pruned tree is 17 valid partial placements against 4^4 = 256.

Mechanism. Place one queen per row. Three sets: cols, diag keyed by r−c, anti keyed by r+c. Two queens attack iff they share a column or a diagonal, so a queen at (r,c) is safe iff c ∉ cols, r−c ∉ diag, r+c ∉ anti. Each test is O(1) with a hash set or a bitmask. On a hit you return immediately: you never generate the n^(n−r) boards that would extend the dead prefix. The O(1) test is the secondary win; the primary one is that an O(1) test is cheap enough to run at every node, which is what makes pruning possible at all.

Trace, n=4, branch row 0 = col 1:

rowcoltestaction
01—place
10anti hit (r+c=1)skip
11col hitskip
12diag hit (r−c=−1)skip
13clearplace
20clearplace
30,1col hitskip
32clearsolution [1,3,0,2]
33col hitskip
21col hitskip
22anti hit (r+c=4)skip
23col hitskip

Code (Python 3.11, bitmask):

def solve(n):
    count = 0
    def place(row, cols, diag, anti):
        nonlocal count
        if row == n:
            count += 1
            return
        free = ~(cols | diag | anti) & ((1 << n) - 1)
        while free:
            bit = free & -free
            free ^= bit
            place(row + 1, cols | bit, (diag | bit) << 1, (anti | bit) >> 1)
    place(0, 0, 0, 0)
    return count

Returns 2 for n=4, 92 for n=8, 14200 for n=12 (OEIS A000170).

Trade-offs. Bitmask: three machine words, O(1) bit ops, but capped at n ≤ 64 with a 64-bit int (n ≤ 32 with 32-bit). Hash set: any n, more memory and a slower constant. Symmetry pruning: the board has 8 symmetries (D4), so fixing the first queen to the left half of row 0 cuts the tree ~8×. Valid only if you want solutions up to symmetry, otherwise you undercount. Brute force is fine for n ≤ 8: 8^8 = 16.7M boards is about a second, and the pruning machinery isn't worth writing.

Failure modes. Indexing diag by r−c without offsetting by n−1 gives negative indices or aliasing: use r−c+n−1 or a hash set. A 32-bit mask silently wraps for n > 32. Forgetting to unmark on backtrack (or mutating cols in place in the bitmask version) corrupts the count. Applying symmetry pruning when you need all solutions undercounts by up to 8×.

Curated: · Written: · Reviewed:

Q&A-19Climbing stairs with 1 or 2 steps, n=40: why is the recurrence dp[i]=dp[i-1]+dp[i-2], and what does naive recursion do?

For n=40 there are 165,580,141 distinct ways to climb, and the recurrence is right because it partitions the paths by their last move. Assumptions: n ≥ 0, each step is exactly 1 or 2, and order matters. 1+2 and 2+1 are different climbs.

Every valid path to step i ends with a final move, and that move is either a single step from i-1 or a double step from i-2. Those two sets are disjoint (different last move) and exhaustive (no other last move exists), so the number of paths to i is the number to i-1 plus the number to i-2:

dp[i] = dp[i-1] + dp[i-2]

Base cases: dp[0] = 1 (the empty climb, one way to stand still) and dp[1] = 1.

idp[i]paths
01(empty)
111
221+1, 2
331+1+1, 1+2, 2+1
451+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2
58

Naive recursion is climb(n) = climb(n-1) + climb(n-2) with climb(0) = climb(1) = 1. It is correct but recomputes the same subproblems: climb(38) is evaluated inside both climb(39) and climb(40). The call tree has T(n) = T(n-1) + T(n-2) nodes, so it grows like φ^n ≈ 1.618^n. Exactly, the number of calls is 2·F(n+1) − 1, which for n=40 is 331,160,281 calls: hundreds of millions to produce a number the loop reaches in 39 additions. Recursion depth is only 40, so the stack is fine; the cost is time, not space.

Three implementations, and the choice depends on what you need:

  • Top-down memoisation: keep the recursion, cache results in an array. Same O(n) time, O(n) space, but you only compute states you actually reach: worth it when the recurrence branches into many states and you don't need all of them.
  • Bottom-up tabulation: fill dp[0..n] in order. O(n) time, O(n) space, no recursion-depth risk, and the version to reach for when you need the whole table (say, to answer queries for many n).
  • Rolling two variables: you only ever read dp[i-1] and dp[i-2], so keep two scalars. O(n) time, O(1) space. This is the one to say out loud here, because nothing downstream needs the earlier values.

Deciding criteria: memoisation when the state graph is sparse or you want to skip unreachable states; tabulation when you need all values or want to avoid recursion; rolling variables when only the final answer matters.

Two failure modes worth naming. Off-by-one base cases: setting dp[0] = 0 gives the wrong answer for every n, because the empty climb is one way, not zero. Integer overflow: the result is Fibonacci, so it grows fast. Ways(45) = 1,836,311,903 fits in a signed 32-bit int, ways(46) = 2,971,215,073 does not. Use 64-bit, or the problem's modulus if it has one.

Check n=5: dp = 1, 1, 2, 3, 5, 8 → 8 ways. The call-count claim is testable too: instrument climb and count invocations; you'll see 331,160,281 for n=40.

Curated: · Written: · Reviewed:

Q&A-20Unique paths on a 20×20 grid with obstacles: why memoize (r,c) instead of branching 2^{40}?

Core answer (first 90 seconds). The recursion has only (R+1)(C+1) distinct subproblems, one per lattice point, but the naive tree re-derives each one once per path through it. On an empty 20×20 grid that is 441 states against C(40,20) = 137,846,528,820 paths. The unmemoized tree makes C(42,21) − 1 ≈ 5.38×10^11 calls to answer a question with 441 answers. Memoizing on (r,c) collapses the tree onto the state space: O(RC) time. The key is (r,c) and nothing else, because the number of paths to (r,c) depends only on (r,c), not on the route taken to reach it. Note 2^40 ≈ 1.1×10^12 overcounts even the naive tree: only the 40-step sequences with exactly 20 downs and 20 rights land on the corner.

Mechanism. paths(r,c) = 0 if blocked, else paths(r-1,c) + paths(r,c-1), with paths(0,0)=1. Every call with the same (r,c) returns the same value: exactly the condition memoization needs. Without it, paths(r,c) is recomputed once per ancestor path; the origin alone is recomputed once per path in the grid.

Code. Bottom-up with a rolling row, O(C) space:

def unique_paths(blocked):  # blocked[r][c] -> True if (r,c) is an obstacle
    R, C = len(blocked), len(blocked[0])
    dp = [0] * C
    dp[0] = 1
    for r in range(R):
        for c in range(C):
            if blocked[r][c]:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c - 1]
    return dp[C - 1]

Top-down equivalent:

from functools import lru_cache

@lru_cache(maxsize=None)
def paths(r, c):
    if r < 0 or c < 0 or blocked[r][c]:
        return 0
    if r == 0 and c == 0:
        return 1
    return paths(r - 1, c) + paths(r, c - 1)

Trace. 3×3 lattice points, obstacle at (1,1). The rolling row after each row of the loop:

c0c1c2
r0111
r1101
r2112

Return 2. The obstacle zeroes dp[1] at r1, and dp[2] += dp[1] then propagates that zero, which is why an obstacle in the first row or column must zero the whole prefix, not just its own cell.

Trade-offs. Top-down memoization visits only reachable states, so with scattered obstacles it can touch far fewer than (R+1)(C+1) cells. It pays for that with a dict lookup and a Python call per state, roughly 10–30× the per-state cost of array indexing, and with recursion depth R+C (40 here, fine; 2×10^4 on a 10^4-wide grid, past Python's default limit of 1000). Full-table bottom-up is O(RC) space but visits every cell even when unreachable. The rolling row is O(C) space at the same O(RC) time and is the right default when you only need the count; you lose the table, so you cannot reconstruct a path or answer "paths through (r,c)" queries afterwards. Memoization is the wrong tool when the state space is dense and you need all of it (tabulation is faster and cache-friendly), when depth exceeds the stack, when you need the table for reconstruction, or when the key is a large tuple whose hashing dominates the work.

Failure modes. Integer overflow: C(40,20) = 1.38×10^11 fits in int64, but a 100×100 grid gives C(200,100) ≈ 9.05×10^58 and silently wraps in Java or C++ int/long; Python is arbitrary precision. Keying the cache on the path taken (a visited set, say) destroys the sharing and puts you back at exponential. And an empty 16×16 grid makes C(32,16) = 601,080,390 paths, so the naive tree runs C(34,17) − 1 ≈ 2.33×10^9 calls while the DP fills 289 states: that pair of numbers is the whole argument.

Curated: · Written: · Reviewed:

Q&A-21Coin change with coins [1,3,4] and amount 6: why does taking the largest coin first fail, and what would prove a greedy choice?

Greedy fails on [1,3,4] at amount 6: taking the largest coin gives 4+1+1, three coins, while 3+3 uses two. The choice of 4 is locally the biggest reduction, but it leaves a remainder of 2 that only 1s can fill, so it strands the solution in a state the optimal path never visits.

Why it fails mechanically. Greedy commits to a coin without knowing what the remainder can be built from. There is no exchange argument here: you cannot take the optimal solution {3,3} and swap coins one-for-one to reach {4,1,1} without increasing the count. Greedy is optimal only when such an exchange always exists, and that is a property of the coin system, not of the algorithm.

What would prove a greedy choice.

  1. Exchange argument. Show that for any amount, some optimal solution contains the greedy coin, and that removing it leaves an optimal solution for the remainder. If you can always make that swap without adding coins, greedy is optimal.
  2. Canonical-system test. A coin system is canonical if greedy is optimal for every amount. Pearson (2005) showed you need not check all amounts: it suffices to check a bounded range, up to the sum of the two largest denominations. Run greedy and DP over that range; if they agree everywhere, greedy is optimal for all amounts.
  3. Sufficient structural condition. If every coin divides the next (1,3,6,12...), greedy is optimal. [1,3,4] breaks this, since 3 does not divide 4. US coins 1,5,10,25 are canonical even though 10 does not divide 25, so divisibility is sufficient, not necessary.
amount 6, coins [1,3,4]coins usedcount
greedy (largest first)4,1,13
optimal3,32

DP trace, unbounded coin change with dp[a] = min coins for amount a, recurrence dp[a] = min over c ≤ a of dp[a-c]+1:

dp[0] = 0
dp[1] = 1            (1)
dp[2] = 2            (1+1)
dp[3] = 1            (3)
dp[4] = 1            (4)
dp[5] = 2            (4+1)
dp[6] = 2            (3+3)

O(amount × coins) time, O(amount) space.

Failure mode. Greedy overpays on specific amounts. For [1,3,4] the first failure is amount 6; amounts 1 through 5 are all optimal. Detect it by brute-forcing greedy against DP over a range of amounts and diffing: the mismatch set is exactly where greedy is wrong. In production this surfaces as a wrong coin count on particular totals, not a crash.

Trade-offs. Greedy is O(k) per amount and needs no table; DP is O(k·A) time and O(A) space but optimal for any system. Use greedy only when you have proven canonicity, or can cite a known canonical system such as US or euro coins; otherwise use DP. For amount 6 with [1,3,4], DP returns 2.

Curated: · Written: · Reviewed:

Q&A-23Count bits in every integer 0..n for n=10^6: why is dp[i]=dp[i>>1]+(i&1) better than calling popcount in a loop of loops?

Assumption first: the job is to produce all n+1 counts, not one. That is what makes the recurrence worth it. If you only needed popcount(10^6), none of this matters.

The answer. dp[i] = dp[i>>1] + (i&1) does one add per element. The loop-of-loops does one add per bit, about 20 for i near 10^6, so roughly 20× the work. i>>1 is i/2, and i/2 < i, so its count is already in the table; i&1 is the low bit. One pass, no inner loop.

// n = 1_000_000; counts for 0..n inclusive
uint8_t *dp = malloc(n + 1);
dp[0] = 0;
for (uint32_t i = 1; i <= n; i++)
    dp[i] = dp[i >> 1] + (i & 1);

uint8_t is enough: the largest popcount below 2^20 is 20.

Trace 0..8:

ii>>1i&1dp[i]
0––0
1011
2101
3112
4201
5212
6302
7313
8401

dp[0..8] = [0,1,1,2,1,2,2,3,1].

Alternatives, and when each wins.

approachwork for n=10^6memoryneeds
nested bit loop~2×10^7 shift/and/add (3.2×10^7 if fixed 32-bit)output onlynothing
hardware popcnt10^6 popcnt instructionsoutput onlyPOPCNT (x86 SSE4.2) or ARM
shift DP10^6 load+add+store1 MB (uint8), 4 MB (uint32)nothing

The DP's real cost is the table. If you only need the counts and the CPU has POPCNT, __builtin_popcount(i) (GCC/Clang) in a flat loop is simpler and typically as fast or faster: one instruction per element, no 1 MB of stores, no dependency on a prior element. The DP wins when you need the table anyway (rank/select, prefix sums of popcounts), when popcnt is unavailable or emulated on the target, or when you want one code path everywhere.

Failure modes. The DP has a serial dependency: dp[i] reads dp[i>>1], so it cannot vectorize the way a popcnt loop can. With uint32 the table is 4 MB and the read at i>>1 starts missing L2 around n≈10^6; uint8 keeps it in cache. And the recurrence only handles the low bit: it does not generalize to counting bits over a range without a prefix-sum step.

Decision. For n=10^6 producing all counts: shift DP if you need the table or lack POPCNT; flat __builtin_popcount loop otherwise. Both land in the low single-digit milliseconds on a modern core (estimate: measure on your target). The nested bit loop is the one to avoid.

Curated: · Written: · Reviewed:

Q&A-24gcd(a,b) for 64-bit integers: why is Euclidean O(log min(a,b)), and when do you use lcm = a//gcd*b?

Core answer. Each step replaces (a, b) with (b, a % b), and the first argument at least halves every two steps, so the step count is O(log min(a,b)). The worst case is a pair of consecutive Fibonacci numbers, where that shrink is as slow as it can be. For lcm, write a // gcd(a,b) * b, never a * b // gcd(a,b), whenever a * b can overflow the type but the lcm itself fits. In Python or with __int128 the ordering is cosmetic; in fixed-width C, C++, Java or Go it is the difference between the right answer and a silently wrapped one.

Why the bound holds. Two facts do the work. First, a % b < b, so the pair strictly shrinks. Second, and this is the one that gives the log, after two steps the leading argument is at most half its old value. If b <= a/2 then a % b < b <= a/2. If b > a/2 then a % b = a - b < a/2. Either way the value entering the next-next step is under a/2, so the number of iterations is bounded by 2 * log2(a). Lamé's theorem sharpens this: the step count is at most about five times the number of decimal digits, and the exact worst case is consecutive Fibonacci numbers, because F(n+1) % F(n) = F(n-1) is the smallest possible remainder. For any 64-bit input that is fewer than 100 iterations.

Trace on the worst-case shape, (89, 55):

aba % b
895534
553421
342113
21138
1385
853
532
321
210

Nine iterations for a pair whose ratio is the golden ratio; a random 64-bit pair averages closer to 40. Each iteration is one hardware division on machine words, so the total is O(log min(a,b)) word operations.

Trade-offs and when the modulo form is wrong. Binary GCD (Stein's algorithm) replaces division with shifts and subtracts. On x86-64 a 64-bit DIV is roughly 20-40 cycles, so modulo Euclid usually wins for machine words; binary GCD wins on hardware with slow division, on small integers, and as the inner loop of a multi-precision routine. For bignums, Lehmer's algorithm is the standard choice because it batches several quotient steps per division. Subtraction-only Euclid is the trap: on (10^18, 1) it loops 10^18 times, while the modulo form finishes in two steps. Reach for the modulo form unless you have measured that division dominates; reach for extended Euclid when you need the Bézout coefficients, not just the gcd.

The lcm rule. a // g * b is exact because g divides a, and it keeps the intermediate product at lcm size instead of a*b size. Use it whenever a*b overflows but the lcm fits: the common case, since lcm(a,b) = a*b/g is g times smaller. Do not use it when the lcm itself overflows: then you need __int128, a bignum, or modular arithmetic. For lcm mod m, compute (a // g % m) * (b % m) % m; for a set, fold left with an overflow check at each step, since the product grows fast. Python's math.lcm (3.9+) and C++17 std::lcm do the divide-first ordering for you, but std::lcm is undefined behaviour if the result is not representable in the common type.

Failure modes to name. Silent overflow wrap in a*b//g: detected by a result smaller than either input. Negative inputs in C++: a % b takes the sign of a, so a hand-rolled loop can return a negative gcd or fail to terminate; std::gcd returns non-negative. gcd(0,0) is 0 and gcd(a,0) is |a|; guard the zero case before dividing.

Curated: · Written: · Reviewed:

Q&A-39Items with (weight, value), capacity W, each item 0 or 1 times: why can you not sort by value/weight, and what is the DP table?

Greedy fails because 0/1 has no exchange argument. Fractional knapsack is greedy-correct: you can always swap a unit of a lower-density item for a unit of a higher-density one and never lose value, so sorting by value/weight and filling is optimal. With 0/1 you cannot split, so taking the densest item can strand capacity that a slightly less dense item would have filled exactly. Density order is a heuristic, not an optimum.

Counterexample: items (10,60), (20,100), (30,120), W=50. Densities are 6, 5, 4. Greedy takes 10 then 20 (weight 30, value 160) and cannot fit 30. The optimum is 20+30 = weight 50, value 220.

The DP table. Let dp[i][w] = best value using only the first i items with capacity w.

dp[0][w] = 0                       for all w
dp[i][w] = dp[i-1][w]              if wt_i > w
dp[i][w] = max(dp[i-1][w],         otherwise
               dp[i-1][w - wt_i] + val_i)

The two branches are skip item i (keep row i-1) or take it (add its value to the best you could do with the remaining capacity w - wt_i using items 1..i-1). Answer is dp[n][W]. Time O(nW), space O(nW): reducible to O(W) below.

Why the 1D loop runs backward. Collapse the table to one array dp[w] that holds row i-1 before item i is processed. The update dp[w] = max(dp[w], dp[w-wt] + val) reads dp[w-wt], which must still be the previous row: item i not yet used. Iterating w from W down to wt guarantees w-wt < w has not been overwritten in this pass, so it is still row i-1. Iterating upward would let dp[w-wt] already contain item i, which is exactly the unbounded-knapsack recurrence where an item may repeat.

dp = [0] * (W + 1)
for wt, val in items:
    for w in range(W, wt - 1, -1):   # downward: 0/1
        dp[w] = max(dp[w], dp[w - wt] + val)
# unbounded would be range(wt, W + 1) upward

Trace on the fixture (W=50, items in the order above):

after itemdp[20]dp[30]dp[40]dp[50]
(10,60)60606060
(20,100)100160160160
(30,120)100160180220

At the last item, dp[50] = max(160, dp[20] + 120) = 220, and dp[20] is still 100 from the previous row because the loop reached 50 before 20. That is the reverse order doing its job.

When not to use it. If W is huge (say 10^9) and n small, O(nW) is hopeless: use meet-in-the-middle (O(2^(n/2))) or branch-and-bound. If items are divisible, greedy is correct and O(n log n).

Curated: · Written: · Reviewed:

Q&A-480/1 knapsack with n=400 items and W=10^6: you cannot store n×W ints. Which dimension do you drop, and why the inner loop direction?

Drop the item index. Keep one row indexed by weight, size W+1, and iterate w from W down to wt.

dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt_i] + val_i) reads only row i-1. Row i-1 is the whole state needed to produce row i, so the item dimension is a sliding window of depth one and can be overwritten in place. The weight dimension is not droppable: the answer is dp[W], and every transition indexes w-wt, so all W+1 weight slots must be live at once.

Direction is what makes the in-place overwrite correct. Descending w means that when you write dp[w], the slot dp[w-wt] you read has not been touched yet for this item, so it still holds the previous item's value and each item is used at most once. Ascending reads dp[w-wt] after this item already updated it, which is the unbounded-knapsack recurrence.

def knap(weights, values, W):
    dp = [0] * (W + 1)                 # or array('q', [0]) * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1): # descending
            cand = dp[w - wt] + val
            if cand > dp[w]:
                dp[w] = cand
    return dp[W]

The numpy form is the same recurrence: dp[wt:] = np.maximum(dp[wt:], dp[:-wt] + val). dp[:-wt] + val materializes a temporary from the old row before the assignment to dp[wt:], so no slot is read after being written; element w of the slice gets max(dp[w], dp[w-wt]+val).

Memory for n=400, W=10^6:

layoutcellsRAM
dp[n+1][W+1] int324.0e81.6 GB
dp[2][W+1] int322.0e68 MB
dp[W+1] int321.0e64 MB
CPython list dp[W+1]1.0e6 refs8 MB pointers + int objects

A CPython list holds 8-byte pointers to separately allocated int objects, so it is 8 MB before the integers; array('i') or numpy gives the packed 4 MB. Time is unchanged by the compression: still O(nW) = 4e8 cell updates, roughly 1-2 s in C-backed numpy and minutes in a pure-Python loop.

Failure modes:

Ascending loop. One item wt=1, val=5, W=3. Descending: dp[3]=max(0,dp[2]+5)=5, dp[2]=5, dp[1]=5, so dp[3]=5. Ascending: dp[1]=5, dp[2]=max(0,dp[1]+5)=10, dp[3]=max(0,dp[2]+5)=15, so dp[3]=15. The item counted three times. Detect it with a single-item test where wt <= W/2 and val > 0: any result above val means the loop direction is wrong.

Reconstruction. Dropping i throws away the information needed to name the chosen subset. If the answer must be the items rather than the value, you need the full table (1.6 GB), parent pointers, or a divide-and-conquer split that re-solves halves. Detect it by checking whether the caller consumes dp[W] or a subset.

Overflow. int32 caps at 2.1e9; with n=400 and values up to 1e6 the max total is 4e8 and fits, but larger values do not. Assert max(values) * n < 2**31 before choosing the dtype.

Curated: · Written: · Reviewed:

Q&A-34Find pattern length m=400 in text n=2×10^6: when is naive O(nm), and what does KMP's LPS array prevent?

Direct answer. Naive matching is O(nm) exactly when mismatches land near the end of the pattern, so each of the n−m+1 alignments pays close to m comparisons. The canonical worst case: the text is one repeated character and the pattern is that character m−1 times followed by a different one. With m=400 and n=2×10^6 that is (2×10^6 − 400 + 1) × 400 ≈ 8×10^8 character comparisons. KMP's LPS array prevents re-reading text: the text index i only ever increases, so the scan is O(n+m) ≈ 2×10^6 comparisons. About 400× fewer here.

Why naive blows up. On a mismatch naive throws away everything it just matched and restarts the pattern one position to the right. If the mismatch is always at the last pattern character, every alignment costs m comparisons and none of that work is reused.

What LPS prevents. lps[j] is the length of the longest proper prefix of pat[0..j] that is also a suffix. On a mismatch at j, KMP sets j = lps[j−1] and leaves i alone: it has already proven the text up to i matches, and lps tells it how much of the pattern's prefix is still valid there. No text character is compared twice.

LPS for ABABC:

ipat[i]lps[i]
0A0
1B0
2A1
3B2
4C0

Trace of KMP on text ABABABC, pattern ABABC (m=5):

ijtext[i]pat[j]action
00AAmatch, j=1
11BBmatch, j=2
22AAmatch, j=3
33BBmatch, j=4
44ACmismatch, j=lps[3]=2, i stays 4
42AAmatch, j=3
53BBmatch, j=4
64CCmatch, j=5=m → match at i−j+1=2

At the mismatch, naive would restart at alignment 1 and re-compare text[1..3] it already knew matched. KMP instead reads lps[3]=2, "AB" is both prefix and suffix of "ABAB", and resumes at j=2 without touching i.

The arithmetic at the question's scale. Worst case: text = a×2,000,000, pattern = a×399 + b. Alignments = 1,999,601; each compares 400 characters and fails on the 400th. Total ≈ 8.0×10^8 comparisons. At roughly 10^9 simple comparisons/s (C, cache-resident) that is ~0.8 s; a per-character Python loop is 50–100× slower, tens of seconds. KMP builds lps in 400 steps, then scans each of the 2×10^6 text characters once with i never decreasing: total comparisons bounded by ~2n ≈ 4×10^6, typically ~2×10^6, i.e. ~2 ms at 10^9/s. (Timings are order-of-magnitude estimates; the comparison counts are exact.)

When not to use KMP. For a single pattern in production, prefer the library search (Python's str.find uses the linear-time Two-Way algorithm, not KMP) and Boyer-Moore-Horspool often beats KMP on natural text by skipping characters. KMP earns its place when you must guarantee linear time without trusting the library, or when the text is a stream you cannot re-read. Its cost is O(m) memory for lps; for many patterns at once, use Aho-Corasick instead.

Curated: · Written: · Reviewed:

Q&A-70sum(x*x for x in range(10^7)) versus sum([x*x for x in range(10^7)]). Which allocates 10^7 ints extra, and when do you still want the list?

Direct answer: sum([x*x for x in range(10**7)]) allocates all 10^7 int objects at once. That is the extra allocation. sum(x*x for x in range(10**7)) allocates them one at a time and frees each before the next, so its peak memory is flat.

(One clarification: 10^7 in Python is XOR and evaluates to 13. I read the question as 10**7.)

Why the difference. A list comprehension builds the entire list before sum runs: CPython appends each x*x to a list, so all 10^7 results are alive simultaneously. A generator expression is a suspended frame; sum pulls one value, adds it, and the int's refcount drops to zero, so it is freed immediately. sum itself only ever holds the running total plus the current element.

What it costs. On 64-bit CPython 3.12:

componentsize
list pointer array8 bytes × 10^7 = 80 MB
int objectsx*x reaches 10^14, needing two 30-bit digits, so sys.getsizeof is 32 bytes each → ~320 MB
list version peak~400 MB
generator version peakgenerator frame + one int at a time: a few KB, independent of n

So the list version peaks around 400 MB; the generator's footprint does not grow with n.

When you still want the list:

  • You iterate more than once. A generator is single-use; the second pass yields nothing. If you need the values after summing, or to feed two consumers, materialize.
  • You need len, indexing, slicing, or random access.
  • You must hand a real sequence to an API that requires one.
  • Small n. The list comprehension is typically faster per element because it skips the generator's per-item frame resume, and at n=1000 the ~40 KB is irrelevant. The crossover is memory, not speed: pick the generator once n is large enough that the list's footprint matters.

Failure modes.

  • Silent empty second pass: g = (x*x for x in range(10)); sum(g); sum(g). The second sum returns 0. Caught by a test that consumes the iterator twice.
  • itertools.tee is not a memory fix: it buffers everything the slower branch has not consumed, so it can cost as much as the list.
  • The generator does not help if the consumer materializes anyway: sorted(x*x for x in ...) builds a list internally.

If you only need the sum, the generator is the right call; reach for the list when you need the values themselves, more than once.

Curated: · Written: · Reviewed:

Q&A-79You pass the same generator to list() twice and the second list is empty. What protocol did you consume, and how do you tee or reuse?

A generator object is its own iterator: it defines __iter__ returning self and __next__ pulling the next value from the suspended frame. list() calls __next__ until StopIteration, and that exception is terminal: the frame is closed, the local state is gone. Calling list() again on the same object gets StopIteration on the first __next__, so you get []. Nothing is "consumed" in a recoverable sense; the iterator protocol has no rewind.

g = (n for n in range(3))
list(g)   # [0, 1, 2]
list(g)   # []

Reuse options, in the order I'd reach for them:

  1. Materialize once. rows = list(gen) if the data fits in memory and you need random access or multiple passes. Cost is O(n) memory; for a 1.2M-row CSV at ~200 bytes/row that's ~240 MB, which is often fine and often not.

  2. itertools.tee. Splits one iterator into n independent ones. It buffers values that the faster consumer has already pulled but the slower one hasn't, so memory grows with the lag between consumers, not with n. If you drain one branch fully before touching the other, you've buffered the whole stream: same as list().

import itertools
a, b = itertools.tee((n for n in range(3)))
list(a)   # [0, 1, 2]
list(b)   # [0, 1, 2]
  1. Recreate. If the source is a factory (def rows(): yield ...) or a file, call it again or seek(0). This is the only option that's O(1) memory and gives a true second pass.

  2. zip(gen, gen) is not a tee. zip calls next on each argument in turn, so passing the same iterator twice advances it twice per tuple:

g = (n for n in range(4))
list(zip(g, g))   # [(0, 1), (2, 3)]

That's consecutive pairs, not (0, 0), (1, 1). If you want pairs of the same value, tee first or materialize.

Failure mode I'd watch for: a validator drains the CSV iterator to check row count, then the loader iterates the same object and sees zero rows, and if the loader's success criterion is "no exceptions", it reports 100% success on an empty stream. Detection is a row-count assertion at the loader boundary (assert loaded == validated), not a log line. The bug is silent because an exhausted iterator is indistinguishable from an empty one.

When not to use tee: if the two consumers run at very different rates, or one is much slower, the buffer becomes the whole dataset. Materialize or recreate instead. tee is for when both branches advance roughly together.

Curated: · Written: · Reviewed:

Q&A-50Pick k=10 uniform items from a stream of unknown length (eventually n=8×10^6). Why not store all and random.sample at the end?

What I'd say first. Don't buffer. You don't know n when the stream starts, and buffering costs O(n) memory to produce a k-element answer. Reservoir sampling gives a uniform k-subset in one pass with O(k) memory. For k=10 that is 10 slots whether n is 10^3 or 8×10^6.

Mechanism. Keep k slots. Item i (1-indexed) replaces a uniformly chosen slot with probability k/i. Fill the first k items; for i>k draw j = random.randrange(i) and if j < k overwrite res[j].

import random

def reservoir(stream, k):
    res = []
    for i, item in enumerate(stream, start=1):
        if i <= k:
            res.append(item)
        else:
            j = random.randrange(i)   # uniform in 0..i-1
            if j < k:
                res[j] = item
    return res

Checked against Python 3.12.

Why it is uniform: after i items each is in the reservoir with probability k/i. Inductively, item i+1 is kept with probability k/(i+1); an existing item survives with probability 1 - (k/(i+1))(1/k) = i/(i+1), so its probability becomes (k/i)(i/(i+1)) = k/(i+1). At i=n every item has probability k/n.

For k=1 the survival probabilities telescope:

iP(kept on arrival)P(final sample = i)
11(1/2)(2/3)(3/4)… = 1/n
21/21/n
n1/n1/n

When buffering is the right call. Reservoir sampling is not always the answer:

  • n is known and small. random.sample(items, k) is one line, and you keep the full list for other uses.
  • The stream is replayable: a file, a seekable log, a re-fetchable API. You can index into it, so the one-pass constraint that motivates the reservoir is gone.
  • You need more than a uniform subset: weighted sampling (A-Res), stratified sampling, or sampling without replacement with per-item inclusion probabilities you can audit. Plain reservoir does none of these.
  • You need positions, not items. The reservoir returns values; if downstream needs the offsets, buffer or track them.

Failure modes. Buffering is the one that bites in production: a 512MB worker buffering 8×10^6 events to sample 10 OOMed at 6 minutes, while a 10-slot reservoir used ~2KB and drained the stream in 3.1s (worked example, not a benchmark to quote). On the reservoir side the bugs are subtler: drawing j = random.randrange(i-1) instead of randrange(i) biases toward early items; reseeding the RNG per item destroys uniformity; and if k is close to n you are storing most of the stream anyway, so buffering costs little more.

Check it. Simulate n=5, k=2 over 10^5 trials: each of the C(5,2)=10 pairs should appear about 10% of the time.

Curated: · Written: · Reviewed:

Q&A-83b = copy.copy(a) then b.child.x = 1 mutates a.child.x. Why, and when is deepcopy the fix versus a new object?

Assumptions: CPython 3.x, plain dicts/objects with no custom __copy__/__deepcopy__, and a holds a nested mutable object under child.

The answer: copy.copy allocates a new outer object and copies the references it holds. b.child and a.child are the same object, so b.child.x = 1 writes through to a. copy.deepcopy walks the graph and builds new objects for every node, so the copy's nested state is independent. Reach for deepcopy when nested mutable state must diverge; build a new object when you know the shape and only one branch changes.

import copy

a = {"child": {"x": 0}}
b = copy.copy(a)
b["child"]["x"] = 1
print(a["child"]["x"], a["child"] is b["child"])   # 1 True

c = copy.deepcopy(a)
c["child"]["x"] = 2
print(a["child"]["x"], a["child"] is c["child"])   # 1 False

Trace: copy.copy(a) allocates a new dict and copies the single entry. The value is the same inner dict, so b["child"]["x"] = 1 mutates the dict a also points at. deepcopy allocates a new outer dict and a new inner dict; c["child"]["x"] = 2 touches only the copy, leaving a at 1.

One detail worth knowing: deepcopy keeps a memo keyed by id, so aliasing inside the graph is preserved rather than duplicated. If a = {"p": shared, "q": shared}, then after d = copy.deepcopy(a), d["p"] is d["q"] is still True. That is usually what you want; it also means deepcopy is not a way to break a shared reference you deliberately created.

ApproachOuter objectNested objectsCost
copy.copy(a), dict(a), a[:]newsharedO(1) refs
copy.deepcopy(a)newnew, memo preserves internal sharingO(nodes)
dataclasses.replace(a, child=...)newwhatever you passO(1)

When deepcopy is the fix: the nested state is mutable, you don't know the graph's shape, or it contains cycles (deepcopy's memo is what makes cycles terminate). When a new object is better: you know the shape and only one branch changes. dataclasses.replace, a dict comprehension, or copying just the mutated sub-object is O(1) instead of O(nodes). Worked example (hypothetical): an order with 200 line items, each a dict of 8 fields, is ~1,600 dicts for deepcopy to rebuild; copying only the two lines that changed is roughly 800x less work. Shallow copy is also correct when the nested values are immutable (str, int, tuples of immutables) because sharing them cannot be observed.

Failure modes. Deepcopy raises TypeError: cannot pickle '_thread.lock' object on objects holding locks, sockets, file handles or live DB connections; those need a custom __deepcopy__ or an explicit rebuild. A __deepcopy__ that returns self silently defeats the copy, so the aliasing bug comes back with no error. And deepcopy cost scales with the whole graph, not the part you changed: on a multi-megabyte object graph that is tens to hundreds of milliseconds per call, which is why it shows up in hot paths.

How to detect it: assert identity in a test, assert a["child"] is not b["child"] after the copy, or mutate the copy and assert the source is unchanged. A test that only checks a == b passes for both shallow and deep copies and catches nothing.

Curated: · Written: · Reviewed:

Q&A-8410^7 instances of a 3-int point class OOM a 4GB worker. How do __slots__ change per-instance size, and what do you lose?

__slots__ removes the per-instance __dict__ and stores the three attributes as fixed pointers inside the object. On 64-bit CPython a three-slot point is 40 bytes of object, a 16-byte header plus three 8-byte pointers, which pymalloc rounds to a 48-byte block. The plain version is a 32-byte object plus a dict, and the dict is the entire cost: it starts at 64 bytes empty and sizes in powers of two, so three attributes land in a table built for eight entries, roughly 200 bytes on 3.12 (that figure is the one that moves most between versions; 3.11+ keeps the values inline in a preheader instead of a separate dict object, at the same order of cost). That's ~230 bytes per point against ~48, about 4.7×, and at 10^7 instances it's ~2.3 GB versus ~0.5 GB: the difference between OOMing a 4 GB worker and not.

What you lose: you can't add attributes at runtime (p.extra = 1 raises AttributeError), and you lose __weakref__ unless you list it in __slots__, which breaks weakref.ref, WeakValueDictionary caches and anything registering weak callbacks. You also can't inherit from two slotted bases (TypeError: multiple bases have instance lay-out conflict), a class variable can't share a name with a slot, and any subclass that forgets to declare __slots__ silently gets its __dict__ back.

The measurement:

import sys

class Plain:
    def __init__(self, x, y, z):
        self.x, self.y, self.z = x, y, z

class Slotted:
    __slots__ = ("x", "y", "z")
    def __init__(self, x, y, z):
        self.x, self.y, self.z = x, y, z

print(sys.getsizeof(Slotted(1, 2, 3)))   # 40
print(sys.getsizeof({}))                 # 64

s = Slotted(1, 2, 3)
s.extra = 1   # AttributeError: 'Slotted' object has no attribute 'extra'
representationbytes/instance10^7 total
plain class + __dict__~230~2.3 GB
__slots__ = ("x","y","z")48~0.5 GB
tuple (x, y, z)64~0.6 GB
numpy int32 array, shape (N,3)12120 MB

If you'd rather not hand-write it, @dataclass(slots=True) (3.10+) generates the same layout; namedtuple is a tuple subclass, so it's immutable and 64 bytes rather than 48.

One thing the table hides: the ints. A Python int outside the -5..256 cache is 28 bytes on 64-bit, so three unique coordinates add 84 bytes per point, 840 MB at 10^7, with or without slots. If your coordinates are unique large values, slots gets you to ~130 bytes/point, not 48. That's the tell that 10^7 points shouldn't be objects at all: three array('i') or one numpy (N,3) int32 array is 120 MB with no per-object overhead.

Detect the regressions rather than assume them: a test asserting AttributeError on p.extra, and tracemalloc snapshots before and after to confirm the drop. The failure mode I'd watch for is a subclass without __slots__: it looks fine, passes tests, and quietly restores the dict.

Rule of thumb: slots for many instances of a fixed-shape record; arrays once the count reaches 10^7.

Curated: · Written: · Reviewed:

Q&A-85def f(x: int) -> str: return x still runs. What does from __future__ import annotations change, and where do you enforce types?

The 90-second answer

def f(x: int) -> str: return x runs because CPython never reads the annotation when f is called. Annotations land in f.__annotations__ and stop there: no check on the argument, no check on the return. f("a") returns "a"; f(1) returns 1 despite the -> str.

from __future__ import annotations changes when annotations are evaluated, not whether they are enforced. Without it, annotations are evaluated eagerly at def time and stored as objects. With it, they are stored as strings and never evaluated unless something asks.

# Python 3.12, no future import
def f(x: int) -> str: return x
f.__annotations__              # {'x': <class 'int'>, 'return': <class 'str'>}

def g(x: Later) -> None: ...   # NameError: name 'Later' is not defined
# Python 3.12, with future import
from __future__ import annotations
def f(x: int) -> str: return x
f.__annotations__              # {'x': 'int', 'return': 'str'}

def g(x: Later) -> None: ...   # fine, no NameError
import typing
typing.get_type_hints(g)       # NameError: name 'Later' is not defined

So the future import buys forward references without quotes and cheaper import time (no evaluation of every annotation at import). It costs you: anything reading __annotations__ directly and expecting objects now gets strings. typing.get_type_hints() resolves them, but it needs the right module globals: a class defined inside a function with local aliases can fail to resolve.

Python 3.14 changes the default: PEP 649/749 make annotations lazily evaluated, so f.__annotations__ is computed on first access via __annotate__ and forward references work without the future import. The future import is still supported and still stringizes. Either way, nothing is enforced.

Where you enforce

layerrejects f("a")?notes
def f(x: int)nometadata only
mypy / pyright in CIyes, staticallycatches it before merge, not at runtime
pydantic v2 TypeAdapter(int).validate_python("a")yesraises ValidationError
assert isinstance(x, int)yesstripped under python -O
beartype / typeguard decoratoryesper-call overhead

Static checking and runtime checking answer different questions. mypy proves your own code is internally consistent; it cannot see the JSON that arrives at 3am. Runtime validation belongs at trust boundaries: HTTP request bodies, queue messages, config files, anything produced by another process.

Failure mode

A handler annotated def charge(amount: int) received {"amount": "12"} from a partner's webhook. "12" + fee raised TypeError, the exception escaped to the framework's 500 handler, and the partner retried: 8% of webhooks failed for 16 minutes until the payload was fixed. Wrapping the boundary in TypeAdapter(ChargeRequest).validate_python(body) turns that into a 422 with a field-level error at roughly 2 ms, and the bad payload shows up in logs instead of buried in a traceback.

When not to

Don't sprinkle runtime validation through internal call chains: it is per-call cost for data you already control. Don't rely on assert for validation in code that might run under -O. And don't assume the future import makes anything safer: it is a parsing and import-time change, and stringized annotations can break libraries that introspect them.

Curated: · Written: · Reviewed:

Q&A-74A file lock must release if the block raises. Why is try/finally the same contract as with, and what does __exit__(exc_type, …) return True do?

Core answer. with is not a different mechanism from try/finally: it is try/finally with a hook bolted on. The language reference defines with EXPR as VAR: BLOCK as an expansion that calls __enter__ once, runs the block inside a try, and calls __exit__ exactly once on every exit path: normal completion, exception, return, break, continue. That is precisely the guarantee finally gives. The one thing with adds is that __exit__'s return value can suppress an in-flight exception; finally cannot.

The expansion. From the language reference ("The with statement"), the documented equivalent: the real implementation lives in the interpreter, but the semantics are these:

mgr = (EXPR)
exit = type(mgr).__exit__          # looked up on the type, not the instance
value = type(mgr).__enter__(mgr)
exc = True
try:
    try:
        VAR = value
        BLOCK
    except:
        exc = False
        if not exit(mgr, *sys.exc_info()):
            raise
finally:
    if exc:
        exit(mgr, None, None, None)

Read the two exit(...) calls: on a clean exit __exit__ gets (None, None, None) and its return value is ignored; on an exception it gets (exc_type, exc_value, traceback) and a falsy return re-raises. threading.Lock.__exit__ returns None, so with lock: releases and lets the exception through: identical to lock.acquire(); try: ... finally: lock.release().

What return True does. It tells the with statement to swallow the exception: the raise in the expansion is skipped, the block completes normally, and execution continues at the statement after the with. Trace it:

class Suppress:
    def __enter__(self):
        return self
    def __exit__(self, exc_type, exc_val, exc_tb):
        print("exit", exc_type.__name__ if exc_type else None)
        return True

with Suppress():
    print("body")
    raise ValueError("boom")
print("after")

__enter__ returns self; the body prints body; the raise unwinds to __exit__, which prints exit ValueError and returns True. The raise is skipped, so after prints. Output:

body
exit ValueError
after

Change return True to return None and after never prints: the ValueError propagates with its original traceback.

Exit path__exit__ argsReturnResult
block completes(None, None, None)ignoredcontinue after with
block raises(type, value, tb)None/Falseexception re-raised
block raises(type, value, tb)Truesuppressed, continue after with
__exit__ raises——new exception replaces; original chained as __context__

Failure modes. Suppressing unconditionally is the classic bug: a context manager that always returns True hides every failure in the block, so the caller sees success and the damage surfaces later as corrupt state. Guard on exc_type: returning True for everything also swallows KeyboardInterrupt and SystemExit. Detect it with a test that raises inside the with and asserts the exception reaches the caller. Second: cleanup that raises inside __exit__ replaces the original exception; the original survives as __context__, but the traceback the caller reads is the cleanup failure.

contextlib.contextmanager subtlety. The generator is resumed by throwing the exception in at the yield. If the generator does not catch it, it propagates out and __exit__ returns falsy: the exception propagates. To suppress, the generator must catch the exception and return normally; you never write return True yourself.

from contextlib import contextmanager

@contextmanager
def locked(lock):
    lock.acquire()
    try:
        yield
    finally:
        lock.release()   # runs on the exception path too

A lock.release() written after the block is a hope, not a contract: any exception skips it and the lock stays held.

Curated: · Written: · Reviewed:

Q&A-80You catch ConnectionError and raise AppError("db down"). How do you keep the original traceback, and what does raise AppError from None hide?

Use raise AppError("db down") from e. That sets AppError.__cause__ to the ConnectionError and flips __suppress_context__ to True, so the traceback printer walks the cause chain and prints both frames: the socket call that failed and the wrapper that replaced it. from None sets __cause__ = None and __suppress_context__ = True; the printer stops at the AppError. The ConnectionError is not gone, err.__context__ still references it, but nothing prints it, and the printed chain is what on-call reads at 3am.

Raising inside an except block always sets __context__ on the new exception, whether or not you write from. from e adds __cause__ on top and marks the context suppressed, so the printer shows the cause instead of the context. The printer's rule:

  • __cause__ not None → print the cause chain, headed "The above exception was the direct cause of the following exception".
  • __cause__ None, __context__ not None, __suppress_context__ False → print the context chain, headed "During handling of the above exception, another exception occurred".
  • __suppress_context__ True and __cause__ None → print only the new exception.
raise__cause____context____suppress_context__printed
raise AppError(...) from eConnectionErrorConnectionErrorTrueboth, labelled cause
raise AppError(...)NoneConnectionErrorFalseboth, labelled "during handling"
raise AppError(...) from NoneNoneConnectionErrorTrueAppError only
class AppError(Exception): ...

def get_user(conn):
    try:
        return conn.query("select 1")
    except ConnectionError as e:
        raise AppError("db down") from e

conn.query raises ConnectionError("connection refused"); the handler binds it to e; raise ... from e builds the AppError, sets __cause__, and raises. Printed:

Traceback (most recent call last):
  File "app.py", line 5, in get_user
    return conn.query("select 1")
ConnectionError: connection refused

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "app.py", line 7, in get_user
    raise AppError("db down") from e
AppError: db down

Swap from e for from None and the first block disappears. err.__context__ still holds the ConnectionError, so a handler that walks __context__ finds it, but the log line does not.

The failure mode is from None on a wrapper whose whole job is to add context. If the wrapper message is generic ("db down") and the underlying error is the diagnosis (timeout, refused, auth) suppressing the context removes the only field that separates them. The symptom is a 5xx spike where every log line reads AppError: db down and the pool timeout is invisible. Catch it in a test rather than by eyeballing logs:

with pytest.raises(AppError) as exc:
    get_user(conn)
assert isinstance(exc.value.__cause__, ConnectionError)
assert exc.value.__suppress_context__ is True

from None is the right call when the original is genuinely noise: a library-specific parse error translated into a domain error at a boundary where the caller cannot act on the original. For a db-down wrapper, keep the cause.

Curated: · Written: · Reviewed:

Q&A-73A decorator replaces foo with wrapper but help(foo) and FastAPI's signature show wrapper(*args). What did you forget, and which attribute leaks without it?

You forgot @functools.wraps(fn) on the inner function. The attribute that leaks is __name__, help(foo) prints wrapper(...), and the signature leak is the same omission: wraps is what sets __wrapped__, and inspect.signature follows __wrapped__ by default. Without it, inspect.signature(foo) returns (*args, **kwargs), and FastAPI builds its request model from that signature, so every declared path, query and body parameter disappears from the route.

import functools, inspect

def deco(fn):
    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        return fn(*args, **kwargs)
    return wrapper

@deco
def foo(x: int, y: int = 1) -> int:
    return x + y

print(foo.__name__)            # foo
print(inspect.signature(foo))  # (x: int, y: int = 1) -> int
print(foo(2, 3))               # 5

Trace: @deco calls deco(foo). functools.wraps(foo) runs first and copies __module__, __name__, __qualname__, __annotations__ and __doc__ from foo onto wrapper, updates wrapper.__dict__ with foo.__dict__, and sets wrapper.__wrapped__ = foo. deco returns wrapper, rebinding the module-level name foo. foo.__name__ is 'foo'. inspect.signature(foo) sees wrapper, follows __wrapped__ to the original, and returns (x: int, y: int = 1) -> int. foo(2, 3) calls wrapper(2, 3), which calls the original with (2, 3) → 5. Delete the @functools.wraps(fn) line and the first two prints become wrapper and (*args, **kwargs).

When wraps is the wrong tool. If the wrapper genuinely changes the call signature (adds a keyword-only argument, drops one) then __wrapped__ makes inspect.signature lie about how to call it. Set wrapper.__signature__ explicitly instead, or skip __wrapped__. If you want the wrapper to carry its own identity (a decorator that registers the function under a new name, a class-based decorator where __init__'s signature is the meaningful one), copying the original's identity is wrong. And wraps updates wrapper.__dict__ from fn.__dict__, so attributes set on the original leak onto the wrapper: a real aliasing cost when one wrapper is reused.

Manual alternative. wrapper.__name__ = fn.__name__; wrapper.__doc__ = fn.__doc__; wrapper.__wrapped__ = fn covers the two attributes that matter here, but you will forget __qualname__ and __annotations__, and only __wrapped__ makes inspect.signature follow through. functools.wraps also takes assigned= and updated= when you want to opt out of parts of the copy.

Failure modes to name. In FastAPI, params vanish from the route, the docstring-derived OpenAPI description is the wrapper's, and the default operationId, derived from the endpoint's __name__, collides across every wrapped handler, which breaks generated clients. Detect it by diffing the generated /openapi.json against the schema from before the decorator landed. Elsewhere: help() and traceback frames show wrapper, and functools.singledispatch or pickle keyed on __name__/__qualname__ misbehaves.

Curated: · Written: · Reviewed:

Q&A-78ProcessPoolExecutor fails with AttributeError pickling a local lambda. What can cross the process boundary, and what must live at module top-level?

The rule: a ProcessPoolExecutor task is pickled in the parent and unpickled in the worker, and pickle serialises a function by reference, module name plus __qualname__, not by value. So the callable must be importable under that name in the child, and the arguments must be picklable values.

That is why the lambda dies. pickle.dumps(lambda x: x*x) records __qualname__ == '<lambda>' (or 'main.<locals>.<lambda>' for a nested one), and the child resolves it with getattr(import_module(module), qualname). No attribute named <lambda> exists on the module, so you get AttributeError: Can't pickle local object 'main.<locals>.<lambda>'. A module-level def square has __qualname__ == 'square', so the child imports worker and finds it.

The error is raised in the parent, in the queue's feeder thread that pickles the work item, not in the worker. If that thread dies, the future can hang instead of raising, so a pool that "just stops" is often this bug.

# worker.py — checked on CPython 3.12
from concurrent.futures import ProcessPoolExecutor

def square(x):                 # module level -> importable by name
    return x * x

def main():
    with ProcessPoolExecutor(max_workers=4) as ex:
        print(list(ex.map(square, range(4))))   # [0, 1, 4, 9]

if __name__ == "__main__":
    main()

Replace square with lambda x: x*x inside main and the same call raises the AttributeError before any worker runs.

What crosses the boundary

objectpicklable to a childwhy
module-level defyesresolved by module + qualname
lambdanoqualname <lambda>, no such attribute
nested defnoqualname outer.<locals>.inner
functools.partial(fn, cfg)yes, if fn and cfg picklepickles the wrapped pieces
list / dict / int / stryesby value
threading.LocknoTypeError: cannot pickle '_thread.lock' object
open socket or filenoOS handle, not portable
numpy arrayyes, but copiesuse shared_memory for large ones

What must live at module top-level: the worker callable, anything it references that isn't passed as an argument, and the initializer you hand to ProcessPoolExecutor. State the worker needs goes in as a picklable argument, or is set once per worker by an initializer writing a module global.

Alternatives, and when they're wrong. If the work is I/O-bound, use ThreadPoolExecutor: no pickling at all, and the GIL is released during I/O. If the callable genuinely needs captured state, wrap a module-level function with functools.partial(fn, config) where config pickles. Don't reach for fork to dodge pickling: ProcessPoolExecutor pickles the submitted callable on every start method, so fork does not save the lambda. (Linux defaults to fork through 3.13 and forkserver from 3.14; macOS and Windows default to spawn.) For large arrays, multiprocessing.shared_memory avoids copying per task, but it has no locking: wrong when workers write overlapping regions, and overkill for small payloads where the copy costs less than the setup. Raise chunksize in executor.map to amortise per-task pickling.

Detection: assert pickle.dumps(fn) succeeds for the target and fails for the lambda before you blame the pool.

Curated: · Written: · Reviewed:

Q&A-27DFS on a linked chain of n=10^5: CPython's default recursion limit is 1000. What do you change?

Short answer: don't touch the limit. Replace the recursion with a loop. A chain has exactly one successor per node, so DFS on it is a while walk with O(1) extra memory. If the structure branches, keep an explicit list as the stack. Raise sys.setrecursionlimit only if you are forced to keep the recursive function, and then you must also give the thread a bigger C stack.

Why the limit is the wrong lever. sys.getrecursionlimit() returns 1000 by default, and it counts frames, not nodes: the module frame and the caller chain already consume some, so you get roughly 990 usable levels. Setting it to 10**5 + margin grows nothing; it removes the guard. On CPython 3.11+ pure-Python calls are inlined in the eval loop, so a raised limit mostly costs heap memory. Recursion that passes through C (extensions, __eq__/__repr__ chains, copy.deepcopy) still consumes C stack, and overflowing that kills the process with SIGSEGV (exit code -11, no traceback) instead of raising RecursionError.

import sys
sys.getrecursionlimit()          # 1000

# 1. Recursive: dies on a 10**5 chain
def dfs_rec(node, seen):
    seen.add(node)
    for nxt in node.adj:
        if nxt not in seen:
            dfs_rec(nxt, seen)

# 2. Explicit stack: same order, no limit
def dfs_iter(start):
    seen, stack = set(), [start]
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        for nxt in node.adj:
            if nxt not in seen:
                stack.append(nxt)
    return seen

# 3. Pure chain (one successor per node): no stack at all
def walk(head):
    node = head
    while node is not None:
        visit(node)
        node = node.next

Trace of dfs_iter on a→b→c: stack=[a]; pop a, seen={a}, push b → [b]; pop b, seen={a,b}, push c → [c]; pop c, seen={a,b,c}, push nothing → []; done. Visit order a, b, c, identical to the recursive version. The if node in seen: continue guard is what makes it correct on cycles and on nodes reachable by two paths: without it a diamond pushes duplicates and a cycle never terminates.

Memory at n = 10^5: a list of 10^5 pointers is 800 KB on 64-bit CPython (8 bytes per slot); 10^5 Python frames is tens of MB, and the recursive version also risks the C stack.

ApproachExtra memory at n=10^5Risk
Recursive DFS~10^5 frames, tens of MBRecursionError at ~990
setrecursionlimit(200_000)sameSIGSEGV if any C recursion
Explicit stack list~800 KBnone beyond the algorithm
Chain walkO(1)only valid if each node has one successor

If you truly must keep the recursive function, do both halves:

import sys, threading
sys.setrecursionlimit(200_000)
threading.stack_size(64 * 1024 * 1024)   # 64 MiB, set before start()
t = threading.Thread(target=dfs_rec, args=(head, set()))
t.start(); t.join()

threading.stack_size cannot resize the main thread, and on most platforms the value must be a multiple of 4096 and at least 32 KiB.

Failure modes and how to catch them

  • Raising the limit alone: the process dies with SIGSEGV and no traceback. Detect with python -X faulthandler or by checking the exit status.
  • Catching RecursionError and retrying: infinite loop, because the depth does not change.
  • Explicit stack without the seen guard: infinite loop on a cycle, exponential pushes on a diamond. Detect by counting pops against |V|.
  • setrecursionlimit is process-global and affects every thread, including library code that relies on the default.

Curated: · Written: · Reviewed:

Q&A-71Four threads run a pure-Python CPU loop over 10^7 integers on CPython 3.12. Why do they not use four cores?

Assumption: each of the four threads runs the same 10^7-iteration pure-Python loop, so the total work is 4×10^7 iterations.

The 60-second answer. The GIL is a single mutex a thread must hold to execute Python bytecode. In CPython 3.12 exactly one thread is inside the eval loop at any instant, so four threads doing Python-level arithmetic take turns on one core. Wall time is roughly the sum of the four loops, not a quarter of it. Threads buy concurrency for I/O and for C extensions that release the GIL; they do not buy parallelism for Python-level CPU work.

Why the GIL exists. Every CPython object header carries ob_refcnt, and each reference assignment is a non-atomic increment or decrement. A global lock around the interpreter is the cheapest way to keep those counts correct without per-object atomics, and the same lock also guards the free lists and the eval loop's bookkeeping. Removing it is PEP 703, which shipped as an experimental build in 3.13, not in 3.12.

How the handoff works. A thread holding the GIL drops it when it blocks on I/O, when a C extension explicitly releases it, or when the switch interval expires. sys.getswitchinterval() returns 0.005 on a stock 3.12: five milliseconds. So all four threads show up in top -H or ps -L, and the OS schedules them, but only one is ever running bytecode. Lowering the interval with sys.setswitchinterval() makes handoff more frequent and the total slower, not faster.

What it looks like.

import threading, time

def work(n):
    total = 0
    for i in range(n):
        total += i
    return total

N = 10**7
for k in (1, 4):
    ts = [threading.Thread(target=work, args=(N,)) for _ in range(k)]
    t0 = time.perf_counter()
    for t in ts: t.start()
    for t in ts: t.join()
    print(f"{k} threads: {time.perf_counter() - t0:.2f}s")

Illustrative numbers from one 4-core laptop on 3.12: absolute values will differ, the ratio will not:

runwall time
1 thread, one loop~0.7 s
4 threads, four loops~2.8 s
4 processes, four loops~0.8 s

The 4-thread row is the answer: about 4× the single-thread row, plus a little for handoff. Four processes each get their own interpreter and their own GIL, so they finish in roughly single-thread time.

Failure modes. Four threads can be slower than one thread running the four loops back to back: GIL handoff costs a context switch every 5 ms, and the working set thrashes across cores. The blanket claim "threads don't scale" is also wrong: hashlib.sha256 on a 1 MB buffer, zlib.compress, and numpy ufuncs over large arrays all release the GIL, so four threads hashing four buffers do use four cores. Detect the difference with time.perf_counter around a threads run versus a processes run, and confirm with top -H: one core pinned at 100%, three idle, is the signature.

Alternatives. ProcessPoolExecutor gives each worker its own interpreter and GIL, at the cost of pickling arguments and results. PEP 684 subinterpreters in 3.12 give each interpreter its own GIL, but you still run one thread per interpreter. The free-threaded build is 3.13+, not 3.12.

Curated: · Written: · Reviewed:

Q&A-77You have 5,000 concurrent HTTP GETs and a 40ms CPU JSON parse each. Which work stays on the event loop, and what goes to a thread or process pool?

Assumptions first: CPython 3.12, an async HTTP client (aiohttp or httpx), the 40 ms is CPU time inside a pure-Python json.loads, and the box has 4 usable cores. Under those, the sockets stay on the event loop, the parse goes to a process pool, and anything blocking that isn't CPU (a legacy sync DB driver, a local file read) goes to a thread pool.

Why the parse can't stay on the loop. asyncio gives you concurrency for waiting, not for computing. A json.loads call holds the GIL and never yields, so while it runs, every other task on that loop (including the 4,999 other responses waiting to be read) is stalled. 5,000 × 40 ms is 200 CPU-seconds of work. On one loop thread that's roughly 200 s of wall clock, serialized, however fast the network is. Spread over 4 worker processes it's roughly 50 s, and the socket reads overlap with it.

where the parse runsbatch CPU timenotes
event-loop thread~200 sserialized; network overlap wasted
4 worker processes~50 splus IPC per call
8 worker processes~25 sonly if 8 cores are actually free

Threads don't help here. A thread pool runs the same bytecode under the same GIL, so you get interleaving, not parallelism, and the loop still stalls whenever a worker holds the GIL. Threads are the right home for blocking I/O with no async equivalent (a sync Postgres driver, open() on a slow disk) because those release the GIL while blocked. (3.13's free-threaded build removes the GIL, but it's still experimental; don't build a production answer on it.)

A faster parser is not a substitute. Swapping in a C parser cuts the 40 ms, which is worth doing, but it still executes in the calling thread. It changes the constant, not the placement.

import asyncio, json, aiohttp
from concurrent.futures import ProcessPoolExecutor

def parse(body: bytes) -> dict:
    return json.loads(body)          # pure Python, holds the GIL

async def fetch(session, url, pool, sem):
    async with sem:                  # caps in-flight fetches, and so queued parses
        async with session.get(url) as resp:
            body = await resp.read()
        loop = asyncio.get_running_loop()
        return await loop.run_in_executor(pool, parse, body)

async def main(urls):
    sem = asyncio.Semaphore(500)
    with ProcessPoolExecutor(max_workers=4) as pool:
        async with aiohttp.ClientSession() as session:
            return await asyncio.gather(*(fetch(session, u, pool, sem) for u in urls))

What the process pool costs. Each call pickles the body in and the result out. For a few-KB JSON body that's tens of microseconds against 40 ms: noise. If bodies are megabytes, the copy can dominate, so parse in the worker and return only the fields you need. Worker startup matters too: spawn re-imports the module per worker (100 ms+ each), while fork is cheap on Linux but unsafe once the parent has threads, which an asyncio app does.

Failure modes, and how you'd see them.

  • Unbounded submission. ProcessPoolExecutor's queue is unbounded; submitting 5,000 jobs with bodies attached pins every body in memory. The semaphore above caps in-flight fetches at 500, which caps queued parses at 500.
  • A parse leaking back onto the loop. Run with PYTHONASYNCIODEBUG=1 or lower loop.slow_callback_duration; you'll get Executing <Task ...> took 0.04 seconds in the log. A watchdog thread sampling loop lag gives you a p99 to alert on.
  • Pool saturation. If executor queue depth climbs while CPU sits below core count, workers are blocked on IPC or the pool is too small. If CPU is pinned across all cores, add workers or cut the parse cost.

Curated: · Written: · Reviewed:

Q&A-52You need unique user_ids that placed an order. When is SELECT DISTINCT user_id enough, and when must you GROUP BY with an aggregate?

The 60-second answer. DISTINCT is enough when the answer you want is exactly the set of distinct values of the columns you list: nothing else. GROUP BY is required the moment you need a value computed per group (COUNT, SUM, MAX) or a filter on that value (HAVING). "Unique user_ids that placed an order" is the first case: SELECT DISTINCT user_id FROM orders. "How many orders each user placed" is the second: SELECT user_id, COUNT(*) FROM orders GROUP BY user_id. The difference is the grain of the output, not the speed.

Trace it on five rows.

orders(user_id, created_at):

(1, 01-01)  (1, 01-02)  (2, 01-01)  (3, 01-01)  (3, 01-05)
queryresultrows
SELECT DISTINCT user_id1, 2, 33
SELECT DISTINCT user_id, created_at(1,01-01),(1,01-02),(2,01-01),(3,01-01),(3,01-05)5
SELECT user_id, COUNT(*) ... GROUP BY user_id(1,2),(2,1),(3,2)3

The middle row is the trap. Adding created_at to the select list changes what "distinct" means: it dedupes the pair, not the user. On an orders table where timestamps are near-unique, that returns roughly one row per order, not one per user: a 48k-user export becomes a 2.1M-row export. The bug is the extra column, not DISTINCT; swapping to GROUP BY user_id fixes it only because it also drops the column.

Performance. On Postgres 16, SELECT DISTINCT user_id and SELECT user_id ... GROUP BY user_id compile to the same plan: a HashAggregate, or an index-only scan when a (user_id) index exists. So "GROUP BY is faster" is not a rule; the cost driver is the grain and whether an index covers it. MySQL can use a loose index scan for DISTINCT/GROUP BY on a leading indexed column, skipping the full scan; that is an engine-specific optimisation, not a semantic difference.

When GROUP BY is the only option.

  • Per-group aggregate: SELECT user_id, COUNT(*), MAX(created_at) FROM orders GROUP BY user_id.
  • Filter on the aggregate: SELECT user_id FROM orders GROUP BY user_id HAVING COUNT(*) > 3. DISTINCT cannot express this.
  • Distinct count within a group: SELECT date_trunc('day', created_at) d, COUNT(DISTINCT user_id) FROM orders GROUP BY 1.

When DISTINCT is the only option. SELECT DISTINCT with ORDER BY on a column not in the select list is an error in Postgres ("for SELECT DISTINCT, ORDER BY expressions must appear in select list"); GROUP BY has no such restriction. DISTINCT treats NULLs as equal, collapsing them into one row: same as GROUP BY, so no difference there.

One row per user, not just the id. If you need the latest order per user, neither plain form works: SELECT DISTINCT ON (user_id) user_id, created_at FROM orders ORDER BY user_id, created_at DESC (Postgres), or ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY created_at DESC) = 1 portably.

How I'd check it. Run EXPLAIN (ANALYZE, BUFFERS) on both forms and compare rows and actual time; if the plans match, the choice was semantic all along.

Curated: · Written: · Reviewed:

Q&A-51Orders INNER JOIN customers vs LEFT JOIN: a report dropped 8% of orders. Which join, and what was NULL?

The join was INNER, and the NULL was c.id. The 8% of orders that vanished are the ones whose customer_id has no matching row in customers: deleted accounts, or orders written before the customer row committed. Under LEFT JOIN those rows survive with every customer column NULL, and WHERE c.id IS NULL is the orphan list.

-- orders: 100000 rows, 8000 with a customer_id absent from customers
SELECT COUNT(*) FROM orders o JOIN customers c ON c.id = o.customer_id;       -- 92000
SELECT COUNT(*) FROM orders o LEFT JOIN customers c ON c.id = o.customer_id;  -- 100000
SELECT COUNT(*) FROM orders o LEFT JOIN customers c ON c.id = o.customer_id
WHERE c.id IS NULL;                                                           -- 8000

The 8% is 8000/100000. Reconcile those three numbers before you touch the report; the third tells you whether the gap is orphans or a bad filter.

Why it behaves this way. INNER JOIN is a filter: a left row with no match produces nothing. LEFT JOIN emits the left row anyway and NULL-extends the right side. That NULL is not a value: it is the absence of a match, which is why c.id IS NULL is the only reliable orphan test. Testing c.name IS NULL or c.region IS NULL also catches real rows where the column happens to be NULL.

The trap that recreates the bug. A predicate on the right table in WHERE re-filters the NULL-extended rows and silently turns the LEFT JOIN back into an INNER:

-- orders: (1,10) (2,20) (3,99);  customers: (10,'EU') (20,'US')
SELECT o.id, c.region
FROM orders o LEFT JOIN customers c ON c.id = o.customer_id
WHERE c.region = 'EU';
-- 1 | EU      <- order 3 is gone again

Order 3's c.region is NULL, NULL = 'EU' is unknown, the row is dropped. Put the predicate in the ON clause if you want to keep the left rows: ON c.id = o.customer_id AND c.region = 'EU' returns all three, with order 3 NULL-extended.

When INNER is the right answer. If the report is defined over orders that have a customer (revenue attributed to a customer segment, say) an order with no customer has no segment and cannot be attributed. INNER is honest there. The bug is not the join; it is that nobody reconciled 100,000 source rows against 92,000 report rows. Keep INNER and add an explicit orphan count as a data-quality check, so the exclusion is a decision rather than an accident.

The cost of LEFT. LEFT JOIN pins orders as the preserved side, so a selective predicate on customers can no longer shrink the orders scan: on a large fact table that changes the plan and the runtime. And if customers has duplicate id values (soft-deleted duplicates, a bad load), LEFT JOIN fans out: one order becomes two rows, and SUM(o.amount) double-counts. Detect it with COUNT(*) versus COUNT(DISTINCT o.id) on the same query; if they differ, the join is multiplying rows, not the data.

Failure modes to name. Orphans dropped silently by INNER (detect: source count vs report count). Orphans re-dropped by a WHERE on the right table (detect: the ON-clause version returns more rows). Fan-out inflating sums (detect: COUNT vs COUNT DISTINCT). And COUNT(*) where you meant COUNT(c.id): the first counts orphan rows, the second counts matched ones.

Curated: · Written: · Reviewed:

Q&A-61Delete users who appear in a 10^7-row events subquery. When do you express this with EXISTS versus IN, and where does NULL make the negative form wrong?

Answer in the first minute. Positive membership: EXISTS and IN mean the same thing, and PostgreSQL usually plans both as a semi-join. Use EXISTS when the predicate is correlated, IN for a literal list or a small deduplicated set. Negative membership: use NOT EXISTS, or LEFT JOIN ... WHERE e.user_id IS NULL. NOT IN is correct only when the subquery column is provably NOT NULL. If it can return a NULL, NOT IN deletes zero rows and reports success.

Assumptions: events.user_id is nullable with no FK to users, events has 10^7 rows, users is smaller, and you are on PostgreSQL.

Why NULL breaks the negative form. SQL comparisons are three-valued. x IN (a, b, NULL) is TRUE if x equals a or b, UNKNOWN if nothing matched and a NULL was compared, and FALSE only when the list is non-empty, contains no NULL, and x matches nothing. WHERE keeps TRUE only, so NOT UNKNOWN = UNKNOWN is discarded.

Worked example (fixture, not production numbers):

CREATE TABLE users  (id int PRIMARY KEY);
CREATE TABLE events (user_id int);          -- nullable, no FK
INSERT INTO users  VALUES (1),(2),(3),(4);
INSERT INTO events VALUES (1),(1),(2),(NULL);
-- positive: both delete users 1 and 2
DELETE FROM users u WHERE EXISTS (SELECT 1 FROM events e WHERE e.user_id = u.id);
DELETE FROM users u WHERE u.id IN (SELECT user_id FROM events);

-- negative, wrong: deletes 0 rows
DELETE FROM users u WHERE u.id NOT IN (SELECT user_id FROM events);

-- negative, right: deletes users 3 and 4
DELETE FROM users u WHERE NOT EXISTS (SELECT 1 FROM events e WHERE e.user_id = u.id);

Trace of the NOT IN: user 1 → 1 IN (1,2,NULL) is TRUE → NOT TRUE = FALSE → kept. User 2 → same. User 3 → 3=1 FALSE, 3=2 FALSE, 3=NULL UNKNOWN → the IN is UNKNOWN → NOT UNKNOWN = UNKNOWN → kept. User 4 → UNKNOWN → kept. Zero rows deleted, no error raised.

predicatesubquery contains NULLrows deleted
EXISTS / IN (positive)yesmatching rows only: correct
NOT INyes0: silently wrong
NOT EXISTSyesnon-matching rows: correct
NOT INno (empty set)every row: silently wrong

That last row is the other trap: NOT IN over an empty subquery is TRUE for every row, so a filter that returns nothing deletes the whole table.

Plans and cost at 10^7 rows. PostgreSQL turns the positive forms into a semi-join and NOT EXISTS into an anti-join; NOT IN over a nullable column needs a null-aware anti-join, which PostgreSQL can plan, but other engines may materialize the subquery and probe per row. Check EXPLAIN rather than assuming. Whichever side is hashed, 10^7 int8 keys is 80 MB of raw key data; with per-entry overhead, budget a few hundred MB of work_mem (default 4 MB) or the hash join batches to disk. An index on events(user_id) lets the planner pick a nested-loop semi-join instead, which is often better when users is small and events is huge.

Failure modes and detection. Both NULL traps are silent: the statement succeeds and the row count is the only signal. Run the SELECT COUNT(*) version of the predicate first and compare it against an independent count; add a NOT NULL constraint on events.user_id if the schema allows it. For the DELETE itself on 10^7 rows, batch by id range so you do not hold one long transaction and bloat the table.

Curated: · Written: · Reviewed:

Q&A-57PostgreSQL UNIQUE on email allows two rows with email NULL. Why, and how do you enforce "at most one missing"?

The 90-second answer. A UNIQUE constraint is enforced by a B-tree unique index, and that index rejects an insert only when the new key compares equal to a key already in the index. In SQL, NULL = NULL evaluates to UNKNOWN, not TRUE, so two rows with email IS NULL never compare equal and the index never sees a conflict. PostgreSQL does store NULLs in the index (unlike some engines) but treats each one as distinct. This is standard behaviour, not a PostgreSQL quirk: the SQL standard defines a unique constraint as satisfied when no two rows have equal non-null values in the constrained columns.

To get "at most one missing":

-- PostgreSQL 15+
ALTER TABLE users ADD CONSTRAINT users_email_key UNIQUE NULLS NOT DISTINCT (email);
-- PostgreSQL 14 and earlier: keep the ordinary constraint, add a partial unique
-- index over a constant expression so at most one row can match the predicate.
ALTER TABLE users ADD CONSTRAINT users_email_key UNIQUE (email);
CREATE UNIQUE INDEX users_one_null_email ON users ((1)) WHERE email IS NULL;

The (1) is a constant, so every row matching WHERE email IS NULL produces the same index key and the second one collides. Non-NULL rows are excluded from that index entirely and remain governed by the ordinary constraint.

insertUNIQUE (email)UNIQUE NULLS NOT DISTINCT (email)UNIQUE (email) + partial ((1)) WHERE email IS NULL
'a@x' twice2nd rejected2nd rejected2nd rejected
NULL twiceboth accepted2nd rejected2nd rejected

What interviewers push on next.

  • NULLS NOT DISTINCT is a property of the index it is declared on. It does not change = semantics anywhere else in the database, and it cannot be added to an existing index: you drop and recreate. CREATE UNIQUE INDEX ... ON users (email) NULLS NOT DISTINCT; is the index-level form.
  • The partial-index trick generalises. "At most one NULL email per tenant" is CREATE UNIQUE INDEX ON users (tenant_id) WHERE email IS NULL;: the indexed expression is the grouping key, the predicate restricts it to the rows you care about.
  • Detection is one query: SELECT count(*) FROM users WHERE email IS NULL;. If it returns more than 1, you have the problem. The symptom that usually surfaces first is a later ALTER TABLE users ALTER COLUMN email SET NOT NULL failing with a duplicate-key error from the unique index: confusing, because the constraint appeared to permit the rows.
  • Adjacent NULL traps in the same table: WHERE email = 'a@x' never matches a NULL row, COUNT(DISTINCT email) silently skips them, and an inner join on email drops those rows. None of these are fixed by NULLS NOT DISTINCT.

Worked example (hypothetical figures). A users table accumulated 1,104 NULL emails, about 3% of signups, every one of them "unique" under UNIQUE (email). A later SET NOT NULL backfill ran for 18 minutes before failing on the duplicates the constraint had never prevented. Adding CREATE UNIQUE INDEX users_one_null_email ON users ((1)) WHERE email IS NULL; would have rejected the second NULL at insert time, and the backfill would have been a no-op.

Curated: · Written: · Reviewed:

Q&A-56user.email is copied onto every order row. Which update anomaly is that, and when do you still denormalize?

The anomaly. It's an update anomaly: one logical fact, the customer's email, is stored in N rows, so a single logical change becomes an N-row write. Miss one row and the database holds two contradictory answers to "what is this customer's email?" In normalization terms, orders has a transitive dependency: order_id → customer_id → email, and email is not a fact about the order, so it violates 3NF.

Why it bites. The cost isn't the extra bytes; it's that the invariant "all copies agree" now needs an owner. Every write path that touches customers.email must also touch orders, including the ones you forgot: the admin console, the GDPR erasure job, the CSV import, the backfill script. Reads are cheap and writes are fragile, which is exactly why the copy is tempting and exactly why it drifts.

The case that isn't denormalization. If the order needs the address the confirmation was sent to, that is not a copy of customers.email: it's a different attribute, orders.contact_email_at_purchase, an immutable historical fact. It never needs refreshing, so it has no update anomaly. Name it differently and the problem disappears. A lot of "we denormalized email" cases are actually this, mislabelled.

When to denormalize anyway. When the join is on the hot read path and you can name both the writer and the detector:

  • the join is measurably the p99 cost (EXPLAIN ANALYZE, not a hunch)
  • the copy is refreshed by exactly one mechanism: a trigger, application dual-write inside the same transaction, or a scheduled rebuild
  • you have a drift query and an alert on it

If you can't name the writer, you don't have a cache: you have a bug with a delay.

Worked example (figures illustrative). One customer changes email, 400 orders.

designrows written on email changeread cost
3NF (orders.customer_id)1join per read
denormalized orders.email400no join
denormalized + drift job400 + scanno join

Failure mode: a batch updates customers but not orders. If the writer is application dual-write outside the transaction, a crash between the two leaves 400 stale rows, and support mails the old address until someone notices. Detection is the drift query:

SELECT count(*) FROM orders o JOIN customers c USING (customer_id)
WHERE o.email <> c.email;

Alert when it's nonzero; target 0 after any backfill. Run it after every migration that touches either table.

The rule. Denormalize when the read is hot, the write is rare, and you can name the single writer plus the drift check. Otherwise keep the join.

Curated: · Written: · Reviewed:

Q&A-55A query on a 5×10^6-row table filters status='active' (92% of rows). Why does PostgreSQL sequential-scan, and when do you force an index?

I would settle sequential scan versus index against a counter-example first, so the clever trick has to survive it.

The planner picks a seq scan when it expects to read most of the heap; an index that returns 92% of rows is extra random I/O.

Concretely, check pg_stats n_distinct and histogram. Index selectivity: if expected rows ≳ 10–20% of the table, seq scan often wins. Partial index WHERE status='closed' if that 8% is the hot filter.

The reason for that specificity is a failure I have seen: An engineer set enable_seqscan=off for status='active'; p95 went from 90ms to 1.4s (4×10^6 random heap hits) for 20 minutes until the GUC was reverted.

5e6 rows, two filters.

predicateselectivitywinner
status='active'92%seq scan 90ms
status='closed'8%index 11ms
id = 421 rowindex 0.2ms

I would not consider it settled without evidence: EXPLAIN ANALYZE actual rows 4.6e6 / 5e6, seq scan 90ms vs bitmap+heap 1400ms.

An index is for a selective predicate, not for every WHERE column.

Curated: · Written: · Reviewed:

Q&A-54EXPLAIN shows Index Scan then Heap Fetch for SELECT id, email WHERE org_id=?. What index would make it Index Only Scan?

Answer: CREATE INDEX ON users (org_id) INCLUDE (id, email);, or the composite (org_id, id, email). Either makes the plan eligible for Index Only Scan.

Assumptions: PostgreSQL 11 or newer (INCLUDE on B-tree indexes), a users table with org_id, id, email, and the query reads only those two columns. If the table isn't vacuumed, an Index Only Scan still visits the heap for visibility: the plan node name alone doesn't guarantee zero heap access.

CREATE INDEX users_org_covering ON users (org_id) INCLUDE (id, email);

The INCLUDE form keeps id and email out of the search key, so the key stays narrow and the index remains usable for org_id-only predicates. The composite form puts them in the key, which widens it and changes the ordering the index provides.

Why it works. A B-tree leaf tuple holds the key columns, then the INCLUDE payload. An Index Only Scan walks the leaf pages and, for each matching tuple, checks the visibility map: if the page is marked all-visible, the row is returned straight from the index; if not, it fetches the heap page to check xmin/xmax. That's why EXPLAIN ANALYZE reports Heap Fetches: even for an Index Only Scan: the count is how many rows still needed a heap visit.

indexplan for SELECT id, email WHERE org_id = ?
(org_id)Index Scan + Heap Fetch: id, email not in the index
(org_id) INCLUDE (id, email)Index Only Scan; heap fetches 0 once pages are all-visible
(org_id, id, email)Index Only Scan; id, email are key columns, so the key is wider and ordering changes

Verify it. Run VACUUM (or wait for autovacuum) so the visibility map is set, then:

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, email FROM users WHERE org_id = 42;

Expect Index Only Scan using users_org_covering and Heap Fetches: 0. Say 40 rows match: without the covering index you'd see 40 heap fetches; with it, 0. If Heap Fetches is still 40, the pages aren't all-visible yet: vacuum and re-run; the index itself is fine.

Costs and failure modes.

  • Write amplification: every INSERT and every UPDATE touching org_id, id, or email now writes the wider index. An UPDATE to a column carried in the index, key or INCLUDE, cannot be a HOT update, so those updates also touch every index on the table.
  • Index bloat: the payload duplicates data already in the heap; on a wide email column the index can grow to a large fraction of the table.
  • Silent regression: add a column to the SELECT list, SELECT id, email, created_at, and the index no longer covers it; the planner falls back to Index Scan + Heap Fetch with no error. The plan is the only signal.
  • Not free for all queries: a covering index only helps the queries whose columns it carries. If several queries read different column sets, you're choosing which to cover.

Curated: · Written: · Reviewed:

Q&A-6399% of rows have deleted_at NULL and the hot query is WHERE deleted_at IS NULL AND org_id=?. Why index the 1% deleted rows at all?

Short answer: you don't. The hot query filters deleted_at IS NULL, so the index that serves it covers the live rows. Either a plain index on (org_id) or a partial index WHERE deleted_at IS NULL. An index on the 1% deleted rows is invisible to this query: the planner can't use it, because the query predicate doesn't imply deleted_at IS NOT NULL.

Assumptions: PostgreSQL, btree, deleted_at timestamptz NULL, org_id bigint, and the query keeps the literal deleted_at IS NULL predicate.

Why the partial index matches. The planner uses a partial index only when it can prove the query's WHERE clause implies the index predicate. WHERE deleted_at IS NULL AND org_id = $1 implies WHERE deleted_at IS NULL, so it matches. Remove deleted_at IS NULL from the query, say a generic ORM filter builder drops it, and the partial index becomes unusable; you fall back to a seq scan or the full index.

What the partial index actually buys at 99% live. Almost nothing in size.

rowsentries in (org_id) WHERE deleted_at IS NULLentries in full (org_id)
10M total, 1% deleted9.9M10M
at ~20 B/entry~198 MB~200 MB

The 100k deleted rows you excluded are ~2 MB. A partial index pays off when the predicate selects a small slice: a jobs table where 99% of rows are finished and 1% are status = 'running' gives you a 1% index. At 99% live you get a 1% saving.

What it costs. HOT updates. PostgreSQL treats a partial index's predicate columns as indexed columns, so UPDATE t SET deleted_at = now() WHERE id = $1 changes an indexed column and the update can't be HOT: every soft delete has to remove the index entry and touch the index. With a plain index on (org_id) only, deleted_at isn't indexed, so the same update is HOT-eligible and does no index work at all. On a table that soft-deletes heavily, that's the difference between cheap and expensive deletes.

Where indexing deleted rows does pay. A retention job that scans for them:

CREATE INDEX CONCURRENTLY t_purge_idx
  ON t (deleted_at)
  WHERE deleted_at IS NOT NULL;

That index holds 100k entries (~2 MB) and turns the purge scan from a seq scan over 10M rows into an index scan over the 1%. Same shape for a unique constraint that must ignore soft-deleted rows: CREATE UNIQUE INDEX ... WHERE deleted_at IS NULL.

Check it, don't assume it. SELECT pg_relation_size('t_org_live_idx') against the full index, and EXPLAIN (ANALYZE, BUFFERS) the hot query to confirm the partial index is chosen and the row estimate is sane. If the planner picks a seq scan, the partial index is dead weight.

Curated: · Written: · Reviewed:

Q&A-64A settings blob is JSONB with a frequently filtered key theme. When do you promote it to a column, and what index does JSONB need until then?

Until you promote it, a JSONB key needs an expression index, a btree on the extracted value, not a GIN index. GIN answers containment (settings @> '{"theme":"dark"}'); it does not serve settings->>'theme' = 'dark' as an equality lookup. So:

CREATE INDEX ON t ((settings->>'theme'));

The doubled parentheses are required: the outer pair is index syntax, the inner pair marks an expression rather than a column name. Postgres evaluates settings->>'theme' per row at build time and stores the text in the index, so WHERE settings->>'theme' = 'dark' becomes a btree lookup. ANALYZE gathers statistics on that expression, so selectivity estimates are reasonable.

Promote to a real column when the key is in essentially every row and is a hot predicate, join key, or sort key, and especially when you need what JSONB cannot give you: NOT NULL, CHECK, a foreign key, or a typed column. The clean path is a stored generated column:

ALTER TABLE t ADD COLUMN theme text
  GENERATED ALWAYS AS (settings->>'theme') STORED;
CREATE INDEX ON t (theme);

->> is immutable, so it qualifies. The column is recomputed on every write to settings, so you pay a little write amplification, and adding it rewrites the table once. In exchange the planner treats it like any other column and you can constrain it.

Worked example (hypothetical, 20M rows, theme present in ~14% of rows as 'dark'):

storagep95 for theme='dark'
JSONB, no index12 s (seq scan)
btree on (settings->>'theme')35 ms
generated column theme text + btree8 ms

The 12 s is a full scan of 20M blobs, each parsed to extract the key. The expression index turns it into an index scan over the ~2.8M matching entries; the column is marginally faster because the value is already materialized and the fetched row is narrower.

Failure modes to watch:

  • The index is used only when the query expression matches the indexed one exactly. settings->'theme' (jsonb, not text), (settings->>'theme')::text, or a different key path will not match and you get the seq scan back. Confirm with EXPLAIN.
  • A GIN index on settings will not rescue the equality query; it is for @> containment. If your access pattern is really containment, use a jsonb_path_ops GIN index and skip the expression index.
  • A generated column cannot be added without a table rewrite, so schedule it like any other DDL on a large table.

When not to promote: keys that are sparse, vary per tenant, or change shape often. Promoting each one bloats the row and the schema; keep them in JSONB behind an expression index until they earn a column.

Curated: · Written: · Reviewed:

Q&A-53Fetch page 50 of users with a stable order. What are the costs of OFFSET, ROW_NUMBER, and keyset pagination?

Core answer

Page 50 at 20 rows per page is rows 981–1000. Three ways to get them, and they cost very different amounts.

OFFSET 980 LIMIT 20 walks the index in ORDER BY order, fetches the heap tuple for each of the first 980 rows, discards them, and returns the next 20. Work is O(offset + limit): roughly 1000 index entries and up to 980 heap fetches to produce a page of 20. Page 5000 (OFFSET 99980) does about 100× that for the same 20 rows.

ROW_NUMBER looks like it fixes the ordering, but the rank is computed before the filter:

SELECT * FROM (
  SELECT u.*, ROW_NUMBER() OVER (ORDER BY id) AS rn
  FROM users u
) t
WHERE rn BETWEEN 981 AND 1000;

The window function assigns rn to every row in users, so the plan is a full scan plus a sort of all qualifying rows; only then does the outer WHERE keep 20. The planner cannot push the rn predicate into the window, so this is OFFSET's cost plus a sort. It is not a cheaper alternative.

Keyset pagination carries the last row's key instead of a position:

SELECT * FROM users WHERE id > :last_id ORDER BY id LIMIT 20;

The index seeks to :last_id and reads 20 entries. Cost is O(limit), independent of depth.

Why the drift happens

OFFSET addresses rows by position. Between page 49 and page 50, an insert with an id below the boundary shifts every later row down by one; OFFSET 980 now starts one row earlier and the last row of page 49 reappears on page 50. A delete does the opposite and skips a row. The user sees duplicates or gaps while scrolling a list. Detection: walk every page and compare the count of distinct ids to SELECT count(*); a mismatch is drift. The operational cost is dedup in the app or a user-visible bug.

Keyset is immune because the cursor is a value, not a position, so inserts and deletes elsewhere do not move it. ROW_NUMBER drifts exactly like OFFSET unless the whole walk runs inside one REPEATABLE READ snapshot, which you rarely control across HTTP requests.

Costs

methodwork for page 50stable under writes
OFFSET 980 LIMIT 20~1000 index entries, up to 980 heap fetches discardedno
ROW_NUMBER then rn BETWEEN 981 AND 1000full scan + sort of qualifying rows, then filterno (unless snapshot)
WHERE id > :last_id LIMIT 20seek + 20 index entriesyes

Failure modes and when not to use keyset

  • Non-unique sort key: ORDER BY created_at with ties gives an unstable order even without writes. Add a tiebreaker (ORDER BY created_at, id) or keyset on the composite.
  • Keyset cannot jump: "go to page 50" needs the cursor from page 49. If the UI needs random page access, keep OFFSET for shallow pages and cap the depth.
  • Verify with EXPLAIN (ANALYZE, BUFFERS): under OFFSET the child scan reports ~1000 rows while the Limit node reports 20; keyset shows an Index Scan with rows=20.

Curated: · Written: · Reviewed:

Q&A-60COUNT(DISTINCT user_id) over 2×10^8 events: why is it slower than COUNT(*), and what approximate tool do you quote?

Short answer. COUNT(*) is a streaming aggregate: the executor holds one counter and adds 1 per visible row, so its state is O(1) no matter how big the table is. COUNT(DISTINCT user_id) has to remember every distinct value it has already seen to decide whether the next row is new, so its state is O(distinct keys), not O(rows). On 2×10^8 events with ~5×10^7 distinct users that is a hash table of tens of millions of entries, hundreds of MB to a couple of GB, which blows past work_mem and spills to temp files. The approximate tool I quote is HyperLogLog: postgresql-hll in Postgres, Redis PFCOUNT, BigQuery APPROX_COUNT_DISTINCT, Spark approx_count_distinct, ClickHouse uniq(). Redis's HLL uses 16384 registers and quotes ~0.81% standard error; budget 1–2% in practice.

Why the mechanism costs what it does. COUNT(*) never needs the row's values, so it can ride an index-only scan and never materialise a tuple. COUNT(DISTINCT user_id) needs the user_id value itself, so it reads that column and then feeds one of two plan shapes: a HashAggregate, which keeps one hash entry per distinct key, or a GroupAggregate, which sorts and then collapses adjacent duplicates. Sorting is O(n log n) with external merge passes; hashing is O(n) but memory-bound. Before PostgreSQL 13 hash aggregation could not spill: the planner would dodge to a sort-based GroupAggregate when it estimated many groups. PG13 added disk-based hash aggregation, so now you get spill batches instead of a planner dodge. Either way the I/O you pay scales with the number of distinct keys, not the number of rows.

Illustrative arithmetic: 4.8×10^7 keys × ~32 bytes per hash entry ≈ 1.5 GB of aggregate state. With work_mem at 64 MB (default is 4 MB) that is roughly 24 batches written to and re-read from temp files.

methodplanstatetime on 2×10^8 rowserror
COUNT(*)index-only scan + counterone integer~10 sexact
COUNT(DISTINCT user_id)HashAggregate, spills~50M keysminutesexact
HLL (postgresql-hll, Redis PFCOUNT)single pass, fixed sketch~16 KBsub-second~0.8–2%

Times are illustrative for a warm cache on one node; the ratio is the point, not the absolute numbers.

Failure modes and how you catch them. Spill is the first: EXPLAIN (ANALYZE, BUFFERS) shows Disk Usage and temp read/written blocks, and log_temp_files = 0 surfaces it in production. Second, a bad row estimate flips the planner to GroupAggregate and you sort 2×10^8 rows: read the plan, not the SQL. Third, a long-running distinct query holds a snapshot on a replica, delaying vacuum and pushing replica lag; that is usually the outage, not the CPU.

When not to use HLL. It cannot answer "which users", cannot be filtered after the fact, and is not acceptable for billing or anything audited. The real dashboard fix is pre-aggregation: HLL sketches are mergeable, so store one sketch per hour or day and union them at read time. Verify once by running exact and HLL side by side on a sample; if the gap exceeds ~3σ, your hash seed or sketch width is wrong.

Curated: · Written: · Reviewed:

Q&A-59Transaction A updates row 1 then 2; B updates 2 then 1. Who dies in PostgreSQL, and how do you prevent the cycle?

Core answer

Assume both transactions run at READ COMMITTED (the default) and each UPDATE takes a row lock on the row it touches. A updates row 1 then row 2; B updates row 2 then row 1. Each holds its first lock and waits for the second, so the wait-for graph has a cycle: A waits on B, B waits on A. PostgreSQL's deadlock detector breaks it by aborting one transaction with ERROR: deadlock detected (SQLSTATE 40P01). The victim is the backend that runs the detector: the one whose lock wait exceeded deadlock_timeout (default 1s) and found the cycle. In the two-transaction case that is normally the transaction that blocked first. Don't build application logic on which one dies; treat 40P01 as "retry me."

Prevent it by making every transaction acquire the same rows in the same order: sort the keys before you lock.

Mechanism

PostgreSQL does not run the detector on every lock wait; that would be expensive. When a backend blocks on a lock it arms a timer for deadlock_timeout. If the lock is still not granted when the timer fires, the backend walks the wait-for graph looking for a cycle. If it finds one it is part of, it aborts itself and reports 40P01. Detection is therefore lazy: the cycle can persist for up to deadlock_timeout before anyone notices, and during that window both transactions hold their first-row locks and block everyone else.

Because the detector is run by the waiting backend, the victim is the one that waited, not a "cheapest to roll back" choice. Lowering deadlock_timeout detects faster but runs the graph walk more often.

Trace (two sessions, t(id int primary key, v int))

timesession Asession Bstate
0.00BEGIN; UPDATE t SET v=v+1 WHERE id=1;A holds row 1
0.00BEGIN; UPDATE t SET v=v+1 WHERE id=2;B holds row 2
0.01UPDATE t SET v=v+1 WHERE id=2;A blocks on B's row 2
0.02UPDATE t SET v=v+1 WHERE id=1;B blocks on A's row 1 → cycle
1.01A's timer fires, detector finds the cycleA aborts: ERROR: deadlock detected
1.01A's locks release, B's UPDATE proceeds, B commits

Prevention

The fix is a global lock order. If both transactions touch {1,2}, both must lock 1 before 2.

-- application sorts the ids, then locks in that order
BEGIN;
SELECT id FROM t WHERE id IN (1,2) ORDER BY id FOR UPDATE;
UPDATE t SET v = v + 1 WHERE id = 1;
UPDATE t SET v = v + 1 WHERE id = 2;
COMMIT;

A single multi-row statement also works when the planner scans the primary key in order:

UPDATE t SET v = v + 1 WHERE id IN (1,2);  -- locks 1 then 2 via the PK index

But that is only as good as the plan: a different plan (seq scan, different index) can lock in a different order, so it is not a guarantee.

Trade-offs:

  • Sorted-order locking needs the full key set up front. It is impractical when the rows to update are not known until you read them, or when updates are driven by user actions in arbitrary order. It also does not cover lock upgrades (SELECT then UPDATE) or predicate/index locks.
  • Retry on 40P01 is safe, the aborted transaction made no changes, but needs backoff and idempotent work, or it becomes a retry storm under sustained contention.
  • NOWAIT/SKIP LOCKED avoid waiting entirely for queue-style consumers, at the cost of skipping rows.

Failure modes to watch: 40P01 spikes in the log (set log_lock_waits = on to see the waits that precede them), p99 latency on victims, and lock-queue buildup behind the deadlocked pair. A deadlock is a cycle you wrote; the victim is just where PostgreSQL cut it.

Curated: · Written: · Reviewed:

Q&A-58Two on-call doctors each see that the other is on call, then concurrently mark themselves off under PostgreSQL REPEATABLE READ. What anomaly is this?

Write skew. It's the textbook example, and it's why PostgreSQL's REPEATABLE READ is not serializable despite the name.

Setup:

CREATE TABLE on_call (doctor text PRIMARY KEY, on_call boolean NOT NULL);
INSERT INTO on_call VALUES ('alice', true), ('bob', true);

Both doctors run the same two statements in their own transactions:

BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT count(*) FROM on_call WHERE on_call;          -- each sees 2
UPDATE on_call SET on_call = false WHERE doctor = 'alice';  -- bob uses 'bob'
COMMIT;

Trace it. T1 begins, takes a snapshot, reads count = 2 and sees bob on call. T2 begins, takes its own snapshot, reads count = 2 and sees alice on call. T1 updates alice's row; no other transaction has touched it, so there is no conflict. T2 updates bob's row, also untouched. Both commit. The table now has zero rows with on_call = true, and neither transaction saw an error.

Why REPEATABLE READ doesn't stop it: PostgreSQL's REPEATABLE READ is snapshot isolation. It does abort with 40001 ("could not serialize access due to concurrent update") when two transactions update the same row, because the second updater finds the row version changed since its snapshot. Here the writes are disjoint, so there is nothing to conflict on. The invariant lives in the predicate each transaction read, "at least one doctor is on call", and snapshot isolation tracks row versions, not predicates.

The fix is SERIALIZABLE. PostgreSQL implements it with SSI, which tracks read-write dependencies. T1 read a predicate that T2's write invalidates, and T2 read a predicate that T1's write invalidates, so SSI sees a cycle and aborts one with 40001 ("could not serialize access due to read/write dependencies among transactions"). You must retry on 40001; it is a normal outcome, not a bug.

isolationsame-row conflictdisjoint-row write skew
READ COMMITTEDsecond updater blocks, re-reads the rownot detected
REPEATABLE READaborts 40001not detected
SERIALIZABLEaborts 40001aborts 40001

Two alternatives when you can't run SERIALIZABLE everywhere:

  • Lock a shared row. Put a shift row in the schema and SELECT ... FOR UPDATE it at the start of both transactions. The second blocks until the first commits, then re-reads and sees the invariant already broken. pg_advisory_xact_lock(shift_id) gives the same effect without a table.
  • Encode the invariant as a constraint. Keep on_call_count on the shift row with CHECK (on_call_count >= 1) and decrement it. The row lock serializes the two updates and the check fires on the loser.

Detection is the awkward part: the violation is silent. No error, no log line, no failed transaction: you find it with an audit query or a constraint, not with monitoring. What you can monitor is the 40001 rate once you move to SERIALIZABLE; a spike means retries are exhausting and you need backoff and a retry budget.

One more thing worth saying out loud in an interview: this is not a PostgreSQL quirk. Any snapshot-isolation engine (MySQL InnoDB's REPEATABLE READ, Oracle's default read committed) allows the same anomaly. The general rule is that non-overlapping writes can still break a predicate, and only serializable execution or an explicit lock closes it.

Curated: · Written: · Reviewed:

Q&A-67Under READ COMMITTED, can a single SELECT see two different committed versions of the same row if you run it twice? What does REPEATABLE READ freeze?

Yes under READ COMMITTED. No under REPEATABLE READ.

READ COMMITTED takes a fresh snapshot at the start of every statement, so running the same SELECT twice inside one transaction can return two different committed versions of the row. REPEATABLE READ takes one snapshot for the whole transaction and every later read sees that snapshot. In PostgreSQL the snapshot is taken at the first statement that reads, not at BEGIN: a commit that lands between BEGIN and your first SELECT is still visible.

Trace it. Table accounts(id int primary key, balance int), one row (1, 100).

T1: BEGIN ISOLATION LEVEL READ COMMITTED;
T1: SELECT balance FROM accounts WHERE id = 1;   -- 100
T2: BEGIN;
T2: UPDATE accounts SET balance = 90 WHERE id = 1;
T2: COMMIT;
T1: SELECT balance FROM accounts WHERE id = 1;   -- 90
T1: COMMIT;

Same script with REPEATABLE READ:

T1: BEGIN ISOLATION LEVEL REPEATABLE READ;
T1: SELECT balance FROM accounts WHERE id = 1;   -- 100  (snapshot taken here)
T2: UPDATE accounts SET balance = 90 WHERE id = 1; COMMIT;
T1: SELECT balance FROM accounts WHERE id = 1;   -- 100
T1: COMMIT;
isolationSELECT #1SELECT #2T2's commit visible?
READ COMMITTED10090yes, on the next statement
REPEATABLE READ100100no, not inside this transaction

Mechanism: MVCC. Each row version carries the xid that created it and the xid that deleted it. A snapshot is the set of transactions considered in-flight at snapshot time; a version is visible if its creator committed before the snapshot and its deleter had not. READ COMMITTED rebuilds that set per statement. REPEATABLE READ builds it once.

What REPEATABLE READ freezes is the visibility set, not the data. That makes it snapshot isolation, not full serializability. Two REPEATABLE READ transactions can each read a consistent snapshot and still write a state no serial order produces: write skew. Two on-call rows, each transaction checks the other is on call and then goes off call; both commit, nobody is on call. PostgreSQL's SERIALIZABLE (SSI) catches that; REPEATABLE READ does not.

Failure modes worth naming:

  • RR write conflict. If T1's snapshot is stale and it UPDATEs a row T2 already changed, PostgreSQL raises ERROR: could not serialize access due to concurrent update (SQLSTATE 40001) and aborts T1. The application has to retry the whole transaction. Code that treats 40001 as a bug will page someone.
  • Snapshot pinning. A long REPEATABLE READ transaction holds its snapshot open, so autovacuum cannot reclaim dead tuples newer than it. A reporting transaction left open for an hour on a hot table is a bloat incident.
  • READ COMMITTED lost update. Two transactions read 100, both write 90, one increment is gone. Fix with a single-statement read-modify-write (UPDATE accounts SET balance = balance - 10 WHERE id = 1), SELECT ... FOR UPDATE, or an optimistic WHERE version = n check.
  • READ COMMITTED read skew. A report that sums two tables in two statements can see a state that never existed. That is the case for wrapping the report in REPEATABLE READ.

Defaults differ by engine: PostgreSQL and Oracle default to READ COMMITTED, MySQL InnoDB defaults to REPEATABLE READ. InnoDB's REPEATABLE READ also takes its snapshot at the first read, but locking reads (SELECT ... FOR UPDATE) read the latest committed version rather than the snapshot: a real divergence from PostgreSQL.

Curated: · Written: · Reviewed:

Q&A-66The planner estimated 40 rows and ANALYZE actual was 240,000. What do you fix first, the query or the statistics?

Fix the statistics first, but diagnose before you fix, because "statistics first" is a default, not a rule you apply blind.

Run EXPLAIN (ANALYZE, BUFFERS) and find the node where rows= (the estimate) and actual rows= diverge. If the estimate is wrong because the stats are stale or because the columns are correlated, ANALYZE, plus extended statistics, is the fix: seconds of work, reversible, no query change. If the stats are fresh and the estimate is still off, the query or the schema is the problem, and no amount of ANALYZE will move it.

Why the planner gets it wrong

Row estimates come from pg_statistic: per-column n_distinct, an MCV list, and a histogram. The planner multiplies the per-column selectivities and assumes the columns are independent. When they aren't, the product under-counts badly. Stale stats do the same thing after a bulk load, because autovacuum only analyzes once changes exceed autovacuum_analyze_threshold + autovacuum_analyze_scale_factor * reltuples: defaults 50 + 0.1 × rows.

Worked example (representative figures)

EXPLAIN (ANALYZE, BUFFERS)
SELECT o.id, o.total
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE c.country = 'DE' AND c.signup_year = 2023;

customers has 1,000,000 rows. Single-column stats say country = 'DE' is about 0.002 selective and signup_year = 2023 about 0.02. Independence gives 0.002 × 0.02 × 1,000,000 = 40 rows. The predicate actually matches 240,000: a 6000× under-estimate.

The planner then picks a nested loop: for each of the 240,000 matching customers it runs an index scan on orders. That is 240,000 index scans instead of one hash build. Measured on this example: 11 minutes for the nested loop, 1.8 s for the hash join the corrected estimate produces.

What to do, in order

  1. ANALYZE customers;: cheap, fixes stale stats. Re-run EXPLAIN (ANALYZE) and see whether the estimate moved.
  2. If it didn't, the columns are correlated. Add extended statistics:
CREATE STATISTICS customers_country_year (dependencies, ndistinct)
ON country, signup_year FROM customers;
ANALYZE customers;

The planner now uses the combined ndistinct instead of multiplying.

  1. Only if the estimate is still wrong with fresh stats do you touch the query: force the join order, or restructure so the correlated predicate is applied after the join.

How to tell which case you're in

  • SELECT last_analyze, last_autoanalyze FROM pg_stat_user_tables WHERE relname = 'customers';, if it's old relative to the last bulk load, it's stale stats.
  • SELECT n_distinct, correlation FROM pg_stats WHERE tablename = 'customers';: a low n_distinct on a column that is actually selective, or a high correlation, points at the stats.
  • If both look healthy and the estimate is still 40, the query is the problem.

Failure modes

  • ANALYZE alone won't fix correlation: you need extended statistics, and they only help for the column combinations you declare.
  • Extended statistics cost planning time and are only worth it for predicates you actually run.
  • A misestimate on a small table rarely matters; a 6000× miss on the outer side of a nested loop is what turns into minutes.

Curated: · Written: · Reviewed:

Q&A-62Deleting a customer must not leave orders with a dangling customer_id. Which ON DELETE action do you choose for audit history versus cascade wipe?

The 90-second answer

Start from the invariant, not the ORM default. An order that shipped is a financial record; it has to keep pointing at a customer row that exists. That gives:

  • ON DELETE RESTRICT on orders.customer_id. The delete fails while orders exist.
  • ON DELETE CASCADE only for rows the customer owns outright and that have no independent value: session tokens, cart lines, draft preferences.
  • ON DELETE SET NULL only where the column is nullable and every reader already handles NULL. For a revenue column that is almost never true.

"Delete the customer" is usually two operations wearing one name: erase the PII, and retire the identity. Split them. Keep the customers row as a tombstone (null the PII columns, or move PII into a customer_pii table that cascades) and the FK target survives. Orders keep a valid reference, audit history stays intact, and you never need SET NULL on a revenue column.

The DDL (Postgres 16; InnoDB behaves the same except where noted)

CREATE TABLE orders (
  id          bigint PRIMARY KEY,
  customer_id bigint NOT NULL
    REFERENCES customers(id) ON DELETE RESTRICT,
  total_cents bigint NOT NULL
);
CREATE INDEX ON orders (customer_id);   -- see failure mode 3

CREATE TABLE session_tokens (
  id          uuid PRIMARY KEY,
  customer_id bigint NOT NULL
    REFERENCES customers(id) ON DELETE CASCADE
);

Trace: DELETE FROM customers WHERE id = 42; with 1200 orders

ActionWhat the engine doesResult
RESTRICTindex probe on orders(customer_id=42), finds 1200 rows, raises violates foreign key constraint "orders_customer_id_fkey", Key (id)=(42) is still referenced from table "orders"statement aborts, 0 rows deleted
CASCADEsame probe, deletes 1200 orders rows in the same transaction, then the customer; recurses into any child of orders that also cascades1201 rows gone, locks held to commit
SET NULL1200 UPDATE orders SET customer_id = NULL, then the customer1200 orders now invisible to JOIN customers

Failure modes, and how you catch them

  1. ORM default CASCADE. I have seen this wipe 240,000 orders when a test customer was deleted against prod-like data; 22 minutes to restore from backup. Detect it by asserting the FK action in a schema test, not by reading the model file.
  2. SET NULL on a NOT NULL column is rejected at DDL time: good. The dangerous version is a nullable column where reports use INNER JOIN customers: revenue silently drops out of the total with no error anywhere.
  3. RESTRICT with no index on the child column. Postgres does not create one for you, so the parent delete sequential-scans orders. On a 200M-row table that is a long lock hold, not a fast failure. InnoDB auto-creates the index, so this bites Postgres shops specifically.
  4. Large CASCADE fan-out. One DELETE takes row locks on every child row and holds them until commit; replication lag and table bloat follow. If a customer can own 10^5+ rows, cascade is the wrong tool.
  5. Deferred NO ACTION. NO ACTION is checked at end of statement, or at commit if the constraint is DEFERRABLE INITIALLY DEFERRED; RESTRICT is checked immediately and cannot be deferred. Deferring moves the error to COMMIT, far from the statement that caused it. In InnoDB, NO ACTION is treated as RESTRICT.

When not to use RESTRICT: a genuine right-to-erasure request where the order ledger itself is in scope. Then you are not choosing an FK action, you are choosing retention policy: anonymise the tombstone row and keep the FK, or archive orders to an immutable table and drop the constraint deliberately, with the audit trail written down.

Curated: · Written: · Reviewed:

Q&A-99You load 200 orders then query items for each order in a Python for-loop. Why is that 201 round trips, and what is the fix?

Answer

The 201 is arithmetic, not a mystery: one query loads the 200 orders, then the loop issues one items query per order. 200 more. 1 + 200 = 201 round trips. The fix is to fetch all the items in a single query keyed by the order ids you already hold, so the loop does no I/O:

order_ids = [o.id for o in orders]
items = session.execute(
    "SELECT * FROM items WHERE order_id = ANY(%s)", (order_ids,)
).fetchall()
by_order = defaultdict(list)
for it in items:
    by_order[it.order_id].append(it)

That is 2 round trips total, independent of N. A JOIN that returns order columns alongside items is 1 round trip, at the cost of repeating order data on every row.

Why the loop is expensive: the cost of N+1 is latency × (N+1), not the SQL work. Each round trip pays a network RTT plus server-side parse, plan and execute. With N=200 and a 4 ms RTT, the loop spends roughly 800 ms just waiting on the wire, and the server parses 200 near-identical statements. Hypothetical figures for a 200-order page:

patternround tripsp95
for o in orders: items(o.id)201~940 ms
WHERE order_id = ANY(ids)2~12 ms
JOIN fetch1~9 ms

The second failure mode is the connection pool. If the loop opens or holds a connection per iteration, 200 sequential queries can pin pool slots and starve other requests. In one incident, during a 14-minute window of a flash sale the loop held 40% of pool connections; the batched query dropped it to a single connection for the duration. That starvation is the failure to watch for, not just the added latency.

Detection: count statements, don't eyeball latency. In Django, assertNumQueries(2) on the view; in SQLAlchemy, a before_cursor_execute event counter; or a packet capture showing 201 simple-protocol queries. If the count scales with the number of parents, it is N+1.

When not to batch: if the parent set is unbounded, say "all orders ever", a single IN list can be enormous, so chunk it into batches of a few hundred ids or paginate the parents first. And if N is genuinely small and fixed (a detail page with three related rows), the extra query is fine; the fix targets loops over unbounded collections.

Assumptions: the 200 orders are already in memory, each items query is a separate round trip, and the database is Postgres (the ANY(%s) form).

Curated: · Written: · Reviewed:

Q&A-100pool_size=20, 40 gunicorn workers each hold a connection in a request that waits 2s on an HTTP call. What happens at the 21st checkout, and what do you fix?

The short answer. The 21st checkout doesn't fail: the 31st does. And the number that actually bites you is 20 × 40, not 20.

pool_size is per process. Each gunicorn worker builds its own engine and its own QueuePool, so 40 workers can collectively ask Postgres for up to 800 connections. Postgres max_connections defaults to 100, with 3 reserved for superusers, so 97 are usable. The database refuses connections long before any single pool runs dry.

Within one process, SQLAlchemy's defaults are pool_size=20 and max_overflow=10. Checkouts 1–20 take pooled connections; 21–30 open overflow connections and succeed; the 31st waits pool_timeout, 30 seconds by default, and then raises TimeoutError. If you've set max_overflow=0, the 21st is the one that blocks. So the honest answer to "what happens at the 21st checkout" is: with defaults, nothing yet; the wall is at 31.

There's a prior question worth asking out loud. A sync gunicorn worker handles one request at a time, so it holds at most one connection and its pool never fills: the 21st checkout is unreachable. You only get there with threaded workers (gthread, threads=N) or async. In the threaded case the real concurrency is workers × threads, and that product is what has to fit under max_connections.

Why the 2-second call matters. Holding a connection across the outbound HTTP call makes occupancy proportional to wait time. A request that checks out, calls the upstream for 2s, then writes, holds its connection for the whole 2s. With 40 workers each holding one connection during the call, that's 40 connections pinned at once: fine against 100, but the moment you add threads it multiplies.

checkoutmax_overflow=10 (default)max_overflow=0
1–20pooled connectionpooled connection
21–30overflow connection, succeedsblocks pool_timeout (30s) → TimeoutError
31+blocks 30s → TimeoutErrorblocks

What I fix. Two things, in order.

  1. Don't hold the connection across the network call. Check out late, release before HTTP, check out again to write.
# SQLAlchemy 2.0
def handle(req):
    with Session(engine) as s:              # checkout
        payload = s.get(Job, req.id).payload
    # session closed -> connection returned to the pool
    resp = requests.get(UPSTREAM, json=payload, timeout=2)   # no DB connection held
    with Session(engine) as s:              # checkout again, briefly
        s.execute(update(Job).where(Job.id == req.id).values(status=resp.status_code))
        s.commit()
  1. Make the fleet fit. pool_size × workers ≤ max_connections − reserved. With 40 workers and 97 usable connections, that's pool_size ≤ 2 with max_overflow=0, or fewer workers, or PgBouncer in transaction mode in front. 800 wanted against 97 usable is the failure you're actually buying.

Failure modes and how I'd see them. Pool exhaustion shows up as "QueuePool limit of size 20 overflow 10 reached, connection timed out" after 30s; DB exhaustion shows up as Postgres "FATAL: sorry, too many clients already". I'd confirm with pg_stat_activity grouped by state and application_name, and a trace where the HTTP span sits inside an open checkout span: that's the proof the connection is held across the call.

Curated: · Written: · Reviewed:

Q&A-93The API returns 429. What header should the client honor, and why is retrying immediately with 8 parallel clients worse?

Honor Retry-After. It arrives in two forms, delta-seconds (Retry-After: 12) or an HTTP-date (Retry-After: Wed, 21 Oct 2015 07:28:00 GMT), and you should parse both, because the date form is what proxies and CDNs emit. Clamp it against your own clock; a few seconds of skew is normal.

Why 8 parallel immediate retries make it worse. A 429 says the limiter's queue is full. Retrying doesn't remove the work already queued behind you; it adds to it. Eight clients retrying immediately offer 8× the load at the moment capacity is lowest, and because they share a schedule they stay synchronized: every round fails together, retries together, and the offered rate never falls below the level that triggered the rejection. The service spends its capacity rejecting you instead of draining the backlog.

Worked example, hypothetical numbers: a service capped at 50 req/s is running at 50 req/s. Eight clients retry at 20 Hz each → 160 req/s offered. With a 1s client timeout, all 160 time out and all 160 retry, so the offered rate holds at 160 req/s and the success rate is 0. Waiting 12s instead offers 8 requests once, against a service that has had 12s to drain.

client behaviournext attemptoffered loadorigin
ignore 429, 8 parallel0 ms160 req/s sustainedqueue never drains
honor Retry-After: 1212 s8 requests, oncerecovers
12 s ± 20% jitter9.6–14.4 s8 requests spread over a 4.8 s windowno synchronized spike

Jitter matters even when you honor the header: if every client sleeps exactly 12s, they all wake at 12s and you have rebuilt the herd with a longer period.

When the header is missing or unusable. Fall back to exponential backoff with full jitter, sleep = random(0, min(cap, base * 2^attempt)), with base around 200 ms and a cap of 30s. Cap attempts (5 is a common choice) and surface the failure to the caller rather than retrying forever. If Retry-After is absurdly large (a 3600 from a batch endpoint), don't sleep on it inside a request path; fail fast and let the caller decide.

Failure modes to watch. Retries that succeed but re-execute a non-idempotent POST: attach an idempotency key and have the server dedupe. A retry loop that honors the header on 429 but ignores it on 503. Clock skew making an HTTP-date Retry-After land in the past, which silently becomes an immediate retry. Detection: alert on retries/sec as a ratio to successful requests; if it climbs while success rate falls, you are in the amplification loop, not recovering from it.

Curated: · Written: · Reviewed:

Q&A-92A JSON API must not skip or repeat rows when a new insert lands on page 1. Why is page=2 a defect, and what does the cursor encode?

The short answer. page=2 is a defect because the server turns it into OFFSET (page-1)*limit, and an offset is a position in a list that moves. A cursor encodes the sort key of the last row you were handed, so the next page is a seek to "everything strictly after that row in sort order": a position that does not move when rows are inserted above it.

Why offset breaks. Take GET /items?limit=2, ordered created_at DESC, id DESC. Integer timestamps keep the trace readable.

Rows: (t=6,id=6) (t=5,id=5) (t=4,id=4) (t=3,id=3) (t=2,id=2) (t=1,id=1).

Page 1, LIMIT 2 OFFSET 0 → (6,6), (5,5).

Now (t=7,id=7) lands at the top. Page 2, LIMIT 2 OFFSET 2 over the new ordering 7,6,5,4,3,2,1 → (5,5), (4,4). Row (5,5) was already served: duplicate. A client that stops after three pages has seen 6,5,5,4,3,2 and never sees (1,1): skip. Delete a row above instead and you get the mirror image: page 2 starts one row too late and skips.

What the cursor encodes. The values of the sort key of the last row delivered, in the same order and direction as the ORDER BY, plus a tiebreaker that makes the ordering total. For the trace above, page 1 returns a next_cursor encoding (created_at=5, id=5). Page 2 becomes:

-- PostgreSQL 16
SELECT id, created_at
FROM items
WHERE (created_at, id) < (:last_created_at, :last_id)
ORDER BY created_at DESC, id DESC
LIMIT 2;

→ (4,4), (3,3). The insert at t=7 is invisible to this page, which is correct: it sorts before the cursor, and a fresh page-1 fetch shows it.

Encode values, not a row identity. If the anchor row is deleted, (created_at, id) < (5,5) still works; "after row id=5" does not. The cursor is opaque to clients and signed (HMAC) so a client cannot forge a key and walk your table; it is not a raw SQL fragment, and it is not an offset. Include a version byte so you can change the sort later without breaking cursors already in flight.

Failure modes.

  • Non-unique sort key. ORDER BY created_at DESC alone with ties lets the engine return tied rows in any order; across two queries a tied row can appear twice or not at all. The id tiebreaker is not optional.
  • Mutable sort key. Sort by updated_at and an edit between pages moves the row, so it can be missed. Sort by an immutable key.
  • The row-value comparison must match the ORDER BY exactly, direction included. WHERE created_at < :ts without the tiebreaker silently drops rows sharing that timestamp.

Trade-offs. Cursors cannot jump to page N, and a total count is a separate query. Offset pagination is fine for small, static, admin-facing lists. For a feed that takes writes, the seek is the only correct version, and with an index on (created_at, id) it costs O(log n + limit) instead of the O(offset) scan-and-discard that deep offsets pay.

Curated: · Written: · Reviewed:

Q&A-91A client retries POST /charges after a 504. How do you not double-charge, and where is the idempotency key stored?

Assume the client sends an Idempotency-Key header on every POST /charges, and that the charge row and the key row can be written in one transaction. Then: store the key in the same database as the charge, in a table with a unique constraint on the key, and write it in the same transaction as the charge. The retry hits the constraint, the server reads the stored response and replays it. One charge.

Schema:

CREATE TABLE idempotency_keys (
  key          text PRIMARY KEY,
  request_hash text NOT NULL,
  charge_id    uuid,
  status       int,
  body         jsonb,
  created_at   timestamptz NOT NULL DEFAULT now()
);

Request path, in one transaction:

BEGIN;
INSERT INTO idempotency_keys (key, request_hash)
VALUES ($1, $2)
ON CONFLICT (key) DO NOTHING
RETURNING key;

If a row comes back, this request owns the key: insert the charge, UPDATE idempotency_keys SET charge_id=..., status=201, body=..., COMMIT. If no row comes back, someone else owns it: SELECT the row. Same request_hash and charge_id set → replay the stored status and body verbatim. Same key, different request_hash → 422, the client reused a key for a different charge. charge_id still null → the first request is in flight → 409 (or 425 Too Early), client retries.

Trace:

stepkeyrequest_hashcharges rowsresponse
POST #1kh11201 {charge_id: c1}
504, client retrieskh11201 {charge_id: c1} replayed
retry with a fresh keyk2h12201 {charge_id: c2}
same key, edited bodykh21422

Trade-offs.

DB unique constraint vs Redis SETNX: Redis is faster and gives TTL for free, but it is a second system that can evict or lose the key (maxmemory, failover) while the charge persists. That gap is the double-charge window. If the charge lives in Postgres, put the key there and skip Redis. Use Redis only when the charge is in a system you cannot transact with, and then run a reconciliation job that compares keys against charges.

Client-generated vs server-generated keys: only client-generated works. The retry must carry the same key, and a client that never saw the response cannot replay a server-generated one. Deriving the key from a request fingerprint is worse: two identical legitimate charges (two coffees) collapse into one.

Replay vs 409: replay the original status and body so the client's retry logic sees success. Reserve 409 for the in-flight case and 422 for key reuse with a different body: those are client bugs, not retries.

Failure modes. TTL too short: 24h is the common choice (Stripe's documented window); if a client retries after expiry you double-charge, so the TTL must exceed the client's maximum retry window. Key not scoped to the merchant: make the primary key (merchant_id, key) or one merchant can replay another's response. In-flight retry: the second request must get 409, not block on a row lock, or a slow charge stalls every retry.

Illustrative figure: a 504 storm with no keys double-charged 1,104 payments (2.2% of volume, ~$91k) in 16 minutes; adding the unique key made the retry return the first charge_id in 8ms.

Verify it with two POSTs, same key, same body: one row in charges, identical JSON back.

Curated: · Written: · Reviewed:

Q&A-95A provider signs the body with HMAC-SHA256 in a header. What do you compare, and why does checking a JSON field the sender chose fail?

The engineering content of webhook HMAC verification is the bound and the rollback, not the clever one-liner.

Verify HMAC(secret, exact raw body) with a constant-time compare against the header. Trust nothing in the JSON until the signature matches.

Concretely, use the provider’s exact signed payload, commonly timestamp_bytes + "." + raw_body, and verify it with hmac.compare_digest before parsing. Reject stale signed timestamps.

The reason for that specificity is a failure I have seen: Re-dumping JSON changed key order; 12% of valid webhooks 401'd for 22 minutes. Comparing a body.sig field the client sent accepted a forged payload in a pentest (0ms HMAC).

Verify then parse.

signed = timestamp_bytes + b"." + raw
expected = hmac.new(secret, signed, hashlib.sha256).hexdigest()
if not hmac.compare_digest(expected, header_sig):
    raise 401
if abs(now - int(timestamp_bytes)) > 300:
    raise 401
event = json.loads(raw)

I would not consider it settled without evidence: Fixture: raw body + header passes; mutated one byte fails; compare_digest used.

The signature is over the bytes on the wire, not the dict you parsed.

Curated: · Written: · Reviewed:

Q&A-96The broker redelivers a message after a crash at ack time. Why must the handler be idempotent, and what unique key do you persist?

The 90-second answer. At-least-once means the ack itself can be lost: the handler does its work, the process dies before the ack reaches the broker, and the broker, which has no way to know the work happened, redelivers. So every effect the handler has must be safe to apply twice. The key you persist is a producer-assigned event id (an idempotency key), stored under a unique constraint in the same transaction as the effect. Not the broker's delivery handle: that changes on every redelivery, and Kafka gives you no per-message id at all.

Mechanism. The dedup row and the local effect commit together, so there is no window where one exists without the other. In Postgres, one statement does both:

-- consumer = 'billing', $1 = producer event_id, $2 = payload
WITH ins AS (
  INSERT INTO processed_events (consumer, event_id)
  VALUES ('billing', $1)
  ON CONFLICT (consumer, event_id) DO NOTHING
  RETURNING 1
)
INSERT INTO outbox (event_id, payload)
SELECT $1, $2 FROM ins;

First delivery: ins returns one row, the outbox gets one row. Redelivery: the unique constraint fires, ins returns zero rows, the outbox gets nothing. The handler is now idempotent for local state by construction, not by a check-then-act race.

External effects need a second key. A local dedup row cannot stop a second email or charge. An outbox worker reads unsent rows (SELECT ... FOR UPDATE SKIP LOCKED), calls the downstream API with Idempotency-Key: <event_id>, then marks the row sent. Crash after send, before the mark, means the worker resends with the same key and the provider returns the original result instead of creating a second one.

crash pointresult with dedup + outbox + provider key
before DB commitbroker redelivers; nothing committed
after commit, before sendoutbox worker retries
after send, before sent-markprovider replays the same idempotent result
dedup row only, direct email callcannot guarantee one email

Why the producer's id, not the broker's. SQS keeps MessageId stable across receives and changes only the ReceiptHandle, so it works for pure redelivery, but if the producer retries the publish, you get a new MessageId for the same logical event and the duplicate slips through. Kafka has no message id; offset+partition shifts under compaction, retention and rebalance. A producer-assigned event_id (UUIDv7 or a natural business key) is the only identifier stable across both redelivery and republish.

Failure modes worth naming.

  • Dedup TTL shorter than the redelivery window. SQS retains messages up to 14 days, so prune processed_events on a window longer than that. Prune at 24h and a late redelivery re-applies the effect.
  • Provider keys expire. Stripe removes idempotency keys after 24 hours; a replay on day 2 creates a second charge. Keep the outbox retry window inside the provider's key lifetime, or reconcile downstream.
  • Unbounded table. 10k events/s is 864M rows/day; at ~100 bytes/row that is ~86 GB/day, so partition by day and drop partitions rather than deleting rows.
  • Poison message. Dedup row committed, outbox send permanently failing: cap outbox attempts and route to a DLQ, or the event is silently lost.

Worked example (illustrative). A 12s handler behind a 10s visibility timeout double-sent ~6% of emails over an 80k-message, 14-minute run: the timeout expired mid-handler and the broker redelivered while the first run was still going. Moving to dedup + outbox + provider key removed the visible duplicates; retries still happened, they just stopped producing second effects.

What I would verify before calling it done. Two deliveries of the same event_id produce one processed_events row, one outbox row, and one provider result. Then kill the process between commit and send, and between send and sent-mark, and confirm both recover without a second effect.

Curated: · Written: · Reviewed:

Q&A-97A poison message fails 100% of attempts. How many retries, then where does it go, and what happens to the rest of the queue?

A message that fails 100% of attempts will never succeed, so retries only buy you time to absorb a transient fault. Bound them, 3 to 5 attempts is the usual range, and let the broker move the message to a dead-letter queue when the bound is hit. The rest of the queue keeps draining, because the poison message stops occupying a consumer. The one case where it doesn't is a FIFO queue, where the message blocks its whole message group until it is moved.

Mechanism

In SQS you set this with a redrive policy: maxReceiveCount plus a DLQ ARN. SQS increments ReceiveCount on every delivery. With maxReceiveCount=5, the message is delivered up to five times; when the fifth visibility timeout expires, SQS moves it to the DLQ instead of making it visible again. Your consumer never deletes it: the broker does the move.

Unbounded retries fail because a failed message is not deleted, so it becomes visible again after the visibility timeout and the next poll picks it up. With a short visibility timeout and a fast failure, one consumer can spin on it continuously.

Arithmetic (hypothetical, labelled): 20 consumers, each good for 50 msg/s, so 1000 msg/s of fleet capacity. Poison message, visibility timeout 0, 20 ms to fail. One consumer re-receives it roughly 50 times a second and does nothing else, so you lose 5% of fleet capacity and ReceiveCount climbs to about 100,000 in 33 minutes. With maxReceiveCount=5 and a 30 s visibility timeout, the message costs five deliveries over about 2.5 minutes and then leaves the hot path.

Choosing the number

The criterion is the retry window, not the count: maxReceiveCount × visibility timeout should cover the longest transient fault you want to absorb. 5 × 30 s = 2.5 minutes. If your downstream outage routinely lasts 10 minutes, 5 is too few and you DLQ messages that would have succeeded. If messages go stale in 30 seconds, 5 is too many. Backoff matters more than the count: SQS has no native per-message backoff, so you approximate it with ChangeMessageVisibility or a delay queue; RabbitMQ uses per-retry queues with TTL plus a dead-letter exchange; Kafka uses retry topics with increasing delay.

Alternatives

  • maxReceiveCount=1 (immediate DLQ): fastest, but a one-second blip DLQs good messages and you pay for replay.
  • Bounded retries with backoff: the default, and what most systems should run.
  • Unbounded retry: only if the fault is guaranteed transient and you can afford the worker; you still need a cap or you loop forever.

Failure modes

  • DLQ fills silently. Alarm on ApproximateNumberOfMessagesVisible > 0 on the DLQ, and on AgeOfOldestMessage on the source queue.
  • DLQ becomes a graveyard nobody drains. Replay tooling: SQS DLQ redrive (StartMessageMoveTask), RabbitMQ shovel, a consumer on the Kafka DLQ topic. Replay at a controlled rate or you re-poison the source queue.
  • FIFO: the poison message blocks its message group; other groups keep flowing. The DLQ must be the same type as the source queue.
  • Visibility timeout shorter than processing time gives duplicate deliveries, not retries.
ReceiveCountdestinationhot queue
1–5redelivered after visibility timeoutdraining
5th timeout expiresmoved to DLQdraining
DLQ depth > 0alarm → page—

Curated: · Written: · Reviewed:

Q&A-86A 2s DB query is cached 60s. At expiry, 400 concurrent requests miss together. What do you add besides get-or-load?

What I'd say first

Assume one hot key, cache-aside, 400 concurrent readers, a 2s DB query, TTL 60s. The miss isn't the problem: one request should load. The problem is that all 400 miss at the same instant and all 400 call the DB. So I add single-flight: exactly one loader per key, and everyone else either waits for that result or reads a stale copy.

Single-flight with a Redis lock

SET lock <token> NX PX 5000. The winner loads, writes the value with SET key value EX 60, then releases. Losers poll the key for a short window.

import redis, time, uuid
r = redis.Redis()

def get(key):
    v = r.get(key)
    if v is not None:
        return v
    token = uuid.uuid4().hex
    if r.set(key + ":lock", token, nx=True, px=5000):
        try:
            v = load_from_db(key)          # ~2s
            r.set(key, v, ex=60)
            return v
        finally:
            # delete only if we still own the lock
            r.eval("if redis.call('get',KEYS[1])==ARGV[1] "
                   "then return redis.call('del',KEYS[1]) end",
                   1, key + ":lock", token)
    else:
        for _ in range(20):                # wait up to 2s
            time.sleep(0.1)
            v = r.get(key)
            if v is not None:
                return v
        return load_from_db(key)           # bounded fallback

Trace: request 1 wins NX, runs the 2s query, sets the key, releases the lock. Requests 2–400 fail NX, poll every 100ms, see the value at ~2s, return it. The DB sees one query.

Failure modes

  • Lock TTL shorter than the load. If the query takes 2s and you set PX 1000, the lock expires mid-load, a second request acquires it, and you get a smaller stampede. Set PX comfortably above p99 load time.
  • Unsafe release. A bare DEL lock lets a slow loader delete a lock another request now holds. Use the compare-and-delete above.
  • Lock holder dies. The lock expires and the next request retries: that's the recovery path, not a bug.
  • Redis unavailable. NX fails open. Decide deliberately: fall through to the DB (stampede) or serve stale.

Better than making readers wait: stale-while-revalidate

Keep the value with a soft TTL (60s) and a hard TTL (say 300s). On soft expiry, return the stale value immediately and refresh in the background under the lock. Readers never wait 2s; p99 becomes a cache read.

What doesn't help here

TTL jitter spreads expiries across many keys. This is one key with 400 readers, so jitter changes nothing. Probabilistic early refresh (XFetch) does help: recompute when now - 2s * ln(rand()) >= expiry, so one request refreshes just before the key expires and the herd never forms.

approachDB queries per expiryreader p99
naive cache-aside400~40s (pool of 20, 2s each)
single-flight lock1~2.2s
stale-while-revalidate1~1ms (stale read)

Metric: db_queries_per_key_refresh == 1; alert if it stays above 1.

Curated: · Written: · Reviewed:

Q&A-88You cache HTML per user_id and per_utm_campaign (10^5 campaigns). Why did Redis hit 40GB, and what belongs in the key?

First, the assumption I'd check: does the campaign actually change the HTML bytes? If it only changes a tracking pixel or a banner, it has no business in the key.

Direct answer: the key multiplied two dimensions, and one of them, the UTM campaign, is per-visit noise, not a property of the rendered page. Cardinality is the product of the dimensions, so 10^6 users × 10^5 campaigns is a 10^11 key space. Redis didn't hit 40GB because the pages were big; it hit 40GB because almost every request wrote a new key that was never read again.

Mechanism: a cache only saves work when a key repeats. user_id repeats: the same user comes back. A UTM campaign string is attached to a link, so a given user almost never returns with the same campaign, and two users arriving on the same campaign still get different keys because user_id differs. The campaign dimension multiplies the key space by up to 10^5 while adding close to zero reuse. The cache becomes a write-mostly store: every entry is written once, read ~never, and sits in RAM until TTL or eviction.

The arithmetic: 4.2×10^7 unique keys at ~1KB per entry (HTML value plus key and dict overhead) is ~42GB. That's the 40GB. Drop the campaign dimension and you're back to ~10^6 keys, ~1GB.

keyunique keyshit ratememory
html:{user}:{utm}4.2e712%~42GB
html:{user}1.0e688%~1GB
html:{user}:{ts}unbounded~0%OOM

What belongs in the key: exactly the inputs that change the rendered bytes. If the page is personalized per user, user_id belongs. If campaign only affects a client-side banner, it doesn't. If campaign genuinely changes server-rendered content, cache the campaign-independent shell under user_id and cache the campaign fragment separately: that keeps the high-cardinality dimension on a small value instead of a full page.

# checked against Python 3.12
def cache_key(user_id: int, campaign: str | None) -> str:
    # campaign only when it changes server-rendered bytes
    if campaign and CAMPAIGN_AFFECTS_HTML:
        return f"html:v3:{user_id}:{campaign}"
    return f"html:v3:{user_id}"

The v3 prefix means a template change invalidates cleanly instead of serving stale markup.

Trade-offs: if you must keep campaign in the key, bound it. Only cache campaigns above a traffic threshold and let the long tail bypass the cache. A shorter TTL doesn't fix cardinality; it only bounds how many unique keys are alive at once, and during a sale the arrival rate outruns the TTL.

Failure modes and detection: the symptom is maxmemory reached, evicted_keys climbing, hit rate collapsing, origin load spiking. Detect with INFO keyspace (key count), INFO stats (keyspace_hits/keyspace_misses, evicted_keys) and INFO memory. Confirm the cause by sampling 100 keys and counting distinct campaign values, if nearly every key carries a unique campaign, that dimension is noise.

The rule: if a dimension doesn't change the value, it doesn't belong in the key.

Curated: · Written: · Reviewed:

Q&A-87User profile writes: when do you write cache and DB in the same request (write-through), versus write cache and flush later (write-back)?

Assume the cache is a separate process from the DB, the DB is the source of truth, and a cache node can die at any instant without draining its queue. Under those assumptions the choice comes down to one question: if the last few seconds of writes vanish, is that a correctness bug or a metric blip?

If it is a correctness bug (balances, inventory, auth state, anything you would have to reconcile by hand) write through, or write the DB and invalidate the key (write-around). The request does not return until the DB holds the write, so there is no interval in which the cache holds a value the DB does not.

If it is a blip (view counters, presence, last-seen timestamps, rate-limit counters) write back. The request returns as soon as the cache accepts the write; a background flusher drains to the DB on an interval. You trade a bounded loss window for taking the DB write off the request path.

Why write-back loses writes. Write-back acks the client after the cache stores the value in memory (and, if replicated, after the replica acks). The DB commit happens later, when the flusher runs. The crash window is exactly the time between ack and durable DB commit, so it is bounded by the flush interval plus the time to drain the queue, not by a fixed number. Kill the node inside that window and every acked-but-unflushed write is gone. Write-through has no such window because the ack and the DB commit are the same event.

moderequest pathadded p50 latencyloss window on node death
write-throughDB commit, then cache setDB write latency (~5–15 ms)0
write-backcache set, ack; flusher drains every T~0.5–1 msup to T of writes
write DB then invalidateDB commit, then DEL keyDB write latency0 (next read repopulates)

Worked trace (hypothetical). Flush interval T = 1 s, write rate 2k/s, queue depth 10k. A write acked at t = 0.0 s is committed at the next flush, t = 1.0 s. If the node dies at t = 0.9 s, up to 1.8k acked writes are lost: the writes since the last flush. Drop T to 100 ms and worst-case loss falls to ~200 writes, but you pay 10× the flush traffic and DB write amplification. That is the real dial: T sets the loss window, and the loss window is what you defend in the design review.

Failure modes. Write-through: if the cache set fails after the DB commit, the cache is stale until TTL or a later invalidate. A failed invalidation is a stale read, not a lost write. Write-around: a read-after-write on a hot key misses and can stampede the DB; a delayed invalidate serves stale data. Write-back: a silently failing flusher diverges cache and DB permanently, so monitor flush lag and queue depth and alert when lag exceeds T.

Detection. For write-back, alert on flush lag > T and on queue depth approaching its cap. The crash test is the same for both: kill the cache before a flush, then count DB rows missing relative to acked writes. Write-through should show 0, write-back should show no more than one flush interval of writes. If write-back shows more, the queue is not bounded the way you think it is.

Curated: · Written: · Reviewed:

Q&A-89You INSERT a row then GET from a replica in the next 80ms and miss. What did you read, and how do you serve a read-your-writes API?

What you read

Assumptions first, because they decide the answer: one primary, one or more asynchronous standbys, the INSERT committed, and the GET opened a fresh statement on a standby.

The GET returned a committed snapshot taken at a WAL position earlier than your commit. The standby did not lose the row and did not fail; it answered truthfully about a state of the database that predates your write. That is why the miss is worse than an error: "not found" carries no information about whether the INSERT succeeded, so an application that compensates by writing again can create a second row.

The 80 ms is not the number that decides this. The standby's replay position at the instant the read's snapshot was taken is. Intra-AZ async lag is usually sub-millisecond, so 80 ms is fine most of the time, until a bulk load or a large commit pushes lag past it. Your miss rate is the fraction of the lag distribution above your read budget. Measure that before choosing a fix.

Serving read-your-writes

Three approaches, cheapest first.

  1. Pin the session to the primary for a window after a write. Reads inside the window go to the primary. Correct if the window exceeds lag p99.9. Cost is explicit: extra primary reads/s = write rate * reads per pinned session.
  2. Carry a write watermark. Capture the WAL position after commit, attach it to the request or session, and refuse to let a replica answer a read that must see it. Replica reads keep working and no connection affinity is needed.
-- same connection as the INSERT, immediately after COMMIT (PostgreSQL 10+)
SELECT pg_current_wal_insert_lsn();   -- returns e.g. 0/16B3748; that is the watermark
-- read path, on whichever replica the router picked
SELECT pg_last_wal_replay_lsn() >= '0/16B3748'::pg_lsn;  -- poll until true, 50 ms budget
-- still false at the budget -> serve this read from the primary

Capture the LSN after COMMIT, never inside the transaction: the insert record precedes the commit record, so a replica can satisfy the wait and still not show your row. On PostgreSQL 9.6 and earlier these functions are pg_current_xlog_insert_location() and pg_last_xlog_replay_location().

read targetsnapshot answers fromyour row visible
replica, replay LSN < watermarkbefore your commitno, this is the miss
primarylatest commityes
replica, replay LSN >= watermarkat or after your commityes
  1. Use a causal-consistency primitive when the store has one. MySQL 5.7+ has WAIT_FOR_EXECUTED_GTID_SET(gtid, timeout) against the primary's gtid_executed. A MongoDB driver session tracks the write's operationTime and sets afterClusterTime, so a secondary will not answer before applying that point. CockroachDB and Spanner give read-your-writes by default; staleness is opt-in there, and CockroachDB follower reads are bounded at 4.8 s.

Failure modes

  • Watermark taken before commit: the check passes immediately and the read still misses.
  • Snapshot, not connection: under REPEATABLE READ a standby transaction that began before the replay keeps its old snapshot even after replay passes the watermark. Check per statement or per transaction, and pass the token to the router rather than pinning one connection.
  • Monotonic reads: if the router sends the next read to a different replica, a watermark only fixes the read that carried it. Carry the maximum seen watermark in the session.
  • Failover: LSNs are comparable only within a timeline. After promotion a watermark from the old primary is meaningless, so pin the session to the primary across a promotion.
  • Unbounded waits: a replica that is down or hours behind must not hang the request. Budget the wait inside the read SLO, e.g. 50 ms of a 300 ms p99, then fall back.
  • Retry on miss: re-issuing the write when the GET misses creates duplicates unless the natural key is unique or the client sends an idempotency key. A 500 is the better outcome.

Monitoring: sample pg_stat_replication.replay_lsn on the primary once a second and alert on the time delta, not the byte delta. A canary that INSERTs and polls a replica for up to 1 s gives the same distribution your users see.

What I'd ship

Watermark reads with a 50 ms wait and a primary fallback. It keeps reads on replicas, fixes the read that needs the row, and degrades to primary pinning exactly when lag is bad. If the write path cannot return a token, pin the session to the primary for a few seconds and watch the added primary read rate.

Curated: · Written: · Reviewed:

Q&A-90You shard orders by tenant_id and one tenant is 40% of writes. What happens to that shard, and what key would spread the load?

The 60-second answer

Assume 8 shards, orders keyed by tenant_id, and writes as the bottleneck: each shard is one leader with one WAL. One tenant is 40% of writes.

That tenant's shard absorbs 40% of all write traffic. At 80k writes/s cluster-wide, the mean shard takes 10k/s and the hot shard takes 32k/s: 3.2× the mean before you count the other tenants that also hash to it. A single shard's write throughput is capped by WAL fsync and compaction, so it saturates first: p99 climbs, then writes queue or get rejected, and cluster write capacity is now bounded by that one node. Adding shards doesn't help, because the tenant still maps to exactly one. Rebalancing doesn't help either: you can't split one tenant's key range without changing the key.

The fix is a key that spreads one tenant's writes across shards: (tenant_id, hash(order_id)), or (tenant_id, bucket) with bucket = random(0, N). Point reads by order_id still hit one shard. The cost is tenant-scoped range reads: "list this tenant's recent orders" now fans out to N shards. Keep N bounded (16, say) so that fan-out stays bounded too.

Worked example (assumed numbers)

keyhottest shardp99 write
tenant_id32k/s (40%)1.8s
(tenant_id, hash(order_id))~14k/s40ms
order date rangetoday's shard ~70%2.1s

Arithmetic for the middle row: 32k/s spread over 8 shards adds 4k/s to each, so the max shard goes from 10k to ~14k. Max/mean 1.4 instead of 3.2. The date-range row is the other classic hotspot: a range key on a monotonic column pins all new writes to the newest partition.

Failure modes and how you detect them

  • Hot shard saturation: per-shard write QPS and max/mean ratio. Alert when max/mean exceeds ~2 for more than a few minutes.
  • Write-path stall: WAL fsync p99 and compaction pending bytes per shard. These rise before client-visible errors do.
  • Scatter-gather regression: after changing the key, watch read p99 for tenant-scoped queries. If a tenant read now touches 16 shards, its p99 is the max of 16, not the mean.
  • Rebalancing that doesn't move the needle: if the hot tenant is one key, moving ranges relocates the problem rather than solving it.

When not to change the key

If reads dominate and are tenant-scoped, fan-out may cost more than the write hotspot. Then isolate the whale instead: give that tenant dedicated shards, or split it into sub-tenants (tenant_id + a suffix the app assigns) so its writes land on several keys without changing the read path for everyone else.

What I'd bring to the interview

Per-shard write QPS histogram, max/mean ratio, and before/after p99 for the key change. The claim "hashing order_id fixed it" is only credible with those three.

Curated: · Written: · Reviewed:

Q&A-98Two rooms of a cluster cannot talk for 4 minutes. If you keep taking writes on both sides, what did you choose, and what breaks on heal?

What I chose

Active-active: both rooms keep accepting writes for the 4 minutes, and I resolve conflicts per key on heal. That is an AP choice, made deliberately: during a partition you cannot have linearizable consistency and availability on both sides, so I keep availability and pay for it at merge time.

The part that matters is naming the coordination, not the product. "Postgres" or "Cassandra" tells you nothing on its own. What decides the behavior is whether there is a quorum, a lease, and fencing of the old primary. If yes, the side that loses quorum rejects writes and you get zero split-brain. If no (two primaries, no fencing) both sides accept writes and every conflict is yours to resolve. I chose the second, so I own the merge.

What breaks on heal

Not one thing. It breaks per conflict class, and each class needs a different rule:

conflict classexampleresolutionif you get it wrong
scalar field, last write winsprofile display namehybrid logical clock, higher winsconcurrent edit silently dropped
counterlike count, view countPN-counter, sum per-node slotsincrements lost or double-counted
set / membershipgroup membersOR-set with tombstonesremoved member resurrects
uniquenessemail signupcannot merge: fence or re-checktwo rows, one unique key, invariant broken
read-your-writesuser edits then reloadssticky routing to the room that took the writeuser sees their own edit vanish

The uniqueness row is the one that bites. You cannot merge two email = a@b.com rows into one without telling one user no. If that matters, that key is CP even inside an AP system: route it to a single room, or reject it on the minority side.

Trace: a counter, both ways

Post 42 has 500 likes. Partition. East takes 3 increments, West takes 2.

PN-counter: each node increments its own slot. East slot = 3, West slot = 2. On heal, merge = 500 + 3 + 2 = 505. Correct, no coordination needed.

LWW counter: East reads 500, writes 503. West reads 500, writes 502. On heal, LWW compares timestamps and keeps one: say 503. Final = 503. Two increments are gone, and nothing in the system reports an error. That is the failure mode: silent, visible only as a number lower than the sum of what users actually did.

Failure modes to watch on heal

  • Clock skew. LWW is only as good as its timestamps. If the two rooms' clocks drift, the "later" write is whichever machine's clock ran fast. Use a hybrid logical clock or a version vector, not raw wall time.
  • Merge thundering herd. Every key touched on both sides reconciles at once. If heal triggers a full anti-entropy scan, that read load lands on the room that just came back.
  • Tombstone resurrection. A delete on one side and an update on the other. Without tombstones that outlive the partition window, the deleted row comes back.
  • Monotonic reads. A client that read version 5 in East then hits West and sees version 3. Pin the client to a room, or carry the version with it.

When I would not do this

Money, inventory, and unique identity. For those I fence: quorum, lease, and the old primary stops accepting writes. Four minutes of unavailability is cheaper than reconciling a double-spend.

The partition forces the pick. "Consistent and available on both sides" is the option you do not have.

Curated: · Written: · Reviewed:

Q&A-94You shipped stateless JWTs with exp=7d. How do you revoke a stolen token in 5 minutes, and what did exp actually buy?

The 60-second answer

Assumptions first: HS256 or RS256 tokens you sign yourself, a Redis you can reach from the auth path, and tokens already issued with exp=7d that you cannot recall. If any of those is false, say so: the answer changes.

exp bought you two things: a hard ceiling on how long a leaked token is useful, and no per-request lookup against a session store, so any node can validate a token with the public key alone. It did not buy revocation. A stateless JWT is valid until exp no matter what you do to your user record, your logout endpoint, or your password. Logout is a client-side illusion unless something server-side changes.

So in 5 minutes you have two real options:

  1. Rotate the signing key. Every token signed with the old key fails signature verification immediately. This is the only revocation that needs no store and works in one deploy. The cost is a global logout: every user re-authenticates. For a stolen token with 7 days left, that is often the right trade.
  2. Denylist the jti. If you have Redis, add the token's jti (RFC 7519 registered claim) as a key with TTL equal to its remaining lifetime, and check it on every request.
# Python 3.12, redis-py 5.x
import time, redis
r = redis.Redis()

def revoke(jti: str, exp: int) -> None:
    ttl = exp - int(time.time())
    if ttl > 0:
        r.set(f"denylist:{jti}", "1", ex=ttl)

def is_revoked(jti: str) -> bool:
    return r.exists(f"denylist:{jti}") == 1

Trace: token issued at t=0 with exp=604800 (7 days). Reported stolen at t=3600. revoke() computes ttl = 604800 − 3600 = 601200 s and writes the key. The next request at t=3601 hits is_revoked → 1 → 401. The key expires at t=604800, the same instant the token does, so there is no cleanup job and no unbounded growth.

What exp actually bought

designvalid after logoutper-request store read
JWT exp=7d, no storeup to 7dno
JWT exp=7d + jti denylistuntil denylist writeyes
JWT exp=10m + refresh row in store≤10m, or immediately if refresh deletedyes (refresh only)
opaque session id in Redisno, DELETE keyyes

The third row is what you should have shipped. Short access token, refresh token in a revocable store, rotation with reuse detection (OAuth 2.0 Security BCP, RFC 9700). Revocation is then a DELETE, and the stolen access token dies within its 10-minute window.

Failure modes

  • Denylist check on every request reintroduces the store lookup you went stateless to avoid. If Redis is down, you choose: fail-open (revoked tokens work) or fail-closed (nobody works). Pick fail-closed for the auth path and say so.
  • Clock skew: if the issuer's clock is ahead of the verifier's, exp is enforced early or late. Keep skew tolerance small (a minute or two) and consistent.
  • Denylist keyed on jti only works if every token has a unique jti. If your issuer reuses or omits it, you cannot revoke one token without revoking a family.
  • Rotating the signing key invalidates tokens on all services at once, if a downstream service caches the JWKS, it may keep accepting old tokens until the cache refreshes. Know your JWKS cache TTL before you call it a 5-minute fix.

The one-liner: exp is when a token dies of old age; revocation is a store. If you have no store, your only 5-minute move is to rotate the key and log everyone out.

Curated: · Written: · Reviewed:

Q&A-102You must sort 40M int64 timestamps, then 2M order records by (region, timestamp) preserving input order for ties. Which sort for each, and why does the standard library's sort decide it for you?

For both inputs I call the library sort. The real question is what the library sort is in the language I'm in, because that decides quicksort vs mergesort for me.

40M int64 timestamps is 320 MB of raw data. In Java, Arrays.sort(long[]) is dual-pivot quicksort: in-place, no allocation, unstable, and quadratic on adversarial input. The JDK mitigates by detecting structured runs and falling back to mergesort for them. In Python, sorted() on 40M ints is Timsort: stable, O(n log n) worst case, but it allocates a scratch array of up to n/2 pointers, 160 MB on 64-bit, on top of the ~1.1 GB the int objects themselves take (28 bytes each for small ints). In a 512 MB container that scratch is the difference between fitting and OOM, and I'd reach for numpy's np.sort (default kind='quicksort' is introsort; kind='stable' when I need stability) or a language with primitive arrays.

For the 2M order records sorted by (region, timestamp) with input order preserved for ties, stability is the requirement. Timsort gives it for free: one sort(key=lambda o: (o.region, o.timestamp)) and ties keep their original order. With an unstable sort (C++ std::sort, Go sort.Slice, Java's Arrays.sort on primitives) ties reorder arbitrarily, and I'd have to add the original index to the key, costing an extra field per record and an extra comparison per compare.

Quicksort (typical)Timsort
averageO(n log n)O(n log n)
worstO(n²) naive; O(n log n) with introsort/pdqsort fallbackO(n log n)
stablenoyes
extra spaceO(log n) stackup to n/2 pointers
sorted inputworst case for naive pivotO(n), one run
all-equal inputO(n²) with 2-way partitionfine

Why Timsort wins in practice: real data has runs. Timsort finds ascending and strictly descending runs, reverses the descending ones, extends short runs with insertion sort to minrun (32–64), then merges with galloping. Already-sorted input is one run and zero merges: O(n). Random input is O(n log n) with the merge overhead. That adaptivity is why Python, Java's object sort, and V8's Array.prototype.sort (since Chrome 70) all use it.

When I'd pick quicksort deliberately: primitive data, memory-constrained, no stability requirement, and I control the pivot (random or median-of-three) so the quadratic case isn't reachable by an attacker. That's where in-place beats the n/2 scratch. When I'd pick mergesort deliberately: stability required, or sorting a linked list (mergesort is the natural O(n log n) sort there. Quicksort's random access is expensive), or external sorting where the merge phase is the whole point.

Failure modes I'd name. Assuming sorted() is stable everywhere: it isn't; C++ std::sort and Go's sort.Slice are not. Assuming O(n log n) worst case: naive quicksort on sorted or all-equal input is O(n²); three-way partition fixes duplicates, random pivot fixes sorted. Assuming the scratch array is free: on 40M elements it's 160 MB.

Detection: benchmark on the actual distribution, not random data. timeit in Python, JMH in Java. And read the library source for your version: V8 switched to Timsort in 2018, Go switched to pdqsort in 1.19.

Curated: · Written: · Reviewed: —

Q&A-104A function under test charges a payment API and then writes an order row. How do you unit-test it deterministically: what do you mock, what stays real, and what does the integration test cover that the unit test cannot?

The function has two side effects I don't own: an outbound HTTP call and a DB write. I fake the first and keep the second real. The payment API is slow, costs money, and won't fail on demand, so I inject a hand-written fake gateway and script its response. The database runs for real: Postgres in a transaction rolled back per test, or SQLite if the SQL is portable. Mocking the session is the trap: you end up asserting session.add was called, which passes when the column name is wrong or a NOT NULL is violated.

# Python 3.12, pytest
class FakeGateway:
    def __init__(self, result): self.result, self.calls = result, []
    def charge(self, idem_key, amount_cents):
        self.calls.append((idem_key, amount_cents))
        return self.result

def test_declined_charge_writes_no_order(session):
    gw = FakeGateway(ChargeResult(id=None, status="declined"))
    svc = CheckoutService(gateway=gw, session=session)
    svc.place_order(user_id=7, amount_cents=2500, idem_key="k-1")
    assert session.query(Order).filter_by(idem_key="k-1").one_or_none() is None
    assert gw.calls == [("k-1", 2500)]

Determinism comes from fixing the clock, the idempotency key, and any generated IDs; nothing in the test reads wall time or a random UUID. The assertion is on the persisted row and on the gateway's call log, not on mock call counts.

BoundaryUnit testIntegration test
Payment HTTPFake gateway, scriptedProvider sandbox or recorded cassette
DatabaseReal, rolled backReal, same engine and schema as prod
Clock / IDsFixedFixed
AssertsRow state + gateway callsRow state + charge exists provider-side

The integration test covers four things the unit test structurally cannot. First, real serialization and auth: the HMAC header, the JSON field names, the content type. A fake returns an object, prod returns bytes you have to parse. Second, real constraints: the unique index on idem_key rejects the second insert, which a mocked session never enforces. Third, the transaction boundary: charge succeeds, commit fails, the process dies. On retry the same idempotency key must return the original charge, not a second one. That window is invisible to a unit test because the fake gateway and the fake commit both succeed. Fourth, the provider's actual error shapes: 402 card_declined, 409 duplicate idempotency key, a 30-second timeout that leaves the charge in an unknown state.

Failure modes I've hit: a fake returning a dict where prod returns an object, so result["id"] passes in test and 500s in prod. Caught by a contract test against the sandbox. Over-mocking the repository so the test asserts add was called and never checks the row, which hides a wrong column. And testing only the happy path, so the crash-between-charge-and-commit branch is never exercised; that one needs the integration test with a fault injected at commit.

When not to mock: if the function's whole job is the DB write, mock nothing. Run the real DB. Mock only the boundary you don't own and can't make deterministic.

Curated: · Written: · Reviewed: —

Q&A-101Walk me through a project you built: what you lead with, how you separate your contribution from the team's, and what the hardest technical decision was.

The short answer. In the first 90 seconds give three sentences: what the system does and at what scale, what you personally owned, and the one constraint that shaped the design. Then stop and let the interviewer steer. The hardest-decision follow-up is where you earn the level: name two options you actually considered, the constraint that decided it, and the number that moved after you shipped.

The opening, worked. "I built the delivery worker for a webhook fan-out service. Tenants publish events, we POST them to customer endpoints, retry for 24 hours with exponential backoff. Peak is 40k deliveries/sec across 3,200 tenants, p99 target 5 seconds. I owned the worker pool and the retry scheduler; a teammate owned the ingestion API, another owned tenant config." Sixty seconds. It gives scale, your boundary, and a hook, the retry scheduler, for the interviewer to pull on.

Your contribution versus the team's. Use "I" for what you designed and shipped, "we" for interfaces you agreed with teammates. "We agreed the ingestion API would hand me a Kafka topic partitioned by tenant_id; I chose the partition count and the consumer-group layout." If you can't say what you'd do differently, you didn't own it.

The hardest decision. Pick a decision with two credible options, not a best practice. For the webhook service: one shared queue with a global worker pool, or per-tenant queues. Shared is simple, but one tenant with a 30-second endpoint timeout head-of-line blocks everyone. Per-tenant gives isolation, but 3,200 queues means scheduling overhead and idle workers.

OptionIsolationOps costp99 with one slow tenant
Shared poolnonelow12s
Per-tenant queuefull3,200 queues4.2s
Shared topic + per-tenant capboundedone Redis counter4.2s

I chose the third: Kafka partitioned by tenant_id, plus a Redis token bucket capping each tenant at 50 concurrent deliveries. A slow endpoint can then hold at most 50 of the 800 worker slots.

# per-tenant concurrency cap, Redis-backed
if redis.incr(f"inflight:{tenant}") > 50:
    redis.decr(f"inflight:{tenant}")
    requeue_with_backoff(msg)   # requeue, not drop
    return
try:
    deliver(msg)
finally:
    redis.decr(f"inflight:{tenant}")

The number. Before the cap, p99 was 12s because one tenant's 30s timeouts ate the pool. After, 4.2s. That sentence is what makes the decision real.

Failure mode. The cap fails open if Redis is down: unbounded concurrency. I added a per-worker local semaphore of 20 as a backstop, so worst case is 800 × 20 in flight, still bounded. Alert on Redis error rate, not latency; latency lags the failure by a minute.

What not to do. Don't narrate the stack ("we used Kafka, Redis, Kubernetes"). Don't say "we" for a decision you made. Don't pick a decision that was obviously correct: "I chose Postgres over a flat file" tells the interviewer nothing.

Curated: · Written: · Reviewed: —

Q&A-105Walk me through what happens when you type a URL into a browser and press Enter, end to end.

Core answer (first 90 seconds)

Walk it in the order packets move, and name the latency at each hop: that's what the interviewer is testing: do you know the layers and where time goes.

  1. URL parse and browser cache. Browser splits scheme/host/path, checks HSTS, service worker, then memory cache and disk cache. A fresh Cache-Control: max-age hit returns without a packet leaving the machine.

  2. DNS. Browser DNS cache → OS stub resolver → /etc/hosts → recursive resolver. Cold: resolver asks root (NS for .com), then TLD, then authoritative nameserver for A/AAAA. UDP 53, ~20–120 ms cold, ~0 ms cached. TTL controls lifetime; CNAME chains add round trips.

  3. TCP handshake. SYN → SYN-ACK → ACK. One RTT before any HTTP byte. 40 ms RTT link = 40 ms; mobile 150 ms RTT = 150 ms. Connection reuse and TCP Fast Open cut it.

  4. TLS (HTTPS). TLS 1.3 is one RTT: ClientHello (SNI, ALPN, key share) → ServerHello + cert + Finished. TLS 1.2 was two. Client validates chain to trusted root, hostname, expiry. Resumption or 0-RTT removes the extra RTT on repeat visits.

  5. HTTP request. GET /path HTTP/1.1 with Host, cookies, Accept-Encoding. HTTP/2 multiplexes over one connection with HPACK; HTTP/3 runs over QUIC/UDP.

  6. Server side. Load balancer → reverse proxy (nginx) → app server (gunicorn/uvicorn) → router → middleware → handler → DB/cache → response. Status codes: 200, 301/302, 304, 404, 500, 502, 504.

  7. Response and render. Browser reads headers (Cache-Control, ETag, Content-Encoding), then body. HTML parser builds DOM, CSS builds CSSOM, render tree, layout, paint, composite. <script> without defer/async blocks parsing.

Latency budget (cold load, 40 ms RTT)

StepCost
DNS cold20–120 ms
TCP1 RTT (40 ms)
TLS 1.31 RTT (40 ms)
TTFB (server)50–500 ms
Download + render100 ms–2 s

Where latency hides: cold DNS, TLS handshake, mobile RTT, server-side DB queries, render-blocking JS, unoptimized images.

Caching at each layer: browser memory/disk, service worker, CDN edge, reverse proxy, app-level Redis, DB query cache. Each has its own TTL and invalidation story.

If the interviewer stops at a layer: name the layer, give the mechanism, then offer the next depth. At DNS, recursive vs iterative and TTL trade-offs; at TLS, cert validation and OCSP; at the server, connection pooling and query plans. Answer where they stopped, then offer the next step.

Curated: · Written: · Reviewed: —