Hidden Assumptions Hunt

Overview

Every algorithm you memorized and every system guarantee you quote comes with a list of preconditions that nobody states out loud. Binary search assumes sorted input, a total order, and an overflow-safe midpoint. Big-O assumes a machine where every memory access costs the same. A “cached” value assumes the world did not change underneath it. This collection takes common textbook rules, makes their hidden assumptions explicit, breaks each one with a concrete counterexample, and rebuilds a corrected statement that survives contact with production.

The framing matters because interviews and incidents rarely punish you for knowing a rule; they punish you for not knowing when the rule stops applying. A candidate who says “binary search is O(log n)” is fine. A candidate who says “binary search is O(log n) comparisons, provided the array is sorted under a strict weak order and the midpoint computation cannot overflow — which the JDK got wrong for nine years” is demonstrating a different level of understanding. That second sentence is the product of this collection’s method. The collection currently audits forty assumption families, from binary-search preconditions to service-registry staleness; the File Inventory below is the authoritative list.

Why Textbook Rules Break at Boundaries

Textbooks optimize for clarity of the core idea, so they study the interior of the design space: sorted arrays, well-behaved hash functions, balanced workloads, infinite memory, single-threaded execution, reliable networks. Production lives at the boundaries: adversarial inputs, sizes that cross integer limits, concurrent access, data that does not fit in RAM, networks that partition, clocks that drift. The rule itself was never false — it was conditional, and the conditions were unstated.

Three forces consistently create the gap:

1. Idealized cost models. The RAM model charges one unit per memory access, so O(1) array access and O(1) hash lookup look equivalent. Real hardware has caches, TLBs, page faults, and NUMA, so the constants differ by orders of magnitude and sometimes the asymptotics themselves change (external-memory algorithms).
2. Idealized semantics. “The midpoint of low and high” is mathematically (low + high) / 2. In 32-bit arithmetic that expression overflows. The algorithm is correct; the translation into a bounded type is not. Textbooks reason in integers; languages hand you fixed-width types.
3. Idealized environments. “The cache returns the current value” assumes no concurrent writer. “The network delivers the request” assumes no partition. “REPEATABLE READ means the same thing everywhere” assumes the SQL standard was implemented identically — it was not, and the divergence between MySQL and PostgreSQL is documented in both vendors’ manuals.

None of this makes the textbooks wrong. It makes them incomplete, and the missing parts are exactly what senior interviews probe.

The Method Used in Every Chapter

Each chapter follows the same five-step pattern, applied to a specific family of assumptions. When you read or recall any chapter, you should be able to reconstruct it from this skeleton:

1. The taught rule. Stated fairly, the way a textbook or a lecture would state it. No strawmen — the rule is genuinely correct under its intended conditions.
2. The hidden assumptions. An explicit list of the preconditions the rule silently relies on, with a note on why each one is usually invisible (usually because it holds in the demo, the unit test, and the classroom example).
3. Counterexample / boundary case. A concrete input, timing, or environment where the rule fails. Every counterexample in this collection is real and checkable — no invented pathology. Where a claim is subtle (integer overflow points, isolation-level behavior, memory-model guarantees), the numbers and quotes were verified against primary sources: the C11 standard draft, the JLS, the Go memory model, PostgreSQL and MySQL manuals, and the original engineering posts.
4. What changes when the assumption is removed. The corrected statement — the same rule, restated with its preconditions explicit, plus the standard defenses (safer idiom, alternative algorithm, explicit contract).
5. Practical consequences and interview implications. Where this shows up in code review, incidents, and interview questions, including the follow-up questions that separate memorized answers from understood ones.

Worked micro-example, so the pattern is visible before you dive in:

• Taught rule: “Binary search runs in O(log n) time.”
• Hidden assumptions: the array is sorted; the comparison is a total (strict weak) order; indices fit in the index type; the midpoint expression cannot overflow.
• Counterexample: Joshua Bloch’s 2006 Google Research post documented that int mid = (low + high) / 2 throws ArrayIndexOutOfBoundsException once the sum of low and high exceeds 2^31 - 1, which is reachable for arrays of roughly 2^30 elements or more. The bug sat in the JDK for about nine years.
• Corrected statement: “Binary search performs O(log n) comparisons and O(log n) index computations, provided the input is sorted under the comparator’s order and index arithmetic is overflow-safe, e.g. mid = low + (high - low) / 2.”
• Consequences: in interviews, this is the canonical “your trivial code has a bug” probe; in practice, it is a template for auditing every arithmetic expression that aggregates sizes, counts, or timestamps.

