Day 23 · Numbered shelves & straight-to-the-page

Arrays & Hashing

You will be able to

Explain how dynamic arrays resize and why append is amortized O(1)
Describe the hash function → bucket → collision chain that makes dict/set O(1) average
State why dict keys must be hashable and what load factor forces a resize
Apply the three hashing patterns: frequency counting, dedupe/seen-sets, and canonical keys
Solve Two Sum, Valid Anagram, and Group Anagrams in one pass each

Today's ~120 minutes

Spaced-rep warm-up: Day 22 ladder + Week 3 due cards	10 min
ELI5 + tech read, watch the hash-buckets visualizer	20 min
Guided: build the toy hash map + three classics	40 min
Practice: two problems solo	20 min
Project: start patterns.md (Hashing section)	20 min
Quiz + flashcards	10 min

Builds on: Day 4 — Collections — lists and dicts · Day 22 — Big O & complexity

The analogy

🧸 ELI5⚙ Tech

A warehouse with numbered shelves is an array: tell the clerk "shelf 4,217" and she walks straight there — one step, no searching — because shelf positions are computed, not hunted for. But ask her "which shelf holds the red vase?" and she must walk every aisle: numbers give instant access by POSITION, and nothing by CONTENT.

Now the coat check at a theater. You hand over your coat; the attendant doesn't remember where every coat is — she runs a little rule on your ticket number ("ticket 731 → hook 31") and walks straight to the hook. That rule is a hash function: it converts the thing you're looking up into a shelf number, so content-based lookup becomes position-based lookup — straight to the page instead of reading the whole book. Occasionally two tickets map to the same hook (a collision); she hangs both coats there and checks the tags — still fast, as long as no hook gets overloaded. When the rack gets crowded, the theater installs a bigger rack and re-hangs everything (a resize). Python's dict and set are exactly this coat check, and they are the single most useful object in your interview toolkit.

Why this matters on the job

Hashing is the workhorse of practical speed: the Day 22 fix ("replace the list scan with a set") IS this lesson, and it recurs everywhere — deduplicating documents in a RAG ingest pipeline (Day 113), caching LLM responses by prompt hash (Day 156), counting token frequencies (Day 96). In interviews, "can I trade O(n) memory for O(1) lookup?" is the first question to ask of almost every array problem — roughly a third of easy/medium problems fall to a hash map. Knowing WHY it's O(1) average (and when it isn't) is what separates users from engineers.

Watch it happen

Straight to the page — how a dict finds keys in O(1)

step 1 / 7

[0]

[1]

[2]

[3]

[4]

Five empty buckets. A hash function turns any key into a number; key % 5 picks the bucket. No searching — the key COMPUTES its own address.

🎯 Predict modespeed1×

Guided practice

guided 1

Build the coat check — a toy hash map

25 min

Create hashmap_lab.py and implement the ToyHashMap from the starter skeleton: 8 buckets, each a list of (key, value) pairs (chaining).
Fill in _bucket_index, put, and get. Run the test block at the bottom — all four asserts should pass.
Add a stats() method printing each bucket's length, then insert 20 string keys and look at the distribution — roughly even is the hash function doing its job.
Sabotage: replace hash(key) with len(key) in _bucket_index and re-run stats with 20 words of similar length. Watch one bucket swell — you have manufactured the O(n) worst case and now understand it forever. Restore hash.
In a comment, answer: why must the table also store the KEY in the bucket, not just the value?

🐍 python — editable, runs in your browser

class ToyHashMap:
    def __init__(self, n_buckets=8):
        self.buckets = [[] for _ in range(n_buckets)]

def _bucket_index(self, key) -> int:
        return hash(key) % len(self.buckets)

def put(self, key, value) -> None:
        bucket = self.buckets[self._bucket_index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:                 # key exists: overwrite
                bucket[i] = (key, value)
                return
        bucket.append((key, value))      # new key: chain it

def get(self, key, default=None):
        bucket = self.buckets[self._bucket_index(key)]
        for k, v in bucket:
            if k == key:
                return v
        return default

def stats(self) -> None:
        for i, b in enumerate(self.buckets):
            print(f"bucket {i}: {len(b)} entries")

m = ToyHashMap()
m.put("ada", 1); m.put("alan", 2); m.put("ada", 3)
assert m.get("ada") == 3          # overwrite worked
assert m.get("alan") == 2
assert m.get("grace") is None
assert m.get("grace", 0) == 0
print("toy hash map: all asserts pass")

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

guided 2

The three patterns in anger

15 min

Solve the three classics in hashing_classics.py, each with a one-line pattern note before the function:

Two Sum (seen-set/complement): given nums and target, return indices of two numbers summing to target — one pass, store number → index, check for the complement BEFORE inserting.
Valid Anagram (frequency map): are two strings anagrams? Compare Counters — or two 26-slot tuples for the purist version.
Group Anagrams (canonical key): group a list of words so all anagrams share a list. Key: tuple(sorted(word)).

For each: state time and space complexity in a comment, and test with the provided cases plus one edge case you invent (empty string, duplicate numbers…).

🐍 python — editable, runs in your browser

from collections import Counter, defaultdict

# Pattern: seen-map with complements — O(n) time, O(n) space
def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}          # number -> index
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    return []

