Python Interview Cheatsheet

01collections — the four you'll actually use

Counter — frequency maps for free

from collections import Counter

c = Counter("mississippi")        # {'i': 4, 's': 4, 'p': 2, 'm': 1}
c.most_common(2)                  # [('i', 4), ('s', 4)]
c["z"]                            # 0 — missing keys are 0, no KeyError
Counter(a) == Counter(b)          # anagram check, one line
c1 - c2                           # multiset difference (drops ≤0 counts)

Use for: anagrams, top-k frequent, character budgets (ransom note: not (Counter(note) - Counter(magazine))).

defaultdict — kill the "if key not in d" dance

from collections import defaultdict

graph = defaultdict(list)         # adjacency lists
graph[u].append(v)                # no KeyError, ever

groups = defaultdict(list)        # grouping by canonical key
groups[key].append(item)

counts = defaultdict(int)         # manual counting (or just use Counter)

deque — the O(1)-both-ends workhorse

from collections import deque

q = deque([start])
q.append(x)                       # right push
q.popleft()                       # left pop — THE reason it exists; list.pop(0) is O(n)
q.appendleft(x); q.pop()          # it's double-ended
dq = deque(maxlen=k)              # auto-evicting window buffer

Use for: BFS (always), sliding-window max (monotonic deque), any queue.

OrderedDict — mostly for LRU

Modern dicts preserve insertion order already; OrderedDict earns its keep via move_to_end(key) + popitem(last=False) — which is a complete LRU cache:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap, self.d = capacity, OrderedDict()
    def get(self, key):
        if key not in self.d: return -1
        self.d.move_to_end(key)                  # mark recently used
        return self.d[key]
    def put(self, key, value):
        self.d[key] = value
        self.d.move_to_end(key)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)           # evict least-recent

02heapq — min-heap on a plain list

import heapq

heapq.heapify(nums)               # O(n), in place; nums[0] is the min
heapq.heappush(h, x)              # O(log n)
x = heapq.heappop(h)              # O(log n)
h[0]                              # peek, O(1)
heapq.heappushpop(h, x)           # push-then-pop, one sift — top-K loops
heapq.nlargest(k, data, key=f)    # quick top-K without manual heap code

The three rules (details in file 06):

maxheap = [-x for x in nums]; heapq.heapify(maxheap)
biggest = -heapq.heappop(maxheap)

03Sorting: sorted, .sort(), and key=

sorted(xs)                        # new list; sorted(s) works on any iterable
xs.sort()                         # in place, lists only; both are stable Timsort

xs.sort(key=lambda p: p[1])                   # by second field
xs.sort(key=lambda p: (-p[1], p[0]))          # DESC count, then ASC name —
                                              # the negate-inside-a-tuple trick
words.sort(key=len)                           # any callable works
intervals.sort()                              # tuples/lists sort lexicographically
                                              # — often exactly what you want

