Top 100 Software Engineer Interview Questions and Answers

The first thing I would pin down about hash map average versus worst case is which input size or concurrent interleaving actually breaks the naive version.

Average-case hash-map lookup is O(1) under uniform hashing; worst case is O(n) when every key collides into one chain or bucket.

Concretely, name the table: expected O(1) for get/put with a good hash and a controlled load factor; worst O(n) for one collision chain. Java 8+ tree bins can improve a collision-heavy bucket toward O(log n) when keys have a usable ordering, but that is an implementation qualification, not the generic hash-table bound.

The reason for that specificity is a failure I have seen: A checkout path hashed 4.2×10^6 attacker-chosen keys into one bucket; p99 jumped from 8ms to 940ms and the box spent 11 minutes at 100% CPU before the WAF hashed on a secret seed.

Same n, two hash-map worlds.

Input	n	Expected get	Worst get
random 64-bit keys	10^6	~1 probe	O(n) chain
all hash to bucket 0	10^6	—	10^6 comparisons
Java 8+ long chain	10^6	—	O(log n) tree

I would not consider it settled without evidence: A microbench of n=10^6 random keys versus n=10^6 colliding keys, plus the runtime's collision strategy in the language docs.

O(1) average is not a contract; O(n) worst is, unless the table trees or randomizes.

I would start two-sum with a hash map from the invariant the function must keep, not from the first algorithm that compiled.

Scan once, storing value→index; for each x look up target−x in the map before inserting x, so you never pair an index with itself.

Concretely, initialize an empty dict. For i, x in enumerate(nums): need = target − x; if need in seen: return [seen[need], i]; seen[x] = i. Time O(n) expected, space O(n). Sort-plus-two-pointers loses the original indices unless you keep them.

The reason for that specificity is a failure I have seen: A nested scan on n=2×10^5 timed out at 8.1s in CI (limit 2s); the hash-map pass finished in 47ms and still returned the first valid pair.

Complement lookup, insert after.

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i  # insert after the lookup
# n=10^6 expected ~47ms; nested loops ~8s

I would not consider it settled without evidence: Unit tests for [2,7,11,15] target 9, for duplicates like [3,3] target 6, and a timing fixture at n=10^6.

Look up the complement before you insert; that is the whole algorithm.

This is a place where a green unit test and a correct handling of two pointers on a sorted array are not the same event.

On a sorted array the pair (L,R) is monotonic: if nums[L]+nums[R] is too small, every pair with this L and a smaller R is smaller still, so you only increment L.

Concretely, start at L=0 and R=n-1 and while L<R compare the sum, incrementing L when it is too small and decrementing R when it is too large, which discards one index per step and therefore runs in at most n-1 iterations.

The reason for that specificity is a failure I have seen: A binary-search-for-complement loop on n=5×10^5 looked O(n log n) on paper and ran 620ms; two pointers finished in 18ms because it never re-scanned.

Each move discards an index.

L	R	sum	Action
0 (-4)	4 (10)	6	too big, R--
0	3 (3)	-1	too small, L++
1 (-1)	3	2	hit

I would not consider it settled without evidence: A dry-run table on [-4,-1,0,3,10] target 2, plus an assertion that the loop body runs ≤ n-1 times.

Sorted plus two pointers is one pass because each move throws an index away forever.

My answer to sliding window versus nested loops begins at the bound: if I cannot name the complexity and the failure case, I do not have a solution.

If the constraint is monotonic — a shorter inner window of a valid window is still valid, or a longer window of an invalid one stays invalid — you can advance the right pointer once and only move left when the invariant breaks.

Concretely, keep a count map and a distinct counter. For R in 0..n-1 add s[R]; while distinct > k, subtract s[L] and L+=1. Track max(R-L+1). Each index enters and leaves the window once: O(n).

The reason for that specificity is a failure I have seen: The nested start/end scan on n=4×10^5 strings spent 14 minutes in a batch job; the window rewrite finished the same file in 1.9s.

At most 2 distinct, s=eceba.

R	window	distinct	L moves	best
0	e	1	0	1
2	ece	2	0	3
3	eceb	3	L to 2 (eb)	3
4	eba	3	L to 3 (ba)	3

I would not consider it settled without evidence: A counter that left and right each increase monotonically, and a fixture "eceba" k=2 → 3 ("ece").

If shrinking never invalidates a good window, you do not restart from every i.

I would treat prefix sums for range queries as a contract over all inputs rather than as a walkthrough of the sample.

A prefix array turns every range sum into two reads: prefix[j+1] − prefix[i], O(1) after O(n) build, only while the source array is immutable.

Concretely, prefix[0]=0; prefix[k+1]=prefix[k]+nums[k]. Answer [i,j] inclusive as prefix[j+1]-prefix[i]. For updates, switch to a Fenwick tree or segment tree; a stale prefix is a silent wrong sum.

The reason for that specificity is a failure I have seen: A reporting job cached prefix sums then applied 12% of rows as late corrections; 3.4×10^6 range queries used the old prefix and over-counted revenue by $2.1M for 40 minutes.

Inclusive range via one extra cell.

prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)

def range_sum(i, j):          # inclusive
    return prefix[j + 1] - prefix[i]
# nums=[2,1,3,4]  sum(1..2)=1+3=4=prefix[3]-prefix[1]

I would not consider it settled without evidence: Assert prefix[n]==sum(nums), and a mutation test that either rebuilds prefix or fails closed until a Fenwick is in place.

Prefix sums are a snapshot; an update without a rebuild is a different array.

The useful question for monotonic stack next-greater is what still happens when the array is empty, duplicated, or already sorted.

Keep indexes whose values are non-increasing; when a new value is strictly larger, it is the next greater for every popped index, and each index is pushed and popped at most once.

Concretely, ans = [-1]*n; stack=[]. For i, x in enumerate(nums): while stack and nums[stack[-1]] < x: ans[stack.pop()] = x; stack.append(i). Remaining indexes have no greater to the right.

The reason for that specificity is a failure I have seen: A nested "scan right from i" on n=8×10^5 prices took 9.4s (timeout 3s); the monotonic stack finished in 61ms and matched the nested result on 500 random arrays.

Pop when the new value is greater.

i	x	stack after	ans writes
0	2	[0]
1	1	[0,1]
2	2	[0,2]	ans[1]=2
3	4	[3]	ans[2]=4, ans[0]=4

I would not consider it settled without evidence: Trace [2,1,2,4,3] → [4,2,4,-1,-1], and a counter that push+pop ≤ 2n.

Amortized O(1) per index is the stack invariant, not a hope.

I would settle binary search on a monotonic predicate against a counter-example first, so the clever trick has to survive it.

Search the answer space when can(mid) is a monotonic boolean: if speed m finishes in H hours, every speed > m also finishes.

Concretely, lo=1, hi=max(piles). While lo<hi: mid=(lo+hi)//2; if hours(mid)<=H: hi=mid; else lo=mid+1. Return lo. hours(m) = sum(ceil(p/m)). The array of piles is not itself the search key.

The reason for that specificity is a failure I have seen: Linear scan of speed 1..10^9 on 10^4 piles ran 250ms×10^5 queries in a contest replica and missed the 2s limit; binary search used 27 probes and 11ms.

First speed that finishes in H=8, piles=[3,6,7,11].

mid	hours(mid)	can?	next
6	6	True	hi=6
3	10	False	lo=4
5	8	True	hi=5
4	8	True	answer 4

I would not consider it settled without evidence: A table that can(m) flips from False to True once, and a check that lo is the first True.

Binary search the predicate, not the array, once False,False,…,True,True is guaranteed.

The judgement in linked-list cycle detection is which operation is O(1) versus O(n), not which library call looks shortest.

If a cycle exists, two pointers at speeds 1 and 2 must meet inside it; if the fast pointer hits null, the list is acyclic.

Concretely, slow=fast=head. While fast and fast.next: slow=slow.next; fast=fast.next.next; if slow is fast: cycle. Meeting index is not the cycle start; a second walk from head at speed 1 finds the entrance.

The reason for that specificity is a failure I have seen: A visited-set walk on a 3.1×10^6-node cycle OOM'd a 512MB worker after 4 minutes; Floyd used two pointers and 38ms.

Meet, then find the entrance.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

I would not consider it settled without evidence: Tests: empty, single node no self-loop, self-loop, cycle at node 3 of 5, plus an assertion that no extra O(n) set is allocated.

Two speeds on a loop collide; a set is optional memory, not the proof.

Where candidates lose the interview on reversing a singly linked list is usually a hidden linear scan inside a loop they already counted as constant.

Walk once, flipping next to prev; keep prev, curr, nxt so you never lose the rest of the list.

Concretely, prev=None; curr=head. While curr: nxt=curr.next; curr.next=prev; prev=curr; curr=nxt. Return prev. Recursion does the same graph but uses O(n) stack frames.

The reason for that specificity is a failure I have seen: A recursive reverse on a 1.2×10^6-node list hit RecursionError at depth 1000 in CPython and crashed a request after 90ms of frames; the iterative reverse finished in 41ms.

Three pointers, one splice.

step	prev	curr	nxt	after splice
0	None	1	2	1→None
1	1	2	3	2→1
2	2	3	None	3→2→1
done	3	None		new head 3

I would not consider it settled without evidence: 1→2→3→None becomes 3→2→1→None, empty and single-node cases, and a depth check that stack growth is O(1).

Save nxt, point at prev, advance; recursion is the same idea with a worse stack.

I would answer tree DFS versus BFS by separating what the test suite proved from what production traffic has not yet shown.

BFS guarantees the shortest path in an unweighted graph. In a tree, DFS or BFS can compute the same root-to-node distance because the path is unique; DFS is also natural for ancestor state and BST bounds.

Concretely, bFS: queue, dist[child]=dist[node]+1. DFS: recurse left/right with a carried bound, or an explicit stack. For minimum hops when multiple paths exist, queue first.

The reason for that specificity is a failure I have seen: A DFS that stopped at the first target in an unweighted graph returned a 14-edge route although a 4-edge route existed; BFS returned the minimum-hop route.

A graph, two distances to D.

Walk	first path to D	distance
DFS left-first	A-B-C-D	3
BFS	A-E-D	2
graph property	multiple paths exist	minimum is 2

I would not consider it settled without evidence: Side-by-side dist maps on a small DAG with multiple paths, plus a unit test that BFS distance equals the minimum hop count.

DFS finds a path; BFS finds the shortest unweighted path.

The engineering content of BST search invariant is the bound and the rollback, not the clever one-liner.

A BST requires every node in the left subtree ≤ node < every node in the right subtree (or a stated strictness), not merely that the two children compare locally.

Concretely, validate with a carrying bound: dfs(node, lo, hi) checks lo < node.val < hi (adjust for duplicates), then left with (lo, val) and right with (val, hi). Search walks left iff target < node.val.

The reason for that specificity is a failure I have seen: A local-child check accepted a tree with 6 in the left of 5 because 6 sat as a right child of 4; a range query returned 12% extra rows for 18 minutes until an inorder dump showed a decrease.

Local children pass; inorder does not.

      5
     / \
    4   7
     \
      6    # 6 > 5, sits in left subtree
inorder: 4,6,5,7  # not sorted → not a BST

I would not consider it settled without evidence: Inorder must be non-decreasing; a counter-example tree that passes child checks and fails bounds.

The BST property is a range on the whole subtree, not a comparison with two children.

Before reaching for a new structure I would write what a correct result for trie prefix matching looks like on n = 1 and n = 10^6.

A trie shares prefixes; reaching the prefix node costs O(characters in the query). Returning completions additionally costs the nodes visited and results emitted, so cap the output rather than calling the whole autocomplete operation O(length).

Concretely, each node maps char→child, with is_word. Insert walks or creates children. Prefix search walks the prefix then DFS/BFS to collect completions, bounded by a limit (e.g. 8).

The reason for that specificity is a failure I have seen: SQL ILIKE 'mac%' on 2×10^5 rows took 420ms p95; an in-memory trie returned 8 completions in 0.9ms after a 1.4s cold build.

Shared prefix ap.

node	children	is_word
""	a	no
a	p	no
ap	p, e	no
app	l	yes (app)
apple		yes

