The Python Refresher (Interview Toolkit)

This is not all of Python. It is the slice that the patterns in this course actually use, the slice that shows up in interviews. The goal is fluency with the containers and the standard-library helpers so that, in Week 5 or Week 13, your attention is on the algorithm and never on “how do I write this in Python.”

Work it actively. Keep a Python REPL open (python3) and type every example yourself; change a value and predict the result before you hit Enter. Reading is not the same as producing, and the interview asks you to produce.

Each section notes the weeks that lean on it most. None of this is the puzzle; these are tools you are allowed to know cold.

flowchart TD
    Q["I need to store..."] --> A{"key-value pairs?"}
    A -->|yes| D["dict (or Counter / defaultdict)"]
    A -->|no| B{"only membership / uniqueness?"}
    B -->|yes| S["set"]
    B -->|no| C{"order matters and I index by position?"}
    C -->|yes| L["list"]
    C -->|no, it is fixed| T["tuple"]

Notice: “which container” is a question you answer dozens of times in this course. Make it reflexive now.

0. Statements: loops, conditionals, functions

If the lines below feel unfamiliar rather than just rusty, work a short intro tutorial before continuing; this page assumes you have met them and only need them fresh.

if n % 2 == 0:           # if / elif / else: branch on a condition
    print("even")
elif n == 1:
    print("one")
else:
    print("odd")

for i in range(5):       # range(5) yields 0, 1, 2, 3, 4
    print(i)

for x in [10, 20, 30]:   # iterate a list's values directly
    print(x)

for ch in "hello":       # a string is iterable; ch is each character in turn
    print(ch)

while n > 0:             # loop until the condition flips
    n -= 1

def add(a, b):           # define a function; `return` hands a value back
    return a + b

print(...) writes to the screen. range(n) gives 0..n-1, range(a, b) gives a..b-1. A function with no return gives back None. And one string idiom you will use in Week 1: sorted("dcba") returns the list ['a', 'b', 'c', 'd'], and "".join(sorted("dcba")) rebuilds it into the string 'abcd', which is the anagram key.

Used heavily in: every week.

1. The REPL, numbers, and two division traps

+ 3 * 4        # 14, normal precedence
** 10          # 1024, exponent
/ 3           # 3.3333333333333335  -> a FLOAT, always
// 3          # 3, floor division -> an INT
% 3           # 1, remainder (modulo)
divmod(10, 3)    # (3, 1), the quotient and remainder together

Two traps that cause real interview bugs:

/ always gives a float. Array indices must be ints. Use // for index math: mid = (lo + hi) // 2, never (lo + hi) / 2.
Floor division and modulo round toward negative infinity. -7 // 2 is -4 (not -3), and -7 % 2 is 1. This matters in math and bit problems (Week 15).

Python integers are arbitrary precision: they never overflow. You will not fight 32-bit overflow the way C programmers do (except in a couple of Week 15 bit problems that ask you to simulate it). For “infinitely large,” use float('inf') and float('-inf'):

best = float('inf')          # smaller than any real number you will compare
best = min(best, candidate)  # common DP / Dijkstra idiom (Weeks 12, 13)

Rounding up, and the `math` module

To round a division up (how many full hours, how many full buckets), use math.ceil(a / b), which needs import math. With positive integers you can skip the float entirely: (a + b - 1) // b equals math.ceil(a / b). Week 5 (Koko Eating Bananas) uses exactly this.

Bit operations

You do not need these until Week 15, but here is the vocabulary so it is not new then. Because Python integers are arbitrary precision, bit tricks never overflow unless you force a width with a mask.

a ^ b           # XOR: 1 where the bits differ. Key facts: x ^ x == 0, x ^ 0 == x.
a & b           # AND: 1 where both bits are 1.
a | b           # OR : 1 where either bit is 1.
~a              # NOT: flips every bit (in Python ~a == -a - 1, since ints are signed).
n << 1          # shift left by one bit  == multiply by 2.
n >> 1          # shift right by one bit == floor-divide by 2 (drops the lowest bit).
n & 1           # read the lowest bit: 1 if n is odd, 0 if even.
n & (n - 1)     # clear the lowest set bit (turn the rightmost 1 into 0).
n & 0xFFFFFFFF  # keep only the low 32 bits: this is how you SIMULATE fixed width,
                # which Python ints do not have (Week 15, Sum of Two Integers).

