Python · Lesson 12

Interview Patterns in Python

The coding-interview patterns written the Python way (hash maps, two pointers, sliding windows, prefix sums, stacks, BFS and DFS, binary search, heaps, intervals and dynamic programming), what each costs, how to recognise it, and how to talk through a solution.

19 min read

In short

  • Know the costs: pop(0) and x in list are O(n)
  • Dicts and Counters replace inner search loops
  • Windows and two pointers only move forward
  • BFS with deque; DFS with your own stack when deep
  • Heaps, bisect, sort-then-sweep, @cache and tables
  • Talk it through: brute force, bottleneck, pattern, cost

Most coding-interview questions are one of about a dozen patterns in disguise. Once you can name the pattern, the solution is mostly known, and what's left is writing it cleanly and explaining what it costs. Python is the best language for this: dict, Counter, deque, heapq, bisect and functools.cache are each one import away, and the code stays short enough to say out loud.

This topic assumes you know the patterns from JavaScript, TypeScript or C# at least a little, and shows the idiomatic Python for each one, with its complexity and a "how to recognise it" line. It starts with what Python's built-ins cost, because an O(n) operation hiding inside a loop is the most common way a correct Python answer turns out O(n²).

Every snippet has a ▶ Try button. Predict the output first, then run it.

What Python's built-ins cost

Interviewers expect you to know these. "Average" means with a reasonable hash function, which is what you always get for ints, strings and tuples.

OperationCostNotes
xs.append(x), xs.pop()O(1) amortisedThe end of a list is cheap
xs[i], xs[i] = x, len(xs)O(1)A list is a dynamic array, like List<T> or a JS array
xs.pop(0), xs.insert(0, x)O(n)Shifts every other element; use deque
x in xs, xs.index(x), xs.count(x), xs.remove(x)O(n)A linear scan
xs[a:b], xs.copy(), xs + ysO(k)Slicing and concatenation copy
x in s, s.add(x) for a setO(1) averageHash lookup
d[k], d[k] = v, k in d, del d[k]O(1) averageHash lookup; k in d checks keys
dq.append, dq.appendleft, dq.pop, dq.popleftO(1)collections.deque
heapq.heappush, heapq.heappopO(log n)h[0] peeks the smallest in O(1)
heapq.heapify(xs)O(n)Faster than n pushes
sorted(xs), xs.sort()O(n log n)Stable (Timsort); sort is in place
bisect.bisect_left(xs, x)O(log n)insort is O(n): it still shifts elements
min(xs), max(xs), sum(xs)O(n)Each one is a full pass
s += t in a loop, for stringsO(n²) totalStrings are immutable; collect parts and "".join once

Two of these cause most surprises. pop(0) on a list looks like a queue but shifts every element, and in on a list looks like a set lookup but scans:

▶ Try
from collections import deque

queue = [1, 2, 3]
first = queue.pop(0)      # O(n): moves 2 and 3 one slot left
dq = deque([1, 2, 3])
also_first = dq.popleft() # O(1)
print(first, also_first, queue, list(dq))

banned = ["spam", "scam", "phish"]
banned_set = set(banned)  # build once: O(n)
print("scam" in banned, "scam" in banned_set)  # O(n) scan vs O(1) hash lookup

Building a string with += in a loop can copy the whole string each time. Collect the pieces in a list and join once:

▶ Try
parts = []
for i in range(5):
    parts.append(str(i))
print("-".join(parts))
print(",".join(f"{n * n}" for n in range(4)))

(CPython sometimes optimises s += t in place, but only sometimes. Don't rely on it in an interview.)

Hash maps: counting and lookups

Recognise it: "have I seen this before?", "how many of each?", "find a pair that...", or any time a nested loop is searching for something. Trading O(n) memory for O(1) lookups is the most common optimisation there is.

Cost: O(n) time and O(n) space for one pass.

Two-sum in one pass: for each number, look up the partner you need, then remember the number.

▶ Try
def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    seen: dict[int, int] = {}            # value -> index
    for i, n in enumerate(nums):
        if target - n in seen:
            return (seen[target - n], i)
        seen[n] = i
    return None


print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 3], 6))
print(two_sum([1, 2], 7))

collections.Counter counts in one line, and defaultdict groups without "is the key there yet?" checks:

▶ Try
from collections import Counter, defaultdict

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(Counter("mississippi").most_common(2))

groups: defaultdict[str, list[str]] = defaultdict(list)
for w in words:
    groups["".join(sorted(w))].append(w)   # anagrams share a sorted key
