Python Interview Cheat Sheet — Data Structures, Standard Library, Idioms, and Gotchas

Bookmark this page. This is the reference sheet for coding interviews in Python — the idioms you'll reach for on a whiteboard, the standard-library shortcuts that turn twenty-line solutions into three-line ones, and the language gotchas (mutable default arguments, late-binding closures, list.pop(0)) that turn correct algorithms into wrong answers. It complements the Big-O cheat sheet; this one is about how to write it in Python, not how fast it runs.

Built-in data structures at a glance

Structure	Constructor	Access	Mutable	Ordered	Hashable	Typical use
`list`	`[1, 2, 3]`	`nums[i]` — O(1)	✓	✓ (insertion)	✗	Dynamic array, stack, queue-with-index
`tuple`	`(1, 2, 3)`	`t[i]` — O(1)	✗	✓	✓	Composite keys, return multiple values
`dict`	`{"a": 1}`	`d[k]` — O(1)*	✓	✓ (insertion order since 3.7)	✗	Hash map
`set`	`{1, 2, 3}`	`x in s` — O(1)*	✓	✗	✗	Membership, dedup
`frozenset`	`frozenset({1, 2})`	O(1)*	✗	✗	✓	Set as a dict key
`str`	`"hello"`	`s[i]` — O(1)	✗	✓	✓	Immutable text — never concat in a loop
`bytes` / `bytearray`	`b"..."` / `bytearray(b"..")`	O(1)	bytes ✗ / bytearray ✓	✓	bytes ✓ / bytearray ✗	Binary data

*Amortised. See the Big-O cheat sheet for worst-case caveats.

`collections` — the interview power tools

from collections import Counter, defaultdict, deque, OrderedDict

Class	Constructor	Signature use
`Counter`	`Counter(iterable)` or `Counter({"a": 3})`	Frequency counts. Comparison via `==` handles multiset equality.
`defaultdict`	`defaultdict(list)` / `defaultdict(int)` / `defaultdict(set)`	Auto-init missing keys. Zero-boilerplate grouping.
`deque`	`deque(iterable, maxlen=None)`	O(1) both ends. Use for BFS queues and sliding windows.
`OrderedDict`	`OrderedDict()`	Insertion-ordered dict with `move_to_end(k)` for LRU cache builds.

`Counter`

c = Counter("mississippi")
# Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})

c.most_common(2)          # [('i', 4), ('s', 4)]
c["z"]                    # 0 — never KeyError
Counter("aab") == Counter("aba")   # True — multiset equality
Counter("aab") - Counter("a")      # Counter({'a': 1, 'b': 1})

Use Counter for anagram groupings, majority-vote problems, LC 383 Ransom Note, LC 49 Group Anagrams.

`defaultdict`

groups = defaultdict(list)
for word in words:
    groups[tuple(sorted(word))].append(word)
# groups[("a", "e", "t")] == ["eat", "tea", "ate"]

adjacency = defaultdict(set)
for u, v in edges:
    adjacency[u].add(v)
    adjacency[v].add(u)

The lambda form is common too: defaultdict(lambda: [0, 0]) for a default of [0, 0]. Never use a shared mutable as the factory itself — see the "Mutable default arguments" gotcha below.

`deque`

q = deque()
q.append(x)      # push right — O(1)
q.appendleft(x)  # push left  — O(1)
q.pop()          # pop right  — O(1)
q.popleft()      # pop left   — O(1)

# BFS queue:
queue = deque([start])
while queue:
    node = queue.popleft()
    for nxt in neighbours(node):
        queue.append(nxt)

Rule: never use a plain list as a BFS queue. list.pop(0) is O(n); deque.popleft() is O(1). See the BFS vs DFS post for the accidental-O(V²) case.

`heapq` — priority queue

import heapq

heap: list[int] = []
heapq.heappush(heap, 3)      # O(log n)
smallest = heapq.heappop(heap)  # O(log n)
heap[0]                        # peek — O(1)

heapq.heapify(existing_list)   # O(n)
heapq.nlargest(k, iterable)    # O(n log k)
heapq.nsmallest(k, iterable)   # O(n log k)

Python's heapq is a min-heap only. For a max-heap, push negated values (-num) or wrap in a tuple with negated key: heapq.heappush(heap, (-priority, item)).

For custom keys with equal priority tiebreaks:

# Tuple form: (priority, tiebreak_counter, item)
counter = 0
heapq.heappush(heap, (priority, counter, item))
counter += 1

