Advanced Data Structures — Overview
Phase 4 — Advanced Data Structures (Days 39-48)
Goal: Add four specialised data structures to your toolkit — Tries, Union-Find, Segment Trees, and Advanced Graphs (Dijkstra, Bellman-Ford, MST, Tarjan). Each one is the only tool that handles a specific class of queries efficiently.
Pre-req: Phase 2 (you should be fluent with BFS/DFS, recursion, and DP).
What You'll Cover
| # | Module | Days | Killer use case |
|---|---|---|---|
| 4.1 | Tries | 39-40 | Prefix queries on millions of words. O(L) per insert / lookup where L = key length. |
| 4.2 | Union-Find | 40-42 | Online connectivity queries. Amortised O(α(n)) per union/find — effectively constant. |
| 4.3 | Segment Trees | 42-44 | Range-sum / range-min queries with point updates in O(log n). Required for Google / Meta. |
| 4.4 | Advanced Graphs | 45-48 | Dijkstra (single-source shortest path), Bellman-Ford (negative weights / k-stops), Prim/Kruskal (MST), Tarjan (bridges & articulation points). |
How Each Module Works
Each one introduces a structure that replaces a worse approach you already know:
| Problem class | Naive approach | Phase 4 upgrade |
|---|---|---|
| "Does the dictionary contain a word with prefix X?" | hashset of all prefixes (huge) | Trie |
| "Are nodes a and b connected after these N edges are added?" | rebuild graph + DFS each query | Union-Find |
| "What's the sum / min in range [l, r] after these updates?" | rebuild prefix array each update | Segment Tree |
| "Shortest path from s to t with weighted edges?" | BFS doesn't handle weights | Dijkstra |
This is the strongest signal you've outgrown a structure: when the same operation is being repeated thousands of times against changing data, Phase 4 is where the right answer lives.
When You Can Skip Days 43-44
The 60-day schedule lists Segment Trees days 43-44 as "optional depth." This is not optional for Google / Meta-level interviews — both companies routinely ask range-query problems. It is genuinely optional for early-career roles at most other companies. Decide based on your target companies, not your time budget.
External Resources (Hand-Picked Supplements)
- William Fiset — Graph Theory (YouTube playlist) — the gold standard for animated Union-Find (path compression + rank), Segment Trees, and Dijkstra/Bellman-Ford. 10-20 min per video. Watch alongside the corresponding module.
- CP-Algorithms — Segment Tree — competitive-programming-grade reference. Skim, don't memorise. Use the lazy propagation section if a problem demands range updates (not just queries).
- Visualgo — Trie — interactive trie insertion and prefix search. Drop in your test strings to see the shared-prefix structure form.
- Codeforces EDU — DSU — short interactive lessons on Union-Find with built-in problems. Excellent post-module reinforcement.
- Stanford CS261 — Optimization — for the truly curious: the rigorous treatment of Dijkstra / Bellman-Ford / network flow.