print(list(groups.values()))
print(Counter("listen") == Counter("silent"))

most_common breaks ties by first appearance, which is why i comes before s (both appear 4 times). Dicts keep insertion order, so groups.values() comes out in the order each group was first seen.

Two pointers

Recognise it: a sorted array and a pair or triple with some sum; reversing or checking a palindrome in place; merging two sorted lists; removing duplicates in place. Two indexes walk towards each other (or in the same direction) and each step rules out part of the input.

Cost: O(n) time, O(1) extra space (plus O(n log n) if you have to sort first).

▶ Try
def pair_with_sum(sorted_nums: list[int], target: int) -> tuple[int, int] | None:
    lo, hi = 0, len(sorted_nums) - 1
    while lo < hi:
        total = sorted_nums[lo] + sorted_nums[hi]
        if total == target:
            return (sorted_nums[lo], sorted_nums[hi])
        if total < target:
            lo += 1        # need more: the smallest value can't be in any pair
        else:
            hi -= 1        # need less: the largest value can't be in any pair
    return None


def is_palindrome(s: str) -> bool:
    chars = [c.lower() for c in s if c.isalnum()]
    return chars == chars[::-1]


print(pair_with_sum([1, 3, 4, 6, 9], 10))
print(pair_with_sum([1, 2, 3], 100))
print(is_palindrome("A man, a plan, a canal: Panama"))

chars[::-1] builds a reversed copy, which is O(n) space. When the interviewer asks for O(1) space, compare s[lo] with s[hi] and move the pointers inward instead.

Sliding window

Recognise it: "contiguous subarray" or "substring" plus "longest", "shortest", "maximum sum" or "at most k". A window [start, end] slides along the input, and you update a running total or count as elements enter and leave, instead of recomputing it.

Cost: O(n) time; O(1) space for a running sum, O(k) for a dict of counts.

A fixed window adds the new element and removes the one that fell out:

▶ Try
def max_window_sum(nums: list[int], k: int) -> int:
    window = sum(nums[:k])
    best = window
    for end in range(k, len(nums)):
        window += nums[end] - nums[end - k]
        best = max(best, window)
    return best


print(max_window_sum([2, 1, 5, 1, 3, 2], 3))

A variable window grows at end and shrinks from start while it breaks a rule. Here: the longest substring with at most k distinct characters.

▶ Try
from collections import Counter


def longest_with_k_distinct(s: str, k: int) -> int:
    counts: Counter[str] = Counter()
    start = best = 0
    for end, ch in enumerate(s):
        counts[ch] += 1
        while len(counts) > k:           # too many distinct: shrink from the left
            counts[s[start]] -= 1
            if counts[s[start]] == 0:
                del counts[s[start]]
            start += 1
        best = max(best, end - start + 1)
    return best


print(longest_with_k_distinct("eceba", 2))
print(longest_with_k_distinct("aabbcc", 1))

It's O(n) even with the inner while: start only moves forward, so across the whole run it moves at most n times. Note the del: a Counter keeps keys whose count drops to zero, and len(counts) would count them.

Prefix sums

Recognise it: many "sum of the range i to j" questions on data that doesn't change, or "how many subarrays sum to k" (especially with negative numbers, where a sliding window doesn't work).

Cost: O(n) to build, then O(1) per range query.

prefix[i] is the sum of the first i elements, so the sum of nums[i:j] is prefix[j] - prefix[i]. itertools.accumulate builds it:

▶ Try
from collections import Counter
from itertools import accumulate

nums = [3, -1, 4, 1, -5, 9]
prefix = [0, *accumulate(nums)]
print(prefix)
print(prefix[4] - prefix[1])       # sum of nums[1:4] = -1 + 4 + 1


def count_subarrays_with_sum(nums: list[int], k: int) -> int:
    seen = Counter({0: 1})         # the empty prefix
    total = count = 0
    for n in nums:
        total += n
        count += seen[total - k]   # earlier prefixes that leave exactly k
        seen[total] += 1
    return count


print(count_subarrays_with_sum([1, 1, 1], 2))
print(count_subarrays_with_sum([3, 4, -7, 3, 1, 3, 1, -4], 7))

The second function is two-sum again, run on prefix sums: a subarray sums to k when two prefixes differ by k.

Stacks

