This page is a stress test . We take the three tools from the parent note —
frequency counting, Two-Sum -style complement lookups, and the LRU cache —
and throw every awkward input at them: empty lists, duplicates, negatives, self-pairs, "no
answer exists", a cache that is full, a cache of capacity zero, and an exam-style twist. If you can
follow every cell below, no interviewer input can surprise you.
Intuition How to read this pageBefore each solution there is a Forecast: line. Cover the steps with your hand and guess the
answer first . Learning happens in the gap between your guess and the truth — that is the whole
point of a scenario matrix.
Every problem in this topic is really one of the cells below. A "cell" is a class of input that
behaves differently from the others — so if we solve one example per cell, we have solved the whole
topic.
#
Tool
Case class
What makes it special
C1
Frequency
Normal input, repeats
The everyday histogram
C2
Frequency
Empty / single input (degenerate)Loop runs 0 or 1 times
C3
Frequency
Order matters (first-unique)
Needs a second pass
C4
Two-Sum
Answer exists early
Complement found before scan ends
C5
Two-Sum
No answer existsMust return "nothing" cleanly
C6
Two-Sum
Negatives + duplicates Complement can be negative / equal to x
C7
Two-Sum
Self-pair trap (target = 2x)Must not use one element twice
C8
LRU
Fill, touch, evict
The classic recency dance
C9
LRU
Capacity = 1 / 0 (limiting)Edge of the definition
C10
LRU + Two-Sum
Real-world word problem / exam twist
Combine two tools
Below, ten worked examples cover all ten cells .
Cell C1 — Normal repeats: count "mississippi"
Count how many times each letter appears in mississippi.
Forecast: how many s? how many i? (Guess before reading.)
Start with an empty map count = {}.
Why this step? A missing key means "seen zero times"; we default to 0 before adding 1.Walk once, left to right , doing count[ch] += 1.
Why this step? One pass is O ( n ) m i s s i s s i p p i.Read off the totals : m:1, i:4, s:4, p:2.
Why this step? Each key's value is just how many times we hit += 1 for it.
Verify: sum of counts = 1 + 4 + 4 + 2 = 11 mississippi has 11 letters. Nothing was
lost or double-counted, so the map is correct.
Cell C2 — Degenerate: empty list and single element
Build a frequency map for (a) [] and (b) ["x"].
Forecast: what does the map look like for an empty input? Will the code crash?
Case (a), the empty list. The loop for ch in [] runs zero times .
Why this step? We must confirm the degenerate case never touches the map, so it stays {}.
No crash — an empty loop is perfectly legal.Case (b), one element. Loop runs once : count["x"] defaults 0, becomes 1.
Why this step? The single-element case is the boundary between "empty" and "many"; it proves
the += 1 logic works even with no repeats.Result: (a) {}, (b) {"x":1}.
Verify: count sum for (a) = 0 = []. For (b) = 1 = ["x"]. ✓
Cell C3 — Order matters: first non-repeating character of "aabbcde"
Return the first character that appears exactly once.
Forecast: which letter? (Careful — it is not the first letter.)
Pass 1 — build totals (order does not matter here):
a:2, b:2, c:1, d:1, e:1.
Why this step? We cannot know a letter is "non-repeating" until we have seen the whole
string, so totals must be complete first.Pass 2 — re-scan in the ORIGINAL order a,a,b,b,c,... and return the first char whose
count is 1.
Why this step? The map has no order; the string does. Re-scanning restores "first".a→2 (skip), a→2, b→2, b→2, c→1 → return c .
Verify: c is at index 4. Its count in the map is 1, and every character before it
(a,b) has count > 1 O ( n ) + O ( n ) = O ( n )
Cell C4 — Answer found early: nums = [4, 3, 5, 2], target = 7
Return indices i, j with nums[i]+nums[j]=7.
Forecast: which two indices? At what step does the scan stop?
seen = {}j. At each step compute complement c = 7 - x.
Why this step? Instead of asking "what pairs with what?", we ask the map "have I already
passed the value I need?" — an O ( 1 ) j=0, x=4: c=3. Is 3 in {}? No. Store seen={4:0}.
Why store after checking? So x can never pair with itself (Cell C7 shows the danger).j=1, x=3: c=4. Is 4 in {4:0}? Yes , at index 0 → return (0, 1).
Why this step? The invariant guarantees seen holds only indices < j, so i=0 ≠ j=1.
Verify: nums[0]+nums[1] = 4+3 = 7 = target. ✓ Indices differ. We stopped at j=1,
never touching indices 2–3.
Cell C5 — No answer exists: nums = [1, 2, 3], target = 100
Return a pair summing to 100, or None if impossible.
Forecast: what should the function return?
j=0,x=1: c=99, not in {}, store {1:0}.j=1,x=2: c=98, not in {1:0}, store {1:0,2:1}.j=2,x=3: c=97, not in {1:0,2:1}, store {1:0,2:1,3:2}.
Why this step? Every complement is larger than any value present — no match can ever occur.Loop ends with no return → function returns NoneWhy this step? "No pair" is a real case; the code must fall off the loop cleanly, not crash.
Verify: the largest possible sum is 2 + 3 = 5 < 100 None is correct. ✓
Cell C6 — Negatives + duplicates: nums = [-3, 4, 3, 90], target = 0
The complement itself is negative, and a value repeats in spirit (-3 and 3).
Forecast: which indices sum to 0?
j=0,x=-3: c = 0-(-3) = 3. Is 3 in {}? No. Store {-3:0}.
Why this step? Shows the map handles negative keys with zero special-casing — hashing
doesn't care about sign.j=1,x=4: c=-4, not present, store {-3:0, 4:1}.j=2,x=3: c = 0-3 = -3. Is -3 in the map? Yes , at index 0 → return (0, 2).
Why this step? The complement -3 was a negative value already stored — proof the trick
works across signs.
Verify: nums[0]+nums[2] = -3+3 = 0 = target. ✓
Cell C7 — Self-pair trap: nums = [3, 3], target = 6
Here target = 2 × 3, so a naive "store first" would match index 0 with itself.
Forecast: correct answer (0,1) or the wrong (0,0)?
j=0,x=3: c = 6-3 = 3. Is 3 in {}? No (map still empty). Store {3:0}.
Why this step? Because we checked before storing , index 0 cannot see itself. This is the
entire reason for the "store after check" order.j=1,x=3: c=3. Is 3 in {3:0}? Yes , at index 0 → return (0, 1).
Why this step? Now two different elements both equal 3 legitimately pair up.
Verify: indices 0 ≠ 1, and nums[0]+nums[1]=3+3=6=target. ✓ Contrast: storing before
checking would have returned (0,0) — using one element twice, which is illegal.
Common mistake The order is the whole gameIn Two-Sum, check the complement, THEN insert x . Reverse it and Cell C7 breaks. This single
line ordering is what makes the invariant "seen = elements strictly to the left" true.
Cell C8 — Fill, touch, evict: capacity = 2
Run: put(1,A), put(2,B), get(1), put(3,C), get(2), get(3).
Forecast: which key gets evicted, and what does get(2) return afterwards?
put(1,A): list 1, map {1}. Most recent = front. put(2,B): list 2,1, map {1,2}. Why? New keys go to the front (most recent side).get(1)→A: we remove then add-front node 1 → list 1,2.
Why this step? Accessing a key makes it the newest ; this is what "recently used" means.put(3,C): add 3 at front → list 3,1,2, but size 3 > cap 2. Evict tail.prev = 2 .
Why this step? The node just before the tail sentinel is by construction the least
recently used — the correct victim.get(2)→ -1 (evicted), get(3)→C (present, now front).
Verify: After step 3, key 1 was newest, so 2 sat at the back and was evicted in step 4.
get(2)=-1 and get(3)=C confirm the final map is {1,3}. ✓
Cell C9 — Limiting capacity: cap = 1, and the cap = 0 edge
(a) cap = 1: run put(1,A), put(2,B), get(1), get(2).
(b) cap = 0: run put(5,X), get(5).
Forecast: with cap 1, does key 1 survive put(2,B)?
(a) put(1,A): list 1, map {1}.put(2,B): add front → 2,1, size 2 > 1. Evict back = 1 . List 2, map {2}.
Why this step? A cache of size 1 can hold only the newest key; every put evicts the old.get(1) → -1 (gone), get(2) → B.(b) cap = 0: put(5,X) adds the node, size 1 > 0, immediately evicts it. Map empty.
Why this step? Capacity 0 means "cache nothing"; the eviction check fires on every put.get(5) → -1.
Verify: (a) final map {2}, so get(1)=-1, get(2)=B. (b) final map {}, so get(5)=-1.
Both edges behave without crashing — the len(map) > cap guard handles cap 0 and cap 1
identically. ✓
Cell C10 — Exam twist: "recently-seen sum" over a stream
A checkout terminal streams prices [5, 5, 10, 5]. Using a frequency map , answer two things
after the stream ends: (i) which price is most frequent, and (ii) using Two-Sum on the
distinct prices [5, 10], is there a pair summing to 15?
Forecast: most frequent price? Does a distinct pair sum to 15?
Frequency pass over [5,5,10,5]: {5:3, 10:1}.
Why this step? One pass turns the raw stream into counts — the histogram tool (Cell C1).Most frequent = key with the largest count = 5 (count 3).
Why this step? A single scan of the small map's values picks the max — O ( k ) Two-Sum on distinct prices [5,10], target 15 : j=0,x=5, c=10 not in {}, store {5:0}.
j=1,x=10, c=5, in {5:0} → return (0,1).
Why this step? The distinct-keys list feeds straight into the complement trick (Cell C4).
Verify: count sum 3 + 1 = 4 = 5 appears 3× vs 10's 1× ✓.
Distinct pair 5+10 = 15 = target at indices (0,1) ✓. Two independent hashing tools chained,
each O ( n ) Time Complexity Analysis ).
Recall Self-test (cover the answers)Which cell has the empty-input frequency map? ::: C2 — the loop runs zero times, map stays {}.
In Two-Sum, why store the value after checking the complement? ::: To stop an element pairing with itself (Cell C7, [3,3], target 6).
With LRU capacity 2, after put(1),put(2),get(1),put(3) — who is evicted? ::: Key 2, because get(1) made 1 the most-recent, leaving 2 at the back.
What does Two-Sum return when no pair exists? ::: None — the loop ends without a match (Cell C5).
Why does LRU need a Doubly Linked List not a singly linked one? ::: A doubly linked node stores prev, so unlinking is O ( 1 ) O ( n )
Mnemonic The scenario checklistE-D-N-S for any hashing problem: E mpty input, D uplicates/negatives, N o-answer
case, S elf-pair / eviction edge. Test all four and nothing surprises you.
Related: Hash Functions · Collision Resolution (Chaining vs Open Addressing) ·
Sliding Window · Caching Strategies .
