10 Coding Interview Patterns in Python

Coding interviews can look like an endless list of unrelated puzzles. They are not. Most problems are one of a small number of patterns in disguise, and once you learn to recognise the pattern, the solution follows a familiar shape. This post walks through ten of the most useful patterns in Python. For each one you get the clue that gives it away, a short tested example, and a link to the full guide.

The examples are small on purpose. The goal is to help you recognise the shape, not to memorise code. All the output shown is real.

Spot the pattern: a cheat sheet

1. Hash map

Clue: you need to look something up again and again, count occurrences, or ask “have I seen this before?”. A dictionary or set answers in O(1) on average, which usually turns an O(n²) double loop into one pass. Two sum: for every number, is the number that completes it already stored?

def two_sum(nums, target):
    seen = {}                              # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

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

Output

[0, 1]
[1, 2]
[]

How much work does that save? We count steps, not seconds, on 1000 numbers where no pair matches, the worst case:

nums = list(range(1000))
target = -1                                # no two numbers add up to this

pairs = 0
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        pairs += 1                         # brute force: look at every pair
print("brute force looks at", pairs, "pairs")

seen, lookups = set(), 0
for x in nums:
    lookups += 1                           # hash set: one lookup per number
    if target - x in seen:
        break
    seen.add(x)
print("hash set does", lookups, "lookups")

Output

brute force looks at 499500 pairs
hash set does 1000 lookups

Full guide: Hash Table in Python.

2. Two pointers

Clue: the data is sorted (or can be), and you look for a pair, or need to work from both ends. One pointer starts at each end, and you move the one that gets you closer to the target. No nested loop is needed:

def pair_in_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        total = nums[lo] + nums[hi]
        if total == target:
            return [lo, hi]
        if total < target:
            lo += 1                        # need a bigger sum
        else:
            hi -= 1                        # need a smaller sum
    return []

print(pair_in_sorted([1, 3, 4, 6, 8, 11], 10))

Output

[2, 3]

Full guide: Two Pointers in Python.

3. Sliding window

Clue: “longest”, “shortest” or “maximum” over a contiguous stretch of a list or string. Instead of recalculating each window from scratch, slide it: add the item that enters and remove the item that leaves.

def max_sum_window(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]    # add the new item, drop the old one
        best = max(best, window)
    return best

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

Output

9

Full guide: Sliding Window in Python.

4. Prefix sums

Clue: many questions about the sum of a range, or the number of subarrays with a given sum. Precompute running totals once, and then any range sum is a single subtraction. Combined with a hash map of the totals seen so far, it counts subarrays with a target sum in one pass:

from itertools import accumulate

nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0] + list(accumulate(nums))
print(prefix)
print(prefix[6] - prefix[2])               # sum of nums[2:6], in one step

def count_subarrays(nums, k):
    seen = {0: 1}                          # prefix sum -> how often it occurred
    total = count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

print(count_subarrays([1, 1, 1], 2))

Output

[0, 3, 4, 8, 9, 14, 23, 25, 31]
19
2

The result 19 is 4 + 1 + 5 + 9. Both subarrays that add up to 2 in [1, 1, 1] are found (positions 0-1 and 1-2), without checking every pair of positions.

5. Binary search

Clue: sorted data, or a question of the form “find the smallest value for which this test passes”. If a test flips from false to true only once as the value grows, you can halve the range at each step:

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi] for which ok(x) is True (ok flips from False to True once)."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(first_true(0, 100, lambda x: x * x >= 50))

Output

8

The smallest number whose square is at least 50 is 8, found in about 7 steps instead of 50. Full guide: Binary Search in Python: 3 Common Variations.

6. Stack

Clue: things that nest or must be undone in reverse order: brackets, expressions, “next greater element”, backing out of a path. The most recent unfinished thing is always the one to handle first.

def is_valid(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif not stack or stack.pop() != pairs[ch]:
            return False
    return not stack

print(is_valid("()[]{}"), is_valid("(]"), is_valid("(("))

Output

True False False

Full guide: Stack in Python: Implementation and Uses.

7. BFS and DFS

Clue: a graph, a tree, a grid or a maze. Shortest number of steps, level by level, or “how many connected groups”. BFS (a queue) gives the fewest steps in an unweighted graph. DFS (a stack or recursion) explores everything and handles cycles and ordering:

from collections import deque

def min_steps(graph, start, goal):
    queue = deque([(start, 0)])
    seen = {start}
    while queue:
        node, steps = queue.popleft()
        if node == goal:
            return steps
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb)
                queue.append((nb, steps + 1))
    return -1

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": ["E"], "E": []}
print(min_steps(graph, "A", "E"), min_steps(graph, "E", "A"))

