Split View: 코딩 테스트 패턴 완전 정복: FAANG 합격을 위한 알고리즘 15 패턴 + 75문제 로드맵

Coding Interview Pattern Mastery: 15 Algorithm Patterns + 75 Problems Roadmap for FAANG 2025

• 1. The State of Coding Interviews in 2025
  • FAANG Interview Frequency Data and Trends
  • The Rise of AI-Aware Coding Rounds
  • NeetCode 150 vs Blind 75 vs Grind 75
  • Language Choice: Python vs Java vs TypeScript
  • 12-Week Study Roadmap Overview
• 2. Pattern 1 — Arrays and Hashing
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Two Sum (LeetCode 1)
  • Variations and Tips
• 3. Pattern 2 — Two Pointers
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Container With Most Water (LeetCode 11)
  • Variations and Tips
• 4. Pattern 3 — Sliding Window
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Longest Substring Without Repeating Characters (LeetCode 3)
  • Variations and Tips
• 5. Pattern 4 — Stack (Monotonic Stack)
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Daily Temperatures (LeetCode 739)
  • Variations and Tips
• 6. Pattern 5 — Binary Search
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Koko Eating Bananas (LeetCode 875)
  • Variations and Tips
• 7. Pattern 6 — Linked List
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Reverse Linked List (LeetCode 206)
  • Variations and Tips
• 8. Pattern 7 — Trees (BFS/DFS)
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Binary Tree Level Order Traversal (LeetCode 102)
  • Variations and Tips
• 9. Pattern 8 — Tries
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Implement Trie (LeetCode 208)
  • Variations and Tips
• 10. Pattern 9 — Heap / Priority Queue
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Find Median from Data Stream (LeetCode 295)
  • Variations and Tips
• 11. Pattern 10 — Backtracking
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Combination Sum (LeetCode 39)
  • Variations and Tips
• 12. Pattern 11 — Graphs (BFS/DFS/Union-Find)
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Number of Islands (LeetCode 200)
  • Union-Find Implementation
  • Variations and Tips
• 13. Pattern 12 — Dynamic Programming (1D)
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Coin Change (LeetCode 322)
  • Variations and Tips
• 14. Pattern 13 — Dynamic Programming (2D)
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Longest Common Subsequence (LeetCode 1143)
  • Variations and Tips
• 15. Pattern 14 — Greedy
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Jump Game (LeetCode 55)
  • Variations and Tips
• 16. Pattern 15 — Intervals and Math
  • Core Idea
  • Time/Space Complexity
  • Representative Problems
  • Python Solution — Merge Intervals (LeetCode 56)
  • Variations and Tips
• 17. 75-Problem Curated Checklist
• 18. Practical Interview Tips
  • 45-Minute Time Allocation
  • The UMPIRE Method
  • Edge Case Checklist
  • How AI Copilots Are Changing Interviews
• 19. Quiz
• 20. References

1. The State of Coding Interviews in 2025

FAANG Interview Frequency Data and Trends

In 2025, FAANG (Meta, Apple, Amazon, Netflix, Google) coding interviews have shifted toward pattern-based problem design. Rather than pure memorization, interviewers now prefer problems that combine or modify known patterns. Graph + DP hybrid questions and Sliding Window + Hash Map combinations appear frequently.

Here is a breakdown of pattern frequency by company in 2025:

The Rise of AI-Aware Coding Rounds

Starting in 2025, some companies have introduced AI copilot-aware coding interviews. These focus less on raw implementation and more on problem analysis, optimal algorithm selection, and code review skills. However, traditional whiteboard coding remains the norm, and understanding algorithm patterns is still essential.

NeetCode 150 vs Blind 75 vs Grind 75

This article selects 75 essential problems from NeetCode 150, organized by pattern.

Language Choice: Python vs Java vs TypeScript

• Python: Concise syntax and fast prototyping. Most popular language at FAANG interviews. Powerful built-in libraries (heapq, collections, itertools)
• Java: Type safety and performance advantages. Preferred at Amazon and Google. Rich data structures (TreeMap, PriorityQueue)
• TypeScript: Advantageous for frontend roles. However, it offers fewer advantages for algorithm problems compared to Python

All code examples in this article use Python.

12-Week Study Roadmap Overview

2. Pattern 1 — Arrays and Hashing

Core Idea

Arrays and hash maps are the foundation of all algorithms. The key technique is using hash map O(1) lookups to reduce brute force O(n^2) to O(n). Essential for frequency counting, duplicate detection, and grouping problems.