Recognise it: matching pairs (brackets, tags), undo, evaluating expressions, "the most recent unmatched thing", and "the next greater/smaller element" (a monotonic stack). A Python list is the stack: append pushes, pop pops, stack[-1] peeks, all O(1).

Cost: O(n) time, O(n) space.

▶ Try
def balanced(text: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack                 # anything left open is unbalanced


for t in ["f(a[1], {b: 2})", "(]", "((", ""]:
    print(repr(t), balanced(t))

A monotonic stack keeps its elements in sorted order by popping everything a new element beats. Each element is pushed and popped at most once, so the nested loop is still O(n) overall. Next greater element:

▶ Try
def next_greater(nums: list[int]) -> list[int]:
    result = [-1] * len(nums)
    stack: list[int] = []            # indexes waiting for a greater value
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            result[stack.pop()] = n
        stack.append(i)
    return result


print(next_greater([2, 1, 2, 4, 3]))

Queues and BFS

Recognise it: "shortest path", "fewest steps", "minimum moves" when every step costs the same; anything "level by level" (a tree's levels, degrees of separation); spreading from several sources at once (rotting oranges, distance to the nearest exit). BFS visits nodes in order of distance, so the first time it reaches a node is the shortest way there.

Cost: O(V + E) time and O(V) space; on a grid, O(rows × cols).

Use collections.deque as the queue. Mark a node as seen when you enqueue it, so nothing is queued twice. On a graph stored as an adjacency dict:

▶ Try
from collections import deque

graph = {
    "ann": ["bob", "cat"],
    "bob": ["dan"],
    "cat": ["dan", "eve"],
    "dan": ["fay"],
    "eve": [],
    "fay": [],
}


def hops(start: str) -> dict[str, int]:
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist


print(hops("ann"))

On a grid, the neighbours are the four squares around you, inside the bounds and not blocked:

▶ Try
from collections import deque


def steps_to_exit(grid: list[str]) -> int:
    rows, cols = len(grid), len(grid[0])
    dist = {(0, 0): 0}
    queue = deque([(0, 0)])
    while queue:
        r, c = queue.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return dist[(r, c)]
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "." and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                queue.append((nr, nc))
    return -1


print(steps_to_exit(["..#",
                     "#..",
                     "#.."]))
print(steps_to_exit([".#",
                     "#."]))

Check the bounds before indexing: grid[-1] doesn't raise in Python, it quietly reads the last row.

DFS and recursion

Recognise it: "explore everything reachable" (count islands, connected components, flood fill), "all paths / all combinations / all subsets" (backtracking), tree problems (depth, path sums), cycle detection and topological order. DFS goes deep first; it does not find shortest paths.

Cost: O(V + E) time; O(V) space for seen, plus the recursion depth.

Recursive DFS is the shortest to write. Counting islands on a grid:

▶ Try
def count_islands(grid: list[str]) -> int:
    rows, cols = len(grid), len(grid[0])
    seen: set[tuple[int, int]] = set()

    def sink(r: int, c: int) -> None:
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "#" or (r, c) in seen:
            return
        seen.add((r, c))
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            sink(nr, nc)

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "#" and (r, c) not in seen:
                islands += 1
                sink(r, c)
    return islands


print(count_islands(["##..",
                     "#..#",
                     "..##",
                     "#..."]))

The caveat: Python has no tail-call optimisation and a recursion limit of about 1,000 frames. A path, a linked list or a degenerate tree a few thousand nodes deep raises RecursionError:

▶ Try
def depth(n: int) -> int:
    return 0 if n == 0 else 1 + depth(n - 1)


print(depth(500))
try:
    depth(5000)
except RecursionError as e:
    print("RecursionError:", e)

sys.setrecursionlimit raises the limit, and since Python 3.11 plain Python recursion no longer uses the C stack, so that often works. But each frame costs memory, and recursion that goes through C code (a @cache wrapper, a key= function) still stops at a separate C limit. The safer answer is an explicit stack, which turns recursion into a loop that reaches the same nodes (not always in the same order):

▶ Try
def reachable(graph: dict[int, list[int]], start: int) -> list[int]:
    seen = {start}
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        order.append(node)
        for nxt in reversed(graph[node]):   # reversed: visit neighbours in listed order
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)
    return order


chain = {i: [i + 1] for i in range(100_000)}
chain[100_000] = []
print(len(reachable(chain, 0)))
print(reachable({1: [2, 3], 2: [4], 3: [], 4: []}, 1))

Swap the stack for a deque with popleft and the same loop is BFS. In an interview, write recursive DFS when the depth is small (balanced trees, small grids) and mention the iterative version when it isn't.

Recognise it: a sorted input and "find", "first", "last", "insert position" or "count in a range"; or, less obviously, "the minimum X such that something works" where bigger X always works if smaller X does. That second form is binary search on the answer.

Cost: O(log n) per search; O(f · log range) for search on the answer, where f is the cost of one check.

Don't hand-write the classic version: bisect does it, without off-by-one bugs. bisect_left returns the first index where x could go (before equal elements), bisect_right the last (after them):

▶ Try
from bisect import bisect_left, bisect_right

scores = [10, 20, 20, 20, 35, 50]
print(bisect_left(scores, 20), bisect_right(scores, 20))
print(bisect_right(scores, 20) - bisect_left(scores, 20))  # how many 20s
i = bisect_left(scores, 36)
print(i, i < len(scores) and scores[i] == 36)              # where 36 would go; not present
print(bisect_right(scores, 30) - bisect_left(scores, 15))  # count in [15, 30]

Search on the answer: the smallest eating speed that finishes all the piles within hours. Each check is an O(n) simulation, and the range of speeds is searched with the low < high loop, which always ends on the first value that works:

▶ Try
def min_speed(piles: list[int], hours: int) -> int:
    def hours_needed(speed: int) -> int:
        return sum((p + speed - 1) // speed for p in piles)   # ceiling division

    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if hours_needed(mid) <= hours:
            high = mid       # mid works: the answer is mid or smaller
        else:
            low = mid + 1    # mid fails: the answer is bigger
    return low


print(min_speed([3, 6, 7, 11], 8))
print(min_speed([30, 11, 23, 4, 20], 5))

Python ints never overflow, so (low + high) // 2 is safe. In Java or C# you'd write low + (high - low) / 2.

Heaps

Recognise it: "top k", "k smallest/largest", "k closest", "the median of a stream", "merge k sorted lists", scheduling ("always process the earliest deadline next"), and Dijkstra's shortest path.

Cost: O(log n) push and pop, O(1) peek, O(n) heapify; top k of n items in O(n log k).

heapq works on a plain list and is a min-heap only. For a max-heap, push negated keys. Tuples compare element by element, so (priority, tie_breaker, item) controls the order:

▶ Try
import heapq

tasks = [(3, "write tests"), (1, "fix prod"), (2, "review PR")]
heapq.heapify(tasks)
print(heapq.heappop(tasks))
print(tasks[0])                          # peek at the next smallest

nums = [5, 1, 9, 3, 7, 2]
print(heapq.nlargest(3, nums), heapq.nsmallest(2, nums))

max_heap = [-n for n in nums]
heapq.heapify(max_heap)
print(-heapq.heappop(max_heap))          # the largest

Merging k sorted lists keeps one entry per list in the heap: the smallest remaining element overall is always at the front of some list.

▶ Try
import heapq


def merge_sorted(lists: list[list[int]]) -> list[int]:
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    out = []
    while heap:
        value, i, j = heapq.heappop(heap)
        out.append(value)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out


print(merge_sorted([[1, 4, 9], [2, 3, 10], [], [5]]))
print(list(heapq.merge([1, 4, 9], [2, 3, 10], [5])))   # the library version

The list index i in each entry breaks ties between equal values, so Python never has to compare the things after it. That matters when those things are dicts or objects, which can't be compared and would raise TypeError.

Intervals

Recognise it: meetings, bookings, time ranges, "merge overlapping", "insert an interval", "can one person attend all", "how many rooms". Almost always: sort by start, then sweep left to right.

Cost: O(n log n) for the sort, then O(n) for the sweep.

▶ Try
def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    merged: list[tuple[int, int]] = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:            # overlaps the last block
            merged[-1] = (merged[-1][0], max(merged[-1][1], end))
        else:
            merged.append((start, end))
    return merged


print(merge_intervals([(8, 10), (1, 3), (2, 6), (15, 18), (17, 20)]))
print(merge_intervals([(1, 10), (2, 3)]))

How many rooms do overlapping meetings need? Sort by start, and keep a heap of end times for the rooms in use. If the earliest-ending room is free by the time the next meeting starts, reuse it:

▶ Try
import heapq


def rooms_needed(meetings: list[tuple[int, int]]) -> int:
    ends: list[int] = []
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)   # reuse the room that frees up first
        else:
            heapq.heappush(ends, end)      # open another room
    return len(ends)


print(rooms_needed([(0, 30), (5, 10), (15, 20)]))
print(rooms_needed([(9, 10), (10, 11)]))

Decide early whether touching intervals ((9, 10) and (10, 11)) overlap, and say it out loud. Here they don't, so one room is enough.

Memoisation and dynamic programming

Recognise it: "how many ways", "minimum cost", "maximum value", "is it possible", over choices that build on smaller versions of the same problem, where a plain recursive solution recomputes the same subproblems again and again. Classics: climbing stairs, coin change, house robber, longest common subsequence, edit distance, knapsack.

Cost: (number of distinct subproblems) × (work per subproblem). Space is the size of the table or cache.

Top-down: write the recursion, then add @functools.cache (Python 3.9+; lru_cache(maxsize=None) before that). The arguments become the cache key, so they must be hashable: pass tuples, not lists.

▶ Try
from functools import cache


@cache
def ways(n: int) -> int:
    """Ways to climb n stairs taking 1 or 2 steps at a time."""
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)


