Extra practicesExtra

⌘ K

Make the path yours

Start at Stop 01 and follow the winding path through all 23 stops.

Color follows the learning spectrum:

01 · FundamentalsBuild a base with sequences, pointers, hashing and sorting. Start here for early-career preparation, and keep using these foundations at every company and later stage.
02 · Core techniquesAtlassian and Shopify illustrate product-engineering targets. Build on your fundamentals with search, trees, heaps, graphs and greedy reasoning, and practice applying them.
03 · Advanced techniquesPrepare cumulatively across 01–03 for big-tech coding interviews. Choose the advanced techniques relevant to your target role, and practice problem solving, tradeoffs, complexity and testing throughout.
04 · Specialist topicsChoose specialist branches that match your role, such as sketches, storage or geometry. Senior and staff engineering also require design, technical judgment and leadership beyond this algorithms map.

The spectrum shows cumulative learning depth. Company and role examples are illustrative, not an employer ranking or a job-readiness guarantee. Focus a topic or show all connections for its exact prerequisites; enter specialist branches when those prerequisites make sense to you.

Preparing for interviews?

For coding interviews at companies such as Google, Meta and Amazon, combine fundamentals, core techniques and the advanced topics relevant to your role. Practice unfamiliar problems, explain tradeoffs, analyze complexity and test edge cases. Follow the employer’s guidance to choose coverage.

You are here
Arrays & Pointers0/11 Sequences, windows & pointer scans
Lists, Stacks & Queues0/13 Linked chains & ordered frontiers
Hashing & Maps0/13 Fast lookups, counting & bitsets
Recursion & D&C0/5 Call frames, base cases & recurrence trees
Sorting0/10 Compare, partition & combine
Search & Intervals0/7 Search spaces, bounds & sweeps
Trees & BSTs0/14 Hierarchy, search & balance
Heaps & Top-K0/9 Priority, streams & top-k
Graphs & DSU0/12 Traversal, DAG order & Union-Find
Caching Systems0/5 Recency, frequency & stampede control
Greedy & Math0/10 Local choices & essential math
Shortest Paths & A*0/7 Dijkstra, relaxations & A* search
Backtracking & DP0/8 Explore choices. Reuse results.
Tries & Segment Trees0/16 Tries, automata & segment trees
Filters & Sketches0/12 Bloom, Cuckoo & HyperLogLog
Flow & Matching0/9 Capacity, cuts & bipartite matching
Geometry0/10 Intersections, hulls & planar sweeps
Advanced Text Indexes0/8 Suffixes, BWT & FM indexes
Advanced Tree Queries0/10 Euler tours, HLD & dynamic forests
Streaming Sketches0/12 Heavy hitters, quantiles & sampling
Storage, Vector & Dist.0/11 B+ trees, LSM, consistent hashing & HNSW
DP & Transforms0/9 Convex hull trick, FFT & transforms
Compression0/6 Huffman, arithmetic & LZ coding

01FundamentalsStartups · early-career roles

02Core techniquesProduct teams · Atlassian, Shopify

03Advanced techniquesBig tech · Google, Meta, Amazon

04Specialist topicsSenior / staff engineering

You are hereArrays & Pointers0/11 Sequences, windows & pointer scans
Lists, Stacks & Queues0/13 Linked chains & ordered frontiers
Hashing & Maps0/13 Fast lookups, counting & bitsets
Recursion & D&C0/5 Call frames, base cases & recurrence trees
Sorting0/10 Compare, partition & combine
Search & Intervals0/7 Search spaces, bounds & sweeps
Trees & BSTs0/14 Hierarchy, search & balance
Heaps & Top-K0/9 Priority, streams & top-k
Graphs & DSU0/12 Traversal, DAG order & Union-Find
Caching Systems0/5 Recency, frequency & stampede control
Greedy & Math0/10 Local choices & essential math
Shortest Paths & A*0/7 Dijkstra, relaxations & A* search
Backtracking & DP0/8 Explore choices. Reuse results.
Tries & Segment Trees0/16 Tries, automata & segment trees
Filters & Sketches0/12 Bloom, Cuckoo & HyperLogLog
Flow & Matching0/9 Capacity, cuts & bipartite matching
Geometry0/10 Intersections, hulls & planar sweeps
Advanced Text Indexes0/8 Suffixes, BWT & FM indexes
Advanced Tree Queries0/10 Euler tours, HLD & dynamic forests
Streaming Sketches0/12 Heavy hitters, quantiles & sampling
Storage, Vector & Dist.0/11 B+ trees, LSM, consistent hashing & HNSW
DP & Transforms0/9 Convex hull trick, FFT & transforms
Compression0/6 Huffman, arithmetic & LZ coding