Time/Space Complexity

• Hash map insert/lookup: O(1) average, O(n) worst case
• Sort-based approach: O(n log n)
• Space: O(n) for hash map storage

Representative Problems

1. Two Sum (LeetCode 1) — Easy
2. Contains Duplicate (LeetCode 217) — Easy
3. Valid Anagram (LeetCode 242) — Easy
4. Group Anagrams (LeetCode 49) — Medium
5. Top K Frequent Elements (LeetCode 347) — Medium

Python Solution — Two Sum (LeetCode 1)

def twoSum(nums: list[int], target: int) -> list[int]:
    # Hash map: value -> index mapping
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Time: O(n), Space: O(n)
# Key insight: Look up complement in hash map in O(1)

Variations and Tips

• Three Sum (LeetCode 15): Sort first, then combine with Two Pointers
• Product of Array Except Self (LeetCode 238): Prefix/suffix product pattern
• Interview tip: Always check if a hash map can provide an O(n) solution first

3. Pattern 2 — Two Pointers

Core Idea

On sorted arrays or strings, use two pointers moving inward from both ends to find pairs that meet a condition. Alternatively, use fast/slow pointers moving in the same direction. Optimizes O(n^2) brute force to O(n).

Time/Space Complexity

• Time: O(n) (if already sorted) or O(n log n) (if sorting needed)
• Space: O(1) — no extra space required

Representative Problems

1. Valid Palindrome (LeetCode 125) — Easy
2. Two Sum II - Sorted Array (LeetCode 167) — Medium
3. 3Sum (LeetCode 15) — Medium
4. Container With Most Water (LeetCode 11) — Medium
5. Trapping Rain Water (LeetCode 42) — Hard

Python Solution — Container With Most Water (LeetCode 11)

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        # Calculate water area with current two walls
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)

        # Move the shorter wall's pointer inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

# Time: O(n), Space: O(1)
# Key insight: Moving the shorter wall is the only way to potentially increase area

Variations and Tips

• Trapping Rain Water: Track maximum heights from both sides
• Interview tip: If the input is sorted, consider Two Pointers first
• For 3Sum, fix one element and use Two Pointers on the remaining

4. Pattern 3 — Sliding Window

Core Idea

Slide a fixed or variable-size window across an array or string to find optimal values (maximum sum, minimum length, valid substrings). Add new elements and remove old ones while maintaining O(n) time.

Time/Space Complexity

• Time: O(n) — each element enters and leaves the window at most once
• Space: O(k) — window size or character set size

Representative Problems

1. Best Time to Buy and Sell Stock (LeetCode 121) — Easy
2. Longest Substring Without Repeating Characters (LeetCode 3) — Medium
3. Longest Repeating Character Replacement (LeetCode 424) — Medium
4. Minimum Window Substring (LeetCode 76) — Hard
5. Sliding Window Maximum (LeetCode 239) — Hard

Python Solution — Longest Substring Without Repeating Characters (LeetCode 3)

def lengthOfLongestSubstring(s: str) -> int:
    char_index = {}  # char -> last seen index
    left = 0
    max_len = 0

    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            # Duplicate found: move left past the duplicate
            left = char_index[s[right]] + 1
        char_index[s[right]] = right
        max_len = max(max_len, right - left + 1)

    return max_len

# Time: O(n), Space: O(min(n, 26))
# Key insight: Track duplicate positions with hash map, update window size

Variations and Tips

• Minimum Window Substring: Track required character counts with a hash map while shrinking
• Fixed-size window: Maintain right - left + 1 == k
• Interview tip: If the problem involves contiguous subarrays or substrings, consider Sliding Window

5. Pattern 4 — Stack (Monotonic Stack)

Core Idea

Leverage the LIFO (Last In First Out) property. Use basic stacks for parentheses matching and expression evaluation. Use Monotonic Stacks for Next Greater/Smaller Element problems — the stack maintains elements in strictly increasing or decreasing order.

Time/Space Complexity

• Time: O(n) — each element is pushed and popped at most once
• Space: O(n) — stack storage

Representative Problems

1. Valid Parentheses (LeetCode 20) — Easy
2. Min Stack (LeetCode 155) — Medium
3. Evaluate Reverse Polish Notation (LeetCode 150) — Medium
4. Daily Temperatures (LeetCode 739) — Medium
5. Largest Rectangle in Histogram (LeetCode 84) — Hard

