Docs
/
DSA Advanced
Chapter 20
20 — Interview Patterns & Problem-Solving Framework
Problem-Solving Framework
1. UNDERSTAND — Read carefully, identify inputs/outputs, ask clarifying questions
2. EXAMPLES — Walk through examples, find edge cases
3. PATTERN — Identify which pattern/data structure fits
4. PLAN — Write pseudocode, define approach
5. CODE — Implement cleanly
6. TEST — Trace through examples, check edge cases
7. OPTIMIZE — Can we improve time/space?
Pattern Recognition Cheat Sheet
| If you see... | Think... | Technique |
|---|---|---|
| "Sorted array" | Binary search | Two pointers, BS on answer |
| "Subarray/substring" | Sliding window | Fixed/variable window |
| "Tree/graph traversal" | BFS/DFS | Queue (BFS), recursion (DFS) |
| "Shortest path" | BFS (unweighted), Dijkstra | Priority queue |
| "Connected components" | Union-Find or DFS | |
| "Top K / K-th element" | Heap | Min-heap of size K |
| "Prefix/suffix" | Trie | Also prefix sums |
| "Choices at each step" | DP or Backtracking | Overlapping → DP, distinct → backtrack |
| "Min/max of all subarrays" | Monotonic stack/deque | |
| "Intervals" | Sort + greedy | Sort by start or end |
| "Permutations/combinations" | Backtracking | |
| "Optimize with constraint" | DP (knapsack family) | |
| "Count ways" | DP | |
| "Unique elements/pairs cancel" | XOR / hashing | |
| "Matrix/grid" | BFS/DFS, DP on grid |
Complexity Targets
| n | Target Complexity | Typical Approach |
|---|---|---|
| ≤ 10 | O(n!) | Backtracking, brute force |
| ≤ 20 | O(2^n) | Bitmask DP, backtracking |
| ≤ 500 | O(n³) | Floyd-Warshall, interval DP |
| ≤ 5000 | O(n²) | DP, two nested loops |
| ≤ 10^6 | O(n log n) | Sorting, binary search, heap |
| ≤ 10^8 | O(n) | Two pointers, sliding window, hashing |
| > 10^8 | O(log n) or O(1) | Math, binary search |
Common Edge Cases
Arrays: empty, single element, all same, sorted, reverse sorted
Strings: empty, single char, all same chars, palindrome
Trees: null, single node, skewed (linked list), perfect binary
Graphs: disconnected, single node, cycle, self-loop
Numbers: 0, 1, negative, MAX_INT, MIN_INT
Data Structure Selection
| Need | Use |
|---|---|
| Fast lookup | HashMap / HashSet — O(1) |
| Sorted order | TreeMap / sorted array — O(log n) |
| FIFO processing | Queue |
| LIFO / matching | Stack |
| Priority access | Heap / Priority Queue |
| Range queries + updates | Segment Tree / Fenwick Tree |
| Prefix matching | Trie |
| Dynamic connectivity | Union-Find |
| Unique + ordered | LinkedHashSet |
Interview Communication Template
1. "Let me make sure I understand the problem..."
→ Restate the problem, clarify constraints
2. "I'm thinking about using [pattern] because..."
→ Explain your reasoning
3. "The time complexity would be O(...) because..."
→ Analyze before coding
4. "Let me trace through this example..."
→ Verify your approach works
5. "One edge case to consider is..."
→ Show thoroughness
6. "We could optimize this by..."
→ Show you can improve
DP vs Greedy vs Backtracking
| DP | Greedy | Backtracking | |
|---|---|---|---|
| Explores | All subproblems | One choice per step | All valid paths |
| Optimal | Always (if correct) | Only if greedy works | Finds all solutions |
| Time | Polynomial | Often O(n log n) | Exponential (pruned) |
| Overlap | Yes (stores results) | No | No |
| Use when | Overlapping subproblems | Local optimal = global | Enumerate/count all |
Common Mistakes
❌ Not handling empty input
❌ Off-by-one errors in binary search (lo < hi vs lo <= hi)
❌ Not considering negative numbers
❌ Modifying input array unintentionally
❌ Not using [...array] when pushing to results (reference bug)
❌ Integer overflow (use BigInt in JS for large numbers)
❌ Wrong graph: directed vs undirected
❌ BFS without visited check → infinite loop
❌ Forgetting to sort before greedy/two-pointer
Key Takeaways
- Pattern recognition is the most important interview skill — drill the table above
- Match input size to complexity target to narrow approach
- Always consider edge cases before coding
- Communicate your thought process — interviewers value reasoning
- Practice the framework: understand → pattern → plan → code → test → optimize
- When stuck: simplify the problem, solve brute force first, then optimize