I would not consider it settled without evidence: Insert ["apple","app","ape"], query "ap" yields those three, and a timing of 10^5 lookups vs a linear scan.

You pay per query character to find the prefix, then for the bounded subtree you enumerate.

The first thing I would pin down about heap for kth-largest is which input size or concurrent interleaving actually breaks the naive version.

The kth largest is the minimum of the current top-k; a min-heap of size k inserts in O(log k) and never stores n.

Concretely, heap of the first k values. For each new x: if x > heap[0], replace the min and heapify. Peek is the kth. Max-heap of all n is extra memory; full sort per insert is O(n log n) per update.

The reason for that specificity is a failure I have seen: Sorting the whole buffer on each of 2×10^6 events at n growing to 10^7 spent 22 minutes overnight; a 50-element heap kept each insert at 0.8μs and the job at 11s.

k=3 min-heap after each insert.

x	heap (min first)	kth
3,1,5	1,3,5	1
12	3,5,12	3
2	3,5,12	3
11	5,11,12	5

I would not consider it settled without evidence: Stream [3,1,5,12,2,11] k=3 ends with heap [5,11,12] and kth=5, plus a memory cap of k+O(1).

Top-k is a tiny min-heap, not a sorted copy of the universe.

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.

cell	first visit layer
(0,0) start	0
(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.

This is a place where a green unit test and a correct handling of Dijkstra versus BFS are not the same event.

BFS minimizes hops, not time; Dijkstra with a min-heap minimizes path cost when all edge weights are non-negative.

Concretely, dist[s]=0, heap (0,s). Pop smallest dist, skip if stale, relax neighbors: nd=d+w; if nd<dist[v]: dist[v]=nd; push (nd,v). Negative edges need Bellman-Ford; 0/1 weights can use deque 0-1 BFS.

The reason for that specificity is a failure I have seen: BFS on a city graph reported 6 hops / 14 minutes while a 9-hop / 8-minute route existed; drivers followed BFS for a week until Dijkstra used the timed edges.

BFS picks more hops that are cheaper? No: BFS picks fewer hops.

path	hops	minutes
A-B-D	2	9+9=18
A-C-E-D	3	2+2+2=6
BFS winner	2	18
Dijkstra winner	3	6

I would not consider it settled without evidence: A 4-node graph where the 2-edge path costs 10 and the 3-edge path costs 3, showing BFS and Dijkstra disagree.

Hops are not minutes; Dijkstra is BFS with a priority on remaining cost.

My answer to union-find connected components begins at the bound: if I cannot name the complexity and the failure case, I do not have a solution.

Union-find (DSU) with path compression and union-by-rank answers connectivity in nearly O(1) per op, α(n), without building neighbor lists.

Concretely, parent[i]=i, rank[i]=0. find(x) compresses to root. union(a,b) links the lower rank. Component count starts at n and decrements on a successful union.

The reason for that specificity is a failure I have seen: Recursive DFS on a 10^6-star graph blew the 1000-frame limit and then an iterative DFS built a 2×10^6-edge list that took 9.1s; DSU finished unions in 420ms.

Path compression after find(2).

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
# 2→1→0 becomes 2→0, 1→0

I would not consider it settled without evidence: Unions (0,1), (1,2), and (3,4) perform three successful merges, so the component count moves from n to n−3.

If you only need "same component?", you do not need a graph object.

I would treat topological sort of a DAG as a contract over all inputs rather than as a walkthrough of the sample.

A topological order exists iff the graph is a DAG; Kahn's algorithm emits nodes with indegree 0, and if it emits fewer than n nodes, a cycle remains.

Concretely, compute indegree[], queue all 0s, pop u, append to order, decrement neighbors, enqueue those that hit 0. If len(order)<n, refuse the build and print nodes still with indegree>0.

The reason for that specificity is a failure I have seen: A DFS "any postorder" on a graph with a 3-cycle still produced a 12-step install list; two packages deadlocked and the job hung 16 minutes until a timeout.

Indegree queue on 4 nodes.

step	queue	emit	indegree left
0	A		B1 C1 D2
1		A	B0 C1 D2
2	B	B	C0 D1
3	C	C	D0
4	D	D	done, n=4

I would not consider it settled without evidence: len(order)==n on a diamond DAG, and a fixture A→B→C→A that returns a cycle error, not a permutation.

If Kahn stops early, you do not have an order; you have a cycle.

The useful question for backtracking with pruning is what still happens when the array is empty, duplicated, or already sorted.

Backtracking builds a partial assignment and prunes as soon as a constraint fails, so most of the search tree is never constructed.

Concretely, place one queen per row. Track used columns and both diagonal encodings (r-c, r+c). Recurse row+1; unmark on return. Stop counting at n rows. Bitmasks work up to n=32.

The reason for that specificity is a failure I have seen: A generate-all-permutations scan for n=10 ran 14 minutes and allocated 3.6×10^6 boards; pruned N-queens finished n=10 in 220ms and n=12 in 8.4s.

Row 1 attack on n=4.

row	col tried	diag r-c	prune?
0	1		place
1	0	hit col? no; diag yes	skip
1	2	clear	place
2	…		continue

I would not consider it settled without evidence: n=4 has 2 solutions, n=8 has 92, and a counter of pruned branches vs full n!.

The search is the tree of partial boards; pruning is the algorithm.

I would settle 1D DP recurrence against a counter-example first, so the clever trick has to survive it.

The last step is either 1 from i-1 or 2 from i-2; those subproblems overlap, so store them once.

Concretely, dp[0]=1; dp[1]=1; for i in 2..n: dp[i]=dp[i-1]+dp[i-2]. O(n) time, O(1) space with two variables. Naive recursion is T(n)=T(n-1)+T(n-2) ≈ φ^n.

The reason for that specificity is a failure I have seen: Naively evaluating climb(40) recursively makes hundreds of millions of calls; the DP loop performs 39 additions and returns 165580141.

Ways to climb n.

i	dp[i]	from
0	1	empty
1	1	1
2	2	1+1, 2
3	3
5	8

I would not consider it settled without evidence: n=5 → 8, and a call-count test that DP does n-1 additions.

If the state is an integer and the last move is local, write the recurrence before the loop.

The judgement in 2D DP versus naive recursion is which operation is O(1) versus O(n), not which library call looks shortest.

Paths to (r,c) equal paths from above plus from the left (if open); that is O(RC) states, each O(1) work, versus exponential overlapping walks.

Concretely, dp[0][0]=1 if open. First row/col prefix until a block. Then dp[r][c]=0 if obstacle else dp[r-1][c]+dp[r][c-1]. Recursion+lru_cache on (r,c) is the same states.

The reason for that specificity is a failure I have seen: A 16×16 DFS without memo hit 1.2×10^9 calls and 19 minutes; 2D DP filled 256 cells in 0.4ms.

dp fill, obstacle at (1,1).

	c0	c1	c2
r0	1	1	1
r1	1	0	1
r2	1	1	2

I would not consider it settled without evidence: 3×2 empty grid → 3 paths, a blocked cell zeros that square, and a cache-size of RC.

The grid is the state space; walking it twice per cell is the bound.

Where candidates lose the interview on greedy correctness versus counterexample is usually a hidden linear scan inside a loop they already counted as constant.

Greedy is correct only with a proof (usually matroid or canonical coin systems); a single counterexample kills it, and then you DP.

Concretely, try greedy: 4+1+1=3 coins. Optimal is 3+3=2 coins. For 0/1 knapsack and general coin systems, use DP. For US coins, greedy is canonical — prove or cite, do not assume.

The reason for that specificity is a failure I have seen: A vending firmware used greedy on [1,3,4] and overcharged hoppers 12% of fills; switching to unbounded-knapsack DP cut fill time to 7ms per amount 0..10^4.

Greedy vs optimal, amount 6.

strategy	coins	count
largest first	4,1,1	3
DP optimal	3,3	2
US coins 6	5,1	2 (canonical)

I would not consider it settled without evidence: The (6,[1,3,4]) counterexample next to a passing US-coin test, so the interviewer sees you know both.

A greedy story without a counterexample hunt is a hope rather than an algorithm.

I would answer merging overlapping intervals by separating what the test suite proved from what production traffic has not yet shown.

Sort by start; a new interval overlaps the merged tail iff new.start ≤ tail.end, then tail.end = max(ends).

Concretely, sort intervals by start. Init merged=[first]. For each next: if next[0] <= merged[-1][1]: merged[-1][1]=max(merged[-1][1], next[1]); else append. Touching depends on whether the product treats [1,2][2,3] as overlap.

The reason for that specificity is a failure I have seen: Unsorted merge on 8×10^4 calendar events left 17% duplicate rooms; after sort-by-start, a 35ms pass collapsed 12,400 overlaps.

Sweep the sorted starts.

next	tail	action
[1,3]	—	start
[2,6]	[1,3]	extend to [1,6]
[8,10]	[1,6]	append
[15,18]	[8,10]	append

I would not consider it settled without evidence: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]], and a test for [1,4][4,5] per the spec.

Sort by start, then there is only one tail that can overlap.

The engineering content of bit counting and masks is the bound and the rollback, not the clever one-liner.

i>>1 is i/2, whose bit count is already known; the low bit is i&1. That fills an array in O(n).

Concretely, ans[0]=0; for i in 1..n: ans[i]=ans[i>>1]+(i&1). Kernighan x&=x-1 counts bits of one x in O(popcount). Masks: (1<<k)-1 for k ones; check flag with flags & MASK.

The reason for that specificity is a failure I have seen: A nested "for bit in 0..31" on n=5×10^6 ran 640ms in a hot encoder; the shift DP filled the table in 28ms.

Build 0..8 from halves.

i	i>>1	i&1	bits
4	2	0	1
5	2	1	2
6	3	0	2
7	3	1	3

I would not consider it settled without evidence: n=5 → [0,1,1,2,1,2], and a random check vs bin(i).count("1").

Half of i already knows its popcount; you only add the LSB.

Before reaching for a new structure I would write what a correct result for GCD Euclidean algorithm looks like on n = 1 and n = 10^6.

gcd(a,b)=gcd(b, a%b) until b=0; each remainder strictly shrinks, and the worst case is consecutive Fibonacci numbers, still logarithmic.

Concretely, while b: a,b = b, a%b; return a. For lcm, compute a//gcd(a,b)b to avoid overflow versus ab//gcd. Fractions in lowest terms divide num and den by gcd.

The reason for that specificity is a failure I have seen: Subtract-until-equal gcd on (10^18, 1) looped 10^18 times and was killed at 8 minutes; modulo Euclidean finished in 0.01ms and 2 steps.

Euclid on 48, 18.

a	b	a%b
48	18	12
18	12	6
12	6	0
6	0	gcd=6

I would not consider it settled without evidence: gcd(48,18)=6, gcd(0,7)=7, and lcm(12,18)=36 via 12//6*18.

Remainder, not subtraction; lcm multiplies after dividing by gcd.

The first thing I would pin down about amortized array doubling is which input size or concurrent interleaving actually breaks the naive version.

Geometric growth (×2) makes the copy cost of a resize chargeable across the 2^{k-1} inserts since the last resize, so total copies are O(n).

Concretely, when size==cap, allocate 2*cap, copy cap elements, then insert. For n=2^k appended elements from capacity 1, total resize copies are 1+2+…+n/2=n−1, hence O(n). Inserting at 0 or mid is still O(n) per op; only the tail append amortizes.

The reason for that specificity is a failure I have seen: A custom buffer that grew by +16 each time copied ~ n^2/32 bytes; n=3×10^5 took 6.2s. Doubling dropped the same load to 19ms.

Copies when capacity doubles.

resize	copies
1→2	1
2→4	2
4→8	4
after n=2^k appends	total n−1

I would not consider it settled without evidence: Sum of resize copies for n=2^k equals n−1, and a resize log at 16,32,64,…

The expensive append pays for a run of cheap ones; linear growth does not.

I would start hidden O(n) inside a counted O(1) from the invariant the function must keep, not from the first algorithm that compiled.

An operation you treated as O(1) that is O(n) — list.pop(0), list.insert(0), x in list, str += in a loop — multiplies the outer bound.

