Common Interview Patterns — Deep Dive

Pattern implementation guide

Each pattern below includes a template implementation, a real interview problem solved with that pattern, and complexity analysis. These are the building blocks that cover the vast majority of coding interview questions at top tech companies.

1. Hash map frequency counter

Template

from collections import Counter

def frequency_pattern(items):
    counts = Counter(items)
    # Query counts as needed
    return counts

Real problem: Group Anagrams

Given a list of strings, group the anagrams together.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # anagrams share sorted form
        groups[key].append(s)
    return list(groups.values())

# group_anagrams(["eat","tea","tan","ate","nat","bat"])
# → [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Time: O(n × k log k) where n is the number of strings and k is the max string length. Space: O(n × k) for storing all strings in the hash map.

Optimization: Instead of sorting each string (k log k), count character frequencies using a tuple of 26 counts as the key — reduces to O(n × k).

def group_anagrams_fast(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(s.count(c) for c in 'abcdefghijklmnopqrstuvwxyz')
        groups[key].append(s)
    return list(groups.values())

2. Two pointers

Template

def two_pointer_converge(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        # Process arr[left] and arr[right]
        if condition_to_move_left:
            left += 1
        else:
            right -= 1

Real problem: Container With Most Water

Given heights, find two lines that form a container holding the most water.

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        best = max(best, width * h)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Time: O(n). Space: O(1).

Why it works: Moving the shorter line inward is always correct because keeping it cannot produce a larger area (width decreases, height is capped by the shorter line).

3. Sliding window

Template

def sliding_window(arr, condition):
    left = 0
    window_state = {}  # track window contents
    best = 0
    for right in range(len(arr)):
        # Add arr[right] to window state
        while not condition(window_state):
            # Remove arr[left] from window state
            left += 1
        best = max(best, right - left + 1)
    return best

Real problem: Longest Substring Without Repeating Characters

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

Time: O(n). Space: O(min(n, alphabet_size)).

The seen dict stores the last index of each character. When a duplicate is found, the left pointer jumps past the previous occurrence.

4. Binary search

Template

def binary_search_boundary(lo, hi, condition):
    while lo < hi:
        mid = (lo + hi) // 2
        if condition(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Real problem: Koko Eating Bananas

Koko has piles of bananas and h hours. Find the minimum eating speed to finish all piles in h hours.

import math

def min_eating_speed(piles, h):
    def can_finish(speed):
        return sum(math.ceil(p / speed) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Time: O(n × log(max_pile)). Space: O(1).

This is binary search on the answer space — a powerful technique where you binary search over possible solutions rather than a sorted array.

5. BFS/DFS

BFS template

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Real problem: Number of Islands

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # mark visited
        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) for recursion stack in worst case.

6. Stack (monotonic stack)

Real problem: Daily Temperatures

Given daily temperatures, find how many days until a warmer temperature.

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []  # indices of unresolved days
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev = stack.pop()
            result[prev] = i - prev
        stack.append(i)
    return result

Time: O(n) — each index is pushed and popped at most once. Space: O(n).

7. Dynamic programming

Real problem: Coin Change

Find the minimum number of coins to make a given amount.

def coin_change(coins, 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

Time: O(amount × len(coins)). Space: O(amount).

Recurrence: dp[a] = min(dp[a - coin] + 1) for each coin ≤ a. Base case: dp[0] = 0.

8. Backtracking

Real problem: Subsets

Generate all subsets of a list of distinct integers.

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

Time: O(n × 2ⁿ). Space: O(n) for recursion depth (excluding output).

9. Greedy

Real problem: Jump Game

Given an array where each element is the max jump length, determine if you can reach the last index.

def can_jump(nums):
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
    return True

Time: O(n). Space: O(1).

Greedy insight: Track the farthest reachable index. If the current index exceeds it, you are stuck.

10. Heap / Priority Queue

Real problem: Merge K Sorted Lists

import heapq

def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
    return result

Time: O(N log k) where N is total elements and k is number of lists. Space: O(k) for the heap.

Combining patterns

Real interview problems often combine two patterns. Examples:

• Sliding window + hash map: Minimum window substring
• Binary search + greedy: Split array largest sum
• BFS + hash map: Word ladder
• Stack + DP: Largest rectangle in histogram
• Two pointers + sorting: 3Sum

When a problem does not fit one pattern cleanly, consider combining two. The constraint analysis guides you: if n ≤ 10⁵, you need O(n log n) or better, which eliminates brute force and narrows the pattern choices.

Interview execution framework

1. Clarify (2 min): Ask about edge cases, constraints, input format.
2. Pattern match (3 min): Identify which pattern(s) apply. State your approach out loud.
3. Code (15 min): Write clean code using the pattern template. Use meaningful variable names.
4. Test (5 min): Trace through an example. Test edge cases (empty input, single element, all same).
5. Optimize (5 min): State the complexity. Discuss if a better approach exists.

One thing to remember: Every interview problem is a pattern in disguise. The skill is not memorizing solutions — it is recognizing which 2-3 patterns could apply, choosing the right one, and adapting the template to the specific problem constraints.