This is the definitive cheat sheet for coding interview patterns. Each pattern is described with: when to recognize it, the template/approach, time complexity, and the key problems. Print this, review it before interviews, and use it as a quick reference during practice. These 15 patterns cover 90%+ of coding interview problems at top tech companies.
Pattern 1-5: Array and String Fundamentals
(1) Two Pointers (Opposite Direction): Recognition: sorted array + find pair/triplet. Template: left=0, right=N-1, move based on comparison. O(N). Problems: Two Sum II, 3Sum, Container With Most Water, Trapping Rain Water. (2) Two Pointers (Same Direction / Fast-Slow): Recognition: linked list cycle, find middle, in-place array modification. Template: slow moves 1, fast moves 2 (or scans ahead). O(N). Problems: Linked List Cycle, Middle of List, Remove Duplicates, Move Zeroes. (3) Sliding Window (Fixed): Recognition: compute over every subarray of size K. Template: maintain window sum/state, slide right, subtract left. O(N). Problems: Max Sum Subarray K, Sliding Window Maximum, Permutation in String. (4) Sliding Window (Variable): Recognition: find shortest/longest subarray satisfying condition. Template: expand right, shrink left while condition holds, track best. O(N). Problems: Min Size Subarray Sum, Longest Without Repeating, Min Window Substring. (5) Prefix Sum / Difference Array: Recognition: range sum queries, subarray sum = K, range updates. Template: prefix[i] = prefix[i-1] + arr[i-1]. Range sum = prefix[r+1] – prefix[l]. O(N). Problems: Subarray Sum Equals K, Range Sum Query, Corporate Flight Bookings.
Pattern 6-10: Search, Sort, and Data Structures
(6) Binary Search: Recognition: sorted array, search space reduction, minimize/maximize answer. Template: left, right, mid = left + (right-left)//2. O(log N). Problems: Search in Rotated Array, Koko Eating Bananas, Split Array Largest Sum. (7) Heap / Priority Queue: Recognition: top-K, merge K sorted, median from stream, scheduling. Template: maintain min/max heap of size K. O(N log K). Problems: Kth Largest, Merge K Lists, Find Median, Task Scheduler. (8) Monotonic Stack: Recognition: next greater/smaller element, histogram area, stock span. Template: decreasing stack, pop when current > top. O(N). Problems: Daily Temperatures, Largest Rectangle in Histogram, Next Greater Element. (9) Hash Map: Recognition: count frequency, find complement, group by key. Template: build map, query in O(1). O(N). Problems: Two Sum, Group Anagrams, Longest Consecutive, Subarray Sum. (10) Trie: Recognition: prefix search, autocomplete, word search in grid. Template: insert/search by character traversal. O(L) per operation. Problems: Implement Trie, Word Search II, Design Autocomplete.
Pattern 11-15: Graphs, Trees, and Advanced
(11) BFS: Recognition: shortest path unweighted, level-order, multi-source spread. Template: queue, visited set, process level by level. O(V+E). Problems: Word Ladder, Rotting Oranges, Binary Tree Level Order, Shortest Path Grid. (12) DFS / Backtracking: Recognition: exhaustive search, permutations, combinations, constraint satisfaction. Template: choose, explore, unchoose. O(branch^depth). Problems: Permutations, Subsets, N-Queens, Word Search, Combination Sum. (13) Dynamic Programming: Recognition: optimal substructure + overlapping subproblems. “Min cost,” “max profit,” “number of ways.” Template: define state, transition, base cases. O varies. Sub-patterns: knapsack, LCS, interval, linear, bitmask, tree DP. Problems: Coin Change, Longest Increasing Subsequence, Edit Distance, House Robber. (14) Union-Find: Recognition: incremental connectivity, grouping, cycle detection in undirected graphs. Template: find with path compression, union by rank. O(alpha(N)) ~= O(1). Problems: Number of Components, Accounts Merge, Redundant Connection, Kruskal MST. (15) Greedy: Recognition: locally optimal leads to globally optimal, interval scheduling, jump games. Template: sort by criterion, process greedily. O(N log N). Problems: Merge Intervals, Jump Game, Task Scheduler, Non-Overlapping Intervals.
Pattern Recognition Decision Tree
When you see a new problem, follow this decision tree: (1) Is it about arrays/strings? -> hash map for complement/grouping, two pointers for sorted data, sliding window for subarrays, prefix sum for range queries. (2) Is it about trees? -> DFS (pre/in/post-order based on information flow direction), BFS for level-order. (3) Is it about graphs? -> BFS for shortest path, DFS for traversal/cycles, Dijkstra for weighted, topological sort for dependencies, Union-Find for connectivity. (4) Is it “find optimal” with subproblems? -> DP. Identify the state and transition. (5) Is it “find all possible”? -> backtracking (DFS with undo). (6) Is it “find top-K” or “merge sorted”? -> heap. (7) Is it “next greater/smaller”? -> monotonic stack. (8) Is it about scheduling/intervals? -> greedy (sort by end time). (9) Is it “minimize the maximum” or “maximize the minimum”? -> binary search on answer. (10) Does it involve prefix matching? -> trie. Practice 3-5 problems per pattern until recognition is automatic. The pattern tells you the template; adapting the template to the specific problem is where your skill shows.
Time Complexity Quick Reference
O(1): hash map lookup, heap peek, array access. O(log N): binary search, balanced BST operations, heap insert/extract. O(N): linear scan, hash map build, two pointers, sliding window, prefix sum. O(N log N): sorting (merge sort, quick sort average), heap with N elements of size K (N log K). O(N^2): nested loops (brute force two sum), simple DP (LIS naive), all pairs in array. O(N^3): Floyd-Warshall, matrix multiplication, interval DP. O(2^N): subsets (power set), bitmask DP. O(N!): permutations, backtracking worst case. O(N * 2^N): TSP with bitmask DP. Target for interviews: O(N) or O(N log N) for array/string problems. O(V+E) for graph problems. O(N*M) for two-string DP. If your solution is O(N^2) and the input is 10^5, you need to optimize. If it is O(N log N) and the input is 10^6, you are fine. Always state the time and space complexity of your solution.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What are the 15 coding interview patterns every engineer should know?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”(1) Two Pointers (opposite) — sorted arrays, pairs. (2) Fast-Slow Pointer — cycles, middle, in-place. (3) Fixed Sliding Window — subarray of size K. (4) Variable Sliding Window — shortest/longest subarray with condition. (5) Prefix Sum — range queries, subarray sum. (6) Binary Search — sorted data, search on answer. (7) Heap — top-K, merge sorted, median. (8) Monotonic Stack — next greater/smaller, histogram. (9) Hash Map — frequency, complement, grouping. (10) Trie — prefix search, autocomplete. (11) BFS — shortest path unweighted, level-order. (12) DFS/Backtracking — exhaustive search, permutations. (13) Dynamic Programming — optimal substructure + overlapping subproblems. (14) Union-Find — connectivity, grouping, MST. (15) Greedy — locally optimal = globally optimal, intervals. Master 3-5 problems per pattern until recognition is automatic.”}},{“@type”:”Question”,”name”:”How do you decide which coding pattern to use for an interview problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Decision tree: Arrays/strings? -> hash map (complement), two pointers (sorted), sliding window (subarrays), prefix sum (ranges). Trees? -> DFS (information flow up/down), BFS (level-order). Graphs? -> BFS (shortest path), DFS (traversal/cycles), Dijkstra (weighted), topological sort (dependencies), Union-Find (connectivity). Find optimal with subproblems? -> DP. Find all possible? -> backtracking. Top-K or merge sorted? -> heap. Next greater/smaller? -> monotonic stack. Scheduling/intervals? -> greedy (sort by end time). Minimize maximum or maximize minimum? -> binary search on answer. Prefix matching? -> trie. The pattern tells you the template; adapting it to the specific problem is your skill. If unsure between DP and greedy: try a small counterexample for greedy. If it fails, use DP.”}}]}