#main-content > astro-island { display: none; } body.bc-full-viewport { height: auto; overflow: visible; }

Explore the learning roadmap

Enable JavaScript for interactive progress. You can read every topic and follow its prerequisites below.

01 — Fundamentals

Startups · early-career roles

Build a base with sequences, pointers, hashing and sorting. Start here for early-career preparation, and keep using these foundations at every company and later stage.

Arrays, Strings & Pointer Scans

Big-O Growth & RAM Memory Layout — Byte addressing, CPU cache lines, worst-case vs amortized cost, and space complexity.
Static Array — Values at contiguous integer positions with O(1) indexed access and O(n) shift insertions.
Dynamic Array — Logical length vs allocated capacity, geometric doubling, and O(1) amortized append.
String & Character Sequences — Code units, immutable vs mutable buffers, slicing bounds, and palindrome scans.
Matrix & 2-D Grid — Row-major addressing, 4-way and 8-way cell neighborhoods, and in-place boundary traversal.
Two Pointers — Converging opposite-end and read/write pointer invariants in O(1) extra space.
Three Pointers & Dutch Flag — Fixed anchor + moving pair and three-way low/mid/high partitioning on one array.
Sliding Window — Fixed and elastic contiguous `[l, r]` windows with O(1) incremental boundary updates.
Prefix-Sum Array — Leading-zero cumulative row turning arbitrary `[start, stop)` range sums into `P[stop] - P[start]`.
Difference Array — Apply batched `[l, r)` range additions via two O(1) boundary deltas before a single prefix pass.
2-D Prefix (Summed-Area) Table — Padded integral matrix answering arbitrary sub-rectangle sums with four corner reads.

Linked Lists, Stacks & Queues

Singly Linked List — Heap-allocated nodes wired by `next` links, dummy heads, and in-place pointer reversal.
Doubly Linked List — Symmetric `prev` and `next` pointers with LEFT/RIGHT sentinels for O(1) arbitrary node splice.
Circular Linked List — Tail-to-head wraparound for round-robin rings and cyclic traversal invariants.
Fast & Slow Pointers (Floyd’s Tortoise & Hare) — Two-speed pointer walks for exact midpoint discovery and O(1)-space cycle entry proof.
Random-Pointer & Multilevel Linked Lists — Interleaved deep-copying of cross-linked nodes and DFS flattening of nested child chains.
Stack (LIFO) — Last-in, first-out top discipline powering nested bracket matching, undo history, and DFS.
Min Stack — Paired value and depth-minimum stacks preserving O(1) minimum queries across pops.
Monotonic Stack — Evict dominated indices on push to find next greater/smaller boundaries in one linear scan.
Queue (FIFO) — First-in, first-out arrival/removal discipline for fair scheduling and level-by-layer BFS.
Queue from Two Stacks — Lazy IN-to-OUT stack reversal achieving amortized O(1) FIFO operations.
Ring Buffer (Circular Queue) — Fixed-capacity array with modular read/write cursors and zero memory allocations.
Deque (Double-Ended Queue) — Symmetric O(1) push and pop at both front and back ends.
Monotonic Deque — Expire out-of-window indices at the front and pop dominated candidates at the back for O(n) sliding maxima.

Bitsets, Hashing, Maps & Sets

Bitset & Bitwise Operations — Word-level XOR/AND/OR shifts, `x & (x - 1)` lowest-set-bit tricks, and packed bitsets.
Direct-Address Table & Frequency Array — Map bounded integer/ASCII domains straight to array slots without hashing overhead.
Hash Functions & Hash Tables — Deterministic hashing, separate chaining vs open addressing, tombstones, and load-factor resizing.
Hash Map (Dictionary) — Unordered key-to-value associations powering complement lookups, grouping, and memoization.
Hash Set — Unique-key membership, O(1) duplicate filtering, and visited-state tracking.
Frequency Map / Counter — Key-to-multiplicity maps handling zero-crossings for anagrams, windows, and subarray counts.
Bucket Array — Group items by bounded integer counts or attributes to avoid O(n log n) sorting.
Multiset (Bag) — Multiplicity-aware sets supporting single-copy vs all-copy erasure.
Multimap — One-to-many key-to-collection mappings for inverted indexes and grouped records.
Insertion-Ordered (Linked) Hash Map — Coordinate a hash index with a doubly-linked chain for deterministic iteration and `move_to_end`.
Randomized Set (`O(1)` Insert, Delete & Sample) — Pair a dense array with a value-to-index map using swap-with-last deletion for uniform `getRandom`.
Randomized Collection with Duplicates — Dense array + value-to-index-set map preserving frequency-weighted sampling under swap-delete.
Cuckoo Hashing — Give each key alternative buckets and relocate occupants when an insertion finds its first choice full.

