The Coding Interview Cheat Sheet: Complexity, Patterns and Python Idioms

This coding interview cheat sheet is the reference sheet I would want open during preparation: the complexity budget implied by each input size, what every operation actually costs in Python, the phrases that give away which pattern a problem wants, the standard library calls worth knowing by heart, and a short checklist to run before you claim a solution works.

It is a lookup table, not a tutorial. If a row makes no sense, that is the topic to go and study.

How to use this coding interview cheat sheet#

Read it in the order an interview happens: constraints, then pattern, then data structure, then code, then check. The most valuable table is the first one, because the bound on n narrows the possible solutions before you have understood the problem.

Complexity budgets by input size#

A judge or an interviewer's mental model allows roughly 10^8 simple operations. Working backwards from that gives a rule of thumb — not a law, but a good first filter.

Two corollaries worth saying out loud in an interview. If n is at most twenty and the answer is an arrangement, the intended solution is exponential and you should stop looking for a clever polynomial one. If n is 10^9, no algorithm may touch every element, so the answer is a formula or a search over the answer space.

What operations cost in Python#

Average-case, with the ones that actually catch people in bold.

The two that quietly ruin submissions are list.pop(0) inside a BFS — use a deque — and string concatenation in a loop, which is quadratic because each += copies the whole string.

Pattern triggers#

What the statement says, and what it usually means. The full version with templates is in the pattern map.

When two patterns fit, name both and pick the one whose correctness you can argue. An interviewer scores the argument, not the guess.

If a row is unfamiliar, its canonical problem is the fastest way in: Two Sum for hash maps, Longest Substring Without Repeating Characters for windows, Koko Eating Bananas for binary search on the answer, and Number of Islands for grids.

Python idioms worth knowing by heart#

The imports:

from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify, nlargest
from bisect import bisect_left, bisect_right
from functools import cache
from math import inf, gcd

Counting, grouping and frequencies:

counts = Counter("mississippi")
top_two = counts.most_common(2)

groups = defaultdict(list)
for word in ["eat", "tea", "tan"]:
    groups["".join(sorted(word))].append(word)

anagram_key = tuple(sorted(Counter("listen").items()))

Heaps, including the max-heap workaround:

def two_largest(nums):
    heap = []                      # min-heap capped at 2; its top is the smaller of the pair
    for value in nums:
        heappush(heap, value)
        if len(heap) > 2:
            heappop(heap)
    return sorted(heap, reverse=True)

def largest_first(nums):
    heap = [-value for value in nums]
    heapify(heap)
    return -heappop(heap)

Binary search over a sorted list, without writing the loop:

def count_in_range(sorted_nums, low, high):
    """How many values fall in [low, high], inclusive."""
    return bisect_right(sorted_nums, high) - bisect_left(sorted_nums, low)

Memoised recursion, which is how every dynamic programming solution should start:

def longest_common_subsequence(a, b):
    @cache
    def best(i, j):
        if i == len(a) or j == len(b):
            return 0
        if a[i] == b[j]:
            return 1 + best(i + 1, j + 1)
        return max(best(i + 1, j), best(i, j + 1))

    return best(0, 0)

Sorting by a compound key — the tuple is the whole trick:

people = [("ada", 36), ("alan", 41), ("grace", 36)]
people.sort(key=lambda person: (person[1], person[0]))
descending_then_ascending = sorted(people, key=lambda p: (-p[1], p[0]))

And the grid bug that costs people a whole interview:

wrong = [[0] * 3] * 4        # four references to the SAME row
right = [[0] * 3 for _ in range(4)]
wrong[0][0] = 1              # every row now starts with 1
right[0][0] = 1              # only the first row changes

If you write a deep recursion on a large grid, raise the limit before it bites:

from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

Edge cases to test, every time#

Run the list, not your intuition. Most of these take five seconds to check and each one has ended somebody's interview.

• Empty input. [], "", a null root, zero nodes.
• One element. Especially with two pointers, windows and midpoints.
• Two elements. The smallest case where "left" and "right" differ.
• All elements identical. Breaks strict comparisons and de-duplication.
• Already sorted, and reverse sorted. The best and worst case for anything with a partition.
• Negatives and zero. Windows over sums silently break with negatives.
• k larger than n, or k equal to zero.
• Duplicates in the input when the answer is a set of indices.
• Disconnected or cyclic graphs, and nodes with no edges.
• Integer division and rounding. Python's // floors toward negative infinity; int() truncates toward zero. They differ on negative numbers.

The thirty-second check before you say "done"#

1. Return type. Index or value? The list, or its length? What do you return on failure — -1, None, or an empty list?
2. Loop bounds. Does the last element get processed? Is range exclusive where you meant inclusive?
3. Empty input. Does it return rather than crash?
4. Mutation. Did you modify the list you are iterating over, or mutate the caller's input without saying so?
5. State reset. Anything initialised outside a loop that should have been inside it, or vice versa?
6. Complexity, out loud. Time and space, with one sentence of justification each.

Then walk one non-trivial example through by hand, out loud, and say which case you are checking. Interviewers score this explicitly, and it is the only reliable way to find your own off-by-one before someone else does.

What to say, and when#

The single most common failure is spending twenty-five minutes coding and none testing, then finding a bug at minute forty with no time to fix it. Testing is not the part you cut when you are behind.

Where to go from here#

If a row above was unfamiliar, that is the topic. The pattern map has a template and three practice problems for each technique; the Blind 75 is the shortest list that covers most of them, with a six-week plan if you want a schedule; and the full problem index is filterable by pattern and difficulty when you want more of one specific thing.

And if you want a second pair of eyes during the interview itself, Stealth Interview is a desktop app for macOS and Windows that reads the problem from a screenshot and walks through the approach, the code and the complexity with you, while staying invisible to screen sharing.