Python refresher

Core containers

list is your array — mutable, ordered, O(1) append/pop from the end, O(n) from the front or middle. tuple is the immutable cousin — hashable, so it's what you use as a dict/set key when a single value won't do (e.g. (row, col) or a 26-length count vector). str is also immutable — every "modification" builds a new string, so accumulating with += in a loop is O(n²); use ''.join(parts) instead.

pair_key = (row, col)                 # tuple -> hashable, usable as a dict key
parts = []
for c in word:
    parts.append(c)
result = ''.join(parts)               # O(n), not O(n^2)

Slicing and unpacking

Slicing never raises on out-of-range bounds, which makes windowing code terser. Negative indices count from the end. Extended unpacking grabs "the rest" in one line.

nums[1:3]        # elements at index 1, 2
nums[:3]          # first three
nums[-2:]         # last two
nums[::-1]        # reversed copy
first, *middle, last = nums   # unpack ends, capture the rest as a list

Comprehensions

Prefer a comprehension over a manual loop when you're building a new container from an existing iterable — it reads as "what" instead of "how".

squares = [x * x for x in nums]
evens = [x for x in nums if x % 2 == 0]
index_of = {x: i for i, x in enumerate(nums)}
distinct = {x % 3 for x in nums}

collections — the workhorses

Four types cover most interview needs. Reach for these before hand-rolling the equivalent with a plain dict or list.

from collections import Counter, defaultdict, deque

freq = Counter(word)              # {'a': 2, 'b': 1, ...}; freq.most_common(k)
freq.subtract(other_counter)      # in-place difference
adj = defaultdict(list)           # missing key -> [] instead of KeyError
adj[u].append(v)

q = deque([1, 2, 3])
q.appendleft(0)                   # O(1) both ends — a plain list is O(n) on the left
q.popleft()

Counter subtraction and +/- operators only keep positive counts, which is occasionally exactly what you want and occasionally a footgun — check the sign convention before relying on it.

Heaps — heapq is min-heap only

There's no separate heap type; a plain list becomes a heap through the functions you call on it. Python's heap is always a min-heap, so for a max-heap or a "top-K largest" pattern, negate on the way in and out.

import heapq

heap = []
heapq.heappush(heap, val)
smallest = heapq.heappop(heap)
heapq.heapify(existing_list)         # O(n), turns a list into a heap in place

heapq.heappush(heap, -val)           # max-heap trick: push negated
largest = -heapq.heappop(heap)

heapq.nlargest(k, nums)               # O(n log k) — don't hand-roll this
heapq.nsmallest(k, nums)

bisect — binary search without writing the loop

import bisect

i = bisect.bisect_left(sorted_list, target)   # first index where target could go
j = bisect.bisect_right(sorted_list, target)  # last index where target could go
bisect.insort(sorted_list, val)                # insert, keeping order (O(n) shift)

bisect_left vs bisect_right only differ on ties — _left gives you the first insertion point, _right the last. Get this backwards and an "insert to keep sorted" problem quietly becomes an off-by-one bug.

Sorting with a key

sorted() and .sort() are stable and take a key, not a comparator — build the key once per element rather than reasoning about pairwise comparisons.

words.sort(key=len)                              # by a single derived value
points.sort(key=lambda p: (p[0], -p[1]))         # multi-key: x asc, y desc
sorted(nums, reverse=True)                        # descending, still stable

itertools for combinatorics

When a pattern calls for "all pairs", "all orderings", or "all picks", these are the O(1)-to-write versions of what you'd otherwise hand-roll with backtracking.

from itertools import permutations, combinations, product, accumulate

list(permutations(nums))          # all orderings, n! of them
list(combinations(nums, 2))       # all size-2 subsets, order doesn't matter
list(product(range(3), repeat=2)) # cartesian power — grid coordinate pairs
list(accumulate(nums))            # running prefix sums

Strings and characters

ord('a'), chr(97)                 # char <-> code point
'Hello World'.lower().split()      # ['hello', 'world']
s.isalnum(), s.isdigit()
s.strip('  padded  ')
f"{name}: {value:.2f}"             # f-strings — prefer these over % or .format

Memoization: functools.lru_cache

For top-down DP, a decorator often beats a hand-rolled memo dict — but every argument must be hashable (no lists), and it's easy to forget the cache persists across calls if you reuse the function across test cases.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Gotchas that cost real interview minutes

• Mutable default arguments — def f(seen=[]): reuses the same list across every call. Use def f(seen=None): seen = seen or [].
• [[0] * m] * n for a 2D grid — this repeats references to one inner list; mutating grid[0][0] mutates every row. Use [[0] * m for _ in range(n)].
• is vs == — is checks identity, == checks equality. Small integers and interned strings can make is "work" by accident; don't rely on it for value comparison.
• Integer division — // floors toward negative infinity in Python, not toward zero. -7 // 2 == -4, not -3. Matters for any "divide and round" logic ported from another language.
• Shallow copy vs deep copy — list(x) / x[:] / x.copy() copy one level; nested lists still share inner references. Use copy.deepcopy when the structure is nested and you need full independence.
• float('inf') / float('-inf') — the idiomatic sentinel for "haven't found a candidate yet" in min/max tracking; avoids a separate found flag.