3.3.10 · D5Hashing
Question bank — Applications — frequency counting, two-sum problem, caching (LRU)
Vocabulary you need before answering (built from zero)
The parent note throws around notation the code assumes. This bank uses the same names, so let's earn every one of them first — with a picture — before any question uses it.
Now every symbol below is defined and pictured. Answer away.
True or false — justify
A hash map gives lookup in every case, so hashing is always the fastest option.
False — is only the average; with a bad hash or adversarial keys all keys collide into one long chain (figure s05, left), degrading to per operation (see Collision Resolution (Chaining vs Open Addressing)).
Frequency counting must always be done in two passes.
False — building the count map is one pass; a second pass is only needed when you must answer in original order (e.g. first non-repeating char). Pure counting is single-pass.
For Two-Sum, sorting the array first and using two pointers is a valid replacement.
False for the index version — sorting scrambles the original indices the problem asks for; you'd need to carry (value, index) pairs and it's still slower than the map.
In the Two-Sum map solution, the map stores keys that are values of the array.
True — we key by the number itself (
seen[x] = j) so that a complement lookup c in seen is a single hash probe (figure s02) on a value.An LRU cache can be built from a hash map alone.
False — a map has no ordering, so finding the least-recently-used key would require scanning all entries, . You need a Doubly Linked List (or ordered map) for recency (figure s01).
A singly linked list would work just as well as a doubly linked list for LRU.
False — moving an arbitrary node to the front requires its predecessor to relink (the two-arrow surgery in figure s05, right); a singly linked list must search to find
prev.In LRU, the node right behind the tail sentinel is always the eviction victim.
True — the list is ordered most-recent-at-front to least-recent-at-back (figure s01), so
tail.prev is by construction the least recently used key.Calling get(key) on an LRU cache never changes the internal ordering.
False — a successful
get counts as a use, so the node is moved to the front, updating recency; only a miss leaves order unchanged.The space cost of frequency counting is always .
False — it is where is the number of distinct keys; only in the worst case (all values distinct) does .
Using the check-then-insert order in Two-Sum is just a stylistic choice.
False — inserting before checking lets an element match itself (e.g. target 6 with a single 3), producing a wrong pair; the order enforces the invariant.
A hash table's insert is always , resize and all.
False — a single insert that triggers a resize costs to rehash every key (figure s04); it is only amortized, averaged over many inserts because doubling makes resizes rare.
A high load factor keeps the table fast.
False — a high means many items per bucket, so chains lengthen and lookups slow; tables resize precisely to pull back down.
Spot the error
count[x] = count[x] + 1 on a fresh key throws a KeyError — how do we fix the intent?
Missing keys have no stored value; use a defaulting structure (
defaultdict(int) or count.get(x, 0) + 1) so an unseen key behaves as before incrementing.Two-Sum code does seen[x] = j first, then if target - x in seen: return .... What breaks?
With
x already inserted, a value that is its own complement (target ) matches itself; the fix is to check the complement before recording x.Someone claims Two-Sum returns the pair with the smallest indices by scanning left to right. What's wrong?
It returns the first completable pair as
j advances, i.e. the pair with the smallest larger index — not necessarily the smallest pair overall; the problem only requires some valid pair.An LRU put inserts the new node but forgets to check len(map) > cap. Consequence?
The cache silently grows past capacity, so it stops being an LRU cache and never evicts — memory grows unbounded.
_remove sets n.prev.next = n.next but omits n.next.prev = n.prev. What corrupts?
The forward chain skips
n, but the backward chain still points into the removed node (only one of the two arrows in figure s05 was redrawn), so later tail.prev traversal or re-insertion reaches a stale node.LRU code deletes del self.map[lru.k] but never calls _remove(lru). What happens?
The map shrinks but the dead node stays wired in the list, so the list length and eviction order no longer match the map — the next eviction targets the wrong node.
A frequency solution uses a fixed 26-slot array for arbitrary Unicode strings. Where does it fail?
Array indexing by character code only works for a small, dense key space (like lowercase a–z); arbitrary Unicode overflows/undersizes it — a general hash map is required.
Someone picks the hash function h(key) = 0 for every key "to keep it simple". What goes wrong?
Every key lands in bucket (figure s05, left), forming one long chain, so every lookup degrades from flat to a full scan — a maximally bad hash.
Why questions
Why does Two-Sum guarantee without an explicit check?
The invariant "when we reach
j, seen holds exactly nums[0..j-1]" means any matched complement was stored at an earlier index, so its index is strictly less than j.Why do we trade memory for time in all three applications?
Each stores previously computed answers (counts, seen values, cached values) in a table so future questions become lookups (flat line, figure s03) instead of repeated scans — see Time Complexity Analysis.
Why does frequency counting beat "sort then count runs"?
Sorting costs (the curving line in figure s03); a hash map counts in a single pass because each element only needs one update, no ordering required.
Why must LRU use two sentinels (head and tail) instead of null-checking edges?
Sentinels guarantee every real node always has a non-null
prev and next (figure s01), so _remove and _add_front never branch on empty/one-element cases — the pointer surgery stays uniform .Why store value → index in Two-Sum rather than index → value?
The question we ask is "have I seen this value (the complement)?", so the value must be the key to make that lookup ; the index is the payload we want to return.
Why does the LRU hash map map to nodes rather than directly to values?
We need to both read the value and splice that entry within the list in ; storing the node gives instant access to its
prev/next pointers (figure s05, right), which a bare value could not (see Caching Strategies).Why is a second, ordered pass needed to find the first non-repeating character?
The count map loses positional order; re-scanning the original string in sequence and returning the first key with count restores the "first" requirement while keeping total work .
Why does doubling the table on resize (rather than adding a fixed number of buckets) preserve amortized ?
Doubling means a resize happens only after ~ new inserts, so its one-off cost, spread over those cheap inserts, averages to a flat constant (figure s04); a fixed-size grow would resize far more often and ruin the average.
Why does a good hash function matter for the flat promise?
Only a uniform scatter keeps every bucket's chain short (figure s05, left panel); pile-ups turn the flat lookup into a linear chain walk.
Edge cases
Two-Sum on nums = [3, 3], target 6 — does the map approach work?
Yes — at
j=1 the complement was stored at index , so it returns (0, 1); the two equal values live at distinct indices.Two-Sum where no pair exists — what should happen?
The loop finishes with no complement ever found, so it returns
None/empty; every index was checked exactly once, still .Frequency counting on an empty list — what is the result?
An empty map; the loop body never runs, and space is — a valid degenerate case that needs no special handling.
LRU cache with capacity — what does put do?
Every insert immediately exceeds capacity and evicts the just-added node, so nothing is ever retained;
get always returns the miss value.LRU put on a key that already exists — does capacity logic still fire?
The old node is removed and a fresh one re-added at front, so map size is unchanged; the
len > cap check sees no growth and correctly evicts nothing.Single-element array in Two-Sum — can it ever return a pair?
No — with only index ,
seen is empty at the sole iteration, so the complement is never found and it returns None; a pair needs two distinct indices.Frequency counting where a Sliding Window moves — must you rebuild the map each step?
No — decrement the count of the element leaving the window and increment the one entering, so each shift is instead of recounting the whole window.
Inserting into a hash table that is exactly at its load-factor threshold — what happens on the next insert?
It triggers a resize: the table doubles and rehashes every existing key into the new buckets (an event, figure s04), then places the new key — after which inserts are cheap again.
What happens to lookups if the hash table never resizes as grows?
The load factor climbs without bound, chains grow ever longer, and average lookup drifts from flat toward linear — the flat-line promise quietly breaks.