FAANG Interview Pattern Recognition

How to Use This Guide

Most interview failures come not from not knowing an algorithm, but from failing to recognise which pattern applies. This guide trains the recognition reflex: read the problem → spot the keyword cluster → map to a pattern → implement.

The Recognition Loop

Step 1: Read the problem statement. Underline the constraints (sorted? distinct? in-place? shortest? count?).

Step 2: Match keywords against the pattern table below.

Step 3: State the pattern out loud: "I think this is a [sliding window / BFS / DP] problem because..."

Step 4: Verify with a small example before coding. Write the template, then fill in problem-specific logic.

Master Pattern Table

                            
                                PatternKeywords in ProblemTimeKey Data Structure

                                Two Pointersorted array, pair sum, palindrome, in-place reverseO(n)Array (two indices)
Sliding Windowsubarray/substring, contiguous, longest/shortest, windowO(n)Deque or hashmap
BFSshortest path, level-order, minimum steps, unweighted graphO(V+E)Queue (deque)
DFSall paths, connected components, cycle detection, count waysO(V+E)Stack / recursion
Backtrackingall combinations/permutations, generate, find all solutionsO(2^n) or O(n!)Recursion + visited set
Binary Search on Answerminimum/maximum possible value, feasibility, "if you can do X"O(n log n)Array (sorted answer space)
Monotonic Stacknext/previous greater/smaller, histogram, temperatureO(n)Stack
Monotonic Dequesliding window max/minO(n)Deque
Heap (Top-K)K largest/smallest/closest, median, priorityO(n log K)Min/max heap
1D DPmaximize/minimize with 1 variable, climb stairs, coin changeO(n)Array dp[n]
2D DPgrid path, edit distance, LCS, string comparisonO(n×m)Matrix dp[n][m]
Interval DPmerge intervals, burst balloons, matrix chainO(n²) or O(n³)dp[i][j]
Union-Findconnected components, merge groups, number of islandsO(α(n))DSU array
Trieprefix, autocomplete, word search, XORO(L)Trie nodes

                            
                        

Pattern	Keywords in Problem	Time	Key Data Structure
Two Pointer	sorted array, pair sum, palindrome, in-place reverse	O(n)	Array (two indices)
Sliding Window	subarray/substring, contiguous, longest/shortest, window	O(n)	Deque or hashmap
BFS	shortest path, level-order, minimum steps, unweighted graph	O(V+E)	Queue (deque)
DFS	all paths, connected components, cycle detection, count ways	O(V+E)	Stack / recursion
Backtracking	all combinations/permutations, generate, find all solutions	O(2^n) or O(n!)	Recursion + visited set
Binary Search on Answer	minimum/maximum possible value, feasibility, "if you can do X"	O(n log n)	Array (sorted answer space)
Monotonic Stack	next/previous greater/smaller, histogram, temperature	O(n)	Stack
Monotonic Deque	sliding window max/min	O(n)	Deque
Heap (Top-K)	K largest/smallest/closest, median, priority	O(n log K)	Min/max heap
1D DP	maximize/minimize with 1 variable, climb stairs, coin change	O(n)	Array dp[n]
2D DP	grid path, edit distance, LCS, string comparison	O(n×m)	Matrix dp[n][m]
Interval DP	merge intervals, burst balloons, matrix chain	O(n²) or O(n³)	dp[i][j]
Union-Find	connected components, merge groups, number of islands	O(α(n))	DSU array
Trie	prefix, autocomplete, word search, XOR	O(L)	Trie nodes

Two Pointer

Use two pointers when the array is sorted (or can be) and you're looking for pairs or palindromic properties. The pointers move toward each other or in the same direction (fast/slow).

Template: Two-Sum on Sorted Array

Keywords: sorted array, find pair with sum = target, no extra space.

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

# LeetCode 167: Two Sum II
print(two_sum_sorted([2,7,11,15], 9))  # [0,1]

