Python Interview Cheat Sheet

Last-minute Python / LeetCode warm-up for coding interviews. The goal is to recognize which structure or built-in to reach for, remember the syntax, and avoid reinventing common operations under time pressure.

Drills below are small templates (Piston Python). Implement the named function; the harness prints the result. For fuller company-style problems see Coding — Easy / Medium / Hard. Approach & Big-O: Coding Interviews.

Memorize first: dict / set / Counter → list-as-stack + deque → enumerate / zip / sorted(..., key=) → binary search, two pointers, sliding window → BFS / DFS / heaps → complexity + edge cases.

Ask on every prompt: do I need fast lookup, ordering, FIFO/LIFO, or priority? That choice usually picks the structure.

1. Data structures at a glance

Need	Python tool	Typical use
Dynamic array / stack	list	Two pointers, DFS, stack problems
Queue / deque	collections.deque	BFS, sliding windows
Frequency counter	collections.Counter	Anagrams, duplicates, top K
Default values	collections.defaultdict	Graphs, grouping
Fast membership / uniqueness	set	Two Sum variants, visited nodes
Key-value lookup	dict	Hash maps, caching
Min/max priority queue	heapq	Top K, scheduling, merging
Binary search	bisect	Sorted arrays
Combinations / permutations	itertools	Backtracking, enumeration

2. collections — high-value tools

Counter

from collections import Counter

nums = [1, 2, 2, 3, 3, 3]
count = Counter(nums)
count[2]              # 2
count.most_common(2)  # [(3, 3), (2, 2)]

Useful for frequency counting, anagrams, duplicates, top-K frequent.

def is_anagram(s, t):
    return Counter(s) == Counter(t)

defaultdict

from collections import defaultdict

groups = defaultdict(list)
for word in ["eat", "tea", "dog"]:
    groups["".join(sorted(word))].append(word)

graph = defaultdict(list)
graph[1].append(2)
graph[1].append(3)

Useful for grouping, adjacency lists, and accumulating without if key not in ….

deque

from collections import deque

q = deque([1, 2, 3])
q.append(4)        # right
q.appendleft(0)    # left
q.pop()            # right
q.popleft()        # left — O(1)

Use deque.popleft() for a queue — not list.pop(0), which shifts the rest of the list.

Drill: Counter & defaultdict

3. Lists, stacks, and queues

List as array and stack

arr = [10, 20, 30]
arr.append(40)   # amortized O(1)
arr.pop()        # O(1)
arr[-1]          # peek last
arr[1:3]         # [20, 30]
arr.reverse()
arr.sort()

Stack = LIFO:

stack = []
stack.append(1)   # push
top = stack[-1]   # peek
top = stack.pop() # pop

Typical: valid parentheses, DFS, monotonic stacks.

Queue = FIFO

from collections import deque

queue = deque()
queue.append("A")
first = queue.popleft()

Typical: BFS, unweighted shortest path, tree level order.

4. Dictionaries and sets

dict — O(1) average lookup

index = {"alice": 10, "bob": 20}
index.get("unknown", 0)
index["carol"] = 30
"bob" in index

Two Sum pattern:

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        needed = target - num
        if needed in seen:
            return [seen[needed], i]
        seen[num] = i
    return []

set — uniqueness / membership

seen = {1, 2, 3}
seen.add(4)
seen.discard(99)  # safe if absent
a & b; a | b; a - b

Typical: duplicates, intersections, visited nodes.

Drill: hash map

5. Heaps (heapq)

Min-heap: smallest at index 0.

import heapq

heap = [5, 2, 8, 1]
heapq.heapify(heap)            # O(n)
heapq.heappush(heap, 3)        # O(log n)
smallest = heapq.heappop(heap) # O(log n)
peek = heap[0]                 # O(1)

Top K largest: heapq.nlargest(k, nums). Max-heap simulation: push/pop negated values.

Typical: top K, merge K lists, scheduling, Dijkstra.

Drill: heap

6. Binary search (bisect)

from bisect import bisect_left, bisect_right

nums = [1, 2, 2, 2, 5, 8]
bisect_left(nums, 2)   # 1 — first 2
bisect_right(nums, 2)  # 4 — after last 2

Manual template ($O(\log n)$):

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

Use on sorted arrays, boundary searches, and monotonic predicates.

Drill: binary search

7. Strings, sorting, iteration

s = "hello"
s[::-1]; s.lower(); s.split(" ")
"-".join(["a", "b"])
s.startswith("he"); s.isdigit()

nums.sort()                    # in place
sorted(nums, key=abs)
sorted(words, key=len)
sorted(words, key=lambda x: x[-1])

for i, value in enumerate(nums):
    ...
for a, b in zip(xs, ys):
    ...
for i in range(len(nums) - 1, -1, -1):
    ...

8. itertools

from itertools import combinations, permutations, product

list(combinations([1, 2, 3], 2))
list(permutations([1, 2, 3], 2))
list(product([0, 1], repeat=3))

Handy for brute force / backtracking — watch exponential blow-ups.

9. Essential templates

BFS

from collections import deque

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

Unweighted shortest paths and level-order exploration.

DFS

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

Connectivity, cycles, path search. Prefer an explicit stack for deep graphs (recursion limit).

Two pointers

def has_pair(nums, target):
    nums = sorted(nums)
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1
    return False

Sliding window (fixed size)

def max_sum_k(nums, k):
    if len(nums) < k:
        return None
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        best = max(best, window)
    return best

Drill: BFS, two pointers, window

10. Complexity quick reference

Operation	Typical complexity
List index	$O(1)$
List append	amortized $O(1)$
x in list	$O(n)$
Set / dict lookup	average $O(1)$
deque.popleft()	$O(1)$
Heap push/pop	$O(\log n)$
Sorting	$O(n\log n)$
Binary search	$O(\log n)$
BFS / DFS	$O(V+E)$

$n$ = elements; $V$ / $E$ = vertices / edges.

Concept check

Quiz

Pick the right tool

1 / 4

You need FIFO level-order traversal of a tree. Best structure?

Pick an answer to see if you are right.

Day-of checklist

1. Restate I/O, constraints, and whether order / duplicates matter.
2. Name the need: lookup, order, FIFO/LIFO, or priority.
3. Brute force → improve; say Big-O out loud.
4. Code the template (hash map, two pointers, BFS, …) then dry-run edges.
5. Watch off-by-one on windows/bisect and recursion depth on DFS.

Also useful: Data structures · Algorithms · SQL cheat sheet.