Google Coding Interview: 12 Key Patterns

Google's coding interviews are standardized around problem-solving rubrics, and twelve recurring patterns cover most of what candidates actually see: Sliding Window, Two Pointers, Fast and Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Tree BFS, Tree DFS, Binary Search, Top K Elements, K-way Merge, and Subsets. Recognising which pattern fits a given problem is the difference between solving it in 20 minutes and stalling for an hour.

This guide walks through each pattern with the problem shapes it solves, the tradeoffs to call out, and the common failures interviewers grade against. For timed practice on the same shapes, Interview Coder's AI Interview Assistant runs drills that match the format.

Google publishes the rubric its interviewers use on the How We Hire page. Four signals get scored on every coding round: General Cognitive Ability, Role-Related Knowledge, Leadership, and Googleyness. The coding rounds map mostly to the first two, and the score sheets ask interviewers to rate problem decomposition, algorithm choice, code quality, and verification, not whether you recognized a specific LeetCode question by number.

That is why pattern grinding pays off more than brute volume. A candidate who has solved 600 random problems but cannot articulate why a question is a Sliding Window question loses points on the algorithm-choice axis. A candidate who has solved 120 problems but can say "this is a monotonic-deque maximum-window problem because we need the max of every k-length subarray, and a deque keeps the answer in O(n)" picks up signal on three of the four scoring axes in one sentence.

Steven Skiena makes a similar argument in The Algorithm Design Manual. His "war stories" all reduce real problems to a known graph, search, or dynamic-programming shape before writing a single line. Gayle McDowell's Cracking the Coding Interview splits its 189 questions into the same kind of pattern buckets for the same reason: the buckets are what transfer between problems.

Empirical interview research backs this up. A 2020 ICSE study on technical interview anxiety found that candidates who could verbalize a known approach inside the first three minutes outperformed candidates with stronger raw coding ability but slower problem framing. The pattern is the anchor that lets the rest of the round go well.

The rest of this guide walks through the twelve patterns Google interviewers keep landing on, with a template, a real LeetCode problem each one cracks, and the specific way candidates lose points on each.

Use this when the problem asks about a contiguous subarray or substring and you need a running aggregate (sum, count, max, distinct character count) over windows of fixed or variable length. The trick is keeping the window invariant maintained in O(1) per step, so the total work stays O(n) instead of the O(n*k) you get from recomputing from scratch.

A canonical example is LeetCode 3, Longest Substring Without Repeating Characters. The window expands on the right, and when a duplicate enters, the left pointer jumps to the position after the previous occurrence of that character.

def longest_unique_substring(s):
    last_seen = {}
    left = best = 0
    for right, c in enumerate(s):
        if c in last_seen and last_seen[c] >= left:
            left = last_seen[c] + 1
        last_seen[c] = right
        best = max(best, right - left + 1)
    return best

Common interviewer trap: the off-by-one when shrinking the window. Candidates often write left = last_seen[c] instead of last_seen[c] + 1, which keeps the duplicate inside the window. Always dry-run with "abba" before you say you are done. The other failure mode is forgetting to guard against the case where the previous index is already outside the current window (last_seen[c] >= left).

Related Google favourites: LeetCode 76 (Minimum Window Substring), LeetCode 239 (Sliding Window Maximum, which needs a monotonic deque on top of the window), LeetCode 567 (Permutation in String).

Reach for Two Pointers when the input is sorted (or can be sorted cheaply) and the problem asks for a pair, triple, or partition that satisfies a predicate. The two pointers walk toward each other from the ends, or in the same direction at different speeds, and prune the search to O(n) instead of O(n^2).

LeetCode 15, Three Sum, is the most-asked instance. Sort the array, fix the first element, then run a two-pointer sweep for the remaining pair sum:

def three_sum(nums):
    nums.sort()
    out = []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i - 1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                out.append([nums[i], nums[l], nums[r]])
                l += 1; r -= 1
                while l < r and nums[l] == nums[l - 1]: l += 1
                while l < r and nums[r] == nums[r + 1]: r -= 1
            elif s < 0: l += 1
            else: r -= 1
    return out

The mistake interviewers grade hardest on is duplicate handling. Skipping the duplicate-skip loops gives you the right sums but a wrong (multi-set) output. Mention duplicate handling out loud before you code it, then add the two inner while loops on purpose.

Other shapes: LeetCode 11 (Container With Most Water), LeetCode 42 (Trapping Rain Water with two pointers), LeetCode 125 (Valid Palindrome).

This pattern is for cycle detection and middle-finding on linked lists or implicit functional graphs (like Happy Number, where the "next" is sum_of_squares_of_digits). One pointer advances by one, the other by two; if they meet, there is a cycle.

