A login service keeps a sorted list of active user IDs and calls contains — or a handwritten linear loop — on every request. The data is already ordered. Nobody “wrote a bad data structure.” They ran the wrong procedure on a layout that already allowed binary search.
An algorithm is a named procedure with an invariant, a cost, and a failure mode. Memorizing names does not skill you up. Matching the job to the procedure does.
This post is the series glossary and index: the words later posts will use without re-defining, a JDK map, and a living table of every algorithm in the series. Later posts link here instead of re-lecturing complexity theory.
How to use this page
You do not need to read fifty posts in textbook order.
- Jump by family — search, sort, graphs, strings, numbers, DP, or systems — if you already know the name and want the pain it targets.
- Follow Start here if you want the algorithms that show up in real code (and interviews) first.
- Treat (upcoming) titles as the map, not a 404. Published titles are links. Titles marked (upcoming) are not live yet — do not invent a URL. This page is updated when one ships.
Each algorithm post stands alone for its own title. Families, the glossary, and the cargo-cult failure modes live here.
Layout vs procedure
The same membership check has a different bill depending on the procedure, even when the layout is already right:
boolean isActive(List<Long> sortedIds, long id) {
return sortedIds.contains(id); // walks a list that was already ordered
}
boolean isActive(long[] sortedIds, long id) {
return Arrays.binarySearch(sortedIds, id) >= 0;
}Both compile. Only the second stays cheap as n grows. Same layout, wrong procedure, different bill.
Data Structures Roadmap owns the layout (ADT vs implementation, contiguous vs linked, how to read a Big-O table). This series does not re-teach those. It owns the procedure you run on a layout you already chose.
| Job | Layout (data-structures) | Procedure (this series) |
|---|---|---|
| Unique membership | HashSet | Usually none — the layout is the lookup |
| Sorted lookup | Sorted array / list | Binary search |
| Unweighted shortest path | Adjacency list | BFS |
| Next-best item | Heap / PriorityQueue | Heap operations; Dijkstra consumes a heap |
| ”Maybe in the set” | Bloom filter | The structure is the algorithm |
Terms this series will not re-teach
Read these once. Later posts link here instead of repeating them.
Algorithm vs data structure. A data structure is a layout. An algorithm is a procedure you run on it. Confusing the two is how a sorted ArrayList still pays linear contains.
Correctness vs complexity. Correctness is the right answer under the claimed invariant. Complexity is how cost grows with n. A correct bubble sort is still the wrong default at a million rows.
In-place. Rearranges existing storage instead of allocating a second copy. Quicksort’s selling point; merge sort usually is not.
Stable (sorts). Equal keys keep their original relative order. Java’s object Arrays.sort is stable (Timsort); primitive Arrays.sort does not promise stability.
Online vs offline. Offline: you see the whole input first. Online: the input arrives as a stream — reservoir sampling, a running Kadane, a token bucket on each request.
Worst vs amortized vs expected. Worst-case is the hostile input. Amortized averages a long sequence. Expected averages random choices or data. Expected is not a guarantee on the next call.
Greedy vs DP vs divide-and-conquer vs backtracking. Greedy takes the local best and never revisits it — legal when a greedy-choice property holds. Dynamic programming is for repeated subproblems with optimal substructure; you write a recurrence and fill a table (or memoize). Divide-and-conquer splits, solves independently, and combines. Backtracking tries a choice, recurses, and undoes. Later posts use those four words without a lecture.
The skill path
Four stages. Stay until the “you are ready” line is true; skipping a stage is how people memorize Dijkstra without being able to say why BFS was enough.
Beginner — search, sorts, and graph walks
Binary search, two pointers, sliding window, prefix sums, quadratic sorts, merge, quick, BFS, DFS.
You are ready when you can say why binary search needs a sorted invariant, why Arrays.sort is not “quicksort the textbook,” and why BFS is a queue.
Intermediate — better sorts, weighted paths, strings, DP
Heap/counting/Timsort, Dijkstra, topological sort, cycle detection, KMP, knapsack, LCS, edit distance.
You are ready when you can name the extra invariant (non-negative weights, DAG, no leftover prefix), not only the nested loop.
Advanced — remaining graphs, sketches, systems
A*, Bellman-Ford, Floyd-Warshall, MST, SCC, remaining string matchers, sketches, consistent hashing, rate limits, consensus at awareness depth.
You are ready for the capstone when you can name the job each is for, not only the loop.
Choose — match the job to the procedure
A decision guide: given a job, which procedure, and which JDK call if there is one. Pick the Right Algorithm: Match the Job to the Procedure (upcoming).
JDK / library map
What to call, not reimplement.
| Job | Call |
|---|---|
| Sorted object arrays / lists | Arrays.sort / Collections.sort (Timsort — not textbook quicksort) |
Primitive arrays (int[], …) | Dual-Pivot Quicksort (Arrays.sort) |
| Sorted lookup | Arrays.binarySearch |
| Shuffle | Collections.shuffle (Fisher-Yates) |
| Next-best / Dijkstra frontier | PriorityQueue |
| Hash / HMAC / AES | MessageDigest / javax.crypto / a vetted library |
| gzip / deflate | java.util.zip |
| Rate limits | Token Bucket / Leaky Bucket (Bucket4j as a pointer, not a tutorial) |
Call the library unless a later post names a reason not to. Do not hand-roll crypto, gzip, or Raft. Arrays.binarySearch encodes a miss as a negative insertion point — the binary-search post owns that encoding.
When algorithms are cargo-cult
The tell is a named loop with the wrong invariant.
- Sorting on every lookup to “make binary search legal.” You paid
O(n log n)to avoid anO(n)scan. - Dijkstra on an unweighted graph. BFS already returns shortest path.
- Hand-rolling Timsort, gzip, or Raft. Object
Arrays.sortis Timsort.java.util.zipis deflate. - A DP table for a greedy job that already has the exchange argument. If greedy-choice holds, the table is homework.
- Treating Bloom or HyperLogLog as exact. Maybe-yes and plus-or-minus are the point.
The healthy trigger is a job you can point at. Name it. If you cannot, do not name an algorithm either.
The catalog
Published titles are links. Titles marked (upcoming) are not live yet. Jump by family; do not treat CLRS chapter order as a reading order.
Search and scan
| Algorithm | Pain it targets | Post |
|---|---|---|
| Binary Search | Sorted lookup without a linear scan | Binary Search: Cut the Space in Half When the Data Is Already Ordered |
| Two Pointers | One pass from both ends instead of nested loops | Two Pointers: One Pass From Both Ends Instead of a Nested Loop |
| Sliding Window | Grow/shrink a range without restarting | Sliding Window: Grow and Shrink a Range Without Restarting the Scan |
| Prefix Sums | Range answer after one precompute | Prefix Sums: Answer a Range in O(1) After One Precompute |
| Kadane | Max subarray without every slice | Kadane: Maximum Subarray Without Trying Every Slice |
| Merge Intervals | Collapse overlaps | Merge Intervals: Collapse Overlaps Instead of Sorting the Same Range Twice |
Sorting
| Algorithm | Pain it targets | Post |
|---|---|---|
| Quadratic Sorts | Small n / Timsort runs; not production defaults | Quadratic Sorts: Insertion, Selection, and Why Bubble Survives Only in Interviews |
| Merge Sort | Stable divide-and-conquer | Merge Sort: Stable Divide-and-Conquer When You Can Afford the Extra Array |
| Quicksort | In-place partition; pivot is the algorithm | Quicksort: Partition in Place and Why the Pivot Policy Is the Algorithm |
| Heapsort | O(n log n) little extra memory | Heapsort: Sort With a Heap When You Need O(n log n) and Little Extra Memory |
| Counting Sort | Small key universe | Counting Sort: Rank by Frequency When the Key Universe Is Small |
| Radix Sort | Digit passes | Radix Sort: Digit Passes When Comparison Is the Wrong Primitive |
| Timsort | What Arrays.sort runs on objects | Timsort: What Arrays.sort Actually Runs on Objects |
| External Sort | File does not fit in RAM | External Sort: K-Way Merge When the File Does Not Fit in RAM |
Graphs and paths
Strings
| Algorithm | Pain it targets | Post |
|---|---|---|
| KMP | Pattern search without sliding back | KMP: Find a Pattern Without Sliding Back on the Text |
| Rabin-Karp | Rolling hash, many pattern checks | Rabin-Karp: Rolling Hash When You Need Many Pattern Checks |
| Boyer-Moore | Skip ahead on a late mismatch | Boyer-Moore: Skip Ahead When the Mismatch Is Near the End |
| Aho-Corasick | Many patterns, one pass | Aho-Corasick: Many Patterns, One Pass Over the Text |
Numbers and sampling
| Algorithm | Pain it targets | Post |
|---|---|---|
| Euclid GCD | GCD, then extended coefficients | Euclid GCD: Subtract, Then Mod, Then Extended Coefficients |
| Binary Exponentiation | Logarithmic multiplies | Binary Exponentiation: pow(base, exp) in Logarithmic Multiplies |
| Fisher-Yates | Unbiased in-place shuffle | Fisher-Yates: Shuffle in Place Without Bias |
| Reservoir Sampling | One-pass sample when n is unknown | Reservoir Sampling: One Pass When You Do Not Know n Up Front |
Dynamic programming and greedy
| Algorithm | Pain it targets | Post |
|---|---|---|
| 0/1 Knapsack | Pick or skip; each item once | 0/1 Knapsack: Pick or Skip When Each Item Exists Once |
| Coin Change | Unbounded combinations | Coin Change: Unbounded Combinations When the Item Can Repeat |
| LCS | Shared subsequence, not contiguous | LCS: Longest Shared Subsequence Without Requiring Contiguous |
| LIS | Increasing subsequence in n log n | LIS: Longest Increasing Subsequence in n log n |
| Edit Distance | Insert / delete / substitute grid | Edit Distance: Insert, Delete, Substitute as a Costed Grid |
| Huffman | Prefix code from frequencies | Huffman Coding: Build a Prefix Code From Frequencies |
| Interval Scheduling | Earliest finish frees the room | Interval Scheduling: Always Take the Finish That Frees the Room Soonest |
| Backtracking | Search with undo | Backtracking: Search With Undo When the Next Choice Depends on the Last |
Systems
| Algorithm | Pain it targets | Post |
|---|---|---|
| Consistent Hashing | Move few keys when a node joins or dies | Consistent Hashing: Move Few Keys When a Node Joins or Dies |
| Token Bucket | Bursts, then an average rate | Token Bucket: Allow Bursts, Then Enforce an Average Rate |
| Leaky Bucket | Smooth bursts into a steady drain | Leaky Bucket: Smooth Bursts Into a Steady Drain |
| Exponential Backoff | Retry with jitter | Exponential Backoff: Retry With Jitter Instead of a Thundering Herd |
| Two-Phase Commit | All prepare, then all commit — it blocks | Two-Phase Commit: All Prepare, Then All Commit — and Why It Blocks |
| Raft | Leader election + log (awareness) | Raft: Elect a Leader and Replicate a Log (Awareness, Not a From-Scratch Cluster) |
| HyperLogLog | Approximate distinct count | HyperLogLog: Approximate Distinct Count in Tiny Memory |
| Count-Min Sketch | Approximate frequencies | Count-Min Sketch: Approximate Frequencies When Exact Maps Do Not Fit |
| LZ77 / DEFLATE | Compression behind zip and gzip | LZ77 and DEFLATE: Sliding-Window Compression Behind zip and gzip |
Capstone
| Algorithm | Pain it targets | Post |
|---|---|---|
| Choose | Match the job to the procedure | Pick the Right Algorithm: Match the Job to the Procedure (upcoming) |
Start here
Book order is a catalog, not a curriculum. Use interview-and-production frequency, not chapter numbers. Linked titles are live; (upcoming) titles are not.
- Binary Search: Cut the Space in Half When the Data Is Already Ordered
- Two Pointers: One Pass From Both Ends Instead of a Nested Loop
- Sliding Window: Grow and Shrink a Range Without Restarting the Scan
- Merge Sort: Stable Divide-and-Conquer When You Can Afford the Extra Array
- Quicksort: Partition in Place and Why the Pivot Policy Is the Algorithm
- BFS: Level Order, Shortest Unweighted Path, and Why the Frontier Is a Queue
- DFS: Finish Times, Recursion vs an Explicit Stack, and What a Cycle Looks Like
- Dijkstra: Shortest Path When Every Edge Weight Is Non-Negative
- Topological Sort: Order a DAG Before You Run the Work
- KMP: Find a Pattern Without Sliding Back on the Text
Wave 3–7 and the capstone live in the catalog; do not treat book/CLRS chapter order as the reading order.
Cheat sheet
Question: what job is hot, and which procedure makes it cheap?
Algorithm: named procedure + invariant + cost + failure mode
Layout: data-structures owns it; this series runs a procedure on it
Invariant: sorted, non-negative weights, DAG, no leftover prefix
JDK defaults: Arrays.sort, Arrays.binarySearch, Collections.shuffle, PriorityQueue
Do not roll: crypto, gzip/deflate, Raft, Timsort
Sketches: Bloom / HyperLogLog / Count-Min are approximate on purposeDo:
- Name the hot job before you name an algorithm.
- Prefer the JDK call in the map unless a later post names a reason not to.
- Check the invariant (sorted, non-negative, DAG) before you run the loop.
Don’t:
- Sort on every lookup to make binary search legal.
- Run Dijkstra on an unweighted graph when BFS already answers.
- Hand-roll Timsort, compression, or Raft.
- Treat Bloom filters or HyperLogLog as exact.
Wrap-up
Algorithms are named procedures with an invariant, a cost, and a failure mode. Search and scan cover most interview frequency; sorts, graphs, strings, DP, and systems cover jobs those loops cannot do at size.
The catalog is the map. Every (upcoming) row is intended coverage, not a dead link. Start with binary search if you are skilling up from scratch.