Hashing, Sets & Recursion

This first block shows the one idea hashing is built on: a hash function takes any key (a word, a number, a tuple) and turns it into an integer. Once you have an integer, you can turn it into an array slot number — and jumping straight to a known array slot is instant (that's the O(1) you keep hearing about).

1. hash("checkout-api") feeds a string into Python's built-in hash function and gets back a big integer. For strings the number changes each time you start Python (a security feature), but within one run it's stable.
2. hash(42) returns 42: small whole numbers just hash to themselves. hash((1, 2)) works because a tuple is immutable (it can never change), so its hash is safe to rely on.
3. The commented-out hash([1, 2]) would raise TypeError: unhashable type: 'list'. A list can change, so its hash could change too — Python forbids using it as a key.
4. The last three lines are the whole trick: slot = hash(key) % size. The % (remainder) squeezes any giant hash integer down into the range 0 .. size-1, i.e. a valid index into an array of that size.

What the output means: For each of "a", "b", "c" you get a line like a -> slot 5 — the array position where that key's value would live. Different keys usually land in different slots.

Try this: Change size from 8 to 4 and re-run: the slot numbers shrink (0–3) and you're more likely to see two keys share a slot — that shared-slot situation is a collision, the topic of §3.

Here you build a working dictionary from scratch using chaining. This is the exact machinery inside Python's dict, shown in ~25 lines. Follow how a key becomes a slot, and how the class keeps buckets short as it grows.

1. __init__ creates self._buckets as a list of empty lists — one empty bucket per slot — and self._n, a running count of how many items are stored.
2. _slot(key) is the hash-to-index step from §1: hash(key) % len(self._buckets) gives the slot number for any key.
3. put finds the right bucket, then loops through it. If the key is already there it overwrites the value (a dict has no duplicate keys); otherwise it appends a new (key, value) pair and bumps the count.
4. get hashes to the same slot and scans just that one short bucket for the key — checking a few entries, not the whole table. That's why lookup is fast on average.
5. The load factor check self._n / len(self._buckets) > 0.75 watches how full the table is. When buckets start getting crowded it calls _resize, which doubles the number of slots and re-inserts (rehashes) every existing pair so buckets stay short again.

What the output means: print(m.get("weather")) prints fn — the value you stored under "weather", fetched by hashing straight to its slot rather than scanning.

Try this: After the puts, add print(m.get("missing")). Because get has default=None, an unknown key returns None instead of crashing — the same behaviour as dict.get.

This is the open-addressing table in code — the diagram above turned into a class. Watch the while loop: that's the probing (walking to the next slot) you saw in the picture.

1. _EMPTY = object() makes a unique sentinel — a one-of-a-kind marker meaning "this slot was never used". Using a special object (not None) means None is still allowed as a real stored value.
2. Two parallel arrays hold the data: self._keys (starts all _EMPTY) and self._vals. Slot i's key is _keys[i] and its value is _vals[i].
3. In put, i = hash(key) % len(self._keys) is the starting slot. The while loop advances i = (i + 1) % len(self._keys) while the slot is occupied by a different key — that's the linear probe, wrapping with %. It stops on an empty slot (new key) or on a matching key (update).
4. get repeats the same walk from the hashed slot, comparing keys, and returns the value when it matches. If it reaches an _EMPTY slot the key was never inserted, so it returns default.

What the output means: This lab defines the class only (no prints). Create one and try it: mp = OpenAddrMap(); mp.put("x", 1); print(mp.get("x")) prints 1.

Try this: Insert several keys that collide, then print(mp._keys) to see how probing tucked them into nearby slots of the same array — no bucket lists anywhere.

Now the payoff: Python's everyday set and dict are just hash tables like the ones you built. This block shows the O(1) powers you get for free.

1. A set stores only keys. Adding "docA" twice keeps just one copy, so len(seen) is 1 — automatic dedup. "docA" in seen is a hash lookup (O(1)), not a scan through every element.
2. Set algebra: a & b is intersection (in both), a | b is union (in either), a - b is difference (in a only). Each runs in time proportional to the set sizes, not the product — far cheaper than nested loops.
3. A dict maps key→value. dispatch["scale"] hashes the key and jumps straight to its slot (O(1)). Since Python 3.7 a dict also remembers insertion order, so iterating gives keys back in the order you added them.

What the output means: Prints 1, then True, then {2, 3} {1, 2, 3, 4} {1}, then fn2 — dedup, fast membership, set algebra, and keyed lookup, all backed by hashing.

Try this: Swap the set for a list: seen = [] and use seen.append(...). Now "docA" in seen must scan the list (O(n)) and duplicates are kept — showing exactly what the hash-based set buys you.

These are the four hashing patterns you'll reach for constantly. Each one uses a set or dict to replace slow "search everything again" work with instant O(1) lookups.

1. 1 · Dedup keeping order: a set named seen answers "have I met this before?" in O(1), while a list named unique records first-seen order. You get uniqueness and original order.
2. 2 · Frequency count: Counter(nums) walks the list once and tallies how many times each value appears — a dict of counts built in O(n). most_common(1) returns the top entry.
3. 3 · Group by a key: defaultdict(list) auto-creates an empty list the first time a new key is used, so by_letter[w[0]].append(w) groups words by their first letter with no "if key missing" boilerplate.
4. 4 · Two-sum in O(n): the dict pos remembers each value's index as you go. For each x you ask "have I already seen target - x?" — an O(1) check that turns a brute-force O(n²) search into a single O(n) pass.

What the output means: No prints except freq.most_common(1) → [(3, 3)] (the value 3 appears 3 times). The comments show each result: unique is [3, 1, 2], the grouping is {'a': [...], 'b': [...]}.

Try this: Memorize the pattern-4 question: "can a hash map remember what I've seen so the inner search becomes O(1)?" It's the single most useful speed-up in coding interviews.

Two recursive functions. Every recursion has the same two ingredients: a base case (the trivial input answered directly) and a recursive case (reduce to a smaller version of the same problem and call yourself).

1. In factorial, the base case is if n <= 1: return 1 — it stops the chain of calls. Without it the function would call itself forever.
2. The recursive case return n * factorial(n - 1) is the same problem on a smaller input (n - 1). Because each call shrinks n, it must eventually hit the base case — matching the push-down/pop-up staircase in the diagram above.
3. flatten shows why recursion suits nested data. For each item, if it's a list it recurses into it with yield from flatten(x) (dig one level deeper); otherwise it yields the plain value. This handles nesting of any depth with no idea how deep it goes.
4. yield/yield from make these generators — they hand back values one at a time, which is why list(...) is used to collect them all.

What the output means: list(flatten([1, [2, [3, 4]], 5])) prints [1, 2, 3, 4, 5] — every nested value pulled out into one flat list, regardless of how deeply it was buried.

Try this: Call factorial(4) and trace it: 4 * 3 * 2 * 1 = 24. Then remove the if n <= 1 base case and call it — Python will raise RecursionError once the stack overflows.

Three ways to compute Fibonacci, from disastrously slow to fast. This is the diagram above turned into code and shows the leap from plain recursion to dynamic programming.

1. 1 · Naive fib_slow is the left tree: it re-derives fib(n-1) and fib(n-2) from scratch every time, so the work doubles at each level — O(2ⁿ). fib_slow(35) already crawls.
2. 2 · Memoized fib_memo is identical except for the @lru_cache(maxsize=None) decorator on top. That cache is a hash map that remembers each fib(k): the second time a value is needed it's an O(1) lookup, collapsing the cost to O(n).
3. 3 · Bottom-up DP fib_dp drops recursion entirely. It keeps just the last two numbers in a, b and rolls forward with a, b = b, a + b — O(n) time and only O(1) memory (no stack, no cache).
4. The single-line swap a, b = b, a + b updates both variables at once from their old values — a clean Python idiom for stepping a sequence forward.

What the output means: print(fib_memo(100)) returns instantly (354224848179261915075). fib_slow(100) would effectively never finish — the same answer, wildly different cost.

Try this: Add @lru_cache(maxsize=None) above fib_slow too and watch it become instant. That one line — caching subproblem results — is the entire idea of dynamic programming.

This is the backtracking skeleton in code — the choice tree above made real. It generates every ordering of a list. Learn this choose / explore / un-choose shape; it solves a whole family of "generate all" problems.

1. Three pieces of shared state: result collects finished answers, used tracks which items are already placed, and path is the arrangement being built right now.
2. The inner backtrack() checks the base case first: when len(path) == len(items), the path is a complete arrangement, so it saves a copy path[:] (a copy, because path keeps changing) and returns.
3. Otherwise it loops over every item, skipping ones already used. The three commented lines are the pattern: choose (mark used, append to path), explore (recurse), un-choose (pop and un-mark to restore state before trying the next sibling).
4. That path.pop(); used[i] = False undo is what makes it backtracking — it rewinds one step so the next loop iteration explores a different branch of the tree.

What the output means: permutations(["a", "b", "c"]) returns all 6 orderings: [['a','b','c'], ['a','c','b'], ['b','a','c'], ['b','c','a'], ['c','a','b'], ['c','b','a']].

Try this: Remove the path.pop(); used[i] = False undo line and re-run — the output breaks, because state is never rewound. That one line is the whole point of backtracking.

The single most common hash-map interview question. The task: find two numbers in the list that add up to target, and return their positions — in one pass, O(n).

1. seen = {} is a dict mapping each value you've passed to its index. It's the "memory" that lets you avoid a second loop.
2. for i, x in enumerate(nums) walks the list once, giving both the index i and the value x.
3. For each x, the missing partner is target - x. if target - x in seen is an O(1) hash lookup asking "did I already pass the number that completes this pair?" — if so, return both indices.
4. If not, record this value with seen[x] = i and move on. Every element is visited once, so the whole thing is O(n) instead of the brute-force O(n²) of comparing all pairs.

What the output means: For two_sum([2, 7, 11], 9) it returns (0, 1), because nums[0] + nums[1] = 2 + 7 = 9.

Try this: This is hashing-pattern 4 from §6 in its purest form. The mental move — "remember what I've seen so the search is O(1)" — is exactly what interviewers are testing.

The backtracking classic: generate every subset (the power set) of a list. For n items there are 2ⁿ subsets, because each item is independently either in or out.

1. res collects finished subsets; path is the subset currently being built. Same two-variable setup as the permutations lab.
2. bt(start) saves the current path[:] (a copy) as a subset every time it's called — including the empty subset at the very start. There's no separate base case because every node of the tree is a valid answer.
3. The loop for i in range(start, len(nums)) only looks forward from start. That forward-only rule is what prevents duplicates like both [1,2] and [2,1] (a subset is unordered).
4. The body is the same choose / explore / un-choose rhythm: path.append(nums[i]) (choose), bt(i + 1) (explore the rest), path.pop() (un-choose to try the next item).

What the output means: subsets([1, 2, 3]) returns all 8 subsets, from [] up to [1, 2, 3]: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]].

Try this: Count them: len(subsets([1,2,3])) is 8 = 2³. Add a fourth number and it becomes 16 — the power set doubles with each new element.