print(ways(5), ways(80))
print(ways.cache_info().currsize)

Without @cache, ways(80) makes more than 10¹⁶ calls; with it, each n is computed once, which is why the cache holds 81 entries. The recursion limit still applies, though: ways(5000) on a cold cache raises RecursionError.

Bottom-up: fill a table from the smallest subproblems up, with a loop and no recursion. Fewest coins to make an amount:

▶ Try
def fewest_coins(coins: list[int], amount: int) -> int:
    INF = amount + 1                      # more coins than could ever be needed
    best = [0] + [INF] * amount           # best[a] = fewest coins that make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1


print(fewest_coins([1, 5, 10, 25], 63))
print(fewest_coins([2], 3))
print(fewest_coins([1, 3, 4], 6))         # greedy 4+1+1 would say 3; the answer is 3+3

That runs in O(amount × len(coins)) time and O(amount) space. For 2D tables, build the rows with a comprehension, [[0] * (n + 1) for _ in range(m + 1)]. [[0] * (n + 1)] * (m + 1) repeats the same row object, so writing one cell changes every row:

▶ Try
bad = [[0] * 3] * 2
good = [[0] * 3 for _ in range(2)]
bad[0][0] = 1
good[0][0] = 1
print(bad, good)

In an interview, start top-down (it falls out of the recursive definition), then offer bottom-up when the input is large or when you can shrink the table to one or two rows.