Python Solution — Daily Temperatures (LeetCode 739)

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # Monotonic decreasing stack: stores indices

    for i in range(n):
        # Pop while current temp is higher than stack top
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            answer[prev_idx] = i - prev_idx
        stack.append(i)

    return answer

# Time: O(n), Space: O(n)
# Key insight: Monotonic decreasing stack computes distance to next greater element in O(n)

Variations and Tips

• Largest Rectangle in Histogram: Monotonic increasing stack to compute max width per height
• Next Greater Element: For circular arrays, iterate 2n times
• Interview tip: When the relationship between current and previous elements matters, think monotonic stack

6. Pattern 5 — Binary Search

Core Idea

Halve the search space in sorted data to find answers in O(log n). Beyond array searching, it also applies to decision problems — converting optimization problems to binary search. Classic patterns include "maximize the minimum" or "minimize the maximum."

Time/Space Complexity

• Time: O(log n)
• Space: O(1) iterative / O(log n) recursive

Representative Problems

1. Binary Search (LeetCode 704) — Easy
2. Search a 2D Matrix (LeetCode 74) — Medium
3. Koko Eating Bananas (LeetCode 875) — Medium
4. Find Minimum in Rotated Sorted Array (LeetCode 153) — Medium
5. Median of Two Sorted Arrays (LeetCode 4) — Hard

Python Solution — Koko Eating Bananas (LeetCode 875)

import math

def minEatingSpeed(piles: list[int], h: int) -> int:
    # Binary search on speed range [1, max(piles)]
    left, right = 1, max(piles)

    while left < right:
        mid = (left + right) // 2
        # Check if Koko can eat all bananas at speed mid within h hours
        hours_needed = sum(math.ceil(pile / mid) for pile in piles)

        if hours_needed <= h:
            right = mid  # Try a slower speed
        else:
            left = mid + 1  # Need a faster speed

    return left

# Time: O(n * log(max(piles))), Space: O(1)
# Key insight: Binary search on the answer for a decision problem

Variations and Tips

• Rotated Sorted Array: Compare mid with endpoints to identify the sorted half
• Decision problem pattern: If canDo(x) is monotonic, binary search applies
• Interview tip: Even if the data is not sorted, if the answer range is monotonic, consider binary search

7. Pattern 6 — Linked List

Core Idea

