Stage 1 · Code
Interview Preparation
FAANG Coding Patterns
Common patterns: sliding window, two pointers, DFS/BFS, backtracking, DP, greedy, monotonic stack.
Pattern Recognition
FAANG interviews test ~20 core patterns. Recognizing the pattern transforms a 45-min struggle into a 15-min solution. Key: identify the pattern from problem statement keywords, then apply the template.
Core Patterns
| Pattern | Keywords | Template | Classic Problems |
|---|---|---|---|
| Sliding Window | subarray/substring, max/min/longest, constraint | Expand right, shrink left while invalid | Max sum subarray size k, Longest substring ≤ K distinct, Min window substring |
| Two Pointers | sorted array, pair sum, palindrome, reverse | left=0, right=n-1, move based on sum | Two Sum II, 3Sum, Container with Most Water, Valid Palindrome |
| Fast/Slow Pointers | cycle detection, middle, linked list | slow=head, fast=head, move 1/2 steps | Linked List Cycle, Middle of List, Cycle Start |
| DFS/Backtracking | all combinations/permutations, subsets, N-Queens | recurse with state, undo on backtrack | Subsets, Permutations, N-Queens, Sudoku Solver |
| BFS | shortest path, level order, multi-source | queue, process level by level | Binary Tree Level Order, Rotting Oranges, Word Ladder |
| Dijkstra/PQ | weighted shortest path, min cost | min-heap by distance | Network Delay Time, Cheapest Flights |
| Monotonic Stack | next greater/smaller, histogram | maintain increasing/decreasing stack | Next Greater Element, Largest Rectangle, Daily Temperatures |
| DP (1D) | fib, knapsack, house robber, LIS | dp[i] = best using first i | Fibonacci, Coin Change, House Robber, LIS |
| DP (2D/Grid) | grid paths, matrix, edit distance | dp[i][j] = best for subgrid | Unique Paths, Min Path Sum, Edit Distance, LCS |
| Bitmask DP | TSP, assignment, subset | dp[mask][last] | Traveling Salesman, Minimum XOR Sum |
Pattern Decision Tree
Quick classification: (1) Subarray/substring with constraint → Sliding Window. (2) Sorted array + pair/triplet → Two Pointers. (3) All combinations/permutations → Backtracking. (4) Shortest path in unweighted → BFS. (5) Weighted shortest path → Dijkstra. (6) Tree/graph traversal all paths → DFS. (7) Optimal substructure + overlapping subproblems → DP. (8) Next greater/prev smaller → Monotonic Stack. (9) Interval scheduling → Greedy. (10) String matching → KMP/Trie.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.