Recursion, Call Stack & Divide-and-Conquer

Recursion Call Stack & Frames — Activation frames, local state suspension, return addresses, and call depth tracking.
Base Cases & Recursive Leap of Faith — Termination invariants, shrinking state arguments, and combining subproblem return values.
Tail Recursion & Explicit Stack Conversion — Accumulator state passing and rewriting deep recursion into explicit iterative stack loops.
Divide & Conquer Decomposition — Split problem instances into independent subproblems, solve recursively, and merge results.
Recurrence Trees & Master Theorem Intuition — Count work per level across branching factor a and shrink factor b to derive O(n log n) vs O(n).

Sorting Algorithms

Bubble Sort & Early-Exit Optimization — Adjacent pairwise swaps bubbling maxima rightward, plus the `swapped` flag for O(n) sorted detection.
Selection Sort — Scan the unsorted suffix for its true minimum and perform at most n − 1 memory writes.
Insertion Sort (Iterative & Recursive) — Grow a sorted left hand one element at a time — adaptive O(n + inversions) speed on nearly sorted runs.
Gnome Sort — Insertion Sort expressed with a single cursor that steps forward when ordered and swaps backward when out of order.
Merge Sort — Halve recursively log₂(n) times and zip sorted halves via two-pointer merge for guaranteed O(n log n) stability.
Heap Sort — Build a max-heap in O(n) in-place, then repeatedly swap the root maximum to the shrinking tail in O(n log n).
Quick Sort & Quickselect — Explain every partition swap, follow the recursive calls, and reuse the same guarantee to find one rank.
Timsort (Production Hybrid Sort) — How Python and Java combine natural run detection, Binary Insertion Sort, and galloping Merge Sort.
Counting Sort — Escape the Ω(n log n) comparison bound using frequency counts and prefix positions over integer keys.
Radix & Bucket Sort — Digit-by-digit stable Counting Sort passes sorting fixed-width integers and strings in O(d · (n + b)).

02 — Core techniques

Product teams · Atlassian, Shopify

Atlassian and Shopify illustrate product-engineering targets. Build on your fundamentals with search, trees, heaps, graphs and greedy reasoning, and practice applying them.

Binary Search, Sweep Line & Intervals

Binary Search (Exact Lookup) — Halve sorted arrays via `l / m / r` invariants without off-by-one infinite loops.
Lower Bound & Upper Bound (`bisect`) — Half-open boundary contracts finding the first ≥ x and first > x across duplicates and rotated arrays.
Binary Search on Answer Space — Turn min-max optimization into binary search over any monotonic `feasible(x)` predicate.
Coordinate Compression — Map sparse 10⁹ coordinates onto dense `[0 .. U-1]` ranks while preserving order and equality.
Merging & Intersecting Intervals — Sort by start coordinate to coalesce overlapping spans and find free gaps in one pass.
Sweep Line & Event Sorting — Convert intervals into `+1 / -1` endpoint events to track peak concurrency and active coverage.
Disjoint Interval Set — Maintain online non-overlapping ranges under dynamic range additions and deletions.

Trees, BSTs & Balanced Search Trees