The tiebreak counter avoids comparing the raw items (which may not implement <) when priorities collide.

`itertools` — combinatorial primitives

from itertools import (
    accumulate, chain, combinations, combinations_with_replacement,
    count, cycle, groupby, permutations, product, repeat, starmap
)

Function	Returns	Example use
`accumulate(iter)`	Running sums	`list(accumulate([1,2,3])) == [1, 3, 6]`
`accumulate(iter, func)`	Running fold	`list(accumulate([1,2,3], max))`
`chain(a, b, ...)`	Flatten iterables	`list(chain([1,2], [3,4]))`
`combinations(iter, r)`	r-length subsets, no repeat	`combinations([1,2,3], 2)` → `(1,2), (1,3), (2,3)`
`combinations_with_replacement`	Same, allow repeats	`(1,1), (1,2), (2,2), …`
`permutations(iter, r=None)`	r-length orderings	`permutations([1,2,3])` → 6 tuples
`product(a, b)`	Cartesian product	`product([1,2], "ab")` → `(1,'a'), (1,'b'), (2,'a'), (2,'b')`
`product(iter, repeat=k)`	k-tuples from iter	`product([0,1], repeat=3)` → 8 binary strings
`groupby(iter, key)`	Consecutive groups	Run-length encoding
`count(start, step)`	Infinite counter	`zip(count(), items)` for indexed traversal
`cycle(iter)`	Infinite loop	Round-robin scheduling

groupby groups consecutive equal elements — sort first if you need global groups.

`bisect` — binary search on sorted lists

import bisect

sorted_list = [1, 3, 5, 7, 9]
bisect.bisect_left(sorted_list, 5)    # 2 — leftmost slot where 5 could go
bisect.bisect_right(sorted_list, 5)   # 3 — rightmost slot where 5 could go
bisect.bisect(sorted_list, 5)         # alias for bisect_right
bisect.insort(sorted_list, 4)         # sorted_list is now [1, 3, 4, 5, 7, 9]

Uses:

Find whether x is in a sorted list: i = bisect_left(a, x); found = i < len(a) and a[i] == x
Count elements <= x: bisect_right(a, x)
Count elements in a range [lo, hi]: bisect_right(a, hi) - bisect_left(a, lo)

For anything more sophisticated than "search a sorted array", roll the boundary template.

`functools` — caching and reduction

from functools import lru_cache, cache, reduce

@cache                       # Python 3.9+, unbounded memoisation
def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)

@lru_cache(maxsize=1024)     # Bounded memoisation
def expensive(x, y): ...

reduce(lambda a, b: a * b, [1, 2, 3, 4])   # 24

Wrap top-down DP recursions in @cache and you've turned an exponential naïve recursion into polynomial-time DP for free.

`math` — the constants and helpers you actually need

import math

math.inf, math.nan
math.floor(x), math.ceil(x), math.trunc(x)
math.gcd(a, b), math.lcm(a, b)
math.isqrt(n)         # integer sqrt — exact, no float rounding
math.comb(n, k)       # binomial coefficient — O(min(k, n-k))
math.perm(n, k)       # n! / (n-k)!
math.log2(n), math.log10(n)

math.inf beats float('inf') for clarity. math.isqrt beats int(x**0.5) for correctness on large integers (the float form drifts).

String operations you'll use every interview

s = "Hello, World!"

# Slicing — creates new string, O(k)
s[7:12]        # "World"
s[::-1]        # "!dlroW ,olleH" — reverse
s[::2]         # every other char

# Case
s.lower(), s.upper(), s.title(), s.swapcase()

# Search
s.find("W")        # index or -1 (never raises)
s.index("W")       # index or ValueError
s.count("l")       # 3
s.startswith("H")
s.endswith("!")

# Classification
"abc123".isalnum()   # True
"abc".isalpha()      # True
"123".isdigit()      # True
"   ".isspace()      # True

# Transformation
s.replace("l", "L")
s.strip(), s.lstrip(), s.rstrip()
"1,2,3".split(",")
"-".join(["a", "b", "c"])   # "a-b-c"

# Encoding
ord("a")            # 97
chr(97)             # "a"
bin(10), oct(10), hex(10)   # "0b1010", "0o12", "0xa"

# Formatting
f"{value:.2f}"      # 2 decimal places
f"{value:>10}"      # right-align in width 10
f"{value:0>4}"      # zero-pad to width 4