Canonical problems: Two Sum II (167), Container With Most Water (11), 3Sum (15), Valid Palindrome (125), Trapping Rain Water (42).

Sliding Window

Sliding window solves "find longest/shortest subarray/substring satisfying condition X" in O(n). Expand right until condition violated; shrink left until condition restored.

Template: Longest Substring with At Most K Distinct Characters

from collections import defaultdict

def longest_substring_k_distinct(s, k):
    """O(n) sliding window with frequency map."""
    freq = defaultdict(int)
    left = 0
    max_len = 0

    for right in range(len(s)):
        freq[s[right]] += 1                      # expand window
        while len(freq) > k:                     # shrink if constraint violated
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        max_len = max(max_len, right - left + 1) # update answer

    return max_len

print(longest_substring_k_distinct("araaci", 2))  # 4 ("araa")

Canonical problems: Minimum Window Substring (76), Longest Substring Without Repeating Characters (3), Sliding Window Maximum (239), Permutation in String (567).

BFS vs DFS Decision

                            
                                QuestionUse BFSUse DFS

                                Shortest path (unweighted)?YesNo
Find if any path exists?EitherYes (simpler)
Count all paths?NoYes (backtracking)
Topological order?Kahn's (BFS)Post-order DFS
Detect cycle?EitherYes (DFS colors)
Tree level order?Yes (natural)Need explicit level tracking

Question	Use BFS	Use DFS
Shortest path (unweighted)?	Yes	No
Find if any path exists?	Either	Yes (simpler)
Count all paths?	No	Yes (backtracking)
Topological order?	Kahn's (BFS)	Post-order DFS
Detect cycle?	Either	Yes (DFS colors)
Tree level order?	Yes (natural)	Need explicit level tracking

Backtracking Template

Universal Backtracking Template

def backtrack(result, current, remaining_choices, ...):
    # Base case: if current is a complete solution
    if is_complete(current):
        result.append(current[:])  # copy!
        return

    for choice in remaining_choices:
        if is_valid(choice, current):
            current.append(choice)           # CHOOSE
            backtrack(result, current, ...)  # EXPLORE
            current.pop()                    # UNCHOOSE (backtrack)


# Example: Generate all subsets (LeetCode 78)
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])   # every state is valid (power set)
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Canonical problems: Subsets (78), Permutations (46), Combination Sum (39), N-Queens (51), Word Search (79), Sudoku Solver (37).

Dynamic Programming Patterns

DP works when the problem has: (1) optimal substructure — optimal solution contains optimal solutions to subproblems, and (2) overlapping subproblems — same subproblems recur many times.

1D DP Template: Coin Change

