Data Structures

Lesson 1: Big-O Intuition

An algorithm's speed isn't measured in seconds — hardware varies — but in how work grows with input size n. Big-O notation describes that growth's shape, ignoring constants. O(1) constant: one step regardless of n (reading arr[0]). O(log n) logarithmic: halving each step (binary search — a billion items needs ~30 checks). O(n) linear: one pass (finding a maximum). O(n log n): efficient sorts. O(n²) quadratic: nested loops over all pairs. O(2^n) exponential: trying every subset — infeasible beyond tiny n.

The key insight: growth class dominates everything. An O(n²) algorithm on a fast computer loses to O(n log n) on a slow one once n is large — doubling n quadruples quadratic work but barely nudges n log n. This is why Google can search billions of pages in milliseconds: the data structures underneath (inverted indexes, trees) turn impossible scans into logarithmic hops. When analyzing, count the dominant operation and drop constants: 3n² + 100n + 5 is O(n²).

Also consider space complexity — memory growth — and the best/average/worst cases. Linear search is O(1) best-case (first item matches) but O(n) worst-case. Amortized analysis averages costly rare operations: Python list append is O(1) amortized even though occasional resizes cost O(n), because resizes are exponentially rare. Choosing structures is choosing trade-offs: speed vs. memory, average vs. worst case, simplicity vs. performance.

Try it yourself: Classify: (a) binary search, (b) bubble sort, (c) printing an n×n multiplication table, (d) recursive Fibonacci fib(n) = fib(n-1) + fib(n-2). For (d), why is it so slow?

Lesson 2: Arrays and Linked Lists

