DSA MASTER
REFERENCE
How to Use This Book
This is a recognition-first reference, not a tutorial. It assumes fluency in Java and programming fundamentals. Every topic opens with a compact concept model (recognition signals → core idea → invariant → complexity), followed by a small set of canonical problems chosen because each teaches a distinct idea, variation, or trap.
How the book is organized — and the order to learn it
Think in two layers: data structures are your vocabulary; patterns are the grammar. You need the vocabulary before the grammar makes sense — but "vocabulary" means the mechanics of each structure (declare, insert, iterate, costs), which is Part I's Java Data-Structures primer and needs zero pattern knowledge. The chapters named Arrays & Hashing, Linked Lists, Trees… in Part III are not "learn the structure" sections — they are collections of pattern problems grouped by the structure they run on. That single distinction fixes the reading order:
- Foundations first (Part I). Read the Java DS primer for pure mechanics and do the Easy structure warm-ups on each container — no patterns required. Skim Complexity.
- Patterns next (Part II → the pattern chapters). This is the real practice. For each pattern: read its card (recognition signals + code template), then work its canonical problems. When a pattern leans on a structure you're rusty on, jump back to that structure's primer section.
- Topic chapters as reference. Trees, Heaps, Graphs, Tries… are where the depth lives; you reach them through the patterns, not before them.
primer (mechanics) → patterns (practice) → topic chapters (depth). Don't read the topic problem-chapters cold before the patterns — that's exactly the confusion to avoid.
before your first problem, read The Interview Playbook — the 6-phase loop (Clarify → Examples → Brute force → Optimize → Code → Verify) that scores you as senior — and pick a track in Study Plans & Revision Cadence. Track what you've mastered in the Master Problem Index.
a few patterns stack on earlier ones. Learn them in this dependency order: recursion → backtracking → dynamic programming; arrays & hashing → prefix sum → sliding window; heaps → Dijkstra & K-way merge; stacks → monotonic stack; trees → tree-DP & tries. If a pattern feels impossible, you're usually missing its prerequisite, not the pattern itself.
Revision passes
- Revision pass — read only the callout boxes: 🔑 Key Insight, 📐 Invariant, ⚠️ Trap, 🔗 Pattern Connection. Each problem is designed to be re-absorbed in under 90 seconds.
- Interview eve — read Part II (decision tree + patterns) and Part IV (cheat sheets) only.
Colour & icon legend — the callout boxes are colour-coded so you can navigate by eye:
(blue) — the one idea that unlocks the problem.
(amber) — the property held true at every step; the backbone of correctness.
(red) — the mistake that fails the interview.
(green) — how this generalizes to the larger family.
(teal) — jargon explained; reference material.
(grey) — worked walkthroughs and secondary notes. Every "Trace it" callout is paired with an Execution Trace — an interactive slider visualization (Play / Prev / Next / Reset + draggable scrubber) that steps through the algorithm frame-by-frame on the example, showing pointer positions, tracked variables, and per-step notes.
Difficulty on practice links is badged too: Easy · Medium · Hard. A thin teal rule under a heading ("What & why…") states that section's purpose in one line.
Every problem is a self-contained unit — Problem (statement + constraints + example) → approach → code first, then a Trace it walkthrough on that code → complexity → traps → variations — so you can drill any one in isolation.
Code conventions — modern Java 17+: ArrayDeque (never Stack), getOrDefault/merge/computeIfAbsent, StringBuilder, var where it aids clarity, int[]{r,c} for grid cells, long wherever sums can overflow, and half-open intervals [lo, hi) for binary search unless noted.
Syllabus & Chapters
Every entry below is a link — click any line to jump straight to that section (works in the PDF and the HTML).
- The Interview Playbook — how to drive the room
- Study Plans & Revision Cadence
- Zero-to-Hero Roadmap — day-by-day plan
- Glossary — Words We Use Everywhere
- Part I — Foundations
- Java Data Structures — A Visual Toolkit (the primer: pure mechanics)
- Java DSA Gotchas — 20 pitfalls that cost interviews
- Complexity, Amortization & the Cost Model
- Data-Structure Operation Costs (with per-structure revision cards)
- Debugging DSA Code — trace tables, adversarial tests, top-5 bugs
- Part II — The 21 Core Patterns (algorithmic techniques)
- The "Which Pattern?" Decision Tree & Recognition Framework
- 1. Sliding Window
- 2. Two Pointers
- 3. Fast / Slow Pointers (Floyd)
- 4. Prefix Sum & Difference Arrays
- 5. Hashing (Two Sum, Group Anagrams, Longest Consecutive)
- 6. Monotonic Stack
- 7. Binary Search
- 8. Binary Search on the Answer
- 9. Top-K / Heap
- 10. K-way Merge
- 11. Merge Intervals
- 12. Sweep Line
- 13. Topological Sort
- 14. Union-Find (DSU)
- 15. Greedy
- 16. Recursion & Backtracking
- 17. Divide & Conquer
- 18. Dynamic Programming
- 19. Trie pattern
- 20. Bit Manipulation & Bitmasking
- 21. Quickselect
- + Math & Number Theory (fast expo, GCD, sieve)
- + Design & Randomized (O(1) structures, reservoir sampling)
- Part III — Data Structures in Depth (containers)
- Arrays (Matrix Mechanics, Cyclic Sort)
- Strings
- Linked Lists
- Stacks & Queues
- Trees (traversal, BST, LCA, diameter, tree DP, serialize, build)
- Heaps (streaming median, gotchas)
- Tries (implement)
- Graphs (BFS, DFS, Dijkstra, Bellman-Ford, MST, bridges/SCC, Eulerian)
- Segment Tree & Fenwick Tree
- Part IV — Cheat Sheets & Self-Check
- Master Cheat Sheets & Templates
- Appendix — Self-Check & Mastery Drills
- Master Problem Index & Tracker (all problems, checkable)
- Practice Solutions Appendix (~320 variations, hints + walkthroughs)
- Mock Interview Transcripts — Easy / Medium / Hard walkthroughs
- Traps Catalog — every [trap] callout consolidated for revision