Linked list problems revolve around pointer manipulation. Reversal, merging, cycle detection, and finding the middle node are recurring themes. The fast/slow pointer technique (Floyd's algorithm) is essential for cycle detection and middle node finding.

Time/Space Complexity

• Traversal: O(n) time, O(1) space
• Recursive approaches: O(n) time, O(n) stack space

Representative Problems

1. Reverse Linked List (LeetCode 206) — Easy
2. Merge Two Sorted Lists (LeetCode 21) — Easy
3. Linked List Cycle (LeetCode 141) — Easy
4. Reorder List (LeetCode 143) — Medium
5. Merge k Sorted Lists (LeetCode 23) — Hard

Python Solution — Reverse Linked List (LeetCode 206)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    prev = None
    current = head

    while current:
        next_node = current.next  # Save next node
        current.next = prev       # Reverse the link
        prev = current             # Advance prev
        current = next_node        # Advance current

    return prev

# Time: O(n), Space: O(1)
# Key insight: Three pointers (prev, current, next) for in-place reversal

Variations and Tips

• Reorder List: Find middle + reverse second half + merge — 3 steps
• Merge k Sorted Lists: Use a min-heap to manage k list heads
• Interview tip: Using a dummy node simplifies edge case handling

8. Pattern 7 — Trees (BFS/DFS)

Core Idea

Tree problems split into recursive DFS (preorder/inorder/postorder) and BFS (level-order). Most binary tree problems can be solved by defining "what to do at the current node, and what to delegate to children."

Time/Space Complexity

• DFS: O(n) time, O(h) space (h = tree height, worst case O(n))
• BFS: O(n) time, O(w) space (w = maximum level width)

Representative Problems

1. Maximum Depth of Binary Tree (LeetCode 104) — Easy
2. Invert Binary Tree (LeetCode 226) — Easy
3. Binary Tree Level Order Traversal (LeetCode 102) — Medium
4. Validate Binary Search Tree (LeetCode 98) — Medium
5. Binary Tree Maximum Path Sum (LeetCode 124) — Hard

Python Solution — Binary Tree Level Order Traversal (LeetCode 102)

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root: TreeNode) -> list[list[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

# Time: O(n), Space: O(n)
# Key insight: Process level_size nodes per iteration to group by level

Variations and Tips

• BST Validation: Check inorder traversal is sorted, or pass value ranges via DFS
• Maximum Path Sum: Postorder traversal computing max contribution from children
• Interview tip: Always handle the base case (null node) first in tree problems

9. Pattern 8 — Tries

Core Idea

A Trie (Prefix Tree) stores strings character by character in a tree structure. Prefix searches take O(m) where m is the string length. Useful for autocomplete, dictionary lookup, and wildcard matching.

Time/Space Complexity

• Insert/Search: O(m) — m is the string length
• Space: O(total characters * alphabet size)

Representative Problems

1. Implement Trie (Prefix Tree) (LeetCode 208) — Medium
2. Design Add and Search Words (LeetCode 211) — Medium
3. Word Search II (LeetCode 212) — Hard

Python Solution — Implement Trie (LeetCode 208)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, prefix: str) -> TrieNode:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

# Time: Insert/Search O(m), Space: O(total characters)
# Key insight: Each node holds a children dict and an end-of-word flag

Variations and Tips

• Word Search II: Trie + DFS backtracking combination
• Design Add and Search Words: Recursive DFS for wildcard .
• Interview tip: When you need repeated prefix lookups across multiple strings, Trie is efficient

10. Pattern 9 — Heap / Priority Queue

Core Idea

A Heap provides O(1) max/min access with O(log n) insert/delete. Essential for Top K problems, streaming median, and task scheduling.

Time/Space Complexity

• Insert/Delete: O(log n)
• Max/Min access: O(1)
• Heapify: O(n)

Representative Problems

1. Kth Largest Element in a Stream (LeetCode 703) — Easy
2. Last Stone Weight (LeetCode 1046) — Easy
3. K Closest Points to Origin (LeetCode 973) — Medium
4. Task Scheduler (LeetCode 621) — Medium
5. Find Median from Data Stream (LeetCode 295) — Hard

Python Solution — Find Median from Data Stream (LeetCode 295)

import heapq

class MedianFinder:
    def __init__(self):
        # max_heap: lower half (store negatives for max heap in Python)
        # min_heap: upper half
        self.max_heap = []  # left half
        self.min_heap = []  # right half

    def addNum(self, num: int) -> None:
        # Always push to max_heap first
        heapq.heappush(self.max_heap, -num)
        # Move max of max_heap to min_heap
        heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))

        # Balance: max_heap should be >= min_heap in size
        if len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def findMedian(self) -> float:
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        return (-self.max_heap[0] + self.min_heap[0]) / 2

# Time: addNum O(log n), findMedian O(1)
# Key insight: Two heaps split data in half to efficiently maintain the median

Variations and Tips

• Task Scheduler: Max heap to schedule the most frequent task first
• Python heapq is a min heap; negate values for max heap behavior
• Interview tip: Top K problems can be solved in O(n log k) with a size-K min heap

11. Pattern 10 — Backtracking

Core Idea

Explore all possible combinations, permutations, and subsets while pruning invalid paths early. The pattern is recursion + choose/unchoose. Since time complexity is exponential, pruning is critical for performance.

Time/Space Complexity

• Subsets: O(2^n)
• Permutations: O(n!)
• Space: O(n) — recursion depth

Representative Problems

1. Subsets (LeetCode 78) — Medium
2. Combination Sum (LeetCode 39) — Medium
3. Permutations (LeetCode 46) — Medium
4. Word Search (LeetCode 79) — Medium
5. N-Queens (LeetCode 51) — Hard

Python Solution — Combination Sum (LeetCode 39)

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    result = []

    def backtrack(start: int, current: list[int], remaining: int):
        if remaining == 0:
            result.append(current[:])  # Add current combination to results
            return
        if remaining < 0:
            return  # Pruning

        for i in range(start, len(candidates)):
            current.append(candidates[i])
            # Same element can be reused -> keep start at i
            backtrack(i, current, remaining - candidates[i])
            current.pop()  # Unchoose (backtrack)

    backtrack(0, [], target)
    return result

# Time: O(2^t) (t = target / min(candidates)), Space: O(target)
# Key insight: Choose -> recurse -> unchoose pattern with pruning

Variations and Tips

• Subsets: Add current state to results at every step
• Permutations: Use a visited array or swap technique
• N-Queens: Track row/column/diagonal conflicts with sets
• Interview tip: Drawing the decision tree helps visualize backtracking patterns

12. Pattern 11 — Graphs (BFS/DFS/Union-Find)

Core Idea

