The 15-minute read
Everything below is Python-specific: the complexities that hold in CPython, the stdlib tools interviewers expect you to reach for, and the traps they watch for. Read top to bottom once, then re-skim the Q&A.
pop(0) is O(n) — use deque.popleft() · [[0]*n]*m aliases rows · heapq is min-heap only · -3 // 2 == -2, -3 % 2 == 1 · list.sort() returns None · strings are immutable, build with "".join(parts)1 · Data structures
append / pop() → O(1) amortized · pop(0) / insert(0) → O(n) · sort() → O(n log n) Timsort, stable, in-place
A dynamic array. Your default sequence. Slicing copies — a[i:j] costs O(k).
a = [3, 1, 2] a.append(4) # O(1) amortized a.pop() # O(1), removes from the end a.sort() # in-place Timsort, returns None b = sorted(a, key=lambda x: -x) # new list, descending
Gotcha: [[]] * n makes n references to the SAME inner list.
get / set / del → O(1) average, O(n) worst case · iteration → insertion order (3.7+)
A hash table. The answer to half of all interview questions. d.get(k, default) avoids KeyError; setdefault builds-and-fetches in one step.
d = {}
d["k"] = 1
d.get("missing", 0) # 0, no KeyError
d.setdefault("k2", []).append(1) # fetch-or-create idiom
for k in list(d): # snapshot keys: safe to mutate inside
del d[k]
Gotcha: never change a dict's size while iterating it — iterate over list(d) instead.
add / discard / membership → O(1) average · | & - → union / intersection / difference
A hash set. Use it for dedup and O(1) "have I seen this" checks — the visited set in every graph problem.
seen = set()
seen.add(x)
if x not in seen: # O(1) membership
...
a | b # union
a & b # intersection
a - b # difference
append / popleft / appendleft → O(1) · indexed access → O(n)
The queue. Every BFS in Python runs on a deque. q = deque([start]), then q.popleft() in the loop.
from collections import deque q = deque([start]) q.append(nxt) # O(1) on the right u = q.popleft() # O(1) on the left q.appendleft(x) # O(1): push front (0-1 BFS trick)
Gotcha: list.pop(0) inside a loop silently turns your O(n) BFS into O(n²).
heappush / heappop → O(log n) · heapify(list) → O(n) · nlargest / nsmallest → O(n log k)
Min-heap on a plain list. Max-heap = push negated values. Tuple entries compare lexicographically — add a tiebreaker counter (priority, i, item) so items never get compared.
import heapq h = [] heapq.heappush(h, (prio, i, item)) # O(log n) prio, _, item = heapq.heappop(h) # smallest first # max-heap: push (-x, i, item) instead top3 = heapq.nlargest(3, nums) # O(n log k), no full sort
defaultdict(list) → auto-creates missing keys · Counter(s) → frequency map in one pass
Grouping: groups = defaultdict(list); groups[key].append(x). Counting: Counter(s).most_common(k). Both are interview shorthand the interviewer expects you to know.
from collections import defaultdict, Counter
groups = defaultdict(list)
groups[key].append(x) # no KeyError, ever
cnt = Counter("abracadabra")
cnt.most_common(2) # [('a', 5), ('b', 2)]
cnt["z"] # 0 — Counter never KeyErrors
slicing / concatenation → O(k) each · join → O(n) total
Both immutable; tuples are hashable so they work as dict keys. Build strings with "".join(parts) — += in a loop is O(n²).
parts = []
for x in items:
parts.append(str(x))
s = "".join(parts) # O(n) total — the fast way
t = (x, y) # hashable: usable as a dict key
d[t] = 1
s[::-1] # reversed copy, O(n)
2 · Algorithm patterns
from collections import deque
q = deque([start]); seen = {start}; dist = 0
while q:
for _ in range(len(q)): # one level = one step
u = q.popleft()
for v in neighbors(u):
if v not in seen:
seen.add(v); q.append(v)
dist += 1
The for _ in range(len(q)) level snapshot is the whole trick — it turns the queue into a clock.
def dfs(u):
seen.add(u)
for v in neighbors(u):
if v not in seen:
dfs(v)
Recursion is fine for interviews, but deep graphs can hit the recursion limit — mention sys.setrecursionlimit or go iterative with an explicit stack.
from bisect import bisect_left
i = bisect_left(a, x) # first index with a[i] >= x
# hand-rolled:
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x: lo = mid + 1
else: hi = mid
State the invariant out loud: "everything left of lo is < x." Off-by-ones live here — test with 0, 1, and 2 elements.
l, r = 0, len(a) - 1
while l < r:
s = a[l] + a[r]
if s == target: return (l, r)
elif s < target: l += 1
else: r -= 1
O(n) time, O(1) space. Requires sorted input — say so before you start.
l = 0
for r in range(len(a)):
window.add(a[r])
while not valid(window): # shrink until valid again
window.remove(a[l]); l += 1
best = max(best, r - l + 1)
Each index enters and leaves once → O(n). Works when expanding right never invalidates a valid window (monotonicity) — name that condition.
a.sort(key=lambda x: x[0]) # in-place, returns None b = sorted(items, key=lambda p: (-p.score, p.name)) # multi-key: tuple keys
Stability means equal keys keep their original order — useful in multi-pass sorts. key= beats cmp= (which doesn't exist in py3).
def backtrack(path, start):
if done(path): ans.append(path[:]); return
for i in range(start, len(nums)):
path.append(nums[i]) # choose
backtrack(path, i + 1) # explore
path.pop() # unchoose
Choose → explore → unchoose. Copy the path (path[:]) when saving — the list keeps mutating.
from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
if n <= 1: return n
return f(n-1) + f(n-2)
Top-down with lru_cache is the fastest correct DP in an interview. Bottom-up tabulation saves the recursion stack. Name the state, the recurrence, and the base case before coding.
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
Path compression + union by rank → amortized ~O(1) per op. The answer whenever components merge over time.
3 · Common Q&A
Floyd's tortoise and hare: slow advances one node, fast advances two. If fast hits None, no cycle; if they meet, there is one. O(n) time, O(1) space — and to find the cycle's start, reset one pointer to head and advance both at speed 1.
OrderedDict: get does move_to_end(k), put evicts with popitem(last=False) when over capacity. From scratch: hash map from key → node plus a doubly-linked list for recency — get/put splice the node to the front in O(1).
BFS for shortest path in unweighted graphs (level order = distance). DFS for exhaustive search, connectivity, cycle detection, topological sort. Both O(V+E); BFS uses more memory (the frontier), DFS risks recursion depth.
Min-heap of size k via heapq: push each element, pop when size exceeds k — the root is the answer. O(n log k). Mention quickselect (O(n) average) as the follow-up they want to hear.
Iterative three-pointer walk: prev, curr = None, head; each step saves curr.next, flips it to prev, advances both. O(n) time, O(1) space. The recursive version is shorter but costs O(n) stack.
Chaining (each bucket holds a list of entries) vs open addressing (probe for the next free slot — linear, quadratic, or double hashing). Keep the load factor under ~0.7 and resize (rehash into a bigger table) when it grows past that.
O(1) average for get/set/delete, O(n) worst case under adversarial hash collisions or during a resize. Iteration is O(n) in insertion order. This is why "use a dict" is a valid complexity claim in an interview.
Two pointers from both ends, O(1) space. The Pythonic s == s[::-1] is O(n) space — fine to mention, but lead with two pointers since it shows the technique.
Sort by start — then every overlap is adjacent. Sweep once: if start <= last_end, extend with max(last_end, end) (the max handles full containment); else start a new group. O(n log n).
Recursion matches divide-and-conquer structure (trees, backtracking) and is easier to get right; iteration avoids Python's recursion limit and per-call overhead. Python has no tail-call optimization, so deep recursion is a real constraint — name it.
Kahn's algorithm: repeatedly emit nodes with indegree 0, decrementing neighbors. If you emit fewer nodes than exist, there's a cycle. DFS post-order reversed works too. Either is O(V+E).
Cache function results so repeated subproblems compute once — @lru_cache turns exponential recursion into polynomial time. Use it when subproblems overlap (Fibonacci, grid paths); it doesn't help when every subproblem is unique.