# Pattern: frequency map — O(n) time, O(1) space (26 letters)
def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

# Pattern: canonical key — O(n·k log k) time for n words of length k
def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: dict[tuple, list[str]] = defaultdict(list)
    for w in words:
        groups[tuple(sorted(w))].append(w)
    return list(groups.values())

assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 3], 6) == [0, 1]        # duplicates: why check-before-insert matters
assert is_anagram("listen", "silent") and not is_anagram("rat", "car")
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

On your own

Two on your own

20 min

No scaffolding. Solve both, stating complexity before you code:

(1) First unique character: given a string, return the index of the first character that appears exactly once, or -1. Target O(n) — two passes allowed.

(2) Longest consecutive sequence: given an unsorted list of ints, return the length of the longest run of consecutive values (e.g. [100, 4, 200, 1, 3, 2] → 4 for 1-2-3-4). Target O(n) — sorting is the O(n log n) trap.

Hints (only if stuck): for (2), put everything in a set; only start counting from numbers whose predecessor is NOT in the set — that guard is what keeps it linear.

Ship before you stop

Start the pattern log

Create patterns.md in your practice repo — the living document that carries you to Day 179. Add today's first section, "Hashing," with: (1) a three-line summary of when to reach for a hash map (need content-based lookup / counting / grouping in O(1) per item); (2) your solved classics (Two Sum, Valid Anagram, Group Anagrams, plus today's practice pair) each with a one-line "the trick was…" note; (3) the recognition cues — phrases in a problem statement that smell like hashing ("appears once", "find pairs", "group by", "seen before"); (4) the honest costs: O(n) extra space, O(1) AVERAGE not worst, keys must be immutable. Commit it. Every pattern day this phase adds a section.

Rubric — check what you completed (0/5)

patterns.md created with the Hashing section in the four-part structureAll five problems solved and runnable in the repo with complexity stated per solutionLongest-consecutive solution runs O(n) (predecessor-guard present), not sort-basedToyHashMap passes its asserts and the sabotage experiment is written up in two sentencesCommitted with a descriptive message

Common mistakes & misconceptions

Using a list as a dict key and being surprised by TypeError: unhashable. Mutable objects can't promise a stable hash; convert to tuple (or frozenset) first.
Calling dict lookup O(1) unconditionally. It is O(1) average; collisions make it O(n) worst-case — the sabotage step showed you exactly how.
Solving Two Sum by inserting first, then checking — which matches a number with itself. Check for the complement before inserting the current number.
Reaching for sorting when a frequency map answers in O(n). "Compare compositions" (anagrams) needs counts, not order.
Forgetting that insert(0, x) and pop(0) on a list shift every element — O(n). If you need cheap operations at both ends, that is tomorrow's deque.
Choosing a canonical key that isn't canonical: "".join(set(word)) loses counts and order — "aab" and "ab" collide. sorted-tuple or count-tuple, nothing cleverer.

Knowledge check

Q1. Why is looking up a key in a dict O(1) on average, regardless of size?

Q2. my_dict[[1, 2]] = "x" raises TypeError. Why?

Q3. Best canonical key to group anagrams under one dict entry?

Go deeper — curated resources

toolVisuAlgo — hash table visualization (collisions & resizing live) ↗15 min bookOpenDSA — hashing chapter ↗25 min courseNeetCode Roadmap — Arrays & Hashing section ↗20 min

If you have a third hour

Python dict internals: compact dicts & insertion order — Since 3.7, dicts preserve insertion order via a compact two-array layout. Skim how the entries array + sparse index table work — it explains both the ordering guarantee and the memory win.

Done means

ToyHashMap works, sabotage experiment observed and explained
Five classics solved with stated complexities; longest-consecutive is O(n)
patterns.md committed with the Hashing section
Quiz ≥ 2/3

How this connects

← Back: Day 4 taught you to USE dict and set; today you know why they are fast and when they are not. Day 22's "swap the list scan for a set" now has a mechanism behind it.

Forward →: Tomorrow's sliding window pairs with a hash map for its hardest problems. The hash-as-address idea returns as cache keys on Day 156 and — transformed into geometry — as the "meaning-based index" of vector databases on Day 115.

Unlocks: D24 Two Pointers & Sliding Window · D25 Stacks & Queues · D28 Week 4 Checkpoint: Pattern Drill · D30 Heaps, Priority Queues & Tries