• key= runs once per element (decorate-sort-undecorate) — cheap even for expensive keys.
• Stability means equal keys keep order ⇒ multi-pass multi-key sorts work (file 08 §4).
• For non-key-expressible comparators (rare — e.g., Largest Number's "a+b vs b+a"): functools.cmp_to_key(cmp).
• min(xs, key=f) / max(xs, key=f) accept the same key — grab "best by criterion" without sorting.

bisect — binary search you don't have to write

import bisect
i = bisect.bisect_left(a, x)      # first index with a[i] >= x
j = bisect.bisect_right(a, x)     # first index with a[i] >  x
count = j - i                     # occurrences of x in sorted a
bisect.insort(a, x)               # insert keeping sorted (O(n) — the shift!)

04Comprehensions & iteration idioms

squares = [x * x for x in xs if x > 0]            # list comp: transform+filter
seen = {canonical(x) for x in xs}                 # set comp
index_of = {v: i for i, v in enumerate(xs)}       # dict comp — Two Sum prep
total = sum(x * x for x in xs)                    # generator: no intermediate list

grid = [[0] * cols for _ in range(rows)]          # 2-D init — THE right way
                                                  # (see §06 for the wrong way)

for i, x in enumerate(xs): ...                    # index + value; never range(len(...)) alone
for a, b in zip(xs, ys): ...                      # parallel iteration
for x in reversed(xs): ...                        # no copy, unlike xs[::-1]
if any(p(x) for x in xs): ...                     # short-circuits
if all(p(x) for x in xs): ...
a, b = b, a                                       # swap, no temp
first, *rest = xs                                 # unpacking

Slicing — each makes a copy, O(k):

xs[2:5]   xs[:3]   xs[3:]   xs[::-1]   xs[::2]

05Strings — the toolbelt

s.split()                 # on any whitespace, drops empties — usually what you want
s.split(",")              # on a literal; keeps empties
" ".join(words)           # inverse; join is THE O(n) way to build strings
s.strip() / lstrip / rstrip
s.lower(); s.upper()
s.startswith(p); s.endswith(p)
s.find(t)                 # index or -1        s.index(t)  # index or ValueError
s.replace(a, b)           # all occurrences, new string
ch.isdigit(); ch.isalpha(); ch.isalnum()
ord('a'), chr(97)         # count-array indexing: ord(c) - ord('a')
f"{name}: {val:.2f}"      # f-strings for any output formatting
int("42"), str(42)        # and int("ff", 16) for base parsing

06The gotchas that eat interview minutes

Mutable default arguments

def f(x, acc=[]):   # [] created ONCE,
    acc.append(x)   # shared across ALL calls
    return acc
f(1); f(2)          # → [1, 2]  !!

def f(x, acc=None):
    if acc is None:
        acc = []
    ...

Corollary: dict/list defaults in recursive helpers (memo={}) technically "work" for single-use functions but leak state between top-level calls — in interviews, pass memo explicitly or use @lru_cache and say why.

Aliasing vs copying

b = a                    # SAME list, two names
b = a[:]                 # shallow copy — new list, same element objects
import copy; copy.deepcopy(a)     # full clone (rarely needed; know it exists)

row = [0] * 3
grid = [row] * 4         # ← FOUR REFERENCES TO ONE ROW
grid[0][0] = 9           # every row now starts with 9  !!
grid = [[0] * 3 for _ in range(4)]    # the fix — fresh row per iteration

Small but real

5 // 2 == 2;  -5 // 2 == -3      # floor division truncates DOWN (not toward 0)
5 % 3 == 2;  -5 % 3 == 1         # % result has the divisor's sign
round(2.5) == 2                  # banker's rounding — round-half-to-EVEN
x == y  vs  x is y               # value equality vs identity; use `is` only for None
                                 # (and cycle-detection node comparisons: slow is fast)
sys.setrecursionlimit(10**6)     # default ~1000; deep DFS on lists/trees can hit it —
                                 # mention it, or go iterative
float('inf'), float('-inf')      # sentinels for min/max tracking
d.get(k, default)                # probe without KeyError or insertion
for k, v in d.items(): ...       # don't iterate keys then re-index

Late binding in loops (occasionally bites in closures)

fns = [lambda: i for i in range(3)]
[f() for f in fns]               # [2, 2, 2] — closures capture the VARIABLE
fns = [lambda i=i: i for i in range(3)]   # fix: default-arg snapshot → [0, 1, 2]

07Gotcha flashcards — drill until instant

def f(x, acc=[]):
    acc.append(x)
    return acc
print(f(1)); print(f(2))

g = [[0] * 3] * 3
g[0][0] = 9
print(g)

print(-7 // 2)
print(-7 % 2)

fns = [lambda: i for i in range(3)]
print([f() for f in fns])

a = [1, 2, 3]
b = [1, 2, 3]
print(a == b, a is b)

d = {}
d["b"] = 1; d["a"] = 2
print(list(d))

a = [[1], [2]]
b = a[:]
b[0].append(9)
print(a)

s = ""
for ch in chunks:
    s += ch

08functools and friends

from functools import lru_cache, cache

@cache                            # 3.9+; = lru_cache(maxsize=None)
def solve(i, remaining): ...      # instant memoization — args must be hashable
                                  # (tuples yes, lists no)

solve.cache_clear()               # between test cases if state matters

import itertools
itertools.permutations(xs, r)     # when the problem ALLOWS library enumeration
itertools.combinations(xs, r)     # (interviewer may want manual backtracking — ASK)
itertools.product(range(3), repeat=2)   # grid coordinates, cartesian choices
itertools.accumulate(xs)          # running prefix sums, one line
itertools.groupby(sorted_xs, key=f)     # run-length-style grouping (must be pre-sorted!)

import math
math.inf, math.ceil(a / b), math.gcd(a, b), math.isqrt(n)
(a + b - 1) // b                  # ceil-division without floats — worth knowing

09Writing clean interview code, fast

Structure to type without thinking:

def solve(nums: list[int], target: int) -> int:
    # 1. guard the trivial cases (empty, single) — cheap correctness points
    if not nums:
        return 0
    # 2. name your state clearly — left/right, lo/hi, seen, best, window
    best = 0
    seen: set[int] = set()
    # 3. the core loop, with the invariant you SAID OUT LOUD as a comment
    for right, x in enumerate(nums):
        ...
    return best

Habits that read as senior:

• Small helper functions (def neighbors(r, c):, def feasible(k):) — they shrink the core loop to the algorithm's shape and give you clean units to test verbally.
• Descriptive-but-short names: lo/hi, seen, freq, best, cur are idiomatic; x1, temp2, data are not. Single letters fine for indices only.
• Early returns over nesting. if not valid: continue beats a 4-deep if-pyramid.
• Type hints on the signature only — one line of professionalism, zero time cost. Skip them inside the body.
• Walk one small example through your code, out loud, before declaring done. Pick an input of size 2–3 plus one edge case (empty, duplicates, all-same). This catches ~80% of bugs and is itself assessed.
• Don't golf. A comprehension is idiomatic; three nested comprehensions with a walrus is a code smell under interview conditions.

The "which structure" reflex table (details in files 02–06):

10The big ops-cost table

11Common interview questions (brief answers)

12Self-test

1. From memory: the one-liner each for (a) anagram check, (b) value→index map, (c) rows×cols zero grid, (d) count of x in a sorted list.
2. What's wrong with def dfs(node, path=[])? Show the fixed signature.
3. Sort a list of (name, count) by count descending, then name ascending — the exact key=.
4. Why is key= called O(n) times rather than O(n log n)? What idiom is this called?
5. Build a max-heap of (priority, task_dict) items where priorities can tie. What breaks naively, and what's the fix?
6. Predict: a = [[0]*2]*3; a[1][0] = 5; print(a). Then write the correct initializer.
7. deque(maxlen=3) — what happens on the 4th append, and name one problem where that's useful.
8. Write the LRU cache with OrderedDict from memory (both methods).
9. Predict: [-3 // 2, -3 % 2, round(0.5), round(1.5)].
10. You have 25 minutes and a medium problem. List your five-step routine from reading the prompt to "done."