Python Coding Interview Cheat Sheet: Patterns and Idioms

What are the common coding interview patterns in Python?

The common coding interview patterns are counting and grouping with Counter or defaultdict, sorting by a tuple key, two pointers and sliding windows, prefix sums, stacks, heaps with heapq for top-k, BFS with a deque, binary search with bisect, and set arithmetic. Recognising the shape in the problem's wording, such as 'top k', 'longest subarray with' or 'shortest path', tells you which idiom to write.

Lesson

Most interview problems are one of about twenty shapes wearing a story, and each shape has a two-to-six-line Python idiom that a fluent candidate types without thinking. Recognising the shape is the skill; the idiom is the reward. This lesson is the sheet: counting and grouping, sorting by key, two pointers and sliding windows, prefix sums, stacks, heaps, BFS with a deque, binary search with bisect, set arithmetic, string building, and the itertools and math helpers — each named, each with its idiom and its complexity, so that in the round you say "this is a frequency count, then a heap" and write it.

Counting and grouping

from collections import Counter, defaultdict
counts = Counter(words)                       # O(n)
counts.most_common(3)                         # top three (ties in insertion order — sort if it matters)
groups = defaultdict(list)
for word in words:
    groups["".join(sorted(word))].append(word)    # anagram groups
by_first = {}
for name in names:
    by_first.setdefault(name[0], []).append(name)

"How many of each", "group by", "find duplicates", "first unique" are all a Counter or a defaultdict. Counter supports +, -, & and | between counters, and counts[x] is 0 for a missing key.

Sorting by key

sorted(items, key=lambda p: (-p.score, p.name))     # descending score, then name
sorted(words, key=len)                               # stable: equal lengths keep input order
max(items, key=lambda p: p.score)                    # first maximum
sorted(pairs)                                        # tuples compare lexicographically

Negate numbers for descending inside a tuple key; reverse=True reverses the whole order. Stability means two sorts compose: sort by the secondary key first, then by the primary.

Two pointers and sliding windows

# longest substring without a repeated character: O(n)
last = {}
start = best = 0
for i, ch in enumerate(s):
    if ch in last and last[ch] >= start:
        start = last[ch] + 1
    last[ch] = i
    best = max(best, i - start + 1)

# pair with a target sum in a sorted list
lo, hi = 0, len(xs) - 1
while lo < hi:
    total = xs[lo] + xs[hi]
    if total == target: break
    if total < target: lo += 1
    else: hi -= 1

A window is a start index that only moves forward and a state (a count, a set, a sum) updated as elements enter and leave. "Longest/shortest subarray with property P", "at most k distinct" are windows. Two pointers walk a sorted array from both ends, or two arrays in step (merging).

Prefix sums and differences

prefix = [0]
for x in xs: prefix.append(prefix[-1] + x)
range_sum = prefix[j + 1] - prefix[i]              # O(1) per query
from itertools import accumulate
prefix = [0, *accumulate(xs)]                      # the same in one line

"Sum of a range", "count of something in a range", "subarray with sum k" (prefix sums plus a dict of seen prefixes) are prefix problems.

Stacks

stack = []
for ch in s:                                        # balanced brackets
    if ch in "([{": stack.append(ch)
    elif not stack or PAIRS[stack.pop()] != ch: return False
return not stack

for i, h in enumerate(heights):                     # next greater element / monotonic stack
    while stack and heights[stack[-1]] < h:
        result[stack.pop()] = h
    stack.append(i)

Brackets, "next greater", "largest rectangle", expression evaluation, undo, DFS without recursion — a list used with append and pop.

Heaps

import heapq
heapq.nlargest(k, xs)                               # O(n log k)
heapq.nsmallest(k, words, key=lambda w: (counts[w], w))
heap = []; heapq.heappush(heap, (dist, node)); dist, node = heapq.heappop(heap)   # min at [0]
heapq.heappush(heap, (-value, item))                # a max-heap by negation
heapq.merge(a, b, c)                                # k sorted iterables, lazily

"Top k", "k-th largest", "merge k sorted", Dijkstra, "schedule by earliest" are heaps. heapify(xs) is O(n).

BFS, DFS and graphs