Output

3 -1

Full guides: Graphs in Python: Adjacency List, BFS and DFS, Binary Tree in Python and Queue and Deque in Python.

8. Heap (top-k)

Clue: “the k largest”, “the kth smallest”, “the most frequent”, or a stream where you keep asking for the smallest or largest item. A heap keeps that item at the top without sorting everything:

import heapq
from collections import Counter

nums = [3, 2, 1, 5, 6, 4]
print(heapq.nlargest(2, nums)[-1])                 # the 2nd largest

words = ["a", "b", "a", "c", "b", "a"]
print(Counter(words).most_common(2))               # the 2 most frequent

Output

5
[('a', 3), ('b', 2)]

Full guide: Heap and heapq in Python: Priority Queues.

9. Backtracking

Clue: “return all”, “generate every”, “list all valid”: subsets, permutations, combinations, placements. Build the answer step by step, and undo each step after exploring it:

def subsets(nums):
    result, path = [], []

    def backtrack(start):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])                   # choose
            backtrack(i + 1)                       # explore
            path.pop()                             # undo

    backtrack(0)
    return result

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

Output

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Full guide: Backtracking in Python: Subsets and Permutations.

10. Dynamic programming

Clue: “minimum”, “maximum”, “how many ways”, “longest”, and the same smaller questions come up many times. Define what a table entry means, and fill it from the smallest case. Coin change asks for the fewest coins:

def min_coins(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount                      # dp[a] = fewest coins for amount a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(min_coins([1, 2, 5], 11), min_coins([2], 3))

Output

3 -1

Full guide: Dynamic Programming in Python for Beginners. It builds on Recursion in Python Explained Simply.

A routine for any problem

1. Restate the problem in your own words, and ask about the input: can it be empty, negative, sorted, or contain duplicates?
2. Try a small example by hand, and write down the expected result.
3. Say the brute-force solution and its cost (see Big O Notation in Python). It shows what work is being repeated.
4. Match a pattern that removes that repeated work, using the cheat sheet above.
5. Code it in small steps, naming variables clearly.
6. Test with the edge cases: empty input, one item, duplicates, the largest case.
7. State the time and space cost of your solution.

Some patterns did not fit in this list: fast and slow pointers on a linked list, prefix search with a trie, sorting first, and merging intervals. They follow the same approach. The Python behind the examples, from comprehensions to Counter, is covered in the Python interview gotchas post.

Try it yourself

Name the pattern for each problem before you read the answer.

1. Find the length of the longest substring without repeating characters, for example in "abcabcbb".

def longest_unique(text):
    last = {}                                      # letter -> last position seen
    start = best = 0
    for i, ch in enumerate(text):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1                   # shrink the window past the repeat
        last[ch] = i
        best = max(best, i - start + 1)
    return best

print(longest_unique("abcabcbb"), longest_unique("bbbbb"), longest_unique(""))

3 1 0

2. Count the number of islands in a grid of land and water.

3. Return all the permutations of a list of numbers.

4. Find the fewest coins that add up to an amount. Would greedy always work?

Run these in our free Python compiler.

Frequently asked questions

What are the most common coding interview patterns?

Hash map, two pointers, sliding window, prefix sums, binary search, stack, BFS and DFS, heap, backtracking and dynamic programming cover a large share of interview questions.

How do I know which pattern to use?

Look for clues in the wording: a sorted array suggests binary search or two pointers, a contiguous subarray suggests a sliding window, shortest path suggests BFS, ‘return all’ suggests backtracking, and ‘minimum’ or ‘count the ways’ suggests dynamic programming.

Should I memorise solutions to coding problems?

No. Learn the patterns and understand why each works. Then a new problem becomes a variation of something you already know.

Which language should I use for coding interviews?

Use the one you know best. Python is popular because it is short to write and has strong built-ins such as dict, set, Counter, heapq and bisect.

How many problems should I practise?

Quality matters more than count. A few well-understood problems per pattern, revisited a week later, work better than hundreds solved once.

What should I say before I start coding?

Restate the problem, confirm the input rules and edge cases, walk through an example, describe the brute-force approach and its cost, and then explain the pattern you will use.

Related reading

• Big O Notation Explained With Python Examples – how to state the cost of a solution.
• Hash Tables in Python: Dict and Set for DSA – the most useful pattern of all.
• Two Pointers Technique in Python – pairs, palindromes and in-place edits.
• 7 Python Gotchas That Trip Up Interviews – the Python side of the interview.