Graph problems fall into connected components, shortest paths, cycle detection, and topological sort. BFS for shortest paths, DFS for path exploration and cycle detection, and Union-Find for connected component management.

Time/Space Complexity

• BFS/DFS: O(V + E) time, O(V) space
• Union-Find: O(alpha(n)) almost O(1) per operation
• Topological Sort: O(V + E)

Representative Problems

1. Number of Islands (LeetCode 200) — Medium
2. Clone Graph (LeetCode 133) — Medium
3. Course Schedule (LeetCode 207) — Medium (Topological Sort)
4. Pacific Atlantic Water Flow (LeetCode 417) — Medium
5. Graph Valid Tree (LeetCode 261) — Medium (Union-Find)

Python Solution — Number of Islands (LeetCode 200)

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r: int, c: int):
        # Out of bounds or water -> return
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # Mark as visited
        # Explore 4 directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

    return count

# Time: O(m * n), Space: O(m * n) worst case recursion depth
# Key insight: DFS flood-fill to mark entire island when a new '1' is found

Union-Find Implementation

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # Number of connected components

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # Union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1
        return True

Variations and Tips

• Course Schedule: Topological sort (Kahn's algorithm) for cycle detection
• Pacific Atlantic Water Flow: Reverse BFS — start from ocean and move inland
• Interview tip: First decide on adjacency list vs matrix representation, then choose BFS/DFS/Union-Find

13. Pattern 12 — Dynamic Programming (1D)

Core Idea

1D DP uses a single variable's optimal substructure. Define a recurrence dp[i] and compute the current state from previous states (dp[i-1], dp[i-2], etc.). Fibonacci, stair climbing, and house robber are classic examples.

Time/Space Complexity

• Time: O(n) to O(n * k)
• Space: O(n) (tabulation) or O(1) (space-optimized)

Representative Problems

1. Climbing Stairs (LeetCode 70) — Easy
2. House Robber (LeetCode 198) — Medium
3. Coin Change (LeetCode 322) — Medium
4. Longest Increasing Subsequence (LeetCode 300) — Medium
5. Word Break (LeetCode 139) — Medium

Python Solution — Coin Change (LeetCode 322)

def coinChange(coins: list[int], amount: int) -> int:
    # dp[i] = minimum coins to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0 amount needs 0 coins

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# Time: O(amount * len(coins)), Space: O(amount)
# Key insight: Try every coin for each amount, taking the minimum

Variations and Tips

• House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — no adjacent houses
• LIS: O(n log n) solution uses binary search with an auxiliary array
• Word Break: dp[i] = any j where dp[j] and s[j:i] in wordSet
• Interview tip: Many 1D DP problems can be space-optimized to O(1), so mention this

14. Pattern 13 — Dynamic Programming (2D)

Core Idea

2D DP defines states over two variables (two strings, grid coordinates, etc.). dp[i][j] represents the result considering the first i elements of input 1 and the first j elements of input 2.

Time/Space Complexity

• Time: O(m * n)
• Space: O(m * n) or O(min(m, n)) with row compression

Representative Problems

1. Unique Paths (LeetCode 62) — Medium
2. Longest Common Subsequence (LeetCode 1143) — Medium
3. Best Time to Buy and Sell Stock with Cooldown (LeetCode 309) — Medium
4. Target Sum (LeetCode 494) — Medium
5. Edit Distance (LeetCode 72) — Medium

Python Solution — Longest Common Subsequence (LeetCode 1143)

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    # dp[i][j] = LCS length of first i chars of text1 and first j chars of text2
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

# Time: O(m * n), Space: O(m * n)
# Key insight: Same char -> diagonal + 1, different -> max of top/left

Variations and Tips

• Edit Distance: Consider insert/delete/replace — three operations
• Target Sum: Transform into a knapsack problem
• Space optimization: If only the previous row is needed, compress to a 1D array
• Interview tip: Clearly define the 2D DP recurrence before coding

15. Pattern 14 — Greedy

Core Idea

Apply locally optimal choices at each step that guarantee globally optimal results. Unlike DP, greedy never reverses previous choices. The challenge is identifying the correct greedy strategy. When proofs are difficult, memorizing patterns is efficient.

Time/Space Complexity

• Usually O(n) or O(n log n) when sorting is needed
• Space: O(1) to O(n)

Representative Problems

1. Maximum Subarray (LeetCode 53) — Medium
2. Jump Game (LeetCode 55) — Medium
3. Jump Game II (LeetCode 45) — Medium
4. Gas Station (LeetCode 134) — Medium
5. Hand of Straights (LeetCode 846) — Medium

Python Solution — Jump Game (LeetCode 55)

def canJump(nums: list[int]) -> bool:
    # goal: position we need to reach (work backward)
    goal = len(nums) - 1

    for i in range(len(nums) - 2, -1, -1):
        if i + nums[i] >= goal:
            goal = i  # Current position can reach goal, so update goal

    return goal == 0

# Time: O(n), Space: O(1)
# Key insight: Greedily check reachability from back to front

Variations and Tips

• Maximum Subarray (Kadane's): Reset running sum to 0 when it goes negative
• Jump Game II: BFS-style level counting for minimum jumps
• Interview tip: If unsure whether greedy is correct, test with small counterexamples

16. Pattern 15 — Intervals and Math

Core Idea

Interval problems revolve around sorting by start or end points, then handling overlaps. Merging, inserting, and minimum meeting rooms are classic examples. Math problems include bit manipulation, modular arithmetic, and geometric calculations.

Time/Space Complexity

• Sorting: O(n log n)
• Scanning: O(n)
• Space: O(n) for result storage

Representative Problems

1. Merge Intervals (LeetCode 56) — Medium
2. Insert Interval (LeetCode 57) — Medium
3. Non-overlapping Intervals (LeetCode 435) — Medium
4. Meeting Rooms II (LeetCode 253) — Medium
5. Rotate Image (LeetCode 48) — Medium

Python Solution — Merge Intervals (LeetCode 56)

def merge(intervals: list[list[int]]) -> list[list[int]]:
    # Sort by start point
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        # If current interval overlaps with the last merged one
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

# Time: O(n log n), Space: O(n)
# Key insight: Sort, then sequentially merge overlapping intervals

Variations and Tips

• Meeting Rooms II: Separate and sort start/end times, then count overlaps
• Non-overlapping Intervals: Sort by end time, then greedily remove minimal intervals
• Rotate Image: Transpose then reverse each row
• Interview tip: For interval problems, first decide the sort key (start vs end)

17. 75-Problem Curated Checklist

Below is a curated 75-problem checklist based on NeetCode 150.

18. Practical Interview Tips

45-Minute Time Allocation

The UMPIRE Method

A systematic framework for solving coding interview problems.

1. U - Understand: Fully understand the problem. Confirm examples, ask clarifying questions.
2. M - Match: Match to known patterns. Identify which of these 15 patterns applies.
3. P - Plan: Create a concrete plan. Write pseudocode.
4. I - Implement: Code cleanly following the plan.
5. R - Review: Review code line by line to catch bugs.
6. E - Evaluate: Analyze time/space complexity. Discuss possible optimizations.

Edge Case Checklist

Commonly missed edge cases during interviews:

• Empty input (empty array, empty string, null/None)
• Single-element input
• All elements identical
• Negative values present
• Very large input (overflow check)
• Unsorted input (never assume sorted unless stated)
• Duplicate elements present

How AI Copilots Are Changing Interviews

Notable changes in 2025 coding interviews:

1. Increased System Design Weight: Since AI can assist coding, architecture design skills matter more
2. Code Review Assessment: More problems asking you to find bugs and performance issues in given code
3. More Variations: Modified conditions on classic problems so memorized solutions fail
4. Live Collaboration: More pair programming-style interviews with the interviewer
5. Algorithm + System Design Hybrids: Discussing algorithm optimization at the system level

19. Quiz

Test your understanding of the material covered.

20. References

1. NeetCode 150 Roadmap — Systematic pattern-based problem classification
2. Blind 75 Problem List — The original curated list
3. Grind 75 by Yangshun — Customizable scheduling
4. LeetCode — Online coding practice platform
5. Introduction to Algorithms (CLRS) — The algorithm bible
6. Grokking the Coding Interview — Pattern-based learning
7. Tech Interview Handbook — Comprehensive interview guide
8. Competitive Programmer's Handbook (Antti Laaksonen) — Free algorithm textbook
9. VisuAlgo — Algorithm visualization tool
10. Big-O Cheat Sheet — Time/space complexity reference
11. Python collections docs — Counter, deque, defaultdict
12. Python heapq docs — Heap operations
13. Back to Back SWE (YouTube) — Algorithm explanations
14. Abdul Bari Algorithms (YouTube) — Algorithm lectures
15. System Design Interview by Alex Xu — System design interview guide
16. Cracking the Coding Interview by Gayle McDowell — Classic interview preparation book