Binary Tree & DFS/BFS Traversals — Left/right child nodes, preorder/inorder/postorder recursion, and level-order FIFO traversal.
N-ary Tree & Rooted Forest — Multi-child hierarchies and disjoint component forests with subtree attach/prune.
Parent Array Representation — Encode rooted trees in a flat array `parent[i]` (`-1` = root) for compact ancestor chains.
Binary Lifting & Lowest Common Ancestor (LCA) — Precompute `2^k` ancestor jumps to answer k-th ancestor and LCA queries in O(log n).
Binary Search Tree (BST) — Left < node < right ordering invariant supporting search, insert, predecessor/successor, and Hibbard delete.
Ordered Map & Ordered Set — Sorted key ADTs supporting `lower_bound`, neighbor lookup, and ordered range iteration.
AVL Tree & Rotations — Strict `|height(L) - height(R)| <= 1` invariant restored via single and double (LL/RR/LR/RL) rotations.
Red-Black Tree — Color and black-height invariants bounding height ≤ 2 log₂(n+1) with ≤ 2–3 rotations per update.
Treap (Tree + Heap) — BST by key + Heap by random priority enabling clean `split` and `merge` in expected O(log n).
Skip List — Probabilistic express-lane linked towers over a sorted list (used in Redis ZSET and HNSW!).
Order-Statistic Tree — Augment balanced BST nodes with `subtree_size` for O(log n) dynamic `rank(x)` and `select(k)`.
Interval Tree — Balanced BST augmented with subtree `max_end` to find overlapping intervals dynamically.
Rope (Text Chunk Tree) — Balanced tree of string chunks indexed by subtree character weights for O(log n) editor splices.
Preorder, Inorder & Postorder Traversal — Visit each tree node in a deliberate order using recursion or an explicit stack.

Heaps, Priority Queues & Streams

Binary Heaps, Priority Queues & Top-K — Pointerless complete binary tree in a flat array (`(i-1)//2`, `2i+1`, `2i+2`), O(n) heapify, and O(n log k) Top-K.
Priority Queue Contract & Tie-Breaking — Priority vs arrival order, comparator inversion, and monotonic tuple tie-breakers in Python.
Streaming Median with Two Heaps — Balance a lower max-heap and upper min-heap to track the live median of a data stream.
Indexed Priority Queue (`decrease-key`) — Coordinate a binary heap with a key-to-array-slot map for O(log n) priority updates and arbitrary delete.
Double-Ended Priority Queue (Min-Max Heap) — Extract both minimum and maximum priorities in O(log n) via alternating min/max levels or lazy twin heaps.
Binomial Heap — Forest of power-of-two binomial trees supporting O(log n) heap merging via binary-addition carries.
Pairing Heap — Self-adjusting multiway heap with O(1) meld/insert and fast practical two-pass pairwise consolidation.
Fibonacci Heap — Lazy root consolidation and cascading cuts achieving theoretical O(1) amortized `decrease-key`.
Quickselect & Order Statistics — Partition around a pivot to select the k-th element without sorting the whole input.

Graphs, Traversal & Union-Find

Graph Models: Undirected, Directed & Weighted — Vertices, directed vs undirected arcs, weights, self-loops, parallel edges, and degree invariants.
Adjacency List — Per-vertex neighbor lists storing sparse graphs in O(V + E) space for fast outgoing iteration.
Adjacency Matrix & Edge List — Dense O(V²) constant-time edge tables (`∅` vs `0` weight) and flat `(u, v, w)` triples for edge sorting.
Implicit Grid Graph — Treat 2-D matrix cells as vertices and 4-way rules + wall checks as on-the-fly edges.
Breadth-First Search (BFS) & Multi-Source BFS — FIFO frontier layers discovering unweighted shortest paths; mark visited on enqueue to prevent duplicates.
Depth-First Search (DFS) & 3-Color Cycle Detection — Explore branches to completion, track `visiting` vs `visited` states, and classify back-edges.
Directed Acyclic Graphs (DAGs) & Topological Sort — Kahn’s in-degree queue and postorder DFS ordering dependencies and detecting blocking cycles.
Disjoint Set / Union-Find (DSU) — Parent-pointer forests with path compression and union by rank/size for near-O(1) connectivity.
Weighted Disjoint Set — Store relative potentials/ratios on parent links to answer equation and parity constraints.
Rollback Disjoint Set — Union by rank without destructive path compression + change-log stack for reversible snapshots.
Minimum Spanning Trees (Kruskal & Prim) — Connect all vertices at minimum edge weight via sorted Edge List + DSU (Kruskal) or Min-Heap cut (Prim).
Tarjan’s SCCs, Bridges & Articulation Points — Discovery timestamps and `low`-link values exposing strongly connected components and single points of failure.

Caching, Eviction & Stampedes