Concretely, use deque.popleft, a set for membership, and join a list of parts. Re-read every call inside the loop against the language cost model, not the name.

The reason for that specificity is a failure I have seen: A parser did s = s[1:] per character on a 2.4×10^6-char file (O(n^2) copies) and ran 11 minutes; a pointer index finished in 90ms.

Same loop, three inner costs.

inner call	per iter	n=10^5 total
list.pop(0)	O(n)	~5s
deque.popleft()	O(1)	8ms
s = s[1:]	O(n)	~4s

I would not consider it settled without evidence: cProfile showing n copies of size n/2, or a rewrite to deque/index with the same tests.

If the inner call walks the whole array, your O(n) loop is O(n^2).

This is a place where a green unit test and a correct handling of recursion stack versus iteration are not the same event.

Recursion depth is a real stack of frames; CPython defaults to 1000, so linear recursion on large n must become an explicit stack or a loop.

Concretely, sys.setrecursionlimit is a last resort (crash risk). Prefer itertools-style loops, an explicit stack list, or heapq/BFS. Tail calls are not optimized in CPython.

The reason for that specificity is a failure I have seen: A recursive flatten on a 12,000-node tree raised RecursionError in 6% of uploads; an explicit stack processed 2×10^5 nodes in 55ms.

Recursive DFS vs explicit stack.

# blows at ~1000 on a chain
def dfs(n):
    if n: dfs(n.next)

stack = [head]
while stack:
    n = stack.pop()
    if n.next:
        stack.append(n.next)

I would not consider it settled without evidence: A test at depth 1500 that fails recursion and passes the iterative rewrite, plus a comment that limit hacks are not the fix.

The call stack is memory with a hard cap; a list stack is the same algorithm without the cap.

My answer to in-place versus extra array begins at the bound: if I cannot name the complexity and the failure case, I do not have a solution.

In-place two pointers overwrite the next write index; an extra array is simpler but O(n) memory the interviewer may forbid.

Concretely, w=0; for x in a: if x!=0: a[w]=x; w+=1. Then fill a[w:] with 0. Extra array: collect nonzeros + zeros. Stability of nonzeros is preserved; do not sort.

The reason for that specificity is a failure I have seen: Copying n=2×10^7 ints to a new list added 160MB and a 1.8s GC pause in a worker with a 256MB cap; in-place finished in 210ms at +0 bytes.

Write pointer skips zeros.

x	w before	a after write
0	0	skip
1	0	[1,…]
0	1	skip
3	1	[1,3,…]
12	2	[1,3,12,0,0]

I would not consider it settled without evidence: [0,1,0,3,12] → [1,3,12,0,0], and a memory delta of ~0 versus n.

The write index is the extra array you did not allocate.

I would treat stable versus unstable sort as a contract over all inputs rather than as a walkthrough of the sample.

A stable sort preserves relative order of equal keys. Python's Timsort is stable; a naive quicksort is not. To sort by A then B, sort by B first then by A with a stable sort, or use a single tuple key.

Concretely, sorted(rows, key=lambda r: (r.last, r.seq)) or two stable sorts: by seq, then by last. Check the language and overload: Java's object-array sort is stable, while primitive elements have no distinct equal-key identity whose order a stability guarantee could preserve.

The reason for that specificity is a failure I have seen: An unstable quicksort on 4×10^5 equal-priority jobs shuffled FIFO order; 9% of work started 14 minutes late versus the ticket sequence.

Same last name, original index.

input	unstable qsort	Timsort key=last
Ann#1, Ann#2	Ann#2, Ann#1	Ann#1, Ann#2
Python sorted		stable
Java Arrays.sort(Object[])		stable

I would not consider it settled without evidence: Two rows with the same last name stay in input order after sorted(), and a counter-example with an unstable partition.

Equal keys still have an order; only a stable sort keeps it.

The useful question for hash collision and equality is what still happens when the array is empty, duplicated, or already sorted.

If a==b then hash(a) must equal hash(b); mutating a field that participates in hash while the object sits in a dict/set orphans the bucket.

Concretely, implement eq and hash on the same frozen fields (id, or a tuple). Never hash a list or a dict. Frozen dataclass or namedtuple avoids mutation after insert.

The reason for that specificity is a failure I have seen: A User.hash used id(self) while eq used .email; a 250k-row de-dupe set kept 12% duplicates and a later lookup miss caused 6 minutes of double billing.

Broken versus frozen identity.

# broken: eq by email, hash by id(self)
# correct:
@dataclass(frozen=True)
class User:
    id: int
    email: str
# hash/eq on (id, email); cannot mutate in a set

I would not consider it settled without evidence: assert hash(u1)==hash(u2) whenever u1==u2, and a test that adding then mutating a hashed field is forbidden.

Equality without a matching hash is a set that lies.

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.

repr	memory	neighbor iter	edge exists
matrix n=1e5	~n^2 bits	O(n)	O(1)
list m=3e5	~n+m	O(deg)	O(deg)
matrix n=800 dense	640k cells	O(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.

The judgement in binary heap versus balanced BST is which operation is O(1) versus O(n), not which library call looks shortest.

A binary heap gives O(log n) insert/extract-min but no O(log n) delete-by-id unless you store handles; a balanced BST (or heap+index) supports ordered keys and delete.

Concretely, dijkstra: heap with stale-distance skips, or decrease-key via index. Leaderboards needing rank of an arbitrary id: policy-based tree / SortedList, not a heap. Heapify is O(n).

The reason for that specificity is a failure I have seen: A game used a heap of 2×10^6 scores and scanned for 80ms to delete one player (O(n)); a SortedList delete was 12μs and p99 dropped from 250ms to 9ms.

Same n=10^6, different missing op.

structure	insert	extract-min	delete by id
binary heap	O(log n)	O(log n)	O(n) scan
heap + handle	O(log n)	O(log n)	O(log n)
balanced BST	O(log n)	O(log n)	O(log n)

I would not consider it settled without evidence: Op-cost table for insert, get-min, delete-id, and a Dijkstra that never decrease-keys but pushes O(m) stale nodes.

A heap is a priority queue, not a dictionary of ranks.

Where candidates lose the interview on LRU cache with hashmap and list is usually a hidden linear scan inside a loop they already counted as constant.

Hash map finds the node in expected O(1); a doubly-linked list splices it to the front in O(1). A Python list .remove(key) is O(n).

Concretely, on get: move node to head. On put of new key at capacity: evict tail, then insert at head. collections.OrderedDict with move_to_end is the same pair.

The reason for that specificity is a failure I have seen: An LRU built on list.remove for 5×10^5 hits at cap=5000 spent 7.4s (O(n) per hit); OrderedDict finished in 62ms.

cap=2 recency (head is hottest).

# put 1, put 2 → head 2-1
# get 1        → head 1-2
# put 3        → evict 2, head 3-1
from collections import OrderedDict
d = OrderedDict()
d[k] = v; d.move_to_end(k); d.popitem(last=False)

I would not consider it settled without evidence: Sequence cap=2: put 1, put 2, get 1, put 3 evicts 2; plus a probe count of 1 per get.

The map finds; the list moves. Without both, one of the operations is linear.

I would answer string matching naive versus KMP by separating what the test suite proved from what production traffic has not yet shown.

Naive retries the pattern from scratch on every mismatch, O((n-m+1)m) worst case. KMP's longest-prefix-suffix table shifts the pattern without rechecking known prefixes.

Concretely, build lps[m] in O(m). Scan text with i,j; on mismatch j=lps[j-1], never decrement i. For production, use the language's built-in search; modern CPython's fastsearch adaptively uses simpler search and the linear-time Two-Way algorithm rather than promising KMP or one fixed implementation.

The reason for that specificity is a failure I have seen: Naive find of a 800-char "aaa…aab" in a 3×10^6 "aaa…" haystack ran 9.1s; KMP finished in 14ms after a 0.2ms LPS build.

LPS for ABABC.

i	pat[i]	lps[i]
0	A	0
1	B	0
2	A	1
3	B	2
4	C	0

I would not consider it settled without evidence: lps for "ABABC" and a mismatch trace that i only increases.

The LPS table is the memory of how much prefix you already matched.

The engineering content of three-sum two-pointer scan is the bound and the rollback, not the clever one-liner.

Fix one index i, then two-sum the suffix with L,R in O(n); skip duplicate values so each triple is unique. Total O(n^2).

Concretely, sort. For i in 0..n-3: if i>0 and nums[i]==nums[i-1]: continue. L=i+1, R=n-1, move on sum vs 0, skip equal nums[L]/nums[R] after a hit.

The reason for that specificity is a failure I have seen: Triple nested loops on n=3000 ran 4.8s in CI (budget 1s); sort + two pointers finished in 85ms and returned 214 unique triples.

i fixed at -1, suffix two-sum to +1.

fixed i	L	R	total	action
-1	-1	2	0	emit [-1,-1,2], move both
-1	0	1	0	emit [-1,0,1], move both
next duplicate -1				skip fixed value

I would not consider it settled without evidence: [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]], and a duplicate-skip test on [0,0,0,0].

Sort once; the third nested loop is a two-pointer on a sorted suffix.

Before reaching for a new structure I would write what a correct result for lowest common ancestor looks like on n = 1 and n = 10^6.

One query: walk parents or recurse carrying found-left/found-right. Many queries: binary lifting on depth and parent[k][v] = 2^k ancestor, O(n log n) preprocess, O(log n) per query.

Concretely, recursive: if node is p or q return node; left=dfs(left), right=dfs(right); if both non-null return node else return left or right. BST: walk from root until split.

The reason for that specificity is a failure I have seen: Parent-walk without depths on 2×10^5-node tree did O(n) per query × 10^4 queries = 14 minutes; binary lifting answered 10^4 queries in 32ms after 180ms preprocess.

Recursive combine.

def lca(node, p, q):
    if node in (None, p, q):
        return node
    L, R = lca(node.left, p, q), lca(node.right, p, q)
    return node if L and R else L or R

I would not consider it settled without evidence: Tree 3 / 5,1 / 6,2,0,8 with p=5,q=1 → 3, and a depth[p]==depth[q] before parent jumps.

The LCA is the first node where p and q sit in different branches — or a lifting meet.

The first thing I would pin down about serializing a binary tree is which input size or concurrent interleaving actually breaks the naive version.

A permutation of values does not recover shape; you must encode nulls (or use parentheses / BFS with explicit None) so the unique tree reconstructs.

Concretely, preorder with sentinels: "1,2,#,#,3,4,#,#,5,#,#". Deserialize with an iterator that consumes # as None. A level-order list with explicit nulls or JSON with left/right fields is also unambiguous but heavier.

The reason for that specificity is a failure I have seen: A values-only inorder dump of 8×10^4 nodes restored the wrong shape for 12% of trees (any with the same inorder); a canary compared hashes and failed for 22 minutes of bad cache keys.

Same inorder, two shapes.

tree	inorder	preorder+nulls
root 1, right child 2	1,2	1,#,2,#,#
root 2, left child 1	1,2	2,1,#,#,#
values-only inorder	collision	shape is ambiguous

I would not consider it settled without evidence: Trees 1/2 and 1\2 share no unique inorder; the sentinel preorder strings differ.

If nulls are not in the string, several trees hash to the same payload.

I would start cycle in a directed graph from the invariant the function must keep, not from the first algorithm that compiled.

A directed cycle is a back edge to a node on the current recursion stack (GRAY), not merely to a previously visited node (BLACK), which may be a cross/forward edge.

Concretely, wHITE/GRAY/BLACK. On visit paint GRAY, recurse unvisited neighbors; if a neighbor is GRAY, cycle. Paint BLACK on exit. Kahn's leftover indegree>0 is the same fact.

The reason for that specificity is a failure I have seen: Treating "visited" as a cycle flagged 19% of DAGs that had cross edges; a package installer refused valid graphs for 8 minutes until three-color DFS shipped.

Three colors.

node state	meaning
WHITE	not started
GRAY	on the current path
BLACK	finished
edge to GRAY	cycle
edge to BLACK	ok in a DAG

I would not consider it settled without evidence: A diamond DAG A→B,A→C,B→D,C→D is acyclic but visits D twice; GRAY never sees D as a back edge.

Visited is not on-stack; only GRAY is a directed cycle.