Never concat with + in a loop. s = s + t is O(n) per iteration, O(n²) total, because str is immutable. Collect pieces in a list and "".join(pieces).

Idioms you'll actually use

Enumerate

for i, val in enumerate(nums):
    ...
for i, val in enumerate(nums, start=1):   # 1-indexed
    ...

Zip

for a, b in zip(list1, list2):
    ...

zip(*matrix)         # transpose — [row1, row2, row3] → cols

# Zip with unequal lengths — stops at shortest
from itertools import zip_longest
zip_longest(a, b, fillvalue=0)

Sorted with key

sorted(items, key=lambda x: x.name)
sorted(items, key=lambda x: (x.priority, -x.age))   # tuple key for multi-sort
sorted(words, key=len)
sorted(strs, key=str.casefold)   # case-insensitive
sorted(items, reverse=True)

Sort is stable — items with equal keys retain input order. Use tuple keys for multi-column sorting; put a - in front of a numeric key to reverse just that column.

Comprehensions

squares = [x * x for x in range(10)]
evens = [x for x in nums if x % 2 == 0]
lookup = {x: i for i, x in enumerate(nums)}
unique = {x for x in items}
grid = [[0] * cols for _ in range(rows)]     # NOT [[0] * cols] * rows — see gotchas

# Generator expression — memory-frugal
total = sum(x * x for x in range(1_000_000))

The gotcha with [[0] * cols] * rows: outer multiplication shares references to the same inner list. Mutating grid[0][0] mutates every row.

Unpacking

a, b = 1, 2
a, b = b, a                    # swap
head, *tail = [1, 2, 3, 4]     # head=1, tail=[2,3,4]
*init, last = [1, 2, 3, 4]     # init=[1,2,3], last=4
first, *_, last = seq          # discard middle

# Function calls
func(*args)          # spread positional
func(**kwargs)       # spread keyword

Walrus (assign inside expression)

while (line := input()) != "":
    process(line)

if (n := len(items)) > threshold:
    print(f"Too many: {n}")

Reserved for cases where you'd otherwise compute the value twice. Overuse makes code harder to read; interviewers won't penalise a plain assignment.

Common interview patterns

Frequency count

counts = Counter(iterable)
# or
counts = defaultdict(int)
for x in iterable:
    counts[x] += 1

Group by key

groups = defaultdict(list)
for item in items:
    groups[key(item)].append(item)

Two-sum with hash map

seen = {}
for i, x in enumerate(nums):
    if target - x in seen:
        return [seen[target - x], i]
    seen[x] = i

Sliding-window frequency

window = defaultdict(int)
left = 0
for right, ch in enumerate(s):
    window[ch] += 1
    while invalid(window):
        window[s[left]] -= 1
        if window[s[left]] == 0:
            del window[s[left]]
        left += 1
    ...

See the sliding-window post for the full pattern.

Top-k with heap

# Top k largest — O(n log k)
top_k = heapq.nlargest(k, iterable, key=lambda x: x.score)

# Or maintain a min-heap of size k
heap = []
for item in stream:
    heapq.heappush(heap, item)
    if len(heap) > k:
        heapq.heappop(heap)
# heap now contains the k largest — O(n log k) total

Grid neighbours (four-directional)

DIRS = ((0, 1), (0, -1), (1, 0), (-1, 0))

for dr, dc in DIRS:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        ...

Eight-directional adds four diagonals: (1, 1), (1, -1), (-1, 1), (-1, -1).

Reverse a linked list

prev = None
while head:
    head.next, prev, head = prev, head, head.next
return prev

The single-line multi-assignment is the interviewer-impressing form. All three RHS values are evaluated before any LHS is written, so no temp variable needed.

Gotchas — the traps

Mutable default arguments

def bad(x, memo=[]):    # DON'T — memo is created ONCE, shared across calls
    memo.append(x)
    return memo

def good(x, memo=None):
    if memo is None:
        memo = []
    memo.append(x)
    return memo

Same trap with def bad(x, memo={}): — the dict is shared. This is the single most common Python interview bug.

Late-binding closures

funcs = [lambda: i for i in range(3)]
[f() for f in funcs]      # [2, 2, 2] — NOT [0, 1, 2]

# Fix: bind i as a default argument
funcs = [lambda i=i: i for i in range(3)]
[f() for f in funcs]      # [0, 1, 2]

