Top Interview Coding Patterns

Real-world analogy

What is it?

Interview coding patterns are reusable algorithmic templates that solve broad categories of problems. Instead of memorizing solutions to 1000 individual problems, mastering 10-15 patterns gives you the tools to solve virtually any problem an interviewer throws at you. Each pattern has a recognizable trigger (problem description keywords), a template (code structure), and variations (twists interviewers add).

Real-world relevance

Google's interview process has been studied extensively. Analysis of thousands of interview questions shows that 15 patterns cover approximately 90% of all coding questions asked at FAANG companies. A former Google interviewer revealed that they deliberately pick problems that test pattern recognition — they want to see if you can identify the underlying structure, not just brute-force a solution.

Key points

• Two Pointers Mastery — Use when dealing with sorted arrays or linked lists where you need to find pairs. Start pointers at both ends (or both at start). Move them based on comparison with target. Covers: pair sum, triplets, removing duplicates, squaring sorted arrays. O(n) time.
• Sliding Window Deep Dive — Use for problems involving contiguous subarrays or substrings with a constraint. Maintain a window that expands right and shrinks left. Two types: fixed-size window (easy) and variable-size window (medium). Covers: max sum subarray, longest substring, minimum window substring.
• BFS vs DFS Decision Framework — BFS = shortest path, level-order, minimum steps. DFS = all paths, combinations, permutations, tree depth. BFS uses a queue, DFS uses recursion/stack. If the problem says 'shortest' or 'minimum steps' — it's BFS. If it says 'all possible' or 'generate all' — it's DFS.
• Dynamic Programming Simplified — DP = recursion + memoization. Step 1: Write the brute force recursive solution. Step 2: Add memoization (top-down) or convert to tabulation (bottom-up). Key question: 'Can I express the answer using answers to smaller subproblems?' If yes → DP.
• Binary Search Variations — Beyond basic search: find first/last occurrence, search in rotated array, find peak element, search in 2D matrix. The key insight: if you can define a condition that splits the search space in half, you can use binary search. Not just for sorted arrays!
• Heap / Priority Queue Patterns — Use for Top K, K-th largest/smallest, merge K sorted lists, scheduling problems. Min-heap for K largest (counterintuitive!), max-heap for K smallest. Always maintain heap size K for O(n log K) instead of O(n log n).
• Graph Pattern Recognition — Adjacency list for sparse graphs, matrix for dense. BFS for shortest unweighted path, Dijkstra for weighted. Topological sort for dependency ordering. Union-Find for connected components. Detect cycle: DFS with 3-state coloring.
• Interval Patterns — Sort by start time first. Then: merge overlapping intervals (expand end), insert interval (binary search insert point), meeting rooms (min-heap for end times). Key insight: after sorting, you only need to compare with the previous interval.
• Backtracking Template — Used for combinations, permutations, subsets, N-Queens. Template: make a choice, recurse, undo the choice (backtrack). Optimization: prune early when you know a path can't lead to a valid solution. Always think: what are my choices at each step?
• Pattern Combination in Hard Problems — Hard problems combine 2-3 patterns. Example: 'Find shortest path with constraints' = BFS + DP. 'Find K closest points' = Heap + Euclidean distance. Practice recognizing multi-pattern problems by breaking them into subproblems.

Code example

# Complete Pattern Templates for Top Interview Patterns
# =====================================================

# 1. TWO POINTERS: Pair with Target Sum (Sorted Array)
\`\`\`python
def pair_with_target(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1    # Need bigger sum
        else:
            right -= 1   # Need smaller sum
    return [-1, -1]
# Time: O(n), Space: O(1)
\`\`\`

# 2. SLIDING WINDOW: Longest Substring with K Distinct Chars
\`\`\`python
def longest_substring_k_distinct(s, k):
    window_start, max_length = 0, 0
    char_freq = {}
    for window_end in range(len(s)):
        right_char = s[window_end]
        char_freq[right_char] = char_freq.get(right_char, 0) + 1
        while len(char_freq) > k:  # Shrink window
            left_char = s[window_start]
            char_freq[left_char] -= 1
            if char_freq[left_char] == 0:
                del char_freq[left_char]
            window_start += 1
        max_length = max(max_length, window_end - window_start + 1)
    return max_length
# Time: O(n), Space: O(k)
\`\`\`

# 3. MODIFIED BINARY SEARCH: Search in Rotated Array
\`\`\`python
def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        # Left half is sorted
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1
# Time: O(log n), Space: O(1)
\`\`\`

# 4. TOP K ELEMENTS: K Largest Numbers (Min-Heap)
\`\`\`python
import heapq
def find_k_largest(nums, k):
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)  # Remove smallest
    return list(min_heap)
# Time: O(n log k), Space: O(k)
\`\`\`

# 5. BACKTRACKING: Generate All Subsets
\`\`\`python
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])  # Add copy
        for i in range(start, len(nums)):
            current.append(nums[i])       # Choose
            backtrack(i + 1, current)      # Explore
            current.pop()                  # Un-choose
    backtrack(0, [])
    return result
# Time: O(2^n), Space: O(n) for recursion stack
\`\`\`

Line-by-line walkthrough

1. 1. Two Pointers: Start at both ends of sorted array. If sum too small, move left up. If too big, move right down. Guaranteed O(n).
2. 2. Sliding Window: The char_freq dictionary tracks what's in our current window. When too many distinct chars, shrink from left.
3. 3. The while loop inside the for loop looks like O(n²) but is actually O(n) — each element enters and leaves the window at most once.
4. 4. Rotated Binary Search: The trick is one half is always sorted. Check if target falls in the sorted half; if yes, search there.
5. 5. Top K with min-heap: Keep only K elements in the heap. When you add element K+1, the smallest gets evicted. What remains = K largest.
6. 6. Backtracking for subsets: At each position, you either include the element or skip it. This creates a binary tree of 2^n possibilities.
7. 7. The pattern of append → recurse → pop is the backtracking template. 'Pop' undoes the choice so you can try the next option.
8. 8. Notice every solution includes time and space complexity — always state this in interviews.

Spot the bug

# Sliding Window: Find max sum subarray of size K
def max_sum_subarray(arr, k):
    max_sum = 0
    window_sum = 0
    for i in range(len(arr)):
        window_sum += arr[i]
        if i >= k:
            window_sum -= arr[i - k]
            max_sum = max(max_sum, window_sum)
    return max_sum

# Test: max_sum_subarray([2, 1, 5, 1, 3, 2], 3)
# Expected: 9 (5+1+3), but returns 6. Why?

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Grokking the Coding Interview Patterns (Design Gurus)
• NeetCode Pattern Explanations (YouTube)
• LeetCode Patterns by Sean Prashad (Sean Prashad)
• VisuAlgo - Algorithm Visualizations (VisuAlgo)