How This Differs From the Sibling Projects

The research projects share a subject pool but not an angle. Use this directory when the question is “what precondition was silently assumed?”; use the others when the question is different:

• Misconceptions targets claims that are false as stated (for example, “hash lookup is always O(1)”). Here, the rules are true as stated — the failure is in the unstated conditions.
• Why-Not Handbook explains why you would choose mechanism A over mechanism B. Here we are not choosing; we are auditing the chosen mechanism’s fine print.
• Follow-up Tree escalates a question into the depth an interviewer adds, layer by layer. The assumptions here are the material those follow-ups are made of.
• Failure Casebook documents named incidents with timelines and primary sources. When an assumption failure has a famous incident behind it, the chapter links to the casebook instead of retelling the story.
• Connection Atlas maps dependencies between topics. The assumptions collection is frequently the reason an edge exists in that graph (for example, isolation-level semantics depending on the concurrency-control mechanism).

If you find the same concept in two projects, the treatment is deliberately different rather than duplicated. Hash tables, for instance, appear in all five projects from five angles: escalation chain (followup), adversarial hashing (this project’s complexity claims), versus binary search (why-not), the O(1) claim (misconceptions), and as database index structure (atlas).

File Inventory

Coverage Ledger

Status per file, the primary sources each relies on, and known gaps. Primary sources marked “verified” were fetched and checked (HTTP 200 plus content inspection) during writing; factual claims from them are quoted or closely paraphrased in the chapters.

Ledger maintenance rule: when a gap is closed, update this table in the same change so status never outruns content.

Interview Questions

1. Why do hidden assumptions matter more in system design interviews than in coding interviews? In coding interviews the constraints are printed in the problem statement (sizes, ranges, sortedness); the assumptions are handed to you. In system design they are not — the interviewer’s follow-ups (“what if the cache goes stale?”, “what if the network partitions?”) are precisely asking you to name and handle assumptions you never wrote down. Candidates who volunteer assumptions preempt half the follow-ups.
2. Give an example where the algorithm was correct but the implementation still failed. Binary search: Bentley proved the algorithm correct, yet the JDK implementation overflowed the midpoint computation for arrays near 2^30 elements, throwing ArrayIndexOutOfBoundsException after roughly nine years in production. The gap was between the mathematical integers of the proof and the fixed-width integers of the machine.
3. How do you systematically find hidden assumptions in your own code? Ask for each quantity: what are its bounds, and what happens at them (empty, one element, maximum, zero, negative)? For each operation: what interleaving would break it? For each external dependency: what does it promise (delivery, ordering, consistency, timing), and what does it merely usually do? Then test the boundaries deliberately rather than incidentally.
4. What is the difference between a misconception and a hidden assumption? A misconception is false as stated (“SELECT never blocks”). A hidden assumption is a true rule plus unstated preconditions (“binary search is O(log n) — if the input is sorted and the midpoint is overflow-safe”). Misconceptions get corrected by denial; assumptions get corrected by completing the sentence.
5. Which hidden assumption has caused the most expensive real-world failures in this collection? Strong candidates: uninitialized memory reads (security-relevant data leaks), lost updates from ORM read-modify-write cycles (financial data corruption), and the “retrying is safe” assumption (duplicate charges and amplified outages). All three are cheap to prevent and expensive to discover in production.

Key Takeaways

• A rule and its preconditions are inseparable; learning the rule without the preconditions is learning half of it.
• Boundary behavior — empty input, maximum input, concurrent access, degraded network — is where textbook rules and production behavior diverge, and it is exactly where interviewers and incidents probe.
• The five-step pattern (taught rule, hidden assumptions, counterexample, corrected statement, consequences) turns any memorized fact into an auditable claim.
• Every counterexample in this collection is real and source-backed; treat the primary sources cited in each chapter as part of the material, not decoration.
• Stating assumptions out loud is the cheapest performance improvement available in an interview: it converts unknown-unknowns into answered follow-ups.

Cross-References

• Misconceptions project — claims that are false as stated, the complement of hidden assumptions.
• Why-Not Handbook — mechanism-level comparisons that rest on the assumptions audited here.
• Follow-up Tree — interview escalation chains built from these boundary cases.
• Failure Casebook — named incidents where one of these assumptions failed in production.
• Connection Atlas — dependency graph between topics, with assumptions as the edges.
• Complexity claims — the RAM-model assumptions behind big-O, audited in depth.
• Memory model — the assumptions about memory and language semantics that underlie every systems claim.