Python Coding Interview Cheat Sheet: The One-Page Reference

You've got 30 minutes before your Python coding interview. Maybe 20. You're not reading a tutorial. You don't need the history of Timsort. You need the facts that actually come up, organized so your panicked eyes can find them fast.

Data structure time complexities, tight algorithm templates, the collections module in under a minute, and the three gotchas that quietly cost people offers. That's it. Go.

Python Time Complexities You Must Have Cold

If you blank on one of these mid-interview, the interviewer notices.

Data Structure	Access	Search	Insert	Delete	Notes
`list`	O(1)	O(n)	O(n)	O(n)	Amortized O(1) for `append` only
`dict`	O(1)	O(1)	O(1)	O(1)	Hash table underneath
`set`	N/A	O(1)	O(1)	O(1)	Same hash table guarantees
`deque`	O(n)	O(n)	O(1)	O(1)	O(1) at both ends only
`heapq` (min-heap)	O(1) peek	O(n)	O(log n)	O(log n)
`sorted()` / `.sort()`	N/A	N/A	N/A	N/A	O(n log n), stable Timsort

The trap: list.pop(0) is O(n), not O(1). Every element shifts left. BFS with a list instead of a deque turns an O(V+E) graph traversal into an O(n²) disaster, and you won't notice until the interviewer quietly updates their notes.

Python Algorithm Templates

Binary Search

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

left + (right - left) // 2 is the right habit even though Python integers don't overflow. Interviewers notice when you use the overflow-safe form. It signals you know why you're writing it, not just that you memorized it.

BFS

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Always deque, always popleft(). Set for visited, not a list. These two details separate people who have actually debugged BFS from people who have only read about it.

DFS

def dfs(node, graph, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)

Looks clean. Works great, right up until your input is a graph with 10,000+ nodes and Python throws RecursionError: maximum recursion depth exceeded. The default limit is 1000 frames. If deep recursion is possible, reach for the iterative version:

def dfs_iterative(graph, start):
    stack = [start]
    visited = {start}
    while stack:
        node = stack.pop()
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

Sliding Window (Variable Size)

def longest_valid_window(arr):
    left = 0
    state = {}
    result = 0

    for right in range(len(arr)):
        state[arr[right]] = state.get(arr[right], 0) + 1

        while not is_valid(state):       # shrink until valid
            state[arr[left]] -= 1
            if state[arr[left]] == 0:
                del state[arr[left]]
            left += 1

        result = max(result, right - left + 1)

    return result

Every element is added once and removed once, so the whole loop runs in O(n). The is_valid check is O(1) if your window state is a hash map.

Two Pointers (Opposite Ends)

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

Requires a sorted array. If the array isn't sorted, a hash map is O(n) and faster. Don't reach for two pointers just because you like the pattern.

Memoized Recursion

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(state):
    if base_case(state):
        return base_value
    return min(dp(next_state) for next_state in transitions(state))

@lru_cache turns any pure recursive function into memoized DP in one line. Every argument must be hashable. Lists are not hashable; use tuples. This bites people who try to pass a list of remaining items and wonder why they get TypeError: unhashable type.

The `collections` Module in 90 Seconds

`Counter`

from collections import Counter

c = Counter("aabbcc")    # Counter({'a': 2, 'b': 2, 'c': 2})
c['a']                   # 2 (returns 0 for missing keys, not KeyError)
c.most_common(2)         # [('a', 2), ('b', 2)]

# Arithmetic
Counter("aab") - Counter("ab")  # Counter({'a': 1})
Counter("aab") & Counter("ab")  # Counter({'a': 1, 'b': 1}), intersection

Use Counter for anagram detection, sliding window character counts, and anything involving frequency maps. It is genuinely one of the nicest things in the standard library.

`defaultdict`

from collections import defaultdict

graph = defaultdict(list)
graph['a'].append('b')   # No KeyError on first access

freq = defaultdict(int)
freq['x'] += 1           # Starts at 0 automatically

Use defaultdict(list) when building adjacency lists. Use defaultdict(int) when counting without wanting to check for key existence. The alternative is if key not in d: d[key] = [] on every insert, which is fine and also deeply annoying.

`deque`

from collections import deque

q = deque()
q.append(1)        # O(1) right
q.appendleft(0)    # O(1) left
q.popleft()        # O(1) left, this is the whole reason to use deque
q.pop()            # O(1) right