Copies, deep and shallow

a = [[1, 2], [3, 4]]
b = a           # b IS a — mutation to either shows in both
b = a[:]        # shallow — top-level copy, inner lists are shared
b = list(a)     # shallow — same
b = a.copy()    # shallow

import copy
b = copy.deepcopy(a)   # inner lists are new objects too

Shallow copies are the correct call for lists of immutable values (numbers, strings, tuples). Reach for deepcopy only when the elements themselves are mutable and you'll mutate them.

`[[0] * cols] * rows` — the shared-inner-list bug

grid = [[0] * 3] * 3      # DON'T — three references to the same list
grid[0][0] = 1
# grid is now [[1, 0, 0], [1, 0, 0], [1, 0, 0]]

grid = [[0] * 3 for _ in range(3)]   # correct — three distinct lists

Integer division vs float

7 / 2       # 3.5   — float division
7 // 2      # 3     — integer floor division
-7 // 2     # -4    — floor rounds TOWARD -inf, not toward zero
int(-7 / 2) # -3    — truncation toward zero

For "round toward zero" semantics on negatives, use int(a / b) or the trickier -(-a // b) for positives. Interviewers accept either; being wrong about -7 // 2 == -4 is common.

Range with negative step

range(10, 0)       # empty — step defaults to 1
range(10, 0, -1)   # 10, 9, 8, ..., 1 — need explicit step

String immutability + `+=` in a loop

result = ""
for chunk in chunks:
    result += chunk      # O(n²) — new string every iteration

# Fix
pieces = []
for chunk in chunks:
    pieces.append(chunk)
result = "".join(pieces)

`is` vs `==`

a = [1, 2, 3]
b = [1, 2, 3]
a == b     # True — equal contents
a is b     # False — different objects

None, True, False       # always compare with `is`
small_ints = 256        # cached; `is` may work, don't rely on it

Rule: is for None, True, False, and identity checks. == for value equality.

Dict ordering

Dicts preserve insertion order since Python 3.7 (a CPython implementation detail in 3.6 that became language spec in 3.7). You can rely on it for interview code; if the interviewer's on 3.5 you have bigger problems.

`range` vs `enumerate`

for i in range(len(nums)):   # C-style; verbose
    use(nums[i])

for i, v in enumerate(nums): # Pythonic; interviewer-preferred
    use(v)

Type hints — the interview-visible parts

from typing import Optional, Callable, Iterable

def two_sum(nums: list[int], target: int) -> list[int]:
    ...

def find(nums: list[int], target: int) -> Optional[int]:
    ...   # returns int or None

def apply(f: Callable[[int], int], values: Iterable[int]) -> list[int]:
    ...

Python 3.9+ lets you use list[int], dict[str, int], tuple[int, str] directly — no List, Dict, Tuple imports from typing. Interviewers rarely require type hints, but writing them makes solutions read more like production code.

Complexity quick reference

For the amortised-O(1) claims, worst-case fallbacks, and language-gotcha table (list.pop(0) is O(n), x in list is O(n), heapq.heapify is O(n) not O(n log n)), see the Big-O cheat sheet.

Interviewers accept "amortised O(1)" as the answer for dict.get, set.add, list.append; they'll dock you if you can't defend it when pressed on collisions or resize.

The patterns this cheat sheet backs

Every pattern post's code samples cash in on some Python-specific idiom or standard-library shortcut listed above.

The sliding-window pattern uses defaultdict(int) for the window frequency and collections.Counter for need/have counting — see the LC 76 walkthrough for how the have count avoids O(alphabet) validity checks.
The two-pointer pattern uses nums.sort() (Timsort, O(n log n) worst case) to unlock the 3Sum reduction, and multi-line dedup with while nums[left] == nums[left + 1] on both sides.
The binary-search template rolls its own with low + (high - low) // 2 — but if you're binary-searching a sorted list of primitives, bisect is the standard-library shortcut.
The monotonic-stack pattern uses a plain list as the stack (O(1) append/pop at the end) and stores indices, not values, to compute distances.
The backtracking template uses list append/pop for the choose/undo rhythm — current.append(x); ...; current.pop(). Recording a snapshot uses result.append(current[:]), one of the language's most interview-critical idioms.
The BFS vs DFS decision post uses collections.deque for the BFS queue and a plain set for the visited set. Never a list for either.

The idioms above aren't decoration. They're the vocabulary the pattern posts assume you already have.