</>

Python Interview Core

data structures · patterns · Q&A — all Python

← CodePrep

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.

C++-brain traps, one last time: 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

list

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.

dict

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.

set

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
collections.deque

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²).

heapq

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
collections.defaultdict · collections.Counter

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
str · tuple

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

BFS — shortest path in an unweighted graph, level by level
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.

DFS — exhaustive search, connectivity, topological order
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.

Binary search / bisect — sorted data, O(log n) lookup or insertion point
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.

Two pointers — sorted arrays, palindromes, in-place partition
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.

Sliding window — longest/shortest subarray satisfying a constraint
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.

Sorting — Timsort, O(n log n), stable
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).

Backtracking — generate all candidates: permutations, subsets, combinations
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.

Dynamic programming — overlapping subproblems + optimal substructure
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.

Union-Find — dynamic connectivity, "are these connected?", Kruskal's
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

Q: How do you detect a cycle in a linked list?

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.

Q: Implement an LRU cache.

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).

Q: BFS vs DFS — when do you use each?

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.

Q: Find the kth largest element.

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.

Q: Reverse a linked list.

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.

Q: How does a hash table resolve collisions?

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.

Q: What's the complexity of Python dict operations?

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.

Q: Check if a string is a palindrome.

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.

Q: Merge overlapping intervals.

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).

Q: Recursion vs iteration — trade-offs?

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.

Q: How do you topologically sort a graph?

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).

Q: What is memoization, and when do you use it?

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.