Language
Python for interviews
Idioms, collections, ListNode/TreeNode, and the gotchas that show up in coding interviews. Python 3.10+; site CI runs 3.12.
Assumes Python 3.10 or newer. The site CI runs 3.12.
match needs 3.10. dict | other and list[int] need 3.9. The walrus operator needs 3.8. math.lcm and int.bit_count need 3.9 and 3.10.
Each Python block below runs on its own.
Names and unpacking
a, b = 1, 2
a, *rest = [1, 2, 3]
assert rest == [2, 3]
a, b = b, a
assert (a, b) == (2, 1)
x = y = z = 0
assert (x, y, z) == (0, 0, 0)type(x) returns the class. isinstance(x, (int, float)) accepts either. int("5"), float("1.5"), str(5), bool(0), and list("ab") are the conversions you actually want. bool(0) is False.
Operators
assert 7 / 2 == 3.5
assert 7 // 2 == 3
assert -3 // 2 == -2 # floor, toward -infinity
assert -3 % 2 == 1 # remainder takes the sign of the divisor
assert 2 ** 10 == 1024
assert (1 < 3 < 5) is True
value = 1 if True else 2
assert value == 1and, or, and not are the boolean operators. in and is are the membership and identity operators. & | ^ ~ << >> are bitwise. See the bit-manipulation pattern for the identities that matter in problems.
x or default returns default for every falsy x, including 0, "", and []. Use x if x is not None else default when those values are real data.
name = "ada"
n = len(name)
assert (n := len(name)) > 2 and n == 3The parentheses around the walrus are required inside an if test.
Strings
name, pi, bits = "ada", 3.14159, 10
text = f"{name!r:>6} {pi:.2f} {1024:,} {bits:08b} {bits=}"
assert text == " 'ada' 3.14 1,024 00001010 bits=10"
s = "ab,cd"
assert s[0] == "a" and s[-1] == "d"
assert s[1:4] == "b,c" and s[::-1] == "dc,ba"
assert s.split(",") == ["ab", "cd"]
assert " ".join(["ab", "cd"]) == "ab cd"
assert s.replace("ab", "xy") == "xy,cd"
assert s.startswith("ab") and s.endswith("cd")
assert s.find("z") == -1
assert "5".isdigit() and "a".isalpha()
assert ord("A") == 65 and chr(65) == "A"s.index("z") raises ValueError when the substring is missing. s.find returns -1. s.split() with no argument splits on whitespace and drops empty pieces. s.strip, lstrip, and rstrip remove ends only.
A format width is a minimum. {10:08b} is 00001010. {1024:08b} is 10000000000, because 1024 already needs 11 bits. !r counts the quotes toward the width, so {name!r:>6} for ada is a single space plus 'ada'.
Lists
bad = [[0] * 2] * 2
bad[0][0] = 1
assert bad == [[1, 0], [1, 0]]
good = [[0] * 2 for _ in range(2)]
good[0][0] = 1
assert good == [[1, 0], [0, 0]]
nums = [3, 1, 2]
nums.append(4)
nums.extend([5])
assert nums == [3, 1, 2, 4, 5]
assert nums.pop() == 5
assert nums == [3, 1, 2, 4]
assert nums[1:3] == [1, 2]
assert sorted(nums) == [1, 2, 3, 4]
assert nums[::-1] == [4, 2, 1, 3]
shallow = nums[:]
shallow.append(9)
assert 9 not in numslist.sort sorts in place and returns None. sorted returns a new list. nums.pop(0) and nums.insert(0, x) are O(n). Use collections.deque when both ends matter.
copy.copy is shallow. copy.deepcopy copies nested containers.
Tuples and sets
pair = (1, 2)
one = (1,)
assert one != (1)
items = {1, 2, 3}
empty = set()
items.add(4)
items.discard(9)
assert items == {1, 2, 3, 4}
a, b = {1, 2}, {2, 3}
assert (a | b, a & b, a - b, a ^ b) == ({1, 2, 3}, {2}, {1}, {1, 3})
assert {1} <= a
assert frozenset([1, 2]) == frozenset([2, 1]){} is a dict. An empty set is set(). remove raises KeyError when the element is missing. discard does not.
Dicts
keys, values = ["a", "b"], [1, 2]
d = dict(zip(keys, values))
assert d.get("z", 0) == 0
d.setdefault("k", []).append(1)
assert d["k"] == [1]
left, right = {"a": 1}, {"b": 2}
assert left | right == {"a": 1, "b": 2}
assert {k: v for k, v in d.items() if k == "a"} == {"a": 1}del d[key] raises KeyError when the key is missing. d.pop(key, None) returns the default. Do not add or remove keys while iterating the dict.
Comprehensions
assert [x * x for x in range(5) if x % 2 == 0] == [0, 4, 16]
matrix = [[1, 2], [3]]
assert [y for row in matrix for y in row] == [1, 2, 3]
squares = (x * x for x in range(3))
assert list(squares) == [0, 1, 4]The parentheses form is a generator. It yields one value at a time and is exhausted after one pass.
Control flow
seen = []
for i, value in enumerate(["a", "b"], start=1):
seen.append((i, value))
assert seen == [(1, "a"), (2, "b")]
assert list(zip([1, 2], ["a", "b", "c"])) == [(1, "a"), (2, "b")]
found = None
for value in [1, 3, 4]:
if value % 2 == 0:
found = value
break
else:
found = -1
assert found == 4The for/else clause runs when the loop did not break.
def classify(cmd):
match cmd:
case "go" | "run":
return "move"
case [x, y]:
return ("pair", x, y)
case {"k": v}:
return ("map", v)
case int() if cmd > 5:
return "big"
case _:
return "other"
assert classify("run") == "move"
assert classify([1, 2]) == ("pair", 1, 2)
assert classify({"k": 3}) == ("map", 3)
assert classify(6) == "big"
assert classify(1) == "other"Functions
def append_bad(value, bucket=[]):
bucket.append(value)
return bucket
first = append_bad(1)
second = append_bad(2)
assert first is second and second == [1, 2]
def append_ok(value, bucket=None):
if bucket is None:
bucket = []
bucket.append(value)
return bucket
assert append_ok(1) == [1]
assert append_ok(2) == [2]
fns = [lambda: i for i in range(3)]
assert [fn() for fn in fns] == [2, 2, 2]
fns = [lambda i=i: i for i in range(3)]
assert [fn() for fn in fns] == [0, 1, 2]
def outer():
count = 0
def inner():
nonlocal count
count += 1
return count
return inner
tick = outer()
assert tick() == 1 and tick() == 2A default argument is evaluated once, at definition. A list, dict, or set default is shared by every caller. A closure over a loop variable sees the variable’s final value unless the value is bound as a default.
def f(a, b=2, /, c=3, *args, d, e=5, **kw):
return (a, b, c, args, d, e, kw)
assert f(1, 2, 3, d=4) == (1, 2, 3, (), 4, 5, {})Names before / are positional-only. Names after * or *args are keyword-only.
sum(nums, 10) adds a start value. The parameter is keyword-capable: sum(nums, start=10).
Decorators
from functools import wraps
def bold(fn):
@wraps(fn)
def wrapper(*args, **kwargs):
return f"<b>{fn(*args, **kwargs)}</b>"
return wrapper
def italic(fn):
@wraps(fn)
def wrapper(*args, **kwargs):
return f"<i>{fn(*args, **kwargs)}</i>"
return wrapper
@bold
@italic
def greet(name):
return f"Hello, {name}"
assert greet("World") == "<b><i>Hello, World</i></b>"
assert greet.__name__ == "greet"@bold above @italic means bold(italic(greet)). The call runs bold, then italic, then the function. @wraps copies the original name onto the wrapper. This is a Python function decorator. The Gang-of-Four decorator is an object wrapper.
Iterators
from itertools import groupby
def gen(n):
yield from range(n)
assert list(gen(3)) == [0, 1, 2]
data = [1, 2, 1]
assert [k for k, _ in groupby(data)] == [1, 2, 1]
data = sorted(data)
groups = [(k, list(g)) for k, g in groupby(data)]
assert groups == [(1, [1, 1]), (2, [2])]itertools.groupby groups adjacent equal keys only. Sort first when the keys are scattered.
itertools also provides chain, islice, product, permutations, combinations, and accumulate.
Classes, dataclasses, exceptions
class Animal:
def __init__(self, name):
self.name = name
def speak(self):
raise NotImplementedError
class Dog(Animal):
def speak(self):
return "woof"
assert Dog("a").speak() == "woof"
from dataclasses import dataclass, field
@dataclass(frozen=True, order=True)
class Point:
x: int
y: int = 0
tags: list = field(default_factory=list)
assert Point(1) < Point(2)field(default_factory=list) gives each instance its own list. A bare tags: list = [] would be shared, and frozen=True rejects it.
def parse(text):
try:
return int(text)
except ValueError:
return None
assert parse("3") == 3 and parse("x") is Noneelse on try runs when no exception was raised. finally runs on the way out. raise New() from err chains the cause.
Files
from pathlib import Path
here = Path("notes.txt")
assert here.suffix == ".txt" and here.stem == "notes"Open text with encoding="utf-8". pathlib.Path.read_text and write_text cover the small cases. A with block closes the file.
Interview collections
from collections import Counter, defaultdict, deque
import heapq
import bisect
assert Counter("abca").most_common(1) == [("a", 2)]
graph = defaultdict(list)
graph["a"].append("b")
assert graph["missing"] == []
q = deque([1])
q.append(2)
assert q.popleft() == 1
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
assert heapq.heappop(heap) == 1
heapq.heappush(heap, -5)
assert -heapq.heappop(heap) == 5
ordered = [1, 3, 3, 7]
assert bisect.bisect_left(ordered, 3) == 1
assert bisect.bisect_right(ordered, 3) == 3heapq is a min-heap. Push the negated value for a max-heap. bisect_left is the first index where the value could sit. bisect_right is the index after every equal value.
Math
import math
assert divmod(7, 3) == (2, 1)
assert pow(2, 10, 1000) == 24
assert math.gcd(12, 18) == 6
assert math.lcm(4, 6) == 12
assert math.isclose(0.1 + 0.2, 0.3)
assert round(1.5) == 2 and round(2.5) == 2 # ties go to the even integer
assert math.inf > 10**18math.prod exists from 3.8. abs(a * b) // math.gcd(a, b) is the LCM on versions without math.lcm.
Identity
assert 1 == 1
sentinel = object()
assert (sentinel is sentinel) is Trueis compares identity. Use it for None and for sentinels. == compares values. CPython interns small ints, so is can look like equality there and then fail for larger ints. Compare values with ==.
Async
import asyncio
async def fetch(n):
return n
async def main():
return await asyncio.gather(fetch(1), fetch(2))
assert asyncio.run(main()) == [1, 2]async with and async for are the async forms of the context manager and the loop.
Typing
from typing import TypeVar
T = TypeVar("T")
def first(xs: list[T]) -> T:
return xs[0]
assert first([1, 2]) == 1
name: str | None = None
assert name is NoneOn 3.12 or newer the same function can be written def first[T](xs: list[T]) -> T. Protocol, TypedDict, Literal, and Final live in typing.
Standard library names
json, re, random, datetime, logging, subprocess, argparse, csv, sqlite3, unittest, and pytest are the ones that show up outside algorithm problems. re.search, re.findall, and re.sub cover most text work. json.loads / json.dumps cover most JSON. Prefer pathlib over hand-rolled paths.
Linked lists
The linked-list template is this node plus reverse and a dummy-head merge.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
def to_list(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
a = ListNode(1, ListNode(2, ListNode(3)))
assert to_list(reverse_list(a)) == [3, 2, 1]Walk with while cur. A dummy head keeps the merge loop from special-casing the first node. None is the empty list.
Trees
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4)))
assert max_depth(root) == 3Recursion on left and right is the DFS template. Level-order is a queue; snapshot len(q) for the current level.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order(root):
if not root:
return []
res, q = [], deque([root])
while q:
level = []
for _ in range(len(q)):
n = q.popleft()
level.append(n.val)
if n.left:
q.append(n.left)
if n.right:
q.append(n.right)
res.append(level)
return res
root = TreeNode(1, TreeNode(2), TreeNode(3))
assert level_order(root) == [[1], [2, 3]]Graphs
The graph-DFS template stores undirected edges as defaultdict(list). Grid flood fill is a stack (or queue) of (r, c) cells.
from collections import defaultdict
def count_components(n, edges):
adj = defaultdict(list)
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
visited = [False] * n
count = 0
def dfs(v):
visited[v] = True
for u in adj[v]:
if not visited[u]:
dfs(u)
for v in range(n):
if not visited[v]:
dfs(v)
count += 1
return count
assert count_components(4, [(0, 1), (2, 3)]) == 2def flood_fill(image, sr, sc, new_color):
orig = image[sr][sc]
if orig == new_color:
return image
rows, cols = len(image), len(image[0])
stack = [(sr, sc)]
while stack:
r, c = stack.pop()
if r < 0 or c < 0 or r >= rows or c >= cols or image[r][c] != orig:
continue
image[r][c] = new_color
stack.extend([(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)])
return image
assert flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) == [
[2, 2, 2],
[2, 2, 0],
[2, 0, 1],
]orig == new_color is the early return that stops an infinite rewrite of the same color.
Union-Find
Path compression plus union by rank. union returns whether the two nodes were in different components.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
self.components -= 1
return True
uf = UnionFind(4)
assert uf.union(0, 1) and uf.union(2, 3)
assert not uf.union(0, 1)
assert uf.components == 2Trie
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_word = True
def _walk(self, s):
node = self.root
for ch in s:
if ch not in node.children:
return None
node = node.children[ch]
return node
def search(self, word):
node = self._walk(word)
return bool(node and node.is_word)
def startsWith(self, prefix):
return self._walk(prefix) is not None
t = Trie()
t.insert("apple")
assert t.search("apple") and not t.search("app")
assert t.startsWith("app")search needs is_word. startsWith only needs the walk to survive.