This is a place where a green unit test and a correct handling of 0/1 knapsack versus greedy are not the same event.

0/1 knapsack is not a fractional knapsack; density greedy can miss the optimum. DP: dp[i][w] = max(skip, take if w>=wt).

Concretely, dp[w]=0 for w=0..W. For each item (wt,val): for w=W down to wt: dp[w]=max(dp[w], dp[w-wt]+val) — reverse iterate so each item is used once. Unbounded knapsack iterates w upward.

The reason for that specificity is a failure I have seen: Density greedy packed less value on the (10,60)/(20,100)/(30,120) W=50 fixture (opt 220 vs greedy 160); production used greedy for 3 days until a DP of W=10^4 filled in 18ms.

Reverse inner loop for 0/1.

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

I would not consider it settled without evidence: Items (10,60), (20,100), (30,120), W=50: density greedy takes weights 10+20 for value 160; the optimum takes 20+30 for value 220.

Fractions make greedy legal; 0/1 makes a table legal.

My answer to integer overflow in midpoints begins at the bound: if I cannot name the complexity and the failure case, I do not have a solution.

lo+hi can overflow the signed max before the divide; mid = lo + (hi-lo)//2 stays in range when lo,hi are in range.

Concretely, use lo + (hi-lo)//2 for binary search. In Python ints are unbounded, so the bug is a Java/C++ tell; still write the safe form in interviews when the language is unspecified.

The reason for that specificity is a failure I have seen: Java binary search on indices near 1.6×10^9 used (lo+hi)/2, overflowed to negative, and looped 100% CPU for 6 minutes on a shard map.

int32 sum overflow.

lo	hi	(lo+hi)/2	lo+(hi-lo)/2
2e9	2e9+2	negative (overflow)	2000000001
0	10	5	5
Python		unbounded	same

I would not consider it settled without evidence: lo=2_000_000_000, hi=2_000_000_002: lo+hi overflows int32; lo+(hi-lo)/2 = 2_000_000_001.

The midpoint is an offset from lo, not a sum that has to fit.

I would treat empty and duplicate edge cases as a contract over all inputs rather than as a walkthrough of the sample.

Empty, single-element, all-duplicates, already-sorted, and reverse-sorted are the cheap counterexamples; samples do not contain them.

Concretely, write fixtures: [], [x], [x,x,x], sorted, reverse. For trees: None, single, skew. For strings: "", "a", all same char. Assert bounds on L,R so empty never indexes.

The reason for that specificity is a failure I have seen: median-of-two-arrays crashed on [] vs [1] with IndexError in 3% of partner jobs; a 40-minute incident until empty-array guards landed.

Two-sum-style helper, five fixtures.

input	target	expected
[]	0	[] or error per spec
[7]	7	[] (need two)
[3,3]	6	[0,1]
[1,2,3]	9	[]
[0,0,0]	0	first pair

I would not consider it settled without evidence: A table of those five inputs with expected output, run in CI on every PR that touches the helper.

If it is not in the sample, it is the first production input.

The useful question for mutating while iterating is what still happens when the array is empty, duplicated, or already sorted.

Iterating a collection while inserting/deleting the same object is undefined; CPython dicts raise RuntimeError if size changes during iteration.

Concretely, iterate list(d), or collect keys-to-delete then delete, or build a new dict. For lists, iterate reversed when popping by index, or build a keep list.

The reason for that specificity is a failure I have seen: A session sweeper did for k in sessions: del sessions[k] and raised RuntimeError on 8% of processes after 2.1×10^5 keys; iterating tuple(sessions) finished in 70ms.

Snapshot keys.

# RuntimeError: dict changed size during iteration
# for k in d:
#     if stale(k): del d[k]
for k in list(d):
    if stale(k):
        del d[k]

I would not consider it settled without evidence: A unit test that mutation during for k in d raises, and the rewrite that snapshots keys.

Walk a snapshot; mutate the live map.

I would settle comparator transitivity against a counter-example first, so the clever trick has to survive it.

A comparator must be a strict weak order: antisymmetric and transitive. Non-transitive compare (or overflow) lets Timsort/quicksort violate invariants and loop or mis-order.

Concretely, compare with key= functions that map to a totally ordered type (tuple, int) instead of a three-way cmp that subtracts. Never compare by "distance to a moving pivot" as a sort key without a total order.

The reason for that specificity is a failure I have seen: A Java compare overflowing int made TimSort throw IllegalArgumentException: Comparison method violates its general contract on 4% of nightly sorts (n=8×10^5, 11 minutes wasted retries).

Non-transitive closer-to-zero compare.

comparison	result
cmp(a,b)	a < b
cmp(b,c)	b < c
cmp(c,a)	c < a
consequence	non-transitive; invalid comparator
safe replacement	Integer.compare(a,b) or a fixed tuple key

I would not consider it settled without evidence: Three values a,b,c where cmp says a<b, b<c, c<a, plus Integer.compare instead of subtract.

If a<b<c<a, the sort is allowed to catch fire.

The judgement in off-by-one in binary search is which operation is O(1) versus O(n), not which library call looks shortest.

Pick one invariant and keep it: either search a closed [lo,hi] with lo<=hi and hi=mid-1, or a half-open [lo,hi) with lo<hi and hi=mid. Mixing them skips or infinite-loops.

Concretely, for first True in a monotonic predicate on [0,n): lo,hi=0,n; while lo<hi: mid=(lo+hi)//2; if pred(mid): hi=mid; else lo=mid+1. Return lo. Off-by-one is usually hi=mid vs mid-1.

The reason for that specificity is a failure I have seen: A mixed loop on n=10^6 never terminated (lo stuck at mid) and a worker hit 100% CPU for 9 minutes until killed.

First index with pred True.

template	loop	on True	on False
half-open [lo,hi)	lo<hi	hi=mid	lo=mid+1
closed [lo,hi]	lo<=hi	hi=mid-1	lo=mid+1
mix hi=mid with lo<=hi			can stall

I would not consider it settled without evidence: Trace lo,hi,mid on array [1,3,3,7] looking for first ≥3 → index 1, for both templates separately.

Closed and half-open are both correct; a hybrid is an infinite loop.

Where candidates lose the interview on Morris or parent pointers is usually a hidden linear scan inside a loop they already counted as constant.

Morris threads the predecessor's right pointer to the current node, visits, then unthreads so the tree is unchanged after the walk.

Concretely, if node.left is None, visit and go right. Else find pred (rightmost in left). If pred.right is None, set pred.right=node and go left. Else pred.right is a thread: clear it, visit node, go right.

The reason for that specificity is a failure I have seen: A recursive inorder on a 1.5×10^6 skewed tree used ~1.5×10^6 frames and crashed; Morris walked it in 120ms at 2 pointers of extra RAM. A bug that forgot to clear threads left 6% of later searches looping.

Thread then unthread.

step	pred.right	action
first visit left	None → node	go left
second find pred	node	clear, visit, go right
done	original	tree restored

I would not consider it settled without evidence: Before/after pointer equality on every right child, plus inorder matching the recursive result on 200 random trees.

O(1) extra means you borrow an edge and give it back.

I would answer graph representation for sparse input by separating what the test suite proved from what production traffic has not yet shown.

Build adjacency lists sized to n, not a matrix and not a dense n-length for unused ids if you can remap; a tree is 2(n-1) directed edges.

Concretely, read n,m; g=[[] for _ in range(n+1)]; for each edge append both ways if undirected. If ids are sparse 64-bit, map to 0..n-1 first. Do not g=[[0]*n for _ in range(n)].

The reason for that specificity is a failure I have seen: A contest submission allocated n×n on n=10^5 for a tree (m=99999) and MLE at 128MB; a compact adjacency representation used O(n+m) storage. In CPython, nested lists and edge tuples usually cost tens of megabytes here, not a language-independent 12MB.

Read a tree.

n, m = 100000, 99999
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = read()
    g[u].append((v, w))
    g[v].append((u, w))
# sum(len(g[i]) for i in range(n+1)) == 2*m

I would not consider it settled without evidence: len(g[u]) sums to 2m, and a memory check that rejects n*n allocations.

The input already told you m; allocate m, not n².

The engineering content of memoization key design is the bound and the rollback, not the clever one-liner.

Memo keys must be hashable and must include every input that changes the answer; a list is unhashable, and omitting an argument silently returns the wrong cached value.

Concretely, tuple(sorted(nums)) or a bitmask for small sets, plus other params in the key. For grids, (r,c,remaining). Don't close over a mutable that is not in the key.

The reason for that specificity is a failure I have seen: A DP helper cached only (r,c) while remaining_k mutated; 31% of paths reused a value from k=2 when k=0, and a pathfinder returned length 7 instead of 12 for 15 minutes.

Wrong key vs full key.

cache key	hidden state	result
(r,c)	k=2 vs k=0	stale hit
(r,c,k)		distinct
list nums		TypeError: unhashable
tuple(nums)		ok

I would not consider it settled without evidence: A test that two calls with different omitted state disagree without the full key, and that tuple(nums) is in the cache info.

If it is not in the key, the cache will treat it as the same problem.

Before reaching for a new structure I would write what a correct result for DP space compression looks like on n = 1 and n = 10^6.

If dp[i][w] only reads dp[i-1][*], keep one array of size W+1; for 0/1, iterate w descending so you read the previous item's value.

Concretely, dp=[0]*(W+1); for each item: for w=W..wt: dp[w]=max(dp[w], dp[w-wt]+val). Unique paths on a grid can keep one row of width C.

The reason for that specificity is a failure I have seen: A packed 400 × 1_000_001 int32 table requests ~1.6GB; one packed int32 row is ~4MB. A CPython list is larger because it stores 8-byte references plus separately allocated integer objects, but the same one-row compression still removes the factor of n.

Memory for W=1e6, n=400.

table	cells	~RAM int32
dp[n+1][W+1]	4e8	1.6GB
dp[2][W+1]	2e6	8MB
packed int32 dp[W+1], reverse w	1e6	4MB
CPython list dp[W+1]	1e6 refs	at least ~8MB plus integer objects

I would not consider it settled without evidence: Assert rolling dp equals the last row of the full table on W=50, n=8.

Keep the dimension the inner index still needs; throw away the item index.

The first thing I would pin down about counting sort versus comparison sort is which input size or concurrent interleaving actually breaks the naive version.

Counting sort is linear in n+k when keys are integers in a small range; comparison sorts are Ω(n log n) and win when k ≫ n or keys are arbitrary objects.

Concretely, count[k]++, prefix sums, write output stably from the back. Radix sort on 32-bit keys is 4 passes of counting on 8-bit digits. Python's Timsort still wins on general objects.

The reason for that specificity is a failure I have seen: Timsort on 2×10^7 bytes-as-ints took 1.9s; counting sort with k=256 finished in 110ms. The same counting sort on 64-bit random ids with k=2^64 is impossible.

n=1e7, two domains.

keys	algorithm	time
0..255	count k=256	110ms
random 64-bit	Timsort	~2s
0..1e9 sparse	radix or Timsort	not count[1e9]

I would not consider it settled without evidence: k=256, n=1e7 timing, versus k=n unique 64-bit keys where you sort.

Linear sort is a gift of a small integer domain, not a general replacement.

I would start reservoir sampling from the invariant the function must keep, not from the first algorithm that compiled.

Reservoir sampling keeps k slots; item i (1-indexed) replaces a slot with probability k/i, which yields a uniform subset without knowing n ahead of time.

Concretely, fill the first k items. For i=k+1..n: j=random.randrange(i); if j<k: res[j]=item. One-item case: keep with probability 1/i.

The reason for that specificity is a failure I have seen: Buffering 8×10^6 events to sample 10 OOMed a 512MB worker at 6 minutes; a 10-slot reservoir used 2KB and finished the stream in 3.1s.

k=1: keep item i with 1/i.

i	P(keep i)	P(final = i)
1	1	1*(1/2)(2/3)(3/4)*… = 1/n
2	1/2	1/n
n	1/n	1/n

I would not consider it settled without evidence: Simulate n=5,k=2 over 10^5 trials: each pair appears ~10% (1/C(5,2)).

Uniform from a stream is k/i at step i, not a list you cannot store.