Used heavily in: Binary Search (5), Advanced Graphs (12), DP (13, 14), Bit/Math (15).

2. Strings

Strings are immutable: you cannot change a character in place. To build a string, collect pieces and join.

s = "hello"
s[0]            # 'h'
s[-1]           # 'o', negative indexes count from the end
s[1:4]          # 'ell', slice [start:stop), stop is exclusive
s[::-1]         # 'olleh', reverse via a step of -1
len(s)          # 5
"a,b,c".split(",")     # ['a', 'b', 'c']
"".join(["a", "b"])    # 'ab'  -> the right way to build a string
ord("a"), chr(97)      # 97, 'a'  -> char <-> codepoint
f"n is {len(s)}"       # 'n is 5', f-strings interpolate

The anti-pattern is result += ch in a loop; because strings are immutable, that rebuilds the whole string each time (O(n^2) overall). Collect into a list and "".join(...) at the end.

Used heavily in: Arrays/Hashing (1), Two Pointers (2), Sliding Window (3), Tries (10), DP on strings (14).

3. Lists

The workhorse. Dynamic array; index in O(1); append and pop at the end in amortized O(1). (Amortized means averaged over many operations: a single append is occasionally slow when the list has to grow its backing array, but across n appends the average cost is O(1). You will use the word in every complexity debrief, so learn it here.)

a = [3, 1, 2]
a[0], a[-1]      # 3, 2
a.append(4)      # [3, 1, 2, 4]
a.pop()          # removes & returns 4  -> this is your STACK (Week 4)
a[1:3]           # [1, 2], slicing makes a COPY of that range
a[:]             # a full shallow copy (used to snapshot a path, Week 9)
len(a)           # length
reversed(a)      # an iterator, oldest trick: list(reversed(a))

Sorting

a = [3, 1, 2]
a.sort()                 # sorts IN PLACE, returns None
b = sorted(a)            # returns a NEW sorted list, leaves a alone
sorted(a, reverse=True)  # descending
pairs = [("ann", 90), ("bo", 70)]
sorted(pairs, key=lambda p: p[1], reverse=True)   # by score, highest first
sorted(words, key=lambda w: (len(w), w))          # by length, then alphabetical

A lambda is a one-line anonymous function: lambda p: p[1] takes one argument p and returns p[1]. The parameter goes before the colon, the returned expression after. Writing a key= function inline is essentially all the lambda you need for this course. key= is the most useful sorting idea here: it sorts by a computed value. Note sort() returns None, so a = a.sort() is a classic bug.

enumerate and zip

for i, x in enumerate(a):        # index and value together
    ...
for i, x in enumerate(a, 1):     # start counting at 1
    ...
for name, score in zip(names, scores):   # walk two lists in lockstep
    ...

List comprehensions

[x * x for x in range(5)]            # [0, 1, 4, 9, 16]
[x for x in a if x % 2 == 0]         # filter to evens
[c for row in grid for c in row]     # flatten a 2-D grid (nested)

Used heavily in: every week.

4. Tuples

An immutable, fixed sequence. Cheap, and hashable, so a tuple can be a dict key or a set member; a list cannot.

p = (3, 4)
x, y = p            # unpacking
a, b = b, a         # swap without a temp (Weeks 2, 6)
seen.add((r, c))    # store a grid cell in a set (Weeks 9, 11)
counts[(r, c)] = 1  # tuple as a dict key

Tuples shine as composite keys (the (row, col) of a grid cell) and as heap entries (priority, item) (Week 8, 12).

Used heavily in: Two Pointers (2), Heap (8), Backtracking (9), Graphs (11, 12).

5. Dictionaries

Key to value, average O(1) lookup, insert, and membership.