Cache Hits, Misses & FIFO Eviction — Temporal/spatial locality, hit ratio math, write-through vs write-back, and First-In First-Out eviction.
LRU Cache & Eviction Policies — Pair a hash map with a sentinel doubly-linked list for O(1) hits, updates, and least-recent eviction.
LFU Cache & TinyLFU Admission — Frequency-bucketed doubly linked lists with `min_freq` tracking and recency tie-breaking in O(1).
Cache Invalidation, TTL & Stale-While-Revalidate — Active vs lazy expiration, cache-aside races, versioned keys, and keeping cached reads fresh.
Cache Stampede & Singleflight Coalescing — Why one expired hot key triggers 1,000 database queries — and how request coalescing & jittered TTL stop it.

Greedy Algorithms & Essential Math

Greedy Choices & Loop Invariants — Choose the best local move while stating an invariant that explains why future options remain valid.
Exchange Arguments for Greedy Proofs — Compare an optimal solution with a greedy choice and show a safe exchange preserves the objective.
Interval Scheduling — Choose a maximum set of non-overlapping intervals by processing the earliest finish first.
Bit Manipulation & XOR Patterns — Use masks, shifts, XOR cancellation, and the n & (n - 1) trick to reason about integer bits.
Euclidean GCD & Least Common Multiple — Reduce a pair of integers through remainders and derive LCM carefully to avoid intermediate overflow.
Modular Arithmetic — Keep calculations within a modulus and distinguish valid addition and multiplication from division.
Binary Exponentiation — Square the base and halve the exponent to replace a linear chain of multiplications.
Sieve of Eratosthenes — Mark composite numbers from each prime square to enumerate primes up to a fixed limit.
Combinatorics & Counting — Use sum and product rules, permutations, and combinations to count outcomes without enumeration.
Reservoir Sampling — Keep a uniform sample from a stream when its final length is unknown.

03 — Advanced techniques

Big tech · Google, Meta, Amazon

Prepare cumulatively across 01–03 for big-tech coding interviews. Choose the advanced techniques relevant to your target role, and practice problem solving, tradeoffs, complexity and testing throughout.

Shortest Paths & Heuristic Search

Dijkstra’s Shortest Path — Greedy min-heap relaxation, lazy stale entries, stopping at pop, and why negative edges break the proof.
0-1 BFS (Deque Shortest Path) — Push 0-cost edges to deque front and 1-cost edges to back to beat Dijkstra in linear O(V + E) time.
Minimax & Bottleneck Paths — Generalize Dijkstra to `max(cost, edge)` and widest-path capacities over monotonic path operators.
A* Search & Heuristic Pathfinding — Guide Dijkstra toward the goal with admissible estimates `f(n) = g(n) + h(n)` around walls and state spaces.
Bidirectional BFS & Dijkstra — Expand frontiers simultaneously from Start and Goal to shrink `b^d` branching down to `2 · b^(d/2)`.
Bellman-Ford & Negative Cycle Detection — V − 1 edge-relaxation rounds handling negative weights, hop limits, and arbitrage/negative cycles.
Floyd-Warshall All-Pairs Shortest Paths — Three-line `k -> i -> j` dynamic programming over intermediate vertices for dense all-pairs routing.

Backtracking & Dynamic Programming

Backtracking & Decision Search Trees — Choose → explore → unchoose state symmetry with constraint pruning for subsets, permutations, and N-Queens.
Sparse Memoization Table (Top-Down DP) — Cache overlapping recursive subproblems by state tuple while distinguishing `0` from uncomputed.
DP Table & 1-D Dynamic Programming — Topological state ordering, bottom-up arrays, and rolling-variable O(1) space compression.
0/1 & Unbounded Knapsack DP — Why iterating capacity backward enforces single-use (0/1) while forward iteration allows reuse (Unbounded).
2-D Grid & Sequence DP (LCS & Edit Distance) — Two-axis DP recurrences aligning prefixes (LCS, Levenshtein Edit Distance) and matrix paths.
Longest Increasing Subsequence (O(n log n)) — Maintain minimal tail candidates with `bisect_left` to accelerate O(n²) DP to O(n log n).
Interval DP & Rerooting Tree DP — Subrange `[l, r]` splits and two-pass postorder/preorder subtree DP.
Bitmask DP (TSP & Subset States) — Encode visited subsets as integer bitmasks to reduce O(n!) permutation search to O(n² · 2ⁿ).

Tries, String Automata & Range Trees