LeetCode 142, Linked List Cycle II, asks for the node where the cycle begins. Floyd's proof gives an elegant second phase: once fast and slow meet, reset slow to head and walk both at speed 1; they meet at the cycle start.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Edge cases interviewers check: empty list, single node with no cycle, single node whose next points to itself, cycle that starts at the head. The most common bug is forgetting the fast.next null check, which crashes on even-length acyclic lists.

Related: LeetCode 202 (Happy Number), LeetCode 876 (Middle of the Linked List), LeetCode 287 (Find the Duplicate Number, where the array is treated as a functional graph).

Use this when intervals can overlap and you need to merge, count, or assign resources to them. The standard move is to sort by start time, then sweep once, merging the current interval with the next whenever they overlap.

LeetCode 56, Merge Intervals, is the base case. LeetCode 253, Meeting Rooms II, is the same pattern with a heap of end times to count concurrent meetings.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

Two failure modes interviewers test: closed vs half-open intervals (does [1,2] overlap [2,3]?), and remembering to take max(out[-1][1], end) rather than just end (otherwise you shrink the merged interval when a fully-contained one comes next). Ask the interviewer about the interval convention before you code, and pick up the clarification signal.

Related: LeetCode 57 (Insert Interval), LeetCode 435 (Non-overlapping Intervals), LeetCode 986 (Interval List Intersections, which uses a two-pointer sweep over two sorted lists).

When the input is a permutation (or near-permutation) of 1..n or 0..n, you can sort it in O(n) and O(1) extra space by swapping each element to its correct index. It only works when values are bounded by the index range.

LeetCode 268 (Missing Number), LeetCode 41 (First Missing Positive), and LeetCode 448 (Find All Numbers Disappeared in an Array) all fall here.

def first_missing_positive(nums):
    n = len(nums)
    i = 0
    while i < n:
        v = nums[i]
        if 1 <= v <= n and nums[v - 1] != v:
            nums[v - 1], nums[i] = nums[i], nums[v - 1]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Watch for the trap: the while loop must advance i only when no swap happened. Beginners write a for loop and lose the in-place guarantee, dropping the runtime to O(n^2) for adversarial inputs. Also remember to ignore values outside [1, n], otherwise you index out of bounds.

Cyclic sort is the rare pattern Google interviewers love specifically because it shows you noticed the value-bound constraint. Saying "the array is length n and the values are in [1, n], so we can sort in place by index" earns immediate algorithm-choice signal.

Three pointers, no extra space: prev, curr, next. Flip pointers as you walk. Variants reverse a sub-list between two indices (LeetCode 92), reverse in groups of k (LeetCode 25), or reverse to detect palindromes (LeetCode 234, which uses fast-slow to find the middle, then reverses the second half).

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

The recursive version is short but stack-bounded; mention both and pick the iterative one in interviews for the O(1)-space sale. The edge case interviewers love is k-group reversal where the tail has fewer than k nodes left (LeetCode 25). Decide up front whether the leftover stays as-is or gets reversed anyway, then state it before coding.

A second classic bug: forgetting to set the old head's next to None. After reversing 1 -> 2 -> 3, node 1 still points at node 2 unless you handle it via the loop invariant. The prev = None start handles this naturally; reviewers grade you on whether you actually understand why.

BFS visits a tree level by level using a queue. It is the right pattern when the answer depends on depth, level ordering, or shortest-path counts in an unweighted graph.

LeetCode 102 (Binary Tree Level Order Traversal) is the template. LeetCode 199 (Right Side View) is the same scaffold with one extra line.

from collections import deque
def level_order(root):
    if not root: return []
    q, out = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

The non-obvious bit is the for _ in range(len(q)) line, which freezes the level boundary before children are added. Skip it and you mix levels together. Interviewers also probe whether you remember to handle the empty-root case explicitly rather than letting the loop start with None.

Related: LeetCode 103 (Zigzag Level Order, where alternating levels reverse), LeetCode 116 (Populating Next Right Pointers), LeetCode 994 (Rotting Oranges, BFS on a grid with multi-source start).

DFS goes as deep as possible before backtracking. It is the right pattern for path sums, subtree properties, and any problem where the answer at a node depends on answers from its children.

LeetCode 124 (Binary Tree Maximum Path Sum) is a Google favourite because it forces the two-value return trick: the maximum path that uses the node as an endpoint (returnable to the parent) is different from the maximum path that passes through the node (a global answer).