An array (Python's list) stores elements in contiguous memory: index i lives at address base + i × size, so random access is O(1). The price: inserting at the front shifts everything (O(n)), and fixed capacity forces occasional O(n) resizes (amortized away in Python). Arrays excel when you read by index and append at the end — the most common pattern in practice.

A linked list chains nodes, each holding data plus a pointer to the next. No contiguous block needed, and inserting/deleting at a known node is O(1) — just rewire pointers. The price: no random access; reaching element i means walking i links (O(n)). Doubly linked lists add backward pointers for O(1) deletion given the node. Python lists are dynamic arrays, not linked lists — but implementing one teaches pointers-by-reference:

class Node:
        def __init__(self, data):
            self.data = data
            self.next = None

    class LinkedList:
        def __init__(self):
            self.head = None
        def prepend(self, data):
            node = Node(data)
            node.next = self.head
            self.head = node
        def to_list(self):
            out, cur = [], self.head
            while cur:
                out.append(cur.data)
                cur = cur.next
            return out

Try it yourself: Extend the LinkedList with append(data) (O(n) walk to the end) and find(value). When would you prefer a linked list over Python's built-in list? (Hint: think about frequent insertions at the front.)

Lesson 3: Searching — Linear vs. Binary Search

Linear search checks items one by one until it finds the target or runs out: simple, works on any list, but O(n) in the worst case. Binary search needs a sorted list, then repeatedly halves the search range: compare the middle, discard the half that cannot contain the target. Its cost is O(log n) — on a million items, at most 20 steps. The trade-off is universal in data structures: a little extra structure (sortedness) buys a lot of speed.

Binary search is easy to get wrong: the classic bugs are off-by-one errors in the loop bounds and infinite loops when the range stops shrinking. The robust pattern keeps lo and hi as the search window and loops while lo <= hi, setting mid = (lo + hi) // 2 and moving lo = mid + 1 or hi = mid - 1 each step — the window always shrinks, so the loop always ends.

Searching also generalizes: Python's bisect module finds insertion points in sorted lists, databases use B-trees (a generalization of binary search) to find records among billions, and autocomplete systems search tries (prefix trees) letter by letter.

Try it yourself: Trace binary search for 30 in [5, 15, 25, 35, 45]. How many comparisons? Answers: mid = 25 < 30 → search right [35, 45]; mid = 35 > 30 → window empty. Not found, 2 comparisons.

Lesson 4: Stacks and Queues

A stack is LIFO — last in, first out, like a stack of plates: push adds to the top, pop removes from the top, peek looks. Both operations are O(1). Stacks model nesting and backtracking: function calls (the call stack — which is why infinite recursion crashes with 'stack overflow'), undo history, browser back buttons, and matching parentheses. Python lists double as stacks (append/pop()).

A queue is FIFO — first in, first out, like a checkout line: enqueue at the back, dequeue from the front. Queues model waiting and fairness: print jobs, task schedulers, breadth-first search. Use collections.deque for O(1) both ends — a plain list's pop(0) is O(n) because everything shifts. A priority queue (heapq) dequeues the smallest item first — the engine behind Dijkstra's shortest-path algorithm and hospital triage systems.

The parentheses-matching algorithm shows stacks' elegance: scan the string, push openers, pop on closers — a mismatch or leftover means unbalanced. This O(n) single pass powers syntax checkers in every compiler and editor. Deques (double-ended queues) allow both ends, useful for sliding-window problems.

Try it yourself: Use a stack to reverse the string 'hello' (push each char, pop all). Simulate a queue with deque: enqueue 1,2,3, dequeue twice, enqueue 4 — what's left, in order? When is a queue better than a stack for processing tasks?

Lesson 5: Hash Maps

A hash map (Python dict) stores key→value pairs with average O(1) lookup, insert, and delete — the closest thing to magic in data structures. The trick: a hash function converts each key into an array index. Looking up phone["Ada"] hashes "Ada" → index 7421 → reads that slot directly, no searching. This powers database indexes, caches, symbol tables in compilers, and the word-counting pattern from the Python course.

Collisions — two keys hashing to one slot — are inevitable (pigeonhole principle). Strategies: chaining (each slot holds a linked list of entries) or open addressing (probe for the next free slot). A good hash function spreads keys uniformly; Python hashes strings with a randomized SipHash. When the table fills past its load factor (~2/3), it resizes — doubling and rehashing everything, an O(n) operation amortized over many O(1) inserts.

Hash maps have limits: worst-case O(n) under adversarial collisions (hash-flooding attacks are real), no ordering (use sorted() or a tree when order matters), and keys must be hashable/immutable — lists can't be dict keys, tuples can. Hash sets (set) are hash maps storing only keys: O(1) membership tests, deduplication, and set algebra (union, intersection). Choosing dict-vs-list is often the single biggest performance decision in a program.

Try it yourself: Write first_repeated(words) returning the first word appearing twice, using a set. Why can't you use a list as a dictionary key? (Try it and read the error.) Group anagrams: given ['eat','tea','tan','ate','nat','bat'], return groups of anagrams using a dict.

Lesson 6: Sets and Dictionaries in Practice

A set is an unordered collection of unique items with O(1) membership testing. Its killer use: removing duplicates and testing membership fast. set([1, 2, 2, 3]) is {1, 2, 3}; 42 in my_set is instant even for a million items, where scanning a list would be slow. Set operations mirror math: union |, intersection &, difference -. Finding the common followers of two accounts is literally a & b.

A dictionary maps keys to values with O(1) average lookup. Practical patterns: counting with counts[word] = counts.get(word, 0) + 1 (or collections.Counter); grouping by a key, e.g. students by grade; and memoization, caching expensive function results: a Fibonacci function that stores computed values in a dict drops from exponential to linear time. Choose keys that are hashable (strings, numbers, tuples) — lists cannot be keys.

Both structures trade memory for speed: they store extra bookkeeping (hash tables) so lookups skip the scan. When you need “have I seen this before?” or “look this up by name,” reach for a set or dict before anything else.

Try it yourself: What does {1, 2, 3} & {2, 3, 4} give? Use a dict to count letters in "banana". Answers: {2, 3}; {'b': 1, 'a': 3, 'n': 2}.

Key vocabulary: Set — an unordered collection of unique items; dictionary — key→value mapping; memoization — caching function results; hashable — usable as a dict key or set member.

Lesson 7: Trees and Recursion

A tree is a hierarchy of nodes: one root, each node having children (and one parent), with leaves having no children. File systems, org charts, HTML documents, and decision trees are all trees. A binary tree gives each node at most two children (left/right); a binary search tree (BST) orders them — left subtree < node < right subtree — enabling O(log n) search, insert, and delete when balanced.

Recursion — functions calling themselves — is trees' natural language: every subtree is itself a tree. A recursive function needs a base case (stopping condition) and a recursive step (progress toward it):

class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left = self.right = None

    def inorder(node):
        if node is None:          # base case
            return
        inorder(node.left)        # recursive step
        print(node.val, end=" ")
        inorder(node.right)

Trees are everywhere in computing: heaps (priority queues), tries (autocomplete), parse trees (compilers), game trees (chess AI). Balanced variants (AVL, red-black) guarantee O(log n) by rotating after inserts; Python's bisect on sorted lists and heapq cover many tree use-cases without building one. The recursive mindset — solve a smaller instance, combine — also underlies divide-and-conquer algorithms like merge sort and quicksort.

Try it yourself: Write recursive count_nodes(root) and tree_height(root) (height of empty tree = -1 or 0 — pick and be consistent). Write factorial(n) recursively, then explain why recursion depth matters in Python (hint: try factorial(2000)).

Lesson 8: Graphs — BFS and DFS

A graph is nodes (vertices) connected by edges — the model for road networks, social networks, and the web. Graphs can be directed or undirected, weighted or unweighted. Two representations: an adjacency list (each node lists its neighbors; compact for sparse graphs) and an adjacency matrix (a grid of connections; fast edge lookups, O(V²) space).

Breadth-first search (BFS) explores level by level using a queue: visit all of a node's neighbors before going deeper. It finds the shortest path (fewest edges) in an unweighted graph — the algorithm behind “degrees of separation” and GPS routing on unweighted maps. Depth-first search (DFS) dives down one path as far as possible before backtracking, using a stack (or recursion). DFS powers maze solving, cycle detection, and topological sorting (ordering tasks with prerequisites, like a build system).

Both visit each node and edge once: O(V + E). The choice is about what you need: shortest path → BFS; explore everything / detect structure → DFS. Dijkstra's algorithm generalizes BFS to weighted graphs, and it runs the world's route planners.

Try it yourself: DFS from A in the same graph (neighbors in alphabetical order). What order? Answers: A → B → D → C (DFS dives to D before backtracking to C).

Key vocabulary: Graph — nodes + edges; BFS — level-by-level search, shortest path; DFS — dive-deep search; adjacency list/matrix — the two graph representations.

Lesson 9: Heaps and Priority Queues

A heap is a tree with a special property: in a min-heap, every parent is smaller than its children, so the smallest item is always at the root. Insert and remove-min both cost O(log n). A priority queue is the interface built on a heap: insert items with priorities and always remove the highest-priority one next. Emergency rooms, operating-system schedulers, and airport boarding all run on priority queues.

Heaps are stored compactly in arrays: the children of index i are at 2i + 1 and 2i + 2. Inserting bubbles the new item up until the heap property holds; removing the root replaces it with the last item and sifts it down. Python's heapq module implements a min-heap: heapq.heappush(h, x), heapq.heappop(h). To make a max-heap, push negated values.

Heap sort builds a heap and repeatedly extracts the minimum: O(n log n) with no extra space. A classic heap application is finding the k largest items in a stream: keep a min-heap of size k and compare each new item to the heap's root — O(n log k) instead of sorting everything.

Try it yourself: Use a min-heap to find the 2 smallest of [7, 3, 9, 1, 5] without fully sorting. What is the root of a max-heap? Answers: Push all, pop twice: 1, then 3. The root of a max-heap is the largest item.

Key vocabulary: Heap — a tree with the heap property; priority queue — remove-highest-priority-first structure; heapq — Python's min-heap module.

Lesson 10: Sorting Algorithms — Merge Sort and Quick Sort

Merge sort is divide and conquer: split the list in half, recursively sort each half, then merge the two sorted halves by repeatedly taking the smaller front element. Merging is O(n), and the recursion is log n levels deep, so the total is O(n log n) in all cases. It needs O(n) extra space for the merge, but it is stable (equal items keep their order) and predictable.

Quick sort picks a pivot, partitions the list into items smaller and larger than the pivot, and recursively sorts each part. Average case O(n log n), but a bad pivot (e.g. always the first element of an already-sorted list) degrades to O(n²). Real implementations pick pivots cleverly (median-of-three, random) and switch to insertion sort for tiny lists. Python's sorted() uses Timsort, which blends merge sort with insertion sort and is the practical default.

The lesson of sorting is bigger than sorting: divide and conquer turns O(n²) problems into O(n log n) ones, and choosing an algorithm means weighing worst case, average case, space, and stability — not just memorizing names.

Try it yourself: Quick sort [3, 1, 4] with pivot 3: what are the two partitions? What is merge sort's worst-case Big-O? Answers: Smaller: [1]; larger: [4]. O(n log n) in the worst case too.

Key vocabulary: Divide and conquer — splitting a problem into smaller copies of itself; pivot — quick sort's dividing element; stable sort — equal items keep their original order.

Lesson 11: Choosing the Right Structure and Interview Practice

Choosing a data structure starts with the operations you need. Frequent lookups by key? A hash map. Need the minimum again and again? A heap. Ordered data with insertions at both ends? A deque. LIFO behavior? A stack. FIFO? A queue. Hierarchy? A tree. Relationships between entities? A graph. Write down the operations and their frequencies first — the structure usually picks itself.

Patterns recur in interview and real problems: two pointers (pair sums in sorted arrays), sliding window (longest substring with constraints), hash map counting (anagrams, first unique character), stack for matching (balanced parentheses), BFS for shortest path, and prefix sums for range queries. Recognizing the pattern is most of the solution.

Practice method: solve a problem on paper first, then code, then test with edge cases (empty input, one item, duplicates, maximum size). Finally, state the Big-O of time and space — interviewers and code reviewers always ask. A solution that works but cannot be explained is only half a solution.

Try it yourself: Which structure tracks the “top 10” scores in a live game: array, heap, or linked list? Why? Answers: A heap (min-heap of size 10): new scores compare against the current 10th place in O(log 10).

Key vocabulary: Two pointers / sliding window — classic array patterns; prefix sum — running totals enabling fast range sums; trade-off — exchanging time, space, and complexity.

Lesson 12: Tries and String Algorithms

A trie (pronounced "try") is a tree for strings: each edge is a letter, and each node represents a prefix. The word "cat" is the path root → c → a → t, and a node is marked as the end of a word. Insert and lookup each cost O(m), where m is the word's length — independent of how many words are stored. Tries power autocomplete (list all words under the prefix node), spell-checkers, and IP routing tables. The cost is memory: every node stores up to 26 child pointers (or a dictionary of children), so a trie uses more space than a flat list of words.

String searching has its own algorithms. The naive search slides the pattern along the text and compares — O(n·m) worst case. The KMP algorithm (Knuth–Morris–Pratt) preprocesses the pattern to learn how far it can skip after a mismatch, reaching O(n + m): when a mismatch occurs, it reuses the partial match instead of restarting. Python's in operator and str.find() use highly optimized search internally (a mix of algorithms), so you rarely implement KMP by hand — but interviews and text editors depend on it.

Real-world application: every keystroke in a search box walks a trie-like structure; DNA sequencers use string algorithms to match billions of base pairs against reference genomes.

Try it yourself: Build a trie (nested dicts) with "apple", "app", "ape". Which nodes are word-ends? In a trie with 1,000 words, how many steps does lookup of a 5-letter word take? Answers: The nodes for "app", "apple", and "ape" are word-ends (note "app" is a word and a prefix); lookup takes 5 steps — O(word length), not O(number of words).

Key vocabulary: Trie — a prefix tree for strings; prefix — the start of a word; autocomplete — suggesting completions for a typed prefix; KMP — a linear-time string-search algorithm; naive search — slide-and-compare string matching, O(n·m).

Lesson 13: Advanced Trees — AVL, B-Trees, and Segment Trees

A plain binary search tree degrades to O(n) when input arrives sorted. Self-balancing trees fix this by restructuring after each insert. An AVL tree keeps every node's two subtrees within height 1 of each other (the balance factor); when an insert breaks that rule, rotations (local rearrangements of a few pointers) restore balance in O(1), keeping all operations at O(log n). Red-black trees use looser rules (coloring nodes red/black) for similar guarantees with less restructuring — Python's bisect on sorted lists and the sortedcontainers library cover many of the same needs.

B-trees generalize the idea to disk: each node holds many keys and many children, so a database can find any record among billions with only 3–4 disk reads — one per tree level. Every major database (SQLite, PostgreSQL, MySQL) stores its indexes in B-trees. A segment tree answers range questions fast: given an array, "what is the sum of elements 3 through 7?" in O(log n), and updates a single element in O(log n), by storing partial sums in a binary tree over the array. It is the engine behind leaderboard ranges and interval queries.

Real-world application: when you search a database, you are almost always walking a B-tree; when a game ranks players in a score range, a segment-tree-like structure answers it.

Try it yourself: Insert 10, 20, 30 into an empty BST. What shape results, and which rotation fixes it? Why do databases prefer B-trees over binary trees? Answers: A right-leaning chain; a left rotation around 10. B-trees have high fan-out, so the tree is shallow and each level costs one disk read — 3–4 reads for billions of rows.

Key vocabulary: AVL tree — a self-balancing BST with balance factor ≤ 1; rotation — a local rearrangement restoring balance; B-tree — a wide, shallow tree used for database indexes; segment tree — a tree for fast range queries and updates.

Lesson 14: Advanced Graphs — Dijkstra, Minimum Spanning Trees, and Topological Sort

BFS finds shortest paths only when every edge costs the same. Dijkstra's algorithm handles weighted graphs (roads with distances, flights with fares): it uses a priority queue to always expand the cheapest unvisited node, and once a node is settled, its shortest distance is final. With a binary heap it runs in O((V + E) log V). It fails on negative edge weights — Bellman–Ford handles those at higher cost. Dijkstra runs every car GPS: the road network is a weighted graph, and your route is the shortest path.

A minimum spanning tree (MST) connects all nodes with the cheapest possible total edge weight — the cheapest way to lay cable to every building, or roads to every town. Kruskal's algorithm sorts all edges and adds the cheapest one that does not create a cycle (using a union-find structure to test cycles); Prim's algorithm grows the tree from one node, always adding the cheapest edge to an outside node. Topological sort orders a directed acyclic graph (DAG) so every prerequisite comes before its dependent — the order a build system compiles files, or a university lists courses: take CS101 before CS201. If the graph has a cycle, no topological order exists.

Real-world application: maps (Dijkstra), network design (MST), and course prerequisites / build systems (topological sort) are three of the most-used graph algorithms in industry.

Try it yourself: Topologically sort: CS101 → CS201 → CS301, and CS101 → MATH200. Give one valid order. Why can't Dijkstra handle negative edge weights? Answers: E.g. CS101, CS201, MATH200, CS301 (any order respecting the arrows). Dijkstra assumes a settled node's distance can never improve, but a later negative edge could improve it.

Key vocabulary: Dijkstra's algorithm — shortest paths on weighted graphs with non-negative weights; MST — cheapest tree connecting all nodes; Kruskal / Prim — two MST algorithms; topological sort — prerequisite-respecting order of a DAG; union-find — a structure for tracking connected components.

Lesson 15: Dynamic Programming

Dynamic programming (DP) solves problems by breaking them into overlapping subproblems, solving each once, and reusing the answers. Its two ingredients: optimal substructure (the best solution is built from best solutions to smaller pieces) and overlapping subproblems (the same small pieces recur). The naive recursive Fibonacci recomputes fib(2) hundreds of times for fib(10); DP stores each value once. Two styles: memoization (top-down — recursion plus a cache dictionary) and tabulation (bottom-up — fill a table iteratively, usually with less overhead and no recursion limit).

Classic DP problems: 0/1 knapsack (pick items with weights and values to maximize value under a weight limit — each item taken at most once); longest common subsequence (LCS) (the longest sequence appearing in both strings, in order — used by diff tools to compare files); coin change (fewest coins for an amount); and edit distance (minimum insertions/deletions/substitutions to turn one string into another — the core of spell-check suggestions). The standard method: define the state, write the recurrence, pick a base case, and decide memoization vs. tabulation.

Real-world application: spell-checkers rank corrections by edit distance; genome aligners use DP to match DNA sequences; route planners cache subproblem results the same way.

Try it yourself: Compute the LCS length of "ABC" and "AC" by hand (answer: 2, "AC"). Write the recurrence for climbing stairs (1 or 2 steps at a time): ways(n) = ? Answers: ways(n) = ways(n-1) + ways(n-2), with ways(0) = 1, ways(1) = 1 — it is Fibonacci in disguise.

Key vocabulary: Dynamic programming — solving overlapping subproblems once and reusing answers; memoization — top-down caching; tabulation — bottom-up table filling; optimal substructure — optimal solutions built from optimal subsolutions; recurrence — the formula relating a problem to smaller versions.

Lesson 16: Greedy Algorithms and Backtracking

A greedy algorithm makes the best-looking local choice at each step and never looks back. Greedy works when a problem has the greedy-choice property: the locally optimal choice is part of a globally optimal solution. Activity selection (pick the maximum number of non-overlapping activities) is the textbook success: sort by finish time, always take the activity that ends first and does not conflict — provably optimal. Coin change with US coins (quarters, dimes, nickels, pennies) is greedy-optimal: always take the largest coin that fits. But greedy fails in general: with coin denominations [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 (3 coins) while the optimum is 3 + 3 (2 coins). Always ask: does the local choice guarantee the global optimum? If unsure, DP is the safe route.

Backtracking is systematic trial and error: build a candidate step by step, and when a step violates a constraint, undo it and try the next option. It is depth-first search over the space of partial solutions, with pruning — abandoning branches that cannot work. The N-Queens problem (place N queens on an N×N board so none attack another) is the classic: place a queen row by row, backtrack when a row has no safe column. Backtracking also solves Sudoku, mazes, and permutations. Its worst case is exponential, but pruning makes many instances fast.

Real-world application: scheduling (greedy), puzzle solvers and game AI (backtracking), and route planning (greedy nearest-neighbor as a fast heuristic) all use these patterns.

Try it yourself: Greedy coin change for 30 cents with US coins: which coins, how many? Give a coin system where greedy fails (other than [1, 3, 4]). Answers: Quarter + nickel = 2 coins. E.g. denominations [1, 5, 6] for amount 10: greedy takes 6 + 1 + 1 + 1 + 1 (5 coins); optimal is 5 + 5 (2 coins).

Key vocabulary: Greedy algorithm — best local choice at each step; greedy-choice property — local optimum leads to global optimum; backtracking — trial and error with undo; pruning — abandoning branches that cannot succeed.

Lesson 17: Sorting II — Heap Sort, Counting Sort, and Timsort

Comparison sorts (merge, quick) cannot beat O(n log n) in the worst case — a mathematical lower bound. But non-comparison sorts can, when the data has structure. Counting sort counts how many times each value occurs, then writes them out in order: O(n + k) where k is the value range — blazing fast when k is small (sorting exam scores 0–100). Radix sort sorts digit by digit (least significant first) using counting sort as a subroutine: O(d·(n + k)) for d digits. Sorting a million 32-bit integers by radix sort is linear in practice.

Heap sort builds a max-heap (O(n)) and repeatedly extracts the maximum, placing it at the end: O(n log n) worst case with O(1) extra space — the only classic sort with both guarantees — but it is not stable and its cache behavior is poor, so it rarely wins in practice. Python's sorted() uses Timsort, a hybrid: it scans for existing runs of ordered data, sorts small runs with insertion sort, and merges runs like merge sort. Timsort is O(n) on nearly-sorted data — the common case in real programs — and O(n log n) worst case, stable, and the reason you should almost never hand-roll a sort in Python.

Real-world application: databases sort with radix-like and merge-like strategies chosen by data size; spreadsheets rely on Timsort-style adaptivity for instant sorts of mostly-sorted columns.

Try it yourself: Radix sort [170, 45, 75, 90, 2]: after sorting by the ones digit, what is the order? Is counting sort a good choice for sorting a million salaries up to $1,000,000? Answers: Ones digits: 170(0), 90(0), 2(2), 45(5), 75(5) → [170, 90, 2, 45, 75]. No — k = 1,000,001 makes the count array huge; use a comparison sort or radix sort instead.

Key vocabulary: Counting sort — sort by counting occurrences, O(n + k); radix sort — digit-by-digit sort using counting sort; heap sort — O(n log n) in-place sort via a heap; Timsort — Python's adaptive hybrid sort; stable sort — equal items keep their order.

Lesson 18: Hashing in Depth, Caches, and Bloom Filters

Lesson 5 introduced hash maps; now look inside. A hash function must be deterministic (same input → same output), fast, and uniform (spreading keys evenly). Python hashes strings with SipHash, randomized per run for security — the same string hashes differently in different runs, which is why you must never persist raw hash values. Collision resolution comes in two families: chaining (each slot holds a linked list of entries — CPython's dict uses a variant of this idea) and open addressing (on collision, probe the next slot — linear probing, quadratic probing, or double hashing). When the load factor (entries / slots) passes ~2/3, the table doubles and rehashes everything — an O(n) resize amortized over many O(1) inserts.

Hashing also powers caches: a web server keeps the most-used pages in a hash map so it need not recompute them. When the cache fills, LRU eviction (Least Recently Used) drops the item unused longest — implemented in Python with functools.lru_cache, which memoizes a function automatically. A Bloom filter is a space-sipping cousin: a bit array plus a few hash functions that can say "definitely not in the set" or "possibly in the set" — it can have false positives but never false negatives. Databases and browsers use Bloom filters to avoid expensive disk or network lookups for things that do not exist.

Real-world application: password storage hashes (with salt — never store plain passwords), content-delivery caches, and Chrome's Safe Browsing checks all run on these ideas.

Try it yourself: With table size 7 and hash = key mod 7, insert 14, 21, 28 by linear probing — which slots? A Bloom filter says "possibly present" for a username — what must you do next? Answers: 14 → slot 0; 21 → slot 0 collides → slot 1; 28 → slots 0, 1 occupied → slot 2. Check the real database — "possibly" might be a false positive.

Key vocabulary: Chaining / open addressing — the two collision strategies; linear probing — checking the next slot on collision; load factor — entries ÷ slots; LRU cache — evict the least-recently-used item; Bloom filter — a space-efficient "definitely not / possibly" membership test.

Lesson 19: Complexity, P vs. NP, and Problem-Solving Patterns

This course has classified problems by how fast they can be solved. The classes have names: P = problems solvable in polynomial time (sorting, shortest path, two-sum) — the "feasible" problems. NP = problems whose solutions can be verified in polynomial time. Every P problem is in NP, but the great open question of computer science — worth a $1 million Millennium Prize — is whether P = NP: can every efficiently verifiable problem also be efficiently solved? Most experts believe not. NP-complete problems (traveling salesperson, Sudoku generalized, satisfiability) are the hardest in NP: solve one efficiently and you solve them all. In practice, NP-complete problems are handled with heuristics, approximation, and backtracking with pruning — not exact answers at scale.

Two more ideas complete your toolkit. Amortized analysis (Lesson 1) averages rare expensive operations over many cheap ones. Space–time trade-offs recur everywhere: memoization trades memory for speed; Bloom filters trade accuracy for space; compression trades CPU time for storage. Finally, the pattern library for interviews and real work: two pointers, sliding window, hash-map counting, stack matching, BFS shortest path, prefix sums, DP, and greedy. Recognizing which pattern fits is most of the solution — the code is usually short once the pattern is chosen.

Real-world application: delivery companies route thousands of stops with heuristics because exact traveling-salesperson solutions are NP-hard; chip designers and airlines live with approximations daily.

Try it yourself: Is sorting in P? Is checking whether a proposed traveling-salesperson tour is under budget in NP? Answers: Yes — sorting is polynomial (O(n log n)). Yes — verifying a tour means adding its edge weights and comparing to the budget, which is polynomial.

Key vocabulary: P — polynomial-time solvable; NP — polynomial-time verifiable; NP-complete — the hardest problems in NP; heuristic — a fast rule giving good-but-not-guaranteed answers; approximation — a solution provably close to optimal.

Lesson 20: Capstone — Build an Autocomplete Engine and Route Planner

Your capstone combines the whole course into two working tools. Part A — Autocomplete engine: build a trie (Lesson 12) over a word list, then given a prefix, return all completions ranked by frequency (store a count at each word-end node; use a heap (Lesson 9) to return the top 5). Part B — Route planner: model a small city's roads as a weighted graph (Lesson 14) and run Dijkstra to answer "fastest route from A to D." Add a menu, save/load the word list and graph from JSON files, and write tests for both.

Plan before coding: data structures first (trie node: children dict, is_word, frequency; graph: adjacency dict of neighbor → weight), then algorithms (trie insert/search/completions; Dijkstra with heapq), then the interface (a menu loop). Test each piece with tiny inputs: a 3-word trie; a 4-node graph whose shortest path you computed by hand in Lesson 14. Measure: time autocomplete on 10,000 words, and state the Big-O of every operation in comments.

Real-world application: search engines and map apps are these two tools at planetary scale — tries over billions of queries, Dijkstra over graphs with hundreds of millions of roads, plus caches and ranking on top.

Try it yourself: Build both tools this week. As a stretch, add "did you mean?" using edit distance (Lesson 15) for misspelled prefixes. What is autocomplete's lookup Big-O for a prefix of length m? Answers: O(m) to reach the prefix node, plus time to collect completions below it.

Key vocabulary: Capstone — a project combining everything learned; ranking — ordering results by relevance or frequency; definition of done — the checklist a project must satisfy.