Trie (Prefix Tree) — Character-branching tree with terminal markers for O(L) prefix search, autocomplete, and safe deletion.
Binary / Bitwise Trie (Maximum XOR) — Fixed-width MSB-to-LSB 0/1 paths greedily choosing opposite bits for O(W) maximum XOR queries.
Radix Tree & Ternary Search Tree — Compress unary trie chains into edge substrings (Radix/Patricia) or 3-way `< / = / >` nodes (TST).
Rolling Hash & Rabin-Karp — Polynomial modular fingerprints sliding across windows in O(1) with collision verification.
KMP & Z-Algorithm (Exact Linear Matching) — Prefix-border `pi` tables and Z-boxes matching patterns in deterministic worst-case O(n + m).
Aho-Corasick Multi-Pattern Automaton — Combine a Trie with BFS failure links and output links to match thousands of keywords in one text scan.
Suffix Array & Kasai’s LCP Array — Sorted suffix start indices + adjacent Longest Common Prefixes indexing all substrings compactly.
Suffix Tree & Suffix Automaton (SAM) — Compressed suffix tries and minimal state-equivalence DAGs with suffix links for O(m) substring queries.
Sparse Table (Static `O(1)` RMQ) — Power-of-two interval blocks answering idempotent Range Minimum/GCD queries in two overlapping reads.
Fenwick Tree (Binary Indexed Tree) — 1-indexed `i ± (i & -i)` lowbit jumps supporting mutable point updates and prefix sums in tiny RAM.
2-D Fenwick Tree — Nested lowbit walks over both axes for mutable submatrix sum queries.
Segment Tree — Balanced interval hierarchy combining disjoint covered nodes for O(log n) mutable range sum/min/max.
Lazy Propagation Segment Tree — Defer range updates inside parent tags and push tags down only when later queries split the interval.
Implicit & Persistent Segment Trees — Allocate sparse nodes on demand over `[0, 10⁹]` and path-copy `O(log n)` nodes to query historical versions.
2-D Segment Tree — Segment tree of segment trees answering arbitrary non-invertible 2-D range min/max updates.
Sparse Matrix (COO & Compressed Sparse Row) — Pack sparse matrices and static graphs into `row_ptr`, `col_idx`, and `values` arrays for cache-fast scans.

04 — Specialist topics

Senior / staff engineering

Choose specialist branches that match your role, such as sketches, storage or geometry. Senior and staff engineering also require design, technical judgment and leadership beyond this algorithms map.

Probabilistic Filters & Sketches

Bloom Filters — Use hashed bit probes to prove absence; inserted items remain present when bits are never incorrectly cleared.
Counting Bloom Filter — Support deletion of known inserted items with counters; prevent overflow and never delete uncertain members.
Cuckoo Filter — Store fingerprints in alternative buckets; delete only known inserted items and handle insertion failure near capacity.
Count-Min Sketch — Estimate item frequencies from rows of hashed counters; nonnegative updates give one-sided overestimation.
HyperLogLog (Distinct Cardinality) — Estimate distinct counts from leading-zero hash registers; precision controls register count and relative error.
Quotient Filter — Split a fingerprint into a bucket quotient and stored remainder while preserving runs for lookup and deletion.
Xor Filter — Build a static membership filter by assigning fingerprints so a small XOR lookup reconstructs each inserted fingerprint.
Binary Fuse Filter — Arrange the hash graph in segments to build a compact static approximate-membership filter.
Blocked Bloom Filter — Keep an item's bit probes within a small block to trade cache locality against false-positive behavior.
MinHash & Jaccard Similarity — Compare sampled minimum hashes to estimate how strongly two sets overlap without retaining every element.
SimHash & Angular Similarity — Accumulate signed feature votes into a compact signature whose Hamming distance approximates angular similarity.
Probability, Hashing & Sketch Error — Distinguish hash collisions, bias, one-sided error, variance, and confidence before choosing a sketch and its parameters.

Storage Engines, Vector Search & Distributed CS