def max_path_sum(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if not node: return 0
        l = max(gain(node.left), 0)
        r = max(gain(node.right), 0)
        best = max(best, node.val + l + r)
        return node.val + max(l, r)
    gain(root)
    return best

The most common bug here is returning node.val + l + r instead of node.val + max(l, r). The former double-counts both branches, which is correct for the global answer but wrong for what bubbles up to the parent. Separating the two values explicitly is what reviewers grade.

Related: LeetCode 543 (Diameter of Binary Tree, same two-value trick), LeetCode 236 (Lowest Common Ancestor), LeetCode 437 (Path Sum III, which combines DFS with a prefix-sum hash map).

Plain binary search on a sorted array is one problem. The interesting Google variants search on a property that becomes monotone over the index, not on equality with a target. Think "smallest x such that f(x) is true", where f is monotone.

LeetCode 33 (Search in Rotated Sorted Array), LeetCode 410 (Split Array Largest Sum), and LeetCode 875 (Koko Eating Bananas) all use binary search on the answer space.

def min_eating_speed(piles, h):
    def hours(k):
        return sum((p + k - 1) // k for p in piles)
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

The off-by-one trap is which side you use for the mid update. The rule: if the predicate is "good enough" and you want the smallest such value, use hi = mid and lo = mid + 1, and exit on lo == hi. Get the invariant wrong and you either infinite-loop or skip the answer. Write the invariant in a comment before you code; interviewers will notice.

Related: LeetCode 153 (Find Minimum in Rotated Sorted Array), LeetCode 540 (Single Element in a Sorted Array), LeetCode 4 (Median of Two Sorted Arrays, the hardest of the bunch).

For "give me the largest, smallest, most-frequent K", reach for a heap of size K. Building a heap of size K and pushing all N elements is O(n log k), which beats sorting at O(n log n) when k is small.

LeetCode 215 (Kth Largest Element in an Array) and LeetCode 347 (Top K Frequent Elements) are the canonical Google asks.

import heapq
def top_k_frequent(nums, k):
    from collections import Counter
    counts = Counter(nums)
    heap = []
    for num, freq in counts.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for _, num in heap]

The trap is direction: for the K largest, keep a min-heap of size K and pop the smallest when you exceed K. Candidates flip this and end up with the K smallest by accident. State the heap type out loud before you instantiate it.

For LeetCode 215 specifically, the strongest answer mentions quickselect (average O(n), worst O(n^2)) and explains when you would pick it over the heap. The heap is more interview-safe; quickselect is the swagger answer.

Related: LeetCode 692 (Top K Frequent Words, where ties break lexicographically), LeetCode 295 (Find Median from Data Stream, which uses two heaps), LeetCode 973 (K Closest Points to Origin).

Merging K sorted lists or streams. The natural data structure is a min-heap holding one element from each list, plus a pointer back into the source list so you can advance after you pop.

LeetCode 23, Merge K Sorted Lists, is the textbook problem. LeetCode 378 (Kth Smallest Element in a Sorted Matrix) and LeetCode 632 (Smallest Range Covering Elements from K Lists) are variations.

import heapq
def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = ListNode()
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

The index i in the heap tuple is there to break ties when two nodes have equal values, because Python's heap will try to compare the ListNode objects directly and crash. Forgetting this is one of the most common bugs in this exact problem.

Total runtime is O(N log k) where N is the total number of nodes. Compare this to repeatedly merging two lists (O(N * k) worst case) and you have the algorithm-choice signal in one sentence.

Backtracking over a choice space. Each recursive call decides whether to include the next element, and the base case emits the current partial. This pattern covers subsets, permutations, combinations, palindrome partitioning, and N-Queens.

LeetCode 78 (Subsets) is the simplest template:

def subsets(nums):
    out = []
    def backtrack(start, path):
        out.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return out

The two failure modes: appending path (a reference) instead of path[:] (a copy), so every emitted subset is the same final empty list. And, for LeetCode 90 (Subsets II) with duplicates, you need the if i > start and nums[i] == nums[i-1]: continue skip after sorting; forgetting it gives duplicate subsets.

Interviewers grade on two things: do you state the recurrence ("at each index, include or exclude") before you code, and do you analyze runtime correctly (O(n * 2^n) for subsets, because there are 2^n subsets and each one is up to n long to copy out)?

Related: LeetCode 46 (Permutations), LeetCode 39 (Combination Sum), LeetCode 131 (Palindrome Partitioning), LeetCode 51 (N-Queens for the harder pruning case).

The signal is in the problem statement. A short cheat sheet:

When two patterns plausibly fit, pick the one with the cleaner invariant and say why out loud. Reviewers grade the choice as much as the code.

Patterns are necessary but not sufficient. The recurring complaints from Google interviewer feedback (collected anecdotally across published guides):

Pick one pattern per session. Solve three problems on it: one easy, one medium, one hard. Time yourself on the medium (25 minutes) and the hard (45 minutes). After each, write one line in a notebook: what shape signalled the pattern, what bug you hit, what the time/space complexity was. After 12 sessions, you have a personal cheat sheet that beats any LeetCode roadmap.

If you want the same kind of timed pressure with structured feedback, that is what Interview Coder drills against. The point is reps under conditions that match the real round, not passive reading.

The patterns themselves are not the secret. They are the public, well-documented scaffolding that lets you spend interview time on the parts Google actually grades: framing the problem, picking the right approach out loud, writing clean code, and verifying it before the timer runs out.