This is a place where a green unit test and a correct handling of INNER JOIN versus LEFT JOIN are not the same event.

INNER JOIN keeps rows with a match on both sides; LEFT JOIN keeps every left row and NULLs the right columns when no match.

Concretely, write FROM orders o LEFT JOIN customers c ON c.id=o.customer_id when orders must survive missing customers. Filter with WHERE c.id IS NULL to find orphans. INNER is the default people type without noticing.

The reason for that specificity is a failure I have seen: An INNER JOIN hid 12,400 orders with deleted customer_ids (8% of GMV) for 14 minutes of a finance export; LEFT JOIN plus an orphan count restored the total to the ledger.

100k orders, 8k missing customers.

join	result rows	orders lost
INNER	92000	8000
LEFT	100000	0
LEFT … WHERE c.id IS NULL	8000	audit

I would not consider it settled without evidence: Row counts: orders 100_000, inner 92_000, left 100_000, orphans 8_000.

INNER JOIN is a filter; LEFT JOIN is a filter you did not apply.

My answer to GROUP BY versus DISTINCT begins at the bound: if I cannot name the complexity and the failure case, I do not have a solution.

DISTINCT deduplicates the selected columns; GROUP BY defines buckets for aggregates (COUNT, SUM). DISTINCT + aggregate without GROUP BY is a different mistake.

Concretely, unique ids: SELECT DISTINCT user_id FROM orders. Counts per user: SELECT user_id, COUNT(*) FROM orders GROUP BY user_id. In PostgreSQL, SELECT user_id, created_at GROUP BY user_id is an error unless created_at is aggregated or functionally dependent.

The reason for that specificity is a failure I have seen: SELECT DISTINCT user_id, created_at still returned 2.1×10^6 rows (almost all unique timestamps) when the author wanted 48k users; a 90s export became a 1.2s GROUP BY user_id.

Same table, two questions.

SQL	rows
DISTINCT user_id	48000
DISTINCT user_id, created_at	2100000
GROUP BY user_id COUNT(*)	48000

I would not consider it settled without evidence: EXPLAIN and row counts: distinct on two columns vs group by one.

DISTINCT is uniqueness of the row you selected; GROUP BY is the bucket you wanted.

I would treat window ROW_NUMBER pagination as a contract over all inputs rather than as a walkthrough of the sample.

OFFSET scans and discards preceding rows. ROW_NUMBER provides explicit ranks but usually still processes all qualifying rows and has the same concurrency drift unless the snapshot is fixed. Keyset pagination is the efficient stable continuation method.

Concretely, sELECT * FROM (SELECT u.*, ROW_NUMBER() OVER (ORDER BY id) rn FROM users u) t WHERE rn BETWEEN 981 AND 1000 still ranks qualifying rows. For deep pages, keyset WHERE id > last_id ORDER BY id LIMIT 20 seeks.

The reason for that specificity is a failure I have seen: OFFSET 50000 LIMIT 20 on a 2×10^6-row table did 380ms of discarded heap fetches; a keyset on (id) returned in 4ms.

Page 50, 20 rows.

method	typical work
OFFSET 980 LIMIT 20	read about 1000 ordered rows
ROW_NUMBER then 981..1000	rank qualifying rows, often all of them
WHERE id > :last_id LIMIT 20	seek and read 20 rows

I would not consider it settled without evidence: EXPLAIN ANALYZE actual rows removed by OFFSET vs Index Scan on id.

A page number is an OFFSET in disguise unless you keyset.

The useful question for covering index is what still happens when the array is empty, duplicated, or already sorted.

A covering index includes every column the query reads, so PostgreSQL can skip the heap (visibility map permitting).

Concretely, cREATE INDEX ON users (org_id) INCLUDE (id, email) or a composite (org_id, id, email). Measure heap fetches in EXPLAIN ANALYZE before/after. Write amplification on extra columns is the cost.

The reason for that specificity is a failure I have seen: A hot endpoint did 1.2×10^6 heap fetches/min at 18ms p95; INCLUDE (email) dropped p95 to 2.1ms and heap fetches by 94%.

Query: id, email WHERE org_id=.

index	plan
(org_id)	Index Scan + heap
(org_id) INCLUDE (id,email)	eligible for Index Only Scan
(org_id,email)	id missing; heap still required

I would not consider it settled without evidence: EXPLAIN ANALYZE: Heap Fetches: 0 on a vacuumed table, matching row count 40.

If the heap is still visited, the index did not cover the SELECT list.

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.

predicate	selectivity	winner
status='active'	92%	seq scan 90ms
status='closed'	8%	index 11ms
id = 42	1 row	index 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.

The judgement in third normal form versus denormalization is which operation is O(1) versus O(n), not which library call looks shortest.

3NF keeps non-key attributes depending on the key; copying email onto orders means an email change must touch history. Denormalize when a join is on the read path p99 budget and the copy has an explicit refresh.

Concretely, normalize to orders.customer_id → customers.email. If you denormalize, define the writer: trigger, application dual-write, or nightly rebuild, and a drift query.

The reason for that specificity is a failure I have seen: A 12% email-update batch updated customers but not 4.2×10^6 order copies; support saw stale mail for 45 minutes. Dual-write in the same transaction fixed new rows; a backfill took 9 minutes.

Email change of 1 user, 400 orders.

design	rows to update
3NF customers.email	1
denormalized order.email	400
allowed denorm	400 + drift job

I would not consider it settled without evidence: COUNT of orders whose email disagrees with customers, target 0 after backfill.

A copied column is a cache; caches drift unless a writer is named.

Where candidates lose the interview on NULL in UNIQUE constraints is usually a hidden linear scan inside a loop they already counted as constant.

Ordinary PostgreSQL UNIQUE permits multiple NULLs. PostgreSQL 15+ UNIQUE NULLS NOT DISTINCT treats NULLs as equal and permits at most one; older versions need separate expression/partial constraints.

Concretely, on PostgreSQL 15+, use UNIQUE NULLS NOT DISTINCT (email). On older versions, retain uniqueness for non-NULL email and add CREATE UNIQUE INDEX ... ON t ((1)) WHERE email IS NULL to allow at most one NULL.

The reason for that specificity is a failure I have seen: A users table grew 1,104 NULL emails (3% of signups) all "unique"; a later NOT NULL backfill failed for 18 minutes on duplicates that UNIQUE had not prevented.

PostgreSQL UNIQUE(email).

insert	UNIQUE(email)	UNIQUE NULLS NOT DISTINCT
'a@x' twice	2nd fails	2nd fails
NULL twice	both ok	2nd fails
PG 14 one NULL	extra unique on ((1)) WHERE email IS NULL

I would not consider it settled without evidence: INSERT two NULL rows under ordinary UNIQUE, then show the constant-expression partial unique index rejecting the second NULL; the original UNIQUE constraint still rejects duplicate non-NULL emails.

UNIQUE does not mean unique among unknowns.

I would answer MVCC write skew by separating what the test suite proved from what production traffic has not yet shown.

Write skew: each transaction's write is disjoint, so row-level locks do not conflict, but the combined predicate is violated. Serializable (SSI) or an explicit lock/constraint is the fix.

Concretely, use SERIALIZABLE and retry on 40001, or SELECT … FOR UPDATE on a parent row, or a constraint that encodes the invariant (at least one on-call). REPEATABLE READ still allows write skew.

The reason for that specificity is a failure I have seen: Both transactions observed another doctor on call, updated different rows, and committed under REPEATABLE READ, leaving zero doctors on call.

On-call invariant: at least one.

isolation	T1 sees B on	T2 sees A on	both turn self off
READ COMMITTED/RR	yes	yes	possible; invariant broken
SERIALIZABLE SSI	yes	yes	one aborts with 40001

I would not consider it settled without evidence: A test that two concurrent transactions under RR both commit, and under SERIALIZABLE one aborts.

Non-overlapping writes can still break a predicate; that is write skew.

The engineering content of deadlock victim is the bound and the rollback, not the clever one-liner.

A deadlock is a cycle in the lock wait graph; PostgreSQL aborts one transaction (the deadlock victim) with 40P01. Prevent by locking rows in a global order.

Concretely, sort ids before UPDATE. Keep transactions short. log_lock_waits and deadlock_timeout (default 1s) surface the cycle. Do not retry forever without backoff.

The reason for that specificity is a failure I have seen: Unordered pair updates deadlocked 40 times/min (12% of checkout TX); p95 jumped by 250ms on victims. Sorting wallet ids cut deadlocks to 0 in 20 minutes of traffic.

Two-row update order.

T1	T2	result
lock 1, wait 2	lock 2, wait 1	40P01
lock min, then max	same order	both commit
victim retry		1 abort, 1 win

I would not consider it settled without evidence: postgres log: deadlock detected, plus a unit test of two orders of FOR UPDATE.

Lock in sorted key order; the victim is a symptom of a cycle you wrote.

Before reaching for a new structure I would write what a correct result for COUNT DISTINCT cost looks like on n = 1 and n = 10^6.

Exact COUNT() must scan visible tuples, possibly through an index-only scan. COUNT(DISTINCT x) additionally deduplicates by hashing or sorting. pg_class.reltuples can provide an approximate row count, not SQL COUNT() semantics.

Concretely, for exact: index on (user_id) still scans matching rows. For dashboards: HyperLogLog (postgresql-hll, Redis PFCOUNT) with ~2% error. Partial DISTINCT in a covering index is rare; pre-aggregate daily uniques.

The reason for that specificity is a failure I have seen: A 15-minute COUNT(DISTINCT) on 2×10^8 rows used 2.4GB work_mem spill and blocked a replica; HLL returned in 80ms at 1.6% error.

2e8 events, unique users ~4.8e7.

method	time	error
COUNT(*)	12s seq	exact rows
COUNT(DISTINCT user_id)	14 min	exact
HLL	80ms	~2%

I would not consider it settled without evidence: EXPLAIN: HashAggregate vs Aggregate, and a comparison of exact 48_112_011 vs HLL 47_900_000.

Distinct is a set; counting rows is not the same hash.

The first thing I would pin down about EXISTS versus IN is which input size or concurrent interleaving actually breaks the naive version.

EXISTS directly expresses a correlated existence test, while IN expresses membership. PostgreSQL can plan either positive form as a semi-join, so inspect the plan instead of claiming one always wins; the sharp semantic difference is NOT IN when the subquery can return NULL.

Concretely, use EXISTS (SELECT 1 FROM events e WHERE e.user_id=u.id) for "has any event" and compare EXPLAIN plans if performance matters. NOT IN (SELECT x) yields unknown for otherwise-unmatched rows when x contains NULL; use NOT EXISTS for the nullable anti-join.

The reason for that specificity is a failure I have seen: NOT IN (SELECT manager_id FROM emp) with a NULL manager_id returned 0 rows (100% wrong) for 9 minutes; NOT EXISTS returned 1,204 un-managed users.

Anti-join with a NULL in the set.

predicate	NULL in subquery	result
NOT IN (1, NULL)	yes	empty (unknown)
NOT EXISTS match		rows without match
EXISTS match		semi-join

I would not consider it settled without evidence: EXPLAIN: Hash Semi Join vs Materialize+IN, plus a NULL fixture for NOT IN.

Positive IN and EXISTS may share a plan; nullable NOT IN and NOT EXISTS do not share semantics.

I would start foreign key ON DELETE from the invariant the function must keep, not from the first algorithm that compiled.

ON DELETE RESTRICT/NO ACTION refuses the delete; CASCADE deletes children; SET NULL orphans with a NULL fk. Pick from the product rule, not the ORM default.

Concretely, rEFERENCES customers(id) ON DELETE RESTRICT for orders you must keep. CASCADE for truly owned rows (session tokens). SET NULL only if the column is nullable and the report handles NULL.

The reason for that specificity is a failure I have seen: ORM default CASCADE wiped 2.4×10^5 orders when a test customer was deleted in prod-like data, 22 minutes to restore from backup.

Delete customer 42.

ON DELETE	orders for 42	allowed?
RESTRICT	1200 remain	DELETE fails
CASCADE	0	DELETE ok, history gone
SET NULL	1200, fk NULL	DELETE ok

