Deep Dive 01 — How to Recognize the Pattern
Deep Dive 01 — How to Recognize the Pattern
Hey everyone! Welcome to the Deep Dives!
Here's the secret nobody tells beginners: you don't memorize 500 problems — you learn ~10 patterns and recognize which one a problem wants. The hardest part of any interview is the first 60 seconds: figuring out the approach. This deep dive gives you a decision tree from problem clues to technique.
What we will cover:
- The master decision tree
- Clue → pattern mapping
- The 8 core patterns recap
- How to read a problem for hidden hints
- Interview Questions
1. The Master Decision Tree
┌─────────────────────────────────────────────────────────────┐ │ "WHICH TECHNIQUE DO I USE?" │ ├─────────────────────────────────────────────────────────────┤ │ │ │ Is the array SORTED? │ │ ├─ find a value? → Binary Search │ │ └─ find a pair/triplet? → Two Pointers │ │ │ │ "subarray" / "substring" + longest/shortest/k? │ │ → Sliding Window │ │ │ │ "have I seen it?" / "count" / "duplicate"? │ │ → Hash Map / Set │ │ │ │ Tree or Graph? │ │ ├─ shortest path (unweighted)? → BFS │ │ └─ explore all / cycles / components? → DFS │ │ │ │ "all combinations / permutations / subsets"? │ │ → Backtracking │ │ │ │ "optimal" + choices + overlapping subproblems? │ │ → Dynamic Programming │ │ │ │ "top K" / "k largest/smallest" / "closest"? │ │ → Heap │ │ │ │ "next greater/smaller element"? │ │ → Monotonic Stack │ │ │ └─────────────────────────────────────────────────────────────┘
2. Clue → Pattern Cheat Table
| Words in the problem | Likely pattern | Chapter |
|---|---|---|
| "sorted array", "find target" | Binary Search | 11 |
| "pair", "two/three numbers sum to" | Two Pointers / Hashing | 06 / 04 |
| "longest/shortest substring", "window size k" | Sliding Window | 07 |
| "duplicate", "seen", "frequency", "count" | Hash Map / Set | 04 |
| "reverse list", "cycle", "middle node" | Linked List (slow/fast) | 08 |
| "valid parentheses", "next greater" | Stack / Monotonic Stack | 09 |
| "level order", "shortest steps", "nearest" | BFS | 18 |
| "connected", "islands", "paths in grid" | DFS | 18 |
| "all subsets / permutations / combinations" | Backtracking | 19 |
| "max/min ways", "can you reach", "optimal" | Dynamic Programming | 21 / 22 |
| "top K", "k closest", "k largest" | Heap | 16 |
| "prefix", "autocomplete", "starts with" | Trie | 17 |
3. The 8 Core Patterns (80% of Problems)
1. Two Pointers — sorted pairs, in-place 2. Sliding Window — contiguous subarray/substring 3. Hashing — seen-before, frequency, grouping 4. Binary Search — sorted search, search-on-answer 5. BFS / DFS — trees & graphs 6. Backtracking — generate all possibilities 7. Dynamic Programming— optimal + overlapping subproblems 8. Heap — top-K, streaming, scheduling
If you can confidently apply these 8, you can solve the vast majority of interview questions. Everything else is a variation or combination of them.
4. Reading a Problem for Hidden Hints
┌─────────────────────────────────────────────────────────────┐ │ HINTS HIDING IN THE CONSTRAINTS │ ├─────────────────────────────────────────────────────────────┤ │ │ │ n ≤ 20 → exponential OK → Backtracking / bitmask │ │ n ≤ 100-500 → O(n²) or O(n³) DP is fine │ │ n ≤ 10⁵ → need O(n log n) or O(n) │ │ n ≤ 10⁹ → O(log n) → Binary Search / math │ │ "modulo 10⁹+7" → counting DP (answer is huge) │ │ "already sorted" → Binary Search or Two Pointers │ │ "return any valid"→ Greedy might work │ │ │ │ The INPUT SIZE often tells you the required complexity, │ │ which points straight at the technique! │ └─────────────────────────────────────────────────────────────┘
5. A 5-Step Approach for Any Problem
1. RESTATE the problem in your own words 2. Note the CONSTRAINTS (n size → target complexity) 3. Find the PATTERN (use the decision tree above) 4. Start with BRUTE FORCE, then optimize toward the target 5. TRACE a small example by hand before coding
Interview Questions — Quick Fire!
Q: A problem mentions a sorted array and asks for a pair summing to a target. Approach?
"Sorted plus pair-sum points to two pointers — start and end moving inward based on whether the current sum is too big or small, O(n) time and O(1) space. If it weren't sorted, I'd use a hash map for O(n)."
Q: How do constraints hint at the intended complexity?
"The input size bounds the acceptable time complexity. n up to 20 suggests exponential backtracking or bitmasking is fine; n up to 10⁵ rules out O(n²) and demands O(n log n) or better; n up to 10⁹ means you need O(log n) like binary search or a math formula. Matching the bound narrows the technique fast."
Q: What clues point to dynamic programming?
"Words like 'maximum', 'minimum', 'number of ways', or 'can you reach', combined with making a sequence of choices where subproblems overlap. If greedy gives a counterexample but the problem has optimal substructure, it's DP."
Q: What's your first move when you see a new problem?
"Restate it, read the constraints to estimate the target complexity, then map the keywords to a pattern using a mental decision tree. I start from a brute force I'm sure is correct and optimize toward the required complexity, tracing a tiny example before writing code."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Decision tree | Map problem clues → technique. |
| 8 core patterns | Cover ~80% of problems. |
| Constraints | Input size reveals target complexity. |
| 5-step approach | Restate → constraints → pattern → brute force → trace. |
What's Next?
Deep Dive 02: Complexity Proofs & Amortized Analysis — go beyond memorizing Big-O to actually proving it, so nothing in an interview can shake you.
Keep coding, keep grinding! See you in the next one!
Post a Comment