Why-Not Handbook

Overview

Most engineering material explains why an approach works. This handbook answers the opposite, harder question: why not the alternative? Each page takes a pair — or a small set — of options that interviewers, code reviewers, and designers routinely contrast (BFS vs DFS, hashing vs binary search, mutex vs semaphore, B-tree vs LSM, caching vs recomputation) and explains the mechanism behind each option deeply enough that the trade-offs fall out as consequences rather than memorized slogans.

The collection deliberately overlaps with the Trade-offs section, which stores quick-reference comparison tables. There, a one-line table row says “hash: O(1) average, no ordering”. Here, the same comparison is re-derived from first principles: how the hash bucket is probed, what the cache does to that probe, what happens under adversarial keys, and the specific workloads where the binary search that “loses” on paper is the correct engineering answer. If you want a fast answer, read trade-offs; if you want to defend that answer under three rounds of “why?”, read here.

The Six-Step Meta-Framework

Every page in this handbook applies the same six steps, in the same order. The order is the point: each step narrows the space so the final recommendation is a consequence of evidence, not taste.

1. Define the problem and its constraints. A comparison without a workload is a slogan. Before comparing, the pages pin down: what the input looks like (size, distribution, mutation rate), what guarantees the caller needs (exact vs approximate, ordering, freshness, worst-case bounds), and what resources are fixed (memory budget, latency budget, hardware). Binary search vs hashing is undecidable until someone says whether range queries are needed and whether keys are adversarial.
2. Explain the mechanism of each option. Not “hash tables are O(1)” but why: hash the key, index into a bucket array, resolve collisions by chaining or probing, resize when load factor exceeds a threshold. Mechanism-level explanations expose the constants, the memory behavior, and the failure modes that asymptotic notation hides. Two operations with the same big-O can differ by 50× in practice, and the mechanism tells you which one.
3. State complexity, guarantees, and failure modes. For each option: worst-case, average-case, and amortized complexity where they differ; the formal guarantees it gives (ordering, stability, linearizability, bounded latency); and the characteristic ways it breaks (rehash storms, deadlocks, frontier blowups, write skew). Guarantees are contracts — the pages state exactly which contract each option signs.
4. Name the conditions where each option wins. Not a generic ranking, but explicit trigger conditions: “DFS wins when the graph is deep and memory is bounded”, “LSM wins when write throughput dominates and reads tolerate milliseconds of staleness”. Every option in every page is the right choice somewhere — the handbook has no strawmen.
5. Find the edge cases and counterexamples. This is where most material stops and this handbook starts. Each page includes at least one non-obvious case where the “obvious” choice fails: BFS frontier blowup on lattice graphs, hash-flooding attacks, lost wakeups in condition variables, write skew under snapshot isolation, cache stampedes after an invalidation. These cases are what interviewers use to separate rote answers from real understanding.
6. Write the decision framework. Each page ends with a table or ordered checklist mapping workload properties to a choice. The framework is falsifiable: if your workload matches the left column, the right column is the recommendation — and the page has already told you what you are giving up.

The framework generalizes beyond the forty comparisons here. When you meet a fresh “X vs Y” question, running these six steps produces an answer that is specific to your constraints and honest about costs.

File Inventory

Coverage Ledger

The same concepts appear across several research projects from deliberately different angles — the coverage plan requires linking, not re-explaining. The ledger below records which angle each project takes so you know where to go next. (Paths are relative to pages in this directory.)

Duplication boundary (from the project plan): trade-offs pages hold the scannable tables; this handbook holds mechanisms, complexity derivations, guarantees, and edge cases. If you find yourself copying a table between the two, link instead.

How to Use This in an Interview

A strong “why not X?” answer has three moves. First, name the mechanism of the rejected option (“a hash table probes one bucket after computing a hash”). Second, state the guarantee you actually need (“I need predecessor queries and ordered iteration”). Third, conclude conditionally, not absolutely (“so for this workload the hash table cannot substitute; for pure point lookups it would be faster”). Pages here give you all three moves pre-assembled, plus the edge case that turns a good answer into a memorable one.

Interview Questions

1. Why does the handbook insist on mechanisms before trade-offs? Because every trade-off line item (“O(1) average”, “stable”, “no ordering”) is a consequence of a mechanism. Deriving consequences from mechanisms lets you answer variants you never memorized — new workload, new failure mode, new hardware — while a memorized table breaks the moment the question changes.
2. What does “conditions where each wins” prevent? Strawman comparisons. If your explanation of an option cannot name a workload where it is the best choice, you do not understand the option — you have only memorized its weaknesses.
3. Give an example of an edge case changing the default choice. On paper, hashing beats binary search for lookups. Under adversarial keys and a known hash function, an attacker forces every key into one bucket and turns O(1) into O(n) — a denial of service. Hardened hash functions (keyed seeds, SipHash) restore the guarantee; alternatively, a sorted array plus binary search gives a hard O(log n) that no input can break. The workload detail — are keys attacker-controlled? — flips the decision.
4. What belongs in a decision framework that does not belong in a trade-off table? An ordering. A table lists dimensions; a framework says which question to ask first (“Do you need ordering? If yes, the hash family is out regardless of everything else”). Ordered checklists mirror how real designs narrow down.
5. How do the coverage boundaries keep the book maintainable? Same concept, different angles, explicit links. The Why-Not Handbook derives from mechanisms; trade-offs summarizes; Follow-up Tree escalates through interview question chains; Misconceptions attacks false claims. A reader landing on any page gets pointers to the others instead of duplicated prose.

Key Takeaways

• Every comparison here runs the same six steps: constraints → mechanisms → complexity/guarantees/failure modes → winning conditions → edge cases → decision framework. The order matters; the last step is a consequence of the first five.
• Mechanisms expose what asymptotic notation hides: cache behavior, constants, amortization spikes, and the exact contract each data structure or system signs.
• No option is a strawman. Each page states the explicit conditions under which the “losing” option is the correct engineering choice.
• Edge cases — adversarial inputs, frontier blowups, write skew, stampedes — are where defaults fail and where interview depth is proven.
• This collection complements, and links to, the quick-reference tables in Trade-offs rather than duplicating them.

Cross-References

• Engineering Trade-offs — the quick-reference comparison tables this handbook goes deeper than.
• Database Trade-offs — high-level SQL/NoSQL, consistency, and indexing tables referenced by the database pages here.
• DSA — the main DSA track whose chapters (sorting, hashing, graphs) provide the tutorial-level background for the mechanism discussions here.
• Follow-up Tree — question-escalation chains for concepts compared in these pages.
• Assumptions Hunt — the hidden assumptions behind the complexity claims this handbook quotes.
• Connection Atlas — dependency-web view of the same database concepts.
• Misconceptions — the false beliefs this handbook’s edge cases are designed to disarm.