def coin_change(coins, amount):
    """LeetCode 322. Minimum coins to make amount."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)

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

print(coin_change([1, 5, 11], 15))  # 3 (11+3*1? No: 5+5+5=3 coins ✓)

2D DP: Edit Distance

Longest Common Subsequence (LeetCode 1143)

def lcs(text1, text2):
    m, n = len(text1), len(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]

print(lcs("abcde", "ace"))  # 3 (a,c,e)

Interval DP: Burst Balloons

Burst Balloons (LeetCode 312)

Think: which balloon is burst last in a range [i, j]? dp[i][j] = max coins from range i..j.

def maxCoins(nums):
    nums = [1] + nums + [1]  # pad with boundary 1s
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):          # window size
        for left in range(0, n - length):
            right = left + length
            for k in range(left+1, right):  # k = last balloon to burst
                dp[left][right] = max(
                    dp[left][right],
                    nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]
                )
    return dp[0][n-1]

print(maxCoins([3, 1, 5, 8]))  # 167

Monotonic Stack

Use when the problem asks: "for each element, find the nearest element to the left/right that is greater/smaller." Every element enters and exits the stack exactly once — O(n) total.

Next Greater Element (LeetCode 496)

def next_greater_element(nums1, nums2):
    """For each num in nums1, find the next greater element in nums2. O(n)."""
    next_greater = {}
    stack = []  # monotonically decreasing

    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num  # found next greater
        stack.append(num)

    while stack:
        next_greater[stack.pop()] = -1  # no next greater

    return [next_greater[n] for n in nums1]

print(next_greater_element([4,1,2], [1,3,4,2]))  # [-1, 3, -1]

Canonical problems: Next Greater Element (496, 503), Daily Temperatures (739), Largest Rectangle in Histogram (84), Trapping Rain Water (42).

Binary Search on Answer

Use when the problem asks for "minimum/maximum value such that a condition holds". Binary search the answer space, check feasibility with a helper function.

Koko Eating Bananas (LeetCode 875)

import math

def min_eating_speed(piles, h):
    """Minimum speed k such that Koko finishes all piles in h hours."""
    def can_finish(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid     # try smaller speed
        else:
            left = mid + 1  # need faster speed
    return left

print(min_eating_speed([3,6,7,11], 8))  # 4

Canonical problems: Search Insert Position (35), Find Peak Element (162), Koko Eating Bananas (875), Split Array Largest Sum (410), Capacity to Ship (1011).

Heap — Top-K Pattern

K Closest Points to Origin (LeetCode 973)

import heapq

def k_closest(points, k):
    """O(n log k) — min-heap of size k (negate distance for max-heap)."""
    # Max-heap of size k: if distance > heap root, don't add
    heap = []  # (-dist, x, y)

    for x, y in points:
        dist = -(x*x + y*y)  # negate for max-heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove the farthest

    return [[x, y] for (_, x, y) in heap]

print(k_closest([[1,3],[-2,2],[5,8],[0,1]], 2))  # [[0,1],[-2,2]]

Canonical problems: K Closest Points (973), Top K Frequent Elements (347), Kth Largest Element (215), Merge K Sorted Lists (23), Median from Data Stream (295).

The 45-Minute Interview Framework

                            Time Budget
                            
                                TimeActivityWhat to Say

                                0–5 minClarify constraints"Is the array sorted? Can it have duplicates? What's the expected input size?"
5–10 minPattern recognition + brute force"My first thought is O(n²) brute force... but I recognise this as a [pattern] problem, which should give O(n)."
10–12 minVerify approach with small exampleTrace through 3–4 elements manually. Catch edge cases.
12–35 minCodeWrite clean code with meaningful variable names. Talk through each step.
35–40 minTestRun through your example, then edge cases: empty input, single element, all same, sorted, reverse-sorted.
40–45 minComplexity analysis"Time: O(n log n) because... Space: O(n) because... Could we reduce space to O(1) by...?"

                            
                        

Time	Activity	What to Say
0–5 min	Clarify constraints	"Is the array sorted? Can it have duplicates? What's the expected input size?"
5–10 min	Pattern recognition + brute force	"My first thought is O(n²) brute force... but I recognise this as a [pattern] problem, which should give O(n)."
10–12 min	Verify approach with small example	Trace through 3–4 elements manually. Catch edge cases.
12–35 min	Code	Write clean code with meaningful variable names. Talk through each step.
35–40 min	Test	Run through your example, then edge cases: empty input, single element, all same, sorted, reverse-sorted.
40–45 min	Complexity analysis	"Time: O(n log n) because... Space: O(n) because... Could we reduce space to O(1) by...?"

                            Common Interview Mistakes
                            Coding without clarifying: Always ask about constraints before touching the keyboard.
Jumping to optimal immediately: State brute force first, then optimise. Interviewers want to see your reasoning process.
Silent coding: Think out loud. If you're stuck, say "I'm thinking about whether I can use X here..."
Forgetting edge cases: Always test empty input and single-element input.
Wrong complexity claim: If you say O(n), know exactly why. Interviewers probe this.

                        

Table of Contents