Recognising the pattern

The problem says...Reach for
"find a pair / have I seen it / count each"dict, set, Counter
sorted input, pairs or in-place changestwo pointers
contiguous subarray or substring, longest/shortest/at most ksliding window
many range sums, or subarrays summing to k with negativesprefix sums + Counter
matching brackets, most recent unmatched, next greaterstack, monotonic stack
fewest steps, shortest path with equal costs, levelsBFS with deque
everything reachable, all paths or combinationsDFS (iterative if deep), backtracking
sorted lookups, or "minimum X that works"bisect, binary search on the answer
top k, k-way merge, always take the smallest nextheapq
ranges of time or numberssort by start, then sweep
count ways, min cost, overlapping subproblems@cache, then a bottom-up table

Talking through a solution

Interviewers grade the conversation as much as the code. A routine that works:

  1. Restate and ask. Repeat the problem in your words. Ask about input size, empty input, duplicates, negatives, and what to return when there's no answer. The answers often pick the pattern for you: n up to 10⁵ rules out O(n²).
  2. Work an example by hand, including an edge case. It catches misunderstandings before any code exists.
  3. Say the brute force and its cost in one sentence ("check every pair, O(n²)"). It shows you can solve it at all, and it's the baseline to improve on.
  4. Name the bottleneck and the pattern. "The inner loop is searching for a partner; a dict makes that O(1)." Agree on the approach before typing.
  5. Write it cleanly, narrating the invariant ("seen holds everything left of i"). Use clear names and the standard library; nobody wants a hand-written heap.
  6. Test it out loud on your example and an edge case, tracing the variables. Fix bugs calmly; finding your own bug is a good signal.
  7. State the time and space complexity, and mention the follow-ups you'd consider: streaming input, input too big for memory, or a recursion depth that needs the iterative version.

The exercises in this topic each take one pattern from the table above and dress it up as a realistic task. Name the pattern first, then write it.

Practise this lesson

In the app: a short video, 8 exercises checked by real tests and a 12-question concept check. Free with a GitHub account.

Open in the app