B-Tree (Page-Oriented Multiway Search) — Pack hundreds of keys per 4 KB–16 KB page so billion-row indexes stay 3–4 disk hops tall.
B+ Tree (Database Clustered & Secondary Indexes) — Separator-only internal nodes + sibling-linked leaf pages powering PostgreSQL/MySQL range scans.
Write-Ahead Log (WAL) & Crash Recovery — Append-only sequential durability before mutating in-memory pages or memtables.
LSM Trees, SSTables & Compaction — Combine Skip-List memtables, immutable sorted SSTable runs, k-way heap merge compaction, and Bloom filters.
Consistent Hashing & Virtual Nodes — Hash servers and keys onto a 2³² ring with virtual nodes so scaling moves only ~1/N keys.
Rate Limiting: Token Bucket, Leaky Bucket & Sliding Log — Protect distributed APIs from burst overload with O(1) token buckets and sliding-window counters.
k-d Tree (Multidimensional Splitting) — Cycle coordinate hyperplane splits for low-dimensional nearest-neighbor and orthogonal box search.
Quadtree & R-Tree (Spatial & Geo Indexes) — Recursive 4-quadrant splits and minimum-bounding-rectangle hierarchies for maps and game worlds.
Spatial Hash Grid & Geohash — Quantize coordinates into cell buckets or Z-order prefix strings for fast local neighbor queries.
Vector Indexing: Flat k-NN, IVF, PQ & HNSW — Escape O(N·d) brute-force embedding scans via Voronoi IVF partitions, PQ codebooks, and HNSW graphs.
Replicated Logs & Raft Leader Consensus — Quorum majorities, randomized election timeouts, and log-matching safety across faulty nodes.

Streaming Statistics & Quantile Sketches

Streaming Models & Error Guarantees — Distinguish one-pass memory limits, rank error, value error, mergeability, and the meaning of a probabilistic guarantee.
Count Sketch — Use signed hash counters and median estimates to cancel collision noise in frequency estimates.
Misra–Gries Frequent Items — Cancel groups of competing items to retain candidates for values that exceed a chosen frequency threshold.
Space-Saving Heavy Hitters — Replace a least-frequent tracked candidate while preserving an error bound on its estimated count.
K-Minimum Values Distinct Sketch — Retain the smallest distinct hash values and estimate set cardinality from the sampling threshold.
Theta Sketch & Set Operations — Use a shared hash threshold to estimate distinct counts while supporting unions, intersections, and set differences.
Compressed Probabilistic Counting — Encode coupon observations to estimate distinct counts with a compact probabilistic summary.
KLL Quantile Sketch — Compact weighted sample levels to estimate ranks and quantiles using bounded memory.
Relative Error Quantiles Sketch — Allocate more rank accuracy toward a chosen distribution tail instead of using a uniform rank-error target.
t-Digest — Merge ordered weighted centroids with finer resolution near distribution tails for practical percentile estimates.
DDSketch — Map magnitudes into logarithmic buckets to estimate quantile values with a controlled relative error.
VarOpt Weighted Sampling — Keep a bounded weighted sample designed for low-variance estimates of subset totals.

Network Flow, Cuts & Matching

Flow Networks & Residual Edges — Model capacities and conservation, then represent both additional flow and reversible choices in a residual graph.
Ford–Fulkerson Augmenting Paths — Increase flow along a residual source-to-sink path and allow later paths to undo earlier choices.
Edmonds–Karp Maximum Flow — Choose each augmenting path with BFS so path lengths bound the number of repeated augmentations.
Dinic's Blocking-Flow Algorithm — Build a BFS level graph and send a blocking flow before rebuilding the reachable levels.
Max-Flow Min-Cut & Reductions — Read a minimum cut from residual reachability and use capacity models to solve separation problems.
Bipartite Matching & Alternating Paths — Grow a matching by flipping an alternating path between unmatched vertices on opposite sides.
Hopcroft–Karp Matching — Batch shortest augmenting paths with BFS layers to accelerate maximum bipartite matching.
Minimum-Cost Flow — Augment along residual paths while accounting for edge costs and reduced-cost potentials.
Hungarian Assignment Algorithm — Adjust dual labels and alternating paths to find a minimum-cost one-to-one assignment.

Computational Geometry

Orientation & Robust Geometric Predicates — Use cross-product signs to distinguish left turns, right turns, and collinearity while handling precision deliberately.
Line Segment Intersection — Combine orientation tests with bounding checks to handle crossings, touching endpoints, and collinear overlap.
Shoelace Polygon Area — Sum oriented edge contributions around a polygon and preserve the distinction between signed and absolute area.
Point-in-Polygon Queries — Use ray crossings or winding counts, with an explicit boundary policy, to classify a query point.
Convex Hull: Monotone Chain — Sort points and remove inward turns while building the lower and upper boundary chains.
Rotating Calipers — Advance supporting contacts around a convex polygon to find extremal pairs without checking every pair.
Closest Pair of Points — Split points by coordinate and inspect a bounded neighborhood in the merge strip.
Sweep-Line Segment Intersections — Maintain an ordered active set and event queue as segment crossings change the sweep order.
Voronoi Diagrams — Partition the plane by nearest sites and relate cell boundaries to distance comparisons.
Delaunay Triangulation — Use the empty-circumcircle condition to connect sites and understand its dual relationship with Voronoi cells.

