Advanced Algorithms
Advanced Algorithms — Overview
Mark when done:
Phase 5 — Advanced Algorithms (Days 49-56)
Goal: Cover the four advanced topic clusters that show up in senior / FAANG interviews: advanced DP variants, math & bit manipulation, string algorithms, and interval algorithms.
Pre-req: Phase 2 DP and Phase 4 advanced data structures.
What You'll Cover
| # | Module | Days | Why it's here |
|---|---|---|---|
| 5.1 | Advanced DP | 49-50 | Bitmask DP, DP on Trees (House Robber III), LIS in O(n log n), Interval DP. The DP variants that don't fit the 1D / 2D-grid templates from Phase 2. |
| 5.2 | Math & Bit Manipulation | 51-52 | XOR identity, fast exponentiation, bit counting, integer overflow handling. Easy points in interviews — and the quickest knowledge gap to close. |
| 5.3 | String Algorithms | 55-56 (optional) | KMP, Z-function, Rabin-Karp. Skim the concepts; do at least one KMP problem. |
| 5.4 | Intervals | 53-54 | Merge / insert / non-overlapping / arrows / intersections. The interval-merging template solves all five with minor variations. |
How to Use This Phase
Phase 5 is broad and shallow by design. You are not expected to master every variant — you are expected to recognise them so you don't freeze in an interview. For each module:
- Read the README's worked example.
- Solve 1-2 problems to lock in the recipe.
- If you struggle, add the topic to your redo queue and revisit weekly.
The most common mistake in Phase 5 is treating it like Phase 1 ("must master every problem"). Don't. Get acquainted with each topic; deep-dive only the ones your target companies are known to ask.
What's Critical vs What's Optional
| Topic | For Google / Meta | For most other companies |
|---|---|---|
| Advanced DP (Bitmask, DP on Trees) | Required | Optional |
| Math & Bit Manipulation | Required (esp. Sum of Two Integers, Pow(x, n)) | Required (Single Number is universal) |
| Intervals | Required | Required |
| String Algorithms (KMP, Z-function) | Often required | Skim only |
External Resources (Hand-Picked Supplements)
- Algorithms Illuminated Part 1 (Tim Roughgarden — free PDF) — the most readable rigorous treatment of divide-and-conquer, master theorem, and sorting. The merge-sort
O(n log n)derivation is the proof that makes Big-O feel less arbitrary. - Errichto — Bitmask DP (YouTube) — 25-min video on bitmask DP with worked examples. Watch before Day 49.
- CP-Algorithms — String Algorithms — KMP, Z-function, Aho-Corasick, suffix arrays. Use the KMP section for the optional string-algorithms module.
- Hackerrank — Bit Manipulation Tutorial — short interactive lessons covering XOR identity, bit manipulation tricks, and integer-overflow gotchas.
- LeetCode Discuss — DP on Trees Master Post — the canonical write-up of the DP-on-trees pattern with House Robber III as the worked example.