deque is the only correct choice for BFS queues. list.pop(0) shifts every element left, making BFS O(n²) on a long path. If you write queue = [] and queue.pop(0) in a coding interview, you will eventually have to explain why your solution is slow. That explanation is not a fun part of the interview.

`heapq`

import heapq

heap = [3, 1, 4, 1, 5]
heapq.heapify(heap)         # In-place, O(n)
heapq.heappush(heap, 2)     # O(log n)
heapq.heappop(heap)         # O(log n), returns minimum

# Max-heap: negate the values
heapq.heappush(heap, -val)
max_val = -heapq.heappop(heap)

# Top-k largest elements: use a min-heap of size k
def kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for n in nums[k:]:
        if n > heap[0]:
            heapq.heapreplace(heap, n)
    return heap[0]

Python's heap is a min-heap. Always. There is no max-heap. The negation trick is not a hack, it's the intended pattern. The min-heap-of-size-k approach for top-k problems is O(n log k), better than sorting when k is small.

Sorting in 60 Seconds

Python sort is stable Timsort. O(n log n) guaranteed, no pathological cases. You won't trigger worst-case behavior by accident.

# Sort by a derived key
intervals.sort(key=lambda x: x[0])                  # by start
words.sort(key=lambda w: len(w))                    # by length
pairs.sort(key=lambda x: (x[0], -x[1]))             # first asc, second desc

# In-place vs new list
arr.sort()              # modifies arr, returns None
sorted(arr)             # returns new list, original unchanged

# Reverse
arr.sort(reverse=True)

list.sort() returns None; sorted() returns the new list. The common mistake is arr = arr.sort(), which assigns None to arr. You will then spend two minutes confused about why arr is None before the interviewer gently asks what you expect that line to return.

If you need a custom comparison rather than a key, use functools.cmp_to_key. It's rare but shows up when you can't express the ordering as a single key, like sorting numbers to form the largest possible integer:

from functools import cmp_to_key

def compare(a, b):
    return int(str(b) + str(a)) - int(str(a) + str(b))

sorted(nums, key=cmp_to_key(compare))

Three Gotchas That Quietly Cost Offers

These are not algorithmic mistakes. They're the bugs that compile, run, produce wrong output, and make you stare at your code for three minutes while the clock ticks.

Mutable default arguments are shared across all calls. Define them as None and initialize inside the function:

def bad(val, lst=[]):     # lst is created once and reused across every call
    lst.append(val)
    return lst

def good(val, lst=None):  # None is replaced each call
    if lst is None:
        lst = []
    lst.append(val)
    return lst

bad(1) returns [1]. Call it again with bad(2) and you get [1, 2]. The list is not reset. Python creates the default value once at function definition time and keeps reusing it. This is one of those things that sounds made-up until you hit it at 2 AM, or in minute 25 of your interview.

// floors toward negative infinity, not zero. -7 // 2 is -4, not -3. If you need truncation-toward-zero (which is what Java, C++, and Go do), use int(-7 / 2) which gives -3. Most interview problems use non-negative indices so this won't bite you often, but it will bite you exactly once per career in a way you won't forget.

Copying nested structures. b = a[:] only copies the outer list. Inner lists are still shared references:

path = [[1, 2], [3, 4]]
shallow = path[:]          # outer copy only
shallow[0].append(99)      # modifies path[0] too, you didn't copy the inner list

import copy
deep = copy.deepcopy(path) # fully independent

In backtracking, this shows up as result.append(path) instead of result.append(path[:]). You append a reference to the list, the list mutates as recursion continues, and when you check result at the end every entry is identical to the last state. The solution looks like it works, it produces the wrong output, and you have seven minutes left.

For more Python-specific footguns, the full Python gotchas guide covers integer caching, is vs ==, and floating-point precision traps.

Before Your Python Coding Interview

Scan the complexity table one more time. The most common failures aren't algorithmic. Engineers blank on list.pop(0) being O(n), or forget that heapq is a min-heap and negate at the wrong moment. These are facts, not reasoning, and facts go stale under pressure if you haven't looked at them recently.

If you want to practice speaking these patterns out loud under realistic pressure, SpaceComplexity runs voice-based DSA mock interviews with rubric-based feedback so you can see exactly where your explanations break down before the real thing.