Tries and String Search
A trie stores strings as shared prefixes, so lookup cost depends on key length instead of the number of keys. This video builds a trie node by node, shows the memory cost of one edge per character, and then moves to radix trees and Aho-Corasick for multi-pattern matching in a single pass.
Topics covered:
- The trie node: one edge per character, one path per key
- Lookup cost: proportional to key length, not dataset size
- Memory cost of per-character nodes and how radix trees fix it
- Prefix queries: autocomplete in a single traversal
- Aho-Corasick: matching many patterns in one pass
- Compressed tries in routers, spell checkers, and tokenizers
Related articles
Hash Tables Aren't Magic
Load factors, collision strategies, and cache misses — why O(1) has a constant that bites when you least expect it.
Amortized Analysis: When O(1) Is Really O(1)
Master aggregate, accounting, and potential methods to prove that worst-case-per-operation bounds hold even when individual operations are expensive.
B-Trees and the Disk Access Pattern
Why every major database uses B-trees instead of binary trees, and how B+ trees optimize for sequential I/O.
More in Algorithms
Hash Tables Under the Hood
Load factors, collision strategies, and cache behavior — why O(1) has a constant that can be 1ns or 200ns.
WatchHeaps and Priority Queues
Binary heaps as arrays — sift up, sift down, and why insert and extract-min are both O(log n) with no pointers.
DetailsHash Maps and Collision Resolution
Hash maps from the memory up — hash functions, collision strategies, and the load factor that decides when a map resizes.
DetailsGraph Algorithms: BFS and DFS
BFS and DFS traced node by node — the queue versus the stack, the visited set, and what each traversal order is good for.
DetailsDynamic Programming, Visualized
Memoization and tabulation as data flow — overlapping subproblems, the DP table, and how state transitions map to code.
DetailsBinary Search Explained
Binary search at the instruction level — midpoint math, cache behavior, and why it beats linear scan on sorted contiguous data.
DetailsRecursion and the Call Stack
How recursive functions actually execute — stack frames, the base case, and what happens to memory when recursion goes deep.
DetailsBig-O Notation, Visually Explained
What O(1), O(n), and O(log n) mean as instruction counts — growth curves drawn to scale, constants, and real workloads.
DetailsSorting Algorithms Under the Hood
Quicksort, merge sort, and insertion sort compared by the operations that matter: comparisons, swaps, cache misses, and allocations.
DetailsDepth, delivered weekly
One technical dispatch a week — articles and episode notes before they go public.
One technical dispatch per week. No noise.