I would not consider it settled without evidence: A failing DELETE when orders exist (RESTRICT), and a passing CASCADE only on a sessions table with 0 revenue.

The FK action is a product decision encoded in DDL.

This is a place where a green unit test and a correct handling of partial index are not the same event.

A partial index WHERE deleted_at IS NULL stores only live rows, smaller and more cache-friendly, matching the predicate the planner needs.

Concretely, cREATE INDEX ON t(org_id) WHERE deleted_at IS NULL. The query must include that predicate (or something the planner proves implies it). Do not also keep a full duplicate index without a reason.

The reason for that specificity is a failure I have seen: With 99% live rows, a live-row partial index is only slightly smaller than the full index. Large savings occur when the indexed predicate selects a small subset, such as 1% active jobs.

Partial index size follows the predicate.

population	live partial index
99% live	approximately 99% of full index
1% live	approximately 1% of full index
benefit at 99% live	predicate matching, not 100× size reduction

I would not consider it settled without evidence: pg_relation_size before/after, and EXPLAIN using the partial index.

Index the rows the query can see; a 99% predicate does not shrink the btree by 100×.

My answer to JSONB versus relational columns begins at the bound: if I cannot name the complexity and the failure case, I do not have a solution.

Relational columns win for predicates, constraints, and stats; JSONB wins for sparse, schema-flex keys. A hot key belongs in a column or an expression index.

Concretely, cREATE INDEX ON t ((settings->>'theme')); or GENERATED ALWAYS AS (settings->>'theme') STORED plus a btree. Promote when that key is in 100% of rows and in WHERE/JOIN.

The reason for that specificity is a failure I have seen: Seq scan on 2×10^7 JSONB blobs for settings->>'theme'='dark' ran 12s (14% of rows); a btree on the expression dropped it to 35ms.

Filter theme=dark, 20M rows.

storage	p95
JSONB no index	12s
btree on (settings->>'theme')	35ms
column theme TEXT	8ms + check

I would not consider it settled without evidence: EXPLAIN seq vs index, and a NOT NULL constraint you cannot put on an arbitrary JSON key without a check.

JSONB is a bag; a WHERE clause wants a column or an expression index.

I would treat Interval merge in one pass as a contract over all inputs rather than as a walkthrough of the sample.

Sorting by start gives the invariant that any interval still able to touch the current block is next in the sweep; without it a long interval can arrive after the block it should have absorbed, and one pass is no longer correct.

Concretely, sort intervals by start ascending, keep one open block [s, e], and for each interval either raise the block's end to max(end, e) when start <= e, or close the block and open a new one.

The reason for that specificity is a failure I have seen: A nightly job swept 2×10^5 booking intervals in stored order; the shape [2,3],[4,5],[1,10] appeared 4,100 times, and each one emitted three windows instead of one, so a $40-per-window rate card billed $120 for a single 10-hour block. One sort key fixed all 4,100 cases at O(n log n) ≈ 3.5×10^6 comparisons.

Sweep of [2,3],[4,5],[1,10], inclusive ends, merge when start <= end.

pass	next interval	action	blocks so far
sorted	[1,10]	open block	[1,10]
sorted	[2,3]	2 <= 10, end = max(10,3)	[1,10]
sorted	[4,5]	4 <= 10, end = max(10,5)	[1,10]
unsorted	[2,3]	open block	[2,3]
unsorted	[4,5]	4 > 3, open new	[2,3] [4,5]
unsorted	[1,10]	1 > 5, open new	[2,3] [4,5] [1,10]

I would not consider it settled without evidence: Show the sweep state on [2,3],[4,5],[1,10] with and without the sort; the two traces must end with different output, and your merge test must compare a start against the open block's end, not the previous interval's end.

Sort by start and the merge rule is one comparison against the open block; skip the sort and you owe a second structure or an O(n²) scan.

The useful question for EXPLAIN ANALYZE actual rows is what still happens when the array is empty, duplicated, or already sorted.

A 6000× misestimate means the planner picked a join order or method for the wrong cardinality; refresh stats and check for correlated columns before rewriting SQL.

Concretely, eXPLAIN ANALYZE (BUFFERS, TIMING). Compare rows= estimate vs actual. ANALYZE the table; for correlated predicates, extended statistics CREATE STATISTICS. Only then add indexes or rewrite.

The reason for that specificity is a failure I have seen: A nested loop expected 40 inner rows and executed 2.4×10^5 × 40 = 9.6e6 inner scans, 11 minutes; after ANALYZE the estimate was 220k and a hash join finished in 1.8s.

Nested Loop node.

field	before ANALYZE	after
rows estimate	40	220000
rows actual	240000	240000
time	11 min	1.8s
join	nested loop	hash

I would not consider it settled without evidence: The two rows= figures next to the same node, plus last_analyze from pg_stat_user_tables.

The plan is innocent until the actual row count convicts the stats.

I would settle transaction isolation read committed against a counter-example first, so the clever trick has to survive it.

READ COMMITTED takes a new snapshot per statement, so two SELECTs in one transaction can see different committed data. REPEATABLE READ (PG) uses one snapshot for the transaction.

Concretely, default in PostgreSQL is READ COMMITTED. For reports that must be consistent, BEGIN ISOLATION LEVEL REPEATABLE READ (or SERIALIZABLE). Lost updates: UPDATE … WHERE version=n or SELECT FOR UPDATE.

The reason for that specificity is a failure I have seen: A billing job summed balances in two statements 250ms apart; a commit in between dropped 6% of a $4.1M total for that run (14 minutes to reverse). Repeatable read made both sums identical.

Two SELECTs in T1, T2 commits between.

isolation	SELECT #1	SELECT #2
READ COMMITTED	100	90
REPEATABLE READ	100	100
T2 UPDATE		committed at 125ms

I would not consider it settled without evidence: A demo: T2 commits an UPDATE between T1's two SELECTs; RC sees the new value on the second SELECT, RR does not.

READ COMMITTED is per statement; a "transaction" is not a frozen photograph.

The judgement in list versus deque is which operation is O(1) versus O(n), not which library call looks shortest.

list.pop(0) and insert(0, x) are O(n) because they shift the tail; collections.deque popleft/appendleft are O(1). list pop() and append() at the right are amortized O(1).

Concretely, use deque for FIFO. Use list as a stack (append/pop). For random access, list wins O(1) index; deque index is O(n).

The reason for that specificity is a failure I have seen: A worker drained 1.5×10^6 events with jobs.pop(0) in 48 seconds; deque.popleft finished in 90ms (530×).

n=1e5 operations.

from collections import deque
# list: pop(0) ~ O(n) each → ~2.1s for 1e5
# deque: popleft() O(1)     → ~8ms for 1e5
q = deque()
q.append(x); q.popleft()

I would not consider it settled without evidence: timeit n=10^5 pop(0) vs popleft, plus a note that deque(maxlen=) is a ring.

The left end of a list is not a queue; a deque is.

Where candidates lose the interview on dict insertion order is usually a hidden linear scan inside a loop they already counted as constant.

Python 3.7+ guarantees that dict preserves insertion order; CPython 3.6 had it only as an implementation detail. set does not promise insertion order, and hash randomization can change its iteration order.

Concretely, use dict or OrderedDict for ordered maps. For a sorted view, sorted(d). JSON object order follows insertion if you dump a dict. Do not use a set as an LRU.

The reason for that specificity is a failure I have seen: A test asserted list({3,1,2})==[3,1,2] and failed on 12% of CI shards (hash seed); switching to a list/dict made 400 tests stable in 8 minutes.

Order guarantees.

type	iteration order
dict (3.7+)	insertion
OrderedDict	insertion + move_to_end
set	arbitrary
PYTHONHASHSEED=random	set order changes

I would not consider it settled without evidence: Python 3.6 implementation detail vs 3.7 guarantee, plus a set iteration that changes with PYTHONHASHSEED.

dict is ordered; set is not a small dict.

I would answer generator versus list comprehension by separating what the test suite proved from what production traffic has not yet shown.

A generator expression yields one value at a time; a list comprehension materializes n elements. Use the list when you iterate twice or need len/index.

Concretely, sum(x*x for x in it) streams. If you pass a generator to a function that iterates twice, the second pass is empty — then you needed a list.

The reason for that specificity is a failure I have seen: A report built a 2.4×10^7-element list of rows (1.9GB) and swapped for 7 minutes; a generator over the cursor kept RSS at 180MB and finished in 41s.

n=10^7 squares into sum.

form	extra list	peak ~
[x*x for x in range(n)]	yes	hundreds of MB
(x*x for x in range(n))	no	small
need two passes	list or tee

I would not consider it settled without evidence: tracemalloc peaks: list ~800MB vs gen ~few MB for n=10^7 small ints, plus a double-iterate test.

If you only need a stream, a list is a bill for RAM.

The engineering content of GIL and CPU-bound threads is the bound and the rollback, not the clever one-liner.

The CPython 3.12 GIL serializes Python bytecode execution. Pure-Python CPU loops need processes for multicore execution, but C extensions such as hashlib may release the GIL and can scale with threads.

Concretely, concurrent.futures.ProcessPoolExecutor for pure-Python CPU. ThreadPoolExecutor for sockets/disk. asyncio for many sockets in one thread. numpy/crypto often release the GIL.

The reason for that specificity is a failure I have seen: A "4-thread" pure-Python numeric loop on 4 cores took 13.9s vs 4.1s in a process pool; threads were serialized by the GIL.

4 cores, CPU-bound work.

workload	threads
pure-Python numeric loop	serialized by GIL
hashlib on large buffers	may run concurrently; releases GIL
blocking I/O	overlaps waits
pure-Python CPU via processes	uses multiple cores

I would not consider it settled without evidence: time.perf_counter around a pure-Python loop in threads vs processes, cores=4, n=10^7.

Threads overlap I/O; processes overlap CPU; the GIL is why.

Before reaching for a new structure I would write what a correct result for frozen dataclass hashing looks like on n = 1 and n = 10^6.

A default mutable dataclass with eq=True has hash=None. frozen=True can generate a field-based hash when all hashed fields are hashable; alternatively use a custom hash based only on immutable identity fields.

Concretely, @dataclass(frozen=True) class Key: … Hash is the tuple of fields. For a mutable payload, use an id as the key and store the payload beside it. unsafe_hash=True on a mutable class is the ghost-bucket bug.

The reason for that specificity is a failure I have seen: An unsafe_hash=True dataclass was inserted into a set and then a hashed field changed, orphaning the entry in its old bucket.

frozen vs mutable in a set.

@dataclass(frozen=True)
class Point:
    x: int
    y: int
s = {Point(1, 2)}
# p.x = 9  # FrozenInstanceError
# unfrozen + mutate → lookup miss, ghost entry

I would not consider it settled without evidence: An unfrozen default dataclass raises TypeError when inserted into a set; assigning a frozen field raises FrozenInstanceError.

If it is in a set, it cannot change the fields that hashed.

The first thing I would pin down about functools wraps on decorators is which input size or concurrent interleaving actually breaks the naive version.

@functools.wraps(fn) copies name, doc, and wrapped so introspection, OpenAPI, and tests still see the original function.

Concretely, from functools import wraps; def deco(fn): @wraps(fn): def wrapper(*a, **k): …; return wrapper. Without wraps, name is wrapper and signature tools break.

The reason for that specificity is a failure I have seen: 12% of routes vanished from generated OpenAPI because every handler was named wrapper; adding wraps restored 48 paths in one deploy (8 minutes).

Name before and after wraps.

	name	signature
no wraps	wrapper	*args, **kwargs
@wraps(fn)	foo	(x, y=1)
FastAPI		params from signature

I would not consider it settled without evidence: assert foo.name=='foo' after decoration, and inspect.signature matches the original params.

The wrapper is the runtime; wraps is the identity you promised callers.

I would start context manager exception safety from the invariant the function must keep, not from the first algorithm that compiled.

with calls exit on both success and exception; returning True from exit swallows the exception. Resource cleanup belongs in exit or finally, not after the block.

Concretely, contextlib.contextmanager: yield in try, release in finally. Do not return True from exit unless you intentionally suppress. Locks, sockets, transactions follow this.

The reason for that specificity is a failure I have seen: A lock.release() after the critical section was skipped by a 500 that raised; 6% of workers stalled 14 minutes until the process limit. with lock: would have released in exit.