d = {}
d["a"] = 1
d["a"]                 # 1
d.get("z", 0)          # 0  -> default instead of KeyError
d["a"] = d.get("a", 0) + 1     # the counting idiom
"a" in d               # True, membership test
for k, v in d.items(): ...     # iterate pairs
for k in d: ...                # iterate keys
d.setdefault("a", [])          # return d["a"], or insert [] and return it if absent
{k: v for k, v in pairs}       # dict comprehension

d.get(key, default) reads with a fallback and does not change the dict; this is how you count and accumulate without a guard clause. d.setdefault(key, default) reads too, but when the key is missing it inserts the default and returns it, which is the one-liner for “walk or create” (you build a trie this way in Week 10: node = node.setdefault(ch, {})). As of Python 3.7+, dicts keep insertion order.

Used heavily in: Arrays/Hashing (1), and everywhere after.

6. Sets

Unordered collection of unique, hashable elements. Average O(1) membership; this is the structure that turns an O(n^2) “have I seen it” scan into O(n).

s = set()
s.add(3)
3 in s                 # True
s.discard(3)           # remove if present, no error if absent
seen = set(nums)       # dedup a list
{1, 2} & {2, 3}        # intersection {2}
{1, 2} | {2, 3}        # union {1, 2, 3}

A visited set is mandatory in graph traversal (Weeks 11, 12); without it you loop forever.

Used heavily in: Arrays/Hashing (1), Backtracking (9), Graphs (11, 12).

7. The collections trio

These three cover most patterns. Import them: from collections import Counter, defaultdict, deque.

Counter

from collections import Counter
c = Counter("aabbbc")          # Counter({'b': 3, 'a': 2, 'c': 1})
c["b"]                         # 3
c["z"]                         # 0, missing keys are 0, no error
c.most_common(2)               # [('b', 3), ('a', 2)]
Counter(a) == Counter(b)       # True if a and b are anagrams (multisets equal)

Used heavily in: Arrays/Hashing (1), Sliding Window (3).

defaultdict

from collections import defaultdict
g = defaultdict(list)          # missing key auto-creates an empty list
g[0].append(1)                 # no KeyError; g is {0: [1]}
counts = defaultdict(int)      # missing key is 0
counts[x] += 1                 # clean counting

Used heavily in: Graphs adjacency lists (11, 12), Tries (10), grouping (1).

deque

A double-ended queue: O(1) append and pop at both ends. A list is O(n) to pop from the front, so use a deque for BFS queues and sliding-window deques.

from collections import deque
q = deque()
q.append(1)        # push right
q.appendleft(0)    # push left
q.popleft()        # pop left (front)  -> BFS uses this
q.pop()            # pop right

Used heavily in: Sliding Window (3), for the monotonic deque (one whose contents are kept in increasing or decreasing order, so the best element is always at one end); Trees BFS (7); Graphs BFS (11). You will build the monotonic deque in Week 3; the word just means “always sorted one way.”

8. heapq (the priority queue)

heapq turns a plain list into a binary min-heap: the smallest element is always at index 0, and push/pop are O(log n).

import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
heapq.heappop(h)        # 1, always the smallest
nums = [5, 1, 3]
heapq.heapify(nums)     # turn a list into a heap in place, O(n)

Two things to know cold:

Python only has a min-heap. For a max-heap, push negated values (heapq.heappush(h, -x)) and negate on the way out. (Week 8.)
Tuples sort lexicographically, so a heap of (priority, item) orders by priority. If two priorities tie, Python compares the second element, which fails if items are not comparable; add a tiebreaker like an incrementing counter: (priority, count, item). (Weeks 8, 12.)
heapq.heappushpop(h, x) pushes x and then pops and returns the smallest, in a single O(log n) call; heapq.heapreplace(h, x) does the pop first, then the push. Both are the efficient way to keep a fixed-size heap (Week 8’s size-k top-k).

Used heavily in: Heap (8), Advanced Graphs / Dijkstra (12).

9. bisect (binary search on a sorted list)

bisect finds the insertion point that keeps a sorted list sorted, in O(log n).