Advanced String Algorithms & Compressed Indexes

LCP Array & Suffix Comparisons — Store common-prefix lengths between neighboring suffixes and combine them with range-minimum queries.
Manacher's Palindrome Algorithm — Reuse mirror radii inside the current rightmost palindrome to avoid repeating character comparisons.
Palindromic Tree (Eertree) — Represent distinct palindromes as nodes linked by longest palindromic suffixes while characters arrive.
Burrows–Wheeler Transform — Reorder text through sorted suffix or rotation order so repeated contexts become easier to compress and index.
Wavelet Tree & Rank/Select — Partition symbols recursively and use bitvector rank information to answer sequence range queries.
FM-Index & Backward Search — Combine the Burrows–Wheeler transform with rank queries to narrow the suffix interval matching a pattern.
SA-IS Induced Suffix Sorting — Classify suffix types, sort selected LMS substrings, and induce the remaining suffix order.
Bit-Parallel String Matching — Pack multiple pattern states into machine-word bits and update them together for each text symbol.

Advanced Trees & Offline Queries

Euler Tour & Subtree Flattening — Record entry and exit positions so a rooted subtree becomes a contiguous interval in an array.
Lowest Common Ancestor Queries — Combine ancestor jumps or Euler-tour range minima to answer where two root paths meet.
Heavy-Light Decomposition — Choose heavy child edges and turn a tree path into a logarithmic number of array intervals.
Centroid Decomposition — Recursively remove balanced separator vertices to organize tree distance and path computations.
Rerooting Dynamic Programming — Pass subtree contributions in both directions so one traversal result can answer every possible root.
Small-to-Large Set Merging — Merge smaller containers into larger ones so each item changes ownership only logarithmically often.
Mo's Offline Range Queries — Reorder range queries so small endpoint adjustments reuse a maintained answer.
Splay Tree — Rotate an accessed node toward the root and analyze the cost over a sequence of operations.
Link-Cut Trees — Maintain preferred paths in a changing forest to support links, cuts, and path aggregates.
Virtual Trees for Marked Nodes — Compress a selected set of tree vertices and their LCAs into a smaller tree for query-specific work.

Advanced DP, Convolution & Transforms

Meet-in-the-Middle Search — Split an exponential choice space into two halves and combine their partial results.
Divide-and-Conquer DP Optimization — Restrict split-point searches recursively when the recurrence has provably monotone optimal choices.
Knuth Optimization — Narrow interval-DP split searches only after proving the required quadrangle and monotonicity conditions.
Convex Hull Trick — Rewrite transitions as line evaluations and maintain the lower or upper envelope under the required ordering assumptions.
Li Chao Segment Tree — Keep the better line at interval midpoints to support line insertion and extremum queries over a bounded domain.
Polynomial Convolution — Combine coefficient arrays by summing products whose indices contribute to the same output position.
Fast Fourier Transform — Evaluate coefficient arrays at structured roots of unity and invert the transform to accelerate convolution.
Number-Theoretic Transform — Perform Fourier-style convolution in a finite field with a suitable modulus and roots of unity.
Subset Zeta & Möbius Transforms — Aggregate values over submasks and invert the aggregation by processing one bit dimension at a time.

Compression & Information Coding

Run-Length Encoding — Encode consecutive equal values as runs and recognize when the representation can grow instead of shrink.
Huffman Prefix Codes — Repeatedly merge the two least frequent symbols or subtrees to build an optimal binary prefix code.
Arithmetic Coding — Refine a numeric interval according to symbol probabilities and emit enough bits to identify the final interval.
LZ77 Sliding-Window Compression — Replace repeated text with a backward distance and match length within a sliding dictionary window.
LZW Dictionary Compression — Grow a phrase dictionary during encoding and reconstruct the same dictionary while decoding codewords.
Delta & Variable-Length Integer Encoding — Store differences between nearby integer values and use variable-length representations when differences are small.

BigOCast algorithm learning and practice roadmap