Generator context manager.

from contextlib import contextmanager
@contextmanager
def locked(lock):
    lock.acquire()
    try:
        yield
    finally:
        lock.release()  # runs on error too

I would not consider it settled without evidence: A test that raises inside with and asserts lock.locked() is False, plus exit returning None.

The release is in exit; a line after the block is a hope.

This is a place where a green unit test and a correct handling of mutable default argument are not the same event.

Default argument values are evaluated once, at function definition, so a mutable default is shared across calls.

Concretely, def f(items=None): if items is None: items=[]. Same for dict, set. Class attributes have an analogous sharing bug.

The reason for that specificity is a failure I have seen: An API handler defaulted filters=[] and appended a tenant id; 9% of requests leaked another tenant's filter for 22 minutes until a canary saw cross-account rows.

Shared default list.

def f(items=[]):
    items.append(1)
    return items
f()  # [1]
f()  # [1, 1]  same list
def g(items=None):
    if items is None:
        items = []
    items.append(1)
    return items

I would not consider it settled without evidence: Two calls f() is f() for the list identity, and a test that consecutive calls return independent lists after the None fix.

The default list is one object; None is a sentinel per call.

My answer to is versus equality begins at the bound: if I cannot name the complexity and the failure case, I do not have a solution.

is tests object identity; == tests value. CPython interned small ints (-5..256) make is accidentally work; it is not a language guarantee for integers or strings.

Concretely, compare values with ==. Use is for None and private sentinel objects (x is MISSING); for booleans, normally test truthiness and use == only when exact value equality is required. Never depend on interning for integers or strings.

The reason for that specificity is a failure I have seen: A cache key path used token is "active" (interned in some builds); 3% of tokens compared False at 257-like identities and skipped writes for 11 minutes.

CPython intern range.

expr	typical CPython
256 is 256	True (intern)
int('257') is 257	often False
int('257') == 257	True
x is None	correct

I would not consider it settled without evidence: id(256) vs id(int('256')) may match; id(257) vs int('257') often does not; == both True.

is is pointer equality; 257 is allowed to be a new box.

I would treat asyncio versus thread pool as a contract over all inputs rather than as a walkthrough of the sample.

asyncio multiplexes waiting sockets; CPU-bound parse still blocks the loop. Offload CPU to process_pool, blocking disk/legacy to thread_pool, keep sockets in async.

Concretely, await session.get. For parse: await loop.run_in_executor(process_pool, parse, body) or a C parser. Don't time.sleep on the loop; asyncio.sleep. Don't run n=5000 OS threads.

The reason for that specificity is a failure I have seen: Parsing 5,000 responses at 40ms CPU each requires 200 CPU-seconds. One event-loop thread needs roughly 200 seconds; four continuously busy processes need roughly 50 seconds for the batch, excluding overhead.

5k GETs, 40ms parse.

parse location	lower-bound batch time
event-loop thread	about 200s
four processes	about 50s
I/O only	governed by network latency

I would not consider it settled without evidence: blocked-event-loop metric > 50ms, plus a split of await vs executor in the flame graph.

The loop waits; it does not hash. Hash in another process.

The useful question for multiprocessing pickle boundary is what still happens when the array is empty, duplicated, or already sorted.

Arguments and callables to child processes are pickled; lambdas, closures, and some thread locks do not pickle. The target function should be a module-level def.

Concretely, def work(x): … at top level. Pass simple args (ids, paths), not open sockets. spawn vs fork: spawn pickles more. shared_memory or a queue for large arrays.

The reason for that specificity is a failure I have seen: A pool of 8 mapped a lambda over 2×10^6 rows and died on pickle in 100% of workers; a top-level function processed 2×10^6 in 38s.

What pickle accepts.

object	pickle to child
module-level def	yes
lambda x: x+1	no
local def	no
list of ints	yes
open socket	no

I would not consider it settled without evidence: pickle.dumps(fn) succeeding for the worker target, failing for the lambda.

Another process only receives what pickle can spell.

I would settle iterator protocol exhaustion against a counter-example first, so the clever trick has to survive it.

A generator is a single-pass iterator; the second for-loop sees StopIteration immediately. Reuse needs a list, itertools.tee, or a new generator.

Concretely, rows=list(gen) if n is small. tee duplicates the stream with a buffer. Files need seek(0) or reopen. Do not assume zip(gen, gen) pairs consecutive — it advances one iterator twice per pair if the same object.

The reason for that specificity is a failure I have seen: A validator consumed the CSV iterator then the loader saw 0 rows and marked 100% success on empty; 14 minutes of silent skip of 1.2×10^6 rows.

One generator, two consumers.

g = (x for x in range(3))
list(g)  # [0, 1, 2]
list(g)  # []
# zip(g, g) on a fresh gen pairs (0,1), (2,Stop) — not (0,0)

I would not consider it settled without evidence: list(g); list(g)==[] for a generator, versus two list comprehensions from a fresh range.

An iterator is a tape, not a list; rewind by copying or recreating.

The judgement in exception chaining from is which operation is O(1) versus O(n), not which library call looks shortest.

raise New from orig sets cause; implicit chaining in except sets context. from None suppresses the context for the client while you still log orig.

Concretely, except ConnectionError as e: raise AppError("db down") from e. Logs should print traceback.cause. Do not empty-except and raise without chaining if operators need the socket error.

The reason for that specificity is a failure I have seen: A wrapper raised AppError from None; on-call spent 18 minutes without the underlying 250ms timeout in the traceback (12% of 5xx that night).

Chain vs suppress.

statement	cause	operator sees
raise App from e	ConnectionError	both
raise App	context set	both, implicit
raise App from None	None	App only

I would not consider it settled without evidence: assert err.cause is conn_err, and a logged chained traceback in a fixture.

from e keeps the crime scene; from None is a redaction.

Where candidates lose the interview on unhashable mutable dict key is usually a hidden linear scan inside a loop they already counted as constant.

dict keys must be hashable: immutable structure whose hash is stable. list and dict are mutable and unhashable; tuple of immutables and frozenset are hashable.

Concretely, key=(user_id, org_id) or frozenset(ids). Never use a list. Nested tuple members must themselves be hashable. Plain user-defined objects normally inherit identity equality and hashing, but built-in dict and list containers are unhashable.

The reason for that specificity is a failure I have seen: A memo tried to key on a list of filters and crashed 100% of those requests; tuple(sorted(filters)) cut cache misses 40% and p95 from 180ms to 12ms.

Keys that hash.

candidate	hashable
(1, "a")	yes
[1, "a"]	no
frozenset({1,2})	yes
{"a": 1}	no

I would not consider it settled without evidence: hash((1,2)) works; hash([1,2]) TypeError; hash(({1},)) TypeError.

If it can change, it cannot be a key.

I would answer sort key stability by separating what the test suite proved from what production traffic has not yet shown.

Timsort is stable, so sort by name then by grade (primary last). A single key=(grade, name) is clearer. Unstable sorts would scramble the secondary key.

Concretely, sorted(rows, key=lambda r: (r.grade, r.name)). Or sorted(sorted(rows, key=name), key=grade) with a stable sort. operator.itemgetter(1,0) avoids a lambda.

The reason for that specificity is a failure I have seen: Two passes of an unstable C qsort left 7% of equal-grade rows not alphabetical; a report's "then by name" was wrong for 9 minutes of a printed run (n=6×10^5).

Primary grade, secondary name.

method	ok?
key=(grade, name)	yes
stable: sort name, then grade	yes
unstable twice	no
Python sorted	stable

I would not consider it settled without evidence: Equal grade 3: Ann before Bob preserved; a counter-example with an unstable comparator.

Secondary order is stability or a tuple; it is not a second wish.

The engineering content of copy versus deepcopy is the bound and the rollback, not the clever one-liner.

copy.copy is shallow: nested objects are aliased. deepcopy recursively clones. Graphs with cycles need deepcopy's memo; often you only needed a new dict at the top.

Concretely, copy.copy / dict.copy / list[:] shallow. copy.deepcopy for nested. Prefer constructing a new DTO field-by-field when the graph is wide (deepcopy of 10^6 nodes is slow).

The reason for that specificity is a failure I have seen: A "clone order" used copy.copy; mutating line items changed the stored order for 4.2% of clones and double-charged $180k over 40 minutes. deepcopy of a 2MB graph took 250ms — a targeted copy of lines was 3ms.

Nested child alias.

import copy
a = {"child": {"x": 0}}
b = copy.copy(a)
b["child"]["x"] = 1
assert a["child"]["x"] == 1  # aliased
c = copy.deepcopy(a)

I would not consider it settled without evidence: id(a.child)==id(b.child) after shallow copy; not equal after deepcopy.

Shallow copy shares the children; that is the bug and the speed.

Before reaching for a new structure I would write what a correct result for slots memory looks like on n = 1 and n = 10^6.

slots replaces per-instance dict with a fixed layout; you cannot add arbitrary attributes unless you include 'dict'.

Concretely, class Point: slots=("x","y","z"). Measure with sys.getsizeof and tracemalloc. Namedtuple/dataclass(slots=True) in 3.10+. Weakref needs 'weakref' in slots.

The reason for that specificity is a failure I have seen: 10^7 Point objects with dict used ~3.2GB and were killed at 8 minutes into a sim; slots used ~0.9GB and finished in 11 minutes.

Rough CPython 64-bit sizes.

type	~bytes / instance	1e7 total
class with dict	~300	~3GB
slots x,y,z	~80	~0.8GB
tuple of 3 ints	~80	~0.8GB

I would not consider it settled without evidence: Compare allocations with tracemalloc and assert that p.extra = 1 raises AttributeError.

Slots buy density; they sell dynamic attributes.

The first thing I would pin down about type hints versus runtime is which input size or concurrent interleaving actually breaks the naive version.

Annotations are not runtime checks in vanilla CPython; they are hints for type checkers and optional runtime libraries (pydantic, beartype, dataclasses).

Concretely, python 3.14 uses PEP 649/749 deferred annotation evaluation by default. The older from future import annotations behavior stringizes annotations and is a distinct compatibility mode; neither behavior validates arguments. Use a schema library or explicit checks at trust boundaries.

The reason for that specificity is a failure I have seen: A hinted int path concatenated "12"+3 from JSON and 500'd 8% of webhooks for 16 minutes; pydantic validation rejected them at 2ms with a 422.

Hint vs check.

layer	rejects f("a")?
def f(x: int)	no
mypy CI	yes, if run
pydantic x: int	yes at parse
assert isinstance	yes if you wrote it

I would not consider it settled without evidence: A call f("not int") succeeding without pydantic, failing with it.

The colon is for mypy; the boundary is for pydantic.

I would start cache-aside stampede from the invariant the function must keep, not from the first algorithm that compiled.

Cache-aside: read cache, on miss load DB then set. A stampede needs a single-flight lock, early refresh, or staggered TTL so one loader fills.

Concretely, sET key NX PX as a lock, or request coalescing in-process, or probabilistic early recompute. Still write the value with SET. Do not have every miss hit the DB.

The reason for that specificity is a failure I have seen: TTL expiry on a hot key sent 400 queries × 2.1s to Postgres (p99 2.1s → 14s) for 3 minutes every hour; a lock cut it to 1 query and 2.2s.

400 misses at TTL.

pattern	DB queries	p99
naive aside	400	14s
single-flight lock	1	2.2s
TTL jitter ±12%	fewer aligned	2.4s

I would not consider it settled without evidence: Metric: db_queries_on_cache_miss == 1 per key per refresh, not 400.

Aside is get-load-set; stampede is get-load-load-load unless you lock.

This is a place where a green unit test and a correct handling of write-through versus write-back are not the same event.

Write-through keeps cache and DB aligned on the request path (higher latency, simpler durability). Write-back is fast and can lose the last writes if the cache node dies before flush.

Concretely, profiles, balances: write-through or write DB then invalidate (write-around). Session counters: write-back with a bounded queue and fsync budget. Always define the crash window.