import bisect
a = [1, 3, 3, 5]
bisect.bisect_left(a, 3)    # 1, leftmost spot (before equal elements)
bisect.bisect_right(a, 3)   # 3, rightmost spot (after equal elements)
bisect.insort(a, 4)         # insert 4, keeping a sorted -> [1, 3, 3, 4, 5]

bisect_left vs bisect_right is the difference between “first index >= x” and “first index > x”; getting it right is half of the boundary-condition battle.

Used heavily in: Binary Search (5), the O(n log n) LIS in 1-D DP (13).

10. Functions, recursion, and memoization

def f(x, y=0):           # y has a default
    return x + y

def outer(nums):
    best = 0
    def inner(i):
        nonlocal best        # write to the enclosing 'best'
        best = max(best, nums[i])
    for i in range(len(nums)):
        inner(i)
    return best

A note on type hints. The practice tests show signatures like def two_sum(nums: list[int], target: int) -> list[int]:. The : list[int] and -> list[int] parts are type hints: optional documentation of the expected types. They do nothing at runtime and you never have to write them; the tests include them only to show you the input and output shapes. (The list[int] form needs Python 3.9+, which this course assumes.)

nonlocal lets a nested helper update a variable in the enclosing function; this is the standard way a tree recursion “records” an answer while it “returns” something else (Week 7).

Recursion depth is capped near 1000 by default. Deep recursion (a long linked list or a skewed tree) can hit RecursionError; you can raise the limit (import sys; sys.setrecursionlimit(10000)) or convert to iteration.

Memoization caches results of pure functions, the heart of top-down DP:

from functools import lru_cache

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

lru_cache requires the arguments be hashable (so pass tuples, not lists). Used heavily in: Trees (7), Backtracking (9), DP (13, 14).

11. Classes you will read (not write much)

LeetCode hands you node classes. You rarely define them, but you must read and traverse them fluently.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Walking them is all attribute access: node.next, node.left, node.val, with None marking the end or an empty child. Used in: Linked List (6), Trees (7).

12. Big-O in five minutes (you state it every debrief)

Complexity describes how work grows as input size n grows, ignoring constants. The ones you will name constantly:

O(1) constant: a dict/set lookup, an array index.
O(log n) logarithmic: binary search, one heap push/pop.
O(n) linear: one pass over the input.
O(n log n): a sort, or n heap operations.
O(n^2) quadratic: nested loops over the input (the brute force you improve away from).
O(2^n) / O(n!) exponential / factorial: subsets, permutations (Week 9), unpruned.

Space complexity counts the extra memory you allocate (the hash map, the recursion stack, the dp table), not the input itself. Debrief question 3 asks for both time and space and “what dominates at scale”; this section is the vocabulary for answering it.

13. The pitfalls that bite beginners (read twice)

These cause more interview bugs than any algorithm mistake.

Pitfall: float vs int division. (lo + hi) / 2 is a float and breaks list indexing. Use //.

Pitfall: 2-D list aliasing. grid = [[0] * cols] * rows makes rows references to the same inner list, so grid[0][0] = 1 changes every row. Always build rows independently:
grid = [[0] * cols for _ in range(rows)]
This bug appears the moment you build a dp table in Week 14.

Pitfall: mutable default arguments. def f(x, acc=[]) reuses the same list across every call, so values leak between calls. Default to None and create inside:
def f(x, acc=None):
    if acc is None:
        acc = []

Pitfall: aliasing vs copying a path. In backtracking (Week 9), results.append(path) stores a reference; when you later mutate path, the stored result changes too. Append a copy: results.append(path[:]).

Pitfall: mutating a list while iterating it. Removing items from a list inside for x in a: skips elements. Iterate a copy (for x in a[:]:) or build a new list.

Pitfall: sort() returns None. a = a.sort() sets a to None. Use a.sort() for in place, or b = sorted(a) for a new list.

How to use this page going forward

You will not remember all of this on the first read, and you do not need to. Pass the Week 0 self-check, then refer back here whenever a week’s “Python idioms refreshed this week” line names something you have gone fuzzy on. By Week 8 or so, most of this will be reflexive, which is exactly the point: a quiet toolbox so your whole attention goes to the pattern.