DSA & Algorithms
Part 1 of 16 · DSA Advanced & Company FavoritesDSA Advanced & Company Favorites - Tries, Greedy, Strings, Design & More
Advanced company-favorite DSA patterns beyond the fundamentals track: tries, bits, greedy, strings, DP advanced, design, concurrency, and mock drills.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The prompt is a company favorite past the core 20
Prefer
Open the wave-2 page that matches the cue
Prefix, XOR, meetings, KMP, SCC, LRU, and print-in-order each have a page.
- Name the cue before you write code.
- State the target complexity with the pattern.
- Save mocks for after the page, not instead of it.
Alternative
Force it into a wave-1 template
Two pointers and a hash map do not grow a trie or prove a greedy choice.
- You miss the prefix structure.
- You skip the exchange argument.
- You start a full distributed design for an LRU class.
Pick the wave-2 page
Read the cue, then open one family.
- 1
Read constraints
Size, alphabet, and whether order is online. - 2
Name the cue
Prefix, bits, meetings, span, or O(1) design. - 3
Open that page
Use the ring. Do not rebuild wave-1.
Overview
Advanced company-favorite DSA patterns beyond the fundamentals track: tries, bits, greedy, strings, DP advanced, design, concurrency, and mock drills.
Why wave-2 (company favorites)
Wave-1 (dsa-interview-patterns-fundamentals) covers the core 20 patterns. Wave-2 adds company-popular gaps: Tries, bits, greedy proofs, advanced intervals, strings/KMP, math, matrix depth, D&C, advanced DP, SCC/bridges, LCA/reroot, design DS, concurrency, coding-shaped system design, and mock drills.
How FAANG / Meta / Amazon-style rounds pick patterns
Decisions
- 1
1. Read constraints
- next2. What is the cue?
- ?
2. What is the cue?
- prefix or XOR3. Trie or bitmasks
- other4. Range, string, or design?
- 3
3. Trie or bitmasks
- ?
4. Range, string, or design?
- range5. Greedy, intervals, or DP
- design6. LRU, locks, or a class API
- 5
5. Greedy, intervals, or DP
- 6
6. LRU, locks, or a class API
Lesson map
DSA Advanced & Company Favorites - Tries, Greedy, Strings, Design & More
Advanced company-favorite DSA patterns beyond the fundamentals track: tries, bits, greedy, strings, DP advanced, design, concurrency, and mock drills.
Architecture. 1. Read constraints Ready. 2. What is the cue? Ready. 3. Trie or bitmasks Ready. 4. Range, string, or design? Ready. 5. Greedy, intervals, or DP Ready. 6. LRU, locks, or a class API Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Read["1. Read constraints Ready"] Cue["2. What is the cue? Ready"] Early["3. Trie or bitmasks Ready"] More["4. Range, string, or design? Ready"] Mid["5. Greedy, intervals, or DP Ready"] Late["6. LRU, locks, or a class API Ready"] Read -->|continues| Cue Cue -->|prefix or XOR| Early Cue -->|other| More More -->|range| Mid More -->|design| Late
Company flavor (heuristics)
- Meta: design DS (LRU), tries/word search, intervals, greedy, grid BFS/DFS
- Amazon: OA arrays/windows/heaps; design; behavioral separate
- Google: harder DP/graphs, correctness proofs, clean complexity; sometimes math
- Unicorn: design + concurrency lite + Mediums under time
Wave-1 map (do NOT recreate)
| Block | Slugs |
|---|---|
| Hub | dsa-interview-patterns-fundamentals |
| 1-7 | arrays-two-pointers, sliding-window, prefix-sums, binary-search, sorting-intervals, stack-monotonic, queue-deque |
| 8-13 | linked-lists, trees-dfs, trees-bfs, BST, heaps-top-k, hashing |
| 14-17 | graphs-dfs-bfs, topo-sort, union-find, shortest-paths |
| 18-20 | dp-1d, dp-2d-knapsack-grid, backtracking |
Wave-2 pattern map (this series)
| # | Slug | Focus |
|---|---|---|
| 1 | dsa-tries-prefix-trees | Tries / Prefix Trees |
| 2 | dsa-bit-manipulation | Bit Manipulation & Bitmasks |
| 3 | dsa-greedy-algorithms | Greedy - proofs & exchange |
| 4 | dsa-intervals-advanced | Intervals - rooms, merge, sweep |
| 5 | dsa-strings-parsing-kmp-rabin | Strings - KMP & rolling hash |
| 6 | dsa-math-number-theory | Math & number theory |
| 7 | dsa-matrix-traversal | Matrix / grid depth |
| 8 | dsa-recursion-divide-conquer | Recursion & D&C |
| 9 | dsa-dp-advanced-patterns | DP advanced patterns |
| 10 | dsa-graph-advanced-scc-bridges | SCC, bridges, bipartite |
| 11 | dsa-tree-advanced-lca-reroot | LCA, rerooting, paths |
| 12 | dsa-design-datastructures | LRU/LFU, MinStack, designs |
| 13 | dsa-concurrency-multithreading-basics | Concurrency LC basics |
| 14 | dsa-system-design-lite-for-coding | Coding-round SD lite |
| 15 | dsa-mock-interview-drills | Timed mocks + checklist |
Nav: Advanced Hub -> 1..15 -> Advanced Hub. Cross-link wave-1 hub everywhere.
Practice the sets on LeetCode Explore.
Study order
- Patch wave-1 weaknesses first (hash, trees, graphs, DP).
- Walk wave-2 1->15; defer concurrency/SD-lite until design DS is solid.
- Finish with mock drills mixing both waves.
Interview pacing (45 min)
0-3 restate; 3-8 name pattern; 8-25 code; 25-35 dry-run; 35-45 complexity + follow-ups.
Big-O extras for wave-2
| Topic | Typical | Notes |
|---|---|---|
| Trie ops | O(L) | L = string length |
| Bitmask subsets | O(n 2^n) | n≤20 |
| Greedy sort+scan | O(n log n) | Prove choice |
| KMP | O(n+m) | LPS preprocess |
| SCC / bridges | O(V+E) | SCC: Tarjan or Kosaraju (directed); bridges: Tarjan low-link (undirected) |
| LCA preprocess | O(n log n) | Query O(log n) |
| LRU get/put | O(1) | Hash + DLL |
Interview Q&A
Wave-1 vs wave-2?
Answer
Wave-1 = core 20; wave-2 = company favorites often missing from first pass.
Meta phone screen?
Answer
Often design DS, BFS/DFS, intervals, greedy Mediums.
When Trie vs HashMap?
Answer
Prefix / shared dictionary paths -> Trie.
When greedy fails?
Answer
Local choice blocks global; need DP or search.
Bitmask DP limit?
Answer
Usually n≤20.
Design vs HLD?
Answer
This series coding-round shapes; not full distributed HLD.
Concurrency on LC?
Answer
Locks/barriers/print-order; language-specific primitives.
How to mock?
Answer
Use drills doc timed sets + checklist.
Cluster map
Hub. DSA Advanced & Company Favorites - Tries, Greedy, Strings, Design & More
- Tries / Prefix Trees
- Bit Manipulation & Bitmasks
- Greedy Algorithms - Proof Sketches & Exchange Arguments
- Intervals Advanced - Meeting Rooms, Merge, Sweep Priorities
- Strings - Parsing, Rolling Hash & KMP intuition
- Math & Number Theory for Interviews (gcd, mod, primes, combinatorics basics)
- Matrix Traversal - Spiral, Islands, DFS/BFS on grids
- Recursion & Divide-and-Conquer - Master theorem intuition, merge patterns
- DP Advanced - State machine DP, Digit DP intro, Interval DP, Bitmask DP
- Graphs Advanced - SCC, Bridges, Articulation, Bipartite
- Trees Advanced - LCA, Rerooting, Path aggregates
- Design Data Structures - LRU/LFU, MinStack, Snapshot, RandomizedSet
- Concurrency Interview Basics - locks, barriers, bounded buffer
- Coding-round System Design Lite - rate limiter, URL shortener coding shapes
- Mock Interview Drills - timed sets by company theme + checklist
How to pick a wave-2 pattern
Press Run. Snippets must be self-contained — no network, files, or native modules.
Press Run. Snippets must be self-contained — no network, files, or native modules.