from collections import deque
graph = defaultdict(list)
for a, b in edges: graph[a].append(b); graph[b].append(a)

dist = {start: 0}
queue = deque([start])
while queue:                                        # BFS: shortest path in edges
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in dist:
            dist[nxt] = dist[node] + 1
            queue.append(nxt)

for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):   # grid neighbours
    r, c = row + dr, col + dc
    if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "#" and (r, c) not in seen: ...

"Shortest path in an unweighted graph or grid", "count islands", "is it connected" are BFS with a deque and a seen set; DFS is the same with a stack (or recursion with the limit raised).

Binary search

from bisect import bisect_left, bisect_right, insort
i = bisect_left(sorted_xs, x)                        # first index with xs[i] >= x
count_less = bisect_left(sorted_xs, x); count_le = bisect_right(sorted_xs, x)
lo, hi = 0, n                                        # search on the answer: smallest ok(mid)
while lo < hi:
    mid = (lo + hi) // 2
    if ok(mid): hi = mid
    else: lo = mid + 1

"First element not below x", "how many are less than x", and "the smallest value for which a predicate holds" (capacity, speed, days — the answer is monotonic).

Sets, strings, itertools, math

a & b, a | b, a - b, a ^ b                            # intersection, union, difference, symmetric
"".join(reversed(s)); s[::-1]; s.split(); " ".join(words)
ord(ch) - ord("a"); chr(ord("a") + k)
s.translate(str.maketrans("", "", ".,!?"))            # strip punctuation in C
from itertools import combinations, permutations, product, groupby, accumulate, pairwise
for key, run in groupby(sorted(xs)): ...              # runs of equal values
for a, b in pairwise(xs): ...                         # adjacent pairs
from math import gcd, lcm, isqrt, comb, inf
list(zip(*grid))                                      # transpose
divmod(seconds, 60); n.bit_count(); f"{x:.2f}"

The sheet, in one table

Key takeaways

• Name the shape first; the idiom follows. Counting, sorting by key, windows, prefixes, stacks, heaps, BFS, bisect and sets cover most rounds.
• Counter/defaultdict for counting and grouping; tuple keys with negation for multi-key sorts.
• Windows and two pointers make O(n²) scans O(n); prefix sums make range queries O(1).
• heapq for top-k and scheduling, deque for BFS, bisect for sorted queries and "search on the answer".
• itertools and math have the helper you were about to write.

Common questions

How do you solve a sliding window problem in Python?

Keep a start index that only moves forward and a state, such as a count, a set, a dict or a sum, updated as elements enter and leave. For the longest substring without repeats, store each character's last index and move start past a repeat; the whole scan is O(n).

How do you get the top k elements in Python?

Use heapq.nlargest(k, xs) or heapq.nsmallest(k, xs, key=...), which run in O(n log k), cheaper than sorting everything when k is small. For a running top k, keep a heap with heappush and heappop, negating values for a max-heap.

How do you sort by multiple keys in Python?

Use a tuple key, negating numbers for descending order: sorted(items, key=lambda p: (-p.score, p.name)) sorts by score descending, then by name ascending. Python's sort is stable, so sorting by the secondary key first and then by the primary key also works.

How do you do BFS in Python?

Use collections.deque as the queue and a dict or set of visited nodes: popleft a node, and for each unvisited neighbour record its distance and append it. BFS finds shortest paths in unweighted graphs and grids; popleft is O(1) where list.pop(0) is O(n).

What does bisect_left return in Python?

The first index at which x could be inserted to keep the list sorted, which is the index of the first element not less than x and also the count of elements less than x. bisect_right gives the count of elements less than or equal to x.

Exercises

eat tea tan ate nat bat

eat tea ate
tan nat
bat
groups 3

abcabcbb

length 3
window abc

In this module: Interview idioms

• The interview template — the round, the file, fast I/O and what is actually judged
• The idiom sheet — the shapes interview problems take and the Python for each (this lesson)
• Pitfalls that fail interviews — the twelve Python mistakes interviewers watch for
• Implement the built-in — a hash map, a dynamic array, an LRU cache and a heap by hand
• Writing clean solutions — structure, names, edges first and the code you can read aloud
• The Python theory drill — thirty questions, thirty answers
• Final checkpoint — Interview idioms