The reason for that specificity is a failure I have seen: Write-back of balances lost 2.1s of increments on a cache restart (12% of a minute's tips, $47k); write-through added 8ms and survived the restart.

Kill cache 200ms after write.

mode	request latency	rows lost
write-through	12ms	0
write-back 1s flush	1ms	last 200ms
DB then delete key	11ms	0 (miss)

I would not consider it settled without evidence: Crash test: kill cache before flush, count missing DB rows; through should be 0.

Through pays latency for the same answer after a crash; back pays RAM for a window of loss.

My answer to cache key cardinality begins at the bound: if I cannot name the complexity and the failure case, I do not have a solution.

A cache key's cardinality is the product of its dimensions; high-cardinality junk (UTM, timestamps) turns the cache into a unique-store.

Concretely, key = function of the inputs that change the value. Bound TTL. Reject putting raw query strings in keys. Measure redis_memory / unique keys.

The reason for that specificity is a failure I have seen: Keys user:utm filled 4.2×10^7 entries (12% hit rate) and OOM'd Redis at 40GB after 18 minutes of a sale; dropping UTM from the key cut memory to 1.1GB and hit rate to 88%.

1e6 users × extra dimensions.

key	unique keys	hit rate
html:{user}:{utm}	4.2e7	12%
html:{user}	1.0e6	88%
html:{user}:{ts}	unbounded	~0%

I would not consider it settled without evidence: INFO keyspace + a sample of 100 keys showing unique UTMs, plus a cardinality budget.

If the key includes noise, you will cache noise at RAM prices.

I would treat primary-replica lag as a contract over all inputs rather than as a walkthrough of the sample.

Replicas are asynchronously behind; a read-your-writes path must hit the primary, wait for a LSN, or use a session sticky that sees the write.

Concretely, after writing, read from the primary or carry the primary’s WAL LSN and poll the replica until pg_last_wal_replay_lsn() reaches it before serving the dependent read. PostgreSQL has no SHOW replay_lsn wait command.

The reason for that specificity is a failure I have seen: A signup read the replica at 250ms lag; 9% of clients saw "user not found" and retried, creating duplicates for 11 minutes until reads went to primary for 2s after INSERT.

INSERT then GET 80ms later.

read target	lag	GET result
replica	250ms	miss
primary	0	hit
replica after wait LSN	0	hit

I would not consider it settled without evidence: lag histogram vs 80ms GET, plus a test INSERT then replica SELECT count=0.

The replica is a delayed photograph; your last write may not be in it.

The useful question for shard key hot spot is what still happens when the array is empty, duplicated, or already sorted.

A shard key with a Zipf hot value pins traffic to one partition; a composite (tenant_id, hash(order_id)) or a random suffix spreads writes at the cost of scatter-gather reads.

Concretely, measure write QPS per shard. If p99 shard is 8× mean, change the key or split the hot tenant. Range keys on timestamps hotspot the latest partition.

The reason for that specificity is a failure I have seen: tenant=ACME at 40% of 80k QPS melted one shard (p99 1.8s, 14 minutes of 429s); hashing order_id dropped that shard to 11% and p99 to 40ms.

8 shards, 80k QPS.

key	hottest shard	p99
tenant_id	40% (32k)	1.8s
hash(order_id)	~12.5%	40ms
date range	today's shard 70%	2.1s

I would not consider it settled without evidence: QPS histogram by shard, max/mean ratio, before/after key.

The key that groups reads can concentrate writes; name the hot value.

I would settle idempotent POST with key against a counter-example first, so the clever trick has to survive it.

Treat POST as at-least-once: clients send Idempotency-Key; the server stores key→response (or key→charge_id) with a uniqueness constraint and replays the same result.

Concretely, uNIQUE(idempotency_key). First writer inserts in the same transaction as the charge. Concurrent retries wait or get 409 then reread. TTL the keys (e.g. 24h). GET is already idempotent; POST is not without a key.

The reason for that specificity is a failure I have seen: 504 retries without keys double-charged 1,104 payments (2.2%, $91k) in 16 minutes; a unique key table made the second POST return the first charge_id in 8ms.

Two POSTs, one 504.

request	key	charges rows
POST #1	k	1
504, client retry	k	1 (replay)
POST different key	k2	2

I would not consider it settled without evidence: Two POSTs with the same key, one row in charges, same JSON body.

Retries will happen; the unique key is the charge.

The judgement in cursor pagination API is which operation is O(1) versus O(n), not which library call looks shortest.

Offset pages shift when inserts land above; a cursor of the last (sort, id) is stable for a seek. Encode opaque, signed, not a raw SQL fragment.

Concretely, gET /items?cursor=…&limit=50. next_cursor from the last row. Document that cursors expire if the sort key is deleted. Prefer (created_at, id) DESC.

The reason for that specificity is a failure I have seen: page=2 skipped 12% of a live feed during a 400 inserts/s launch (users saw dups on page=1 refresh) for 9 minutes; cursor seeks neither skipped nor duplicated.

Insert during pagination.

method	after 400 inserts on top
page=2 offset	skip 400, dups possible
cursor (ts,id)	next older 50
page=1 refresh	new 50

I would not consider it settled without evidence: Insert above, then next page with offset vs cursor: offset misses, cursor continues.

A page number is a moving OFFSET; a cursor is a bookmark.

Where candidates lose the interview on 429 and Retry-After is usually a hidden linear scan inside a loop they already counted as constant.

429 means capacity; Retry-After (seconds or HTTP date) is the server's backoff. Immediate parallel retries amplify the overload (thundering herd).

Concretely, honor Retry-After; else exponential backoff with jitter (e.g. 200ms × 2^n ± 20%). Cap attempts. Idempotency keys on retried POSTs. Don't spin 8 workers on 429.

The reason for that specificity is a failure I have seen: Clients ignored 429 and retried at 20Hz; origin CPU 100% for 11 minutes, success rate 18%. Honoring Retry-After: 12s plus jitter restored 99% in 40s.

Retry-After: 12.

client	next try	origin
ignore, 8 parallel	0ms	100% CPU
wait 12s	12s	recovers
wait 12s ±20% jitter	9.6–14.4s	no spike

I would not consider it settled without evidence: A client test that sleeps the header value, and a load test where jitter cuts synchronized retry spikes by 70%.

429 is a schedule; Retry-After is the clock.

I would answer JWT expiry versus session store by separating what the test suite proved from what production traffic has not yet shown.

exp is a validity ceiling, not a revocation list. Stateless JWT cannot be killed early without a blocklist, short exp+refresh, or a server session store.

Concretely, access token exp=10m, refresh in a revocable store. Or jti in Redis until exp. Logout deletes the refresh row. Don't treat 7d JWT as a session you can cancel.

The reason for that specificity is a failure I have seen: A leaked 7d JWT was used for 14 hours after "logout" (no store); a jti blocklist with 10m access tokens cut the window to 8 minutes p99.

Stolen token after logout.

design	valid after logout
JWT exp=7d, no store	yes, up to 7d
JWT exp=10m + refresh row	until 10m or refresh delete
opaque session id in Redis	no, DELETE key

I would not consider it settled without evidence: Logout then replay Authorization: still 200 with long-lived JWT; 401 with session delete or jti.

exp is when it dies of old age; revocation is a store.

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.

Before reaching for a new structure I would write what a correct result for at-least-once queue consumers looks like on n = 1 and n = 10^6.

At-least-once delivery requires idempotent effects. A local unique constraint deduplicates local database work, but external effects require a transactional outbox plus a provider idempotency key or an idempotent downstream API.

Concretely, in one database transaction, insert message_id into the dedup table and enqueue an outbox row. An outbox worker sends using message_id as the provider idempotency key and records completion.

The reason for that specificity is a failure I have seen: A 12s handler with a 10s visibility timeout double-sent 6% of emails (n=80k, 14 minutes); an outbox plus provider idempotency key dropped visible duplicates while retries still happened.

Crash before ack.

crash point	outbox/provider-idempotency result
before DB commit	broker redelivers; no committed effect
after DB commit, before send	outbox retries
after send, before completion mark	provider replays same idempotent result
plain dedup row + email call	cannot guarantee exactly one email

I would not consider it settled without evidence: Two deliveries, one outbox row, one provider result for the same idempotency key.

The queue will deliver twice; the provider key makes it one effect.

The first thing I would pin down about dead-letter after retries is which input size or concurrent interleaving actually breaks the naive version.

Bound retries (e.g. 5) then move to a dead-letter queue so the hot queue keeps draining. An unbounded retry pins a worker forever.

Concretely, maxReceiveCount=5, DLQ with alarm on DLQ depth. Inspect payload, fix, replay. Do not delete silently. Backoff between attempts (1s, 4s, 16s).

The reason for that specificity is a failure I have seen: A malformed JSON retried at 50/s for 18 minutes, starved 12% of healthy messages (p99 9s); DLQ after 5 attempts restored p99 to 80ms and left 1 poison message to inspect.

maxReceiveCount=5.

attempt	dest	main queue
1–5 fail	retry	blocked if no cap
6	DLQ	draining
alarm	DLQ depth>0	page

I would not consider it settled without evidence: DLQ depth=1, main queue age=2s, retry count on the message=5.

A poison message belongs in a DLQ, not on the hot loop.

I would start CAP during a partition from the invariant the function must keep, not from the first algorithm that compiled.

During a partition you cannot guarantee both linearizable consistency and availability to every partition. An AP design accepts writes on both sides and reconciles; a quorum-fenced CP design rejects writes where it cannot prove leadership.

Concretely, name the coordination, not just the database brand. A PostgreSQL primary can keep accepting writes without consulting a majority; consistency during automated failover depends on quorum, leases, and fencing the old primary. Multi-leader or Dynamo-style designs accept split writes only with explicit conflict rules.

The reason for that specificity is a failure I have seen: A dual-writer "stay available" mode accepted 8,400 conflicting user profiles during a 4-minute partition; LWW dropped 12% of east-coast edits on merge (22 minutes of support).

4-minute partition, 2 sides.

choice	writes during	heal
CP (quorum + fencing)	side without quorum rejects writes	0 split-brain conflicts
AP (both)	8400 + 3100	merge/LWW
LWW		12% lost

I would not consider it settled without evidence: A runbook: partition → refuse writes vs accept+vector clocks, plus a count of conflicts on heal.

The partition forces a pick; "we are consistent and up" is the third option you do not have.

This is a place where a green unit test and a correct handling of N+1 query in a loop are not the same event.

N+1 is one query plus N per-parent queries; the cost is latency×(N+1), not the SQL per se. Fix with a JOIN, WHERE parent_id IN (…), or a dataloader batch.

Concretely, sELECT * FROM orders LIMIT 200; SELECT * FROM items WHERE order_id = ANY(%s). In ORMs: select_related/prefetch_related. Log statement count in tests (assert ≤ 3).

The reason for that specificity is a failure I have seen: 200 orders × 4ms RTT = 800ms+ plus 200 parses; p95 was 940ms. One IN query returned in 12ms. 14 minutes of a sale the loop held 40% of pool connections.

200 parents.

pattern	round trips	p95
for o in orders: items(o.id)	201	940ms
WHERE order_id = ANY(ids)	2	12ms
JOIN fetch	1	9ms

I would not consider it settled without evidence: django assertNumQueries(2) or a packet capture of 201 simple protocol queries.

The loop is a query planner that only knows N; SQL already had IN.

My answer to connection pool exhaustion begins at the bound: if I cannot name the complexity and the failure case, I do not have a solution.

A pool is a hard cap; checkout waits until timeout then fails. Holding a connection across a slow outbound call multiplies occupancy by wait time.

Concretely, checkout late, release before HTTP. pool_size × processes < database max_connections. Statement timeout. Never unbounded create_engine per request.

The reason for that specificity is a failure I have seen: 20 connections × 40 workers tried 800 real sockets; PG max_connections=100, 12% of requests 30s pool timeout for 16 minutes. Releasing before the HTTP call dropped occupancy to 18.

Hold across 2s HTTP, pool=20.

design	connections	21st request
hold during HTTP	20 full	wait/timeout 30s
release then HTTP	~burst	checkout ok
40 workers × 20	800 wanted	PG refused

I would not consider it settled without evidence: pg_stat_activity count vs pool timeout errors, plus a trace that the HTTP span sits inside an open checkout.

The pool is empty because you waited on the network while holding a session.