Algorithms from zero
Hashing: free-recall review
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before you open the model answer — the effort of recall is what makes hashing stick when you need it in an interview or at 2am.
Reconstruct the unit’s core mechanisms — what a hash function buys, how collisions are resolved, why the load factor governs cost, why resize is amortized O(1), and the patterns built on top — without looking back at the lessons.
- 01What does a hash function actually buy you, and what is the cost of that O(1) average lookup?
- 02What is a collision, and how does separate chaining resolve it?
- 03Define the load factor and explain why it, not the total item count, governs lookup cost.
- 04Why is hash-table insert O(1) amortized even though a single insert can be O(n)?
- 05Compare the seen pattern and the complement pattern, and give a problem each solves in one pass.
- 06When does a hash table fail to deliver O(1), and what do you do about it?
If you could reconstruct each answer from memory, you hold the unit’s spine: a hash function buys O(1) average access at the price of memory and ordering; collisions are inevitable and chaining stores them in per-bucket lists; the load factor — not raw item count — sets the average chain length and thus the cost; resize keeps it bounded at O(1) amortized; and the seen, complement, frequency, and grouping patterns are all this machinery applied. The guarantee is conditional, and a randomized hash is what defends it against untrusted input.