Python interview cheat sheet

Lines ending in # -> show what Python 3.13 really returns: every block runs, and all 176 of those results are checked. The Postgres cards ran against PostgreSQL 17 with psycopg 3.2 and 3.3.

Approach

Which pattern?

Match the wording of the problem to a technique. Most problems are one of these.

Signal → technique

If the problem says / has…Reach forJump to
Find a pair / complement, seen-before, count, group by keyHash map, set, Counter, defaultdictBuilt-ins, Arrays
Sorted array, pair that sums to X, palindrome, in-placeTwo pointersArrays
Contiguous subarray / substring, “longest / shortest with condition”, “size k”Sliding window (the condition must move one way as the window grows; with negative numbers use prefix sums)Arrays
“Subarray sum equals k”, range sumsPrefix sum + hash mapArrays
Sorted input, or “minimum X such that condition holds”Binary search (on index or on the answer)Arrays
“Maximum of every window of size k”Monotonic dequeArrays
Matching brackets, undo, “most recent”StackArrays
Next greater / smaller element, histogram, temperaturesMonotonic stackArrays
Overlapping ranges, meetings, merge / insert intervalsSort by start, then scan (heap of end times for rooms)Arrays
Linked list: cycle, middle, kth from endFast & slow pointers, dummy headLinked lists
Tree: depth, path, validate, “return info up from children”Recursive DFSTrees
Tree “by level”, right side view, min depthBFS with deque, loop len(q) per levelTrees
Grid / graph, islands, connected components, flood fillDFS or BFS + visited setGraphs
Shortest path, unweighted / “minimum steps”BFS (multi-source if many starts)Graphs
Shortest path with non-negative weightsDijkstra (heap); negative weights need Bellman-FordGraphs
Prerequisites, dependencies, ordering, cycle in directed graphTopological sort (Kahn’s BFS)Graphs
Merge groups, redundant edge, cycle in undirected graphUnion-FindGraphs
Top K, Kth largest, K closest, merge K sorted, running medianHeap (heapq), size-k heap, two heapsHeaps
“Design a class that supports get / put / …”Hash map + the right second structureClasses & OOP
LRU cache, O(1) move-to-front or evictionDict + doubly linked listLRU Cache
“Support begin / commit / rollback”Dict + a stack of undo logsKey-value store
Prefix matching, autocomplete, word dictionaryTrieTrie
All subsets / permutations / combinationsBacktrackingBacktracking & DP
“Number of ways”, min cost, overlapping subproblemsDP (memoized recursion first)Backtracking & DP
Shared counter / dict / cache touched by several threadsthreading.Lock around every read-modify-writeConcurrency
Many network or DB calls at onceThreadPoolExecutor, or asyncio + semaphoreConcurrency
CPU-heavy work in parallelProcessPoolExecutor (sidesteps the GIL)Concurrency
Several workers pulling jobs from one Postgres tableFOR UPDATE SKIP LOCKEDPostgres

Input size → target complexity

n up toAim forUsually means
10–12O(n!)Permutations, brute force
20–25O(2ⁿ)Subsets, bitmasks, backtracking
~500O(n³)Triple loop, small DP
10³–5·10³O(n²)Double loop, 2-D DP (10⁸ steps is too slow in pure Python)
10⁵–10⁶O(n log n) or O(n)Sort, heap, two pointers, window, hash map
10⁹+O(log n), O(√n) or O(1)Binary search, math, a loop up to isqrt(n)

Interview flow, every problem

  1. Restate the problem and ask: input size, empty input, duplicates, negatives, sorted?
  2. Work a tiny example by hand, out loud.
  3. Say the brute force and its complexity, then name the pattern that beats it.
  4. Code with clear names; pull repeated logic into a helper.
  5. Test by walking your example through the code, then edge cases: empty, one item, all equal.
  6. State time and space complexity for each function.

Cost of the built-ins

Say these out loud when you state complexity. Dict and set costs are averages.

Operation costs

StructureFast: O(1)O(log n)Slow: O(n) or worse
lista[i], a[i] = x, append, pop(), len–x in a, pop(0), insert(0, x), remove(x), index(x), slice a[i:j] O(j − i) (copies), sort O(n log n)
dict / setget, set, in, del, add, discard–iterate; sorted(d) O(n log n)
dequeappend, appendleft, pop, popleft, q[0], q[-1]–q[i] in the middle, x in q
heapqh[0] (peek min)heappush, heappopheapify O(n), nlargest(k) O(n log k), removing an arbitrary item
bisect–bisect_left, bisect_rightinsort (O(log n) search, O(n) insert)
strs[i], len–s += c in a loop can be O(n²) (CPython often avoids it; don’t rely on that): build a list and "".join; sub in s, slicing, s[::-1]
Counterlookup, c[x] += 1–Counter(xs) O(n), most_common(k) O(n log k)

Python fluency

Imports

LeetCode pre-imports most of these. A plain editor or CoderPad does not, so paste this at the top.

The import block

from collections import defaultdict, Counter, deque, OrderedDict
from heapq import heappush, heappop, heapify, heappushpop, nlargest, nsmallest
from bisect import bisect_left, bisect_right, insort
from functools import cache, lru_cache, cmp_to_key, reduce
from itertools import accumulate, combinations, permutations, product, chain, groupby
from math import inf, gcd, isqrt, ceil, floor, sqrt
from typing import List, Optional, Dict, Tuple
from dataclasses import dataclass, field
from abc import ABC, abstractmethod
import math, sys
sys.setrecursionlimit(10**6)   # default is ~1000: deep DFS crashes without this

@cache needs Python 3.9+, itertools.pairwise and bisect(..., key=) need 3.10+. sortedcontainers.SortedList exists on LeetCode but usually not elsewhere.

In your own code, prefer the built-in generics (list[int], dict[str, int], 3.9+) and int | None (3.10+). Use typing.List and Optional only to match LeetCode’s stub signatures.

Data structures & built-ins

Core

The stuff people forget. Each line's # -> comment is the real result.

list & slicing

a = [5, 3, 8, 1]
a[-1]                  # -> 1
a[1:3]                 # -> [3, 8]       end index excluded
a[::-1]                # -> [1, 8, 3, 5]  reversed copy
a[::2]                 # -> [5, 8]
b = a[:]               # shallow copy
a.append(9); a.pop()   # pop() removes and returns the last item (9)
a.index(8)             # -> 2            raises ValueError if missing
a.count(3)             # -> 1
sum(a), max(a), min(a) # -> (17, 8, 1)
a.extend([4, 4])       # add many
a.remove(4)            # removes the FIRST 4 only
a                      # -> [5, 3, 8, 1, 4]
grid = [[0] * 3 for _ in range(2)]   # 2 rows x 3 cols, rows independent
grid                   # -> [[0, 0, 0], [0, 0, 0]]

str

s = "Hello, World"
s.lower()                   # -> 'hello, world'
s.split(", ")               # -> ['Hello', 'World']
"a b  c".split()            # -> ['a', 'b', 'c']  no arg = any whitespace
" ".join(["a", "b", "c"])   # -> 'a b c'
s.find("o")                 # -> 4  -1 if missing (.index raises)
s.replace("l", "L")         # -> 'HeLLo, WorLd'
"  hi ".strip()             # -> 'hi'
s.startswith("He")          # -> True
"a1".isalnum(), "a".isalpha(), "7".isdigit()  # -> (True, True, True)
ord("a"), chr(97)           # -> (97, 'a')
ord("c") - ord("a")         # -> 2  letter -> index 0..25
"".join(sorted("cab"))      # -> 'abc'  anagram key
s[::-1]                     # -> 'dlroW ,olleH'
f"{3.14159:.2f}"            # -> '3.14'
list("abc")                 # -> ['a', 'b', 'c']

Strings are immutable. Build a list of pieces, then "".join(pieces).

dict

d = {"a": 1}
d.get("z", 0)                    # -> 0  no KeyError
d.setdefault("b", []).append(5)  # create if missing, then use
d                                # -> {'a': 1, 'b': [5]}
"a" in d                         # -> True  checks KEYS
d.pop("a")                       # -> 1
for key, value in d.items():
    pass
scores = {"ana": 3, "bo": 9, "cy": 5}
max(scores, key=scores.get)      # -> 'bo'  key with the largest value
sorted(scores, key=scores.get)   # -> ['ana', 'cy', 'bo']
{v: k for k, v in scores.items()}  # -> {3: 'ana', 9: 'bo', 5: 'cy'}

defaultdict

groups = defaultdict(list)          # missing key -> []
for w in ["eat", "tea", "tan", "ate"]:
    groups["".join(sorted(w))].append(w)
dict(groups)        # -> {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}

count = defaultdict(int)            # missing key -> 0
for ch in "hello":
    count[ch] += 1
count["l"]          # -> 2

graph = defaultdict(list)           # adjacency list
neighbors = defaultdict(set)        # dedupes edges
best = defaultdict(lambda: inf)     # any default via lambda
best["x"]           # -> inf

Reading a missing key creates it. Use key in d if you only want to check.

Counter

c = Counter("banana")
c                     # -> Counter({'a': 3, 'n': 2, 'b': 1})
c["z"]                # -> 0  missing counts are 0
c.most_common(2)      # -> [('a', 3), ('n', 2)]
Counter("abc") == Counter("cab")   # -> True  anagram check
c - Counter("aan")    # -> Counter({'b': 1, 'a': 1, 'n': 1})  drops <= 0
c.total()             # -> 6  Python 3.10+
c["a"] -= 3
if c["a"] == 0:
    del c["a"]        # sliding windows: delete zero counts so len(c) is right
len(c)                # -> 2

set

s, t = {1, 2, 3}, {2, 3, 4}
s & t           # -> {2, 3}     intersection
s | t           # -> {1, 2, 3, 4}  union
s - t           # -> {1}        difference
s ^ t           # -> {1, 4}     in exactly one
s.add(5)
s.discard(99)   # no error if missing (s.remove raises KeyError)
seen = set()
seen.add((0, 1))        # tuples work as members; lists do not (unhashable)
len(set([1, 1, 2]))     # -> 2  dedupe

deque (queue / both ends)

q = deque([1, 2, 3])
q.append(4)         # right end
q.appendleft(0)     # left end
q.popleft()         # -> 0  O(1); list.pop(0) is O(n)
q.pop()             # -> 4
q[0], q[-1]         # -> (1, 3)  peek both ends
last3 = deque(maxlen=3)
for x in range(5):
    last3.append(x) # old items fall off the left
last3               # -> deque([2, 3, 4], maxlen=3)

Use for BFS (append + popleft) and sliding-window max/min.

heapq (priority queue)

h = [5, 1, 8, 3]
heapify(h)              # O(n), in place, MIN-heap
h[0]                    # -> 1  peek smallest
heappush(h, 0)
heappop(h)              # -> 0
# max-heap: push negatives
mx = []
for x in [5, 9, 2]:
    heappush(mx, -x)
-heappop(mx)            # -> 9
# (priority, item) tuples sort by priority first
tasks = []
heappush(tasks, (2, "write"))
heappush(tasks, (1, "read"))
heappop(tasks)          # -> (1, 'read')
nlargest(2, [4, 1, 7, 3])                   # -> [7, 4]
nsmallest(1, ["bbb", "a", "cc"], key=len)   # -> ['a']

Ties on priority compare the next tuple field. If that field can’t be compared (e.g. a node object), insert a counter: (priority, i, node).

bisect (binary search on a sorted list)

a = [1, 3, 3, 5]
bisect_left(a, 3)     # -> 1  first index with a[i] >= 3
bisect_right(a, 3)    # -> 3  first index with a[i] > 3
bisect_right(a, 3) - bisect_left(a, 3)   # -> 2  how many 3s
bisect_left(a, 4)     # -> 3  where 4 would go
insort(a, 4)          # insert keeping sorted (O(n) shift)
a                     # -> [1, 3, 3, 4, 5]
# "largest value <= x": index bisect_right(a, x) - 1
a[bisect_right(a, 2) - 1]   # -> 1

Sorting, lambda & idioms

Core

Sorting with key and lambda

nums = [3, -1, 2]
sorted(nums)                  # -> [-1, 2, 3]  returns NEW list
nums.sort(reverse=True)       # in place, returns None
nums                          # -> [3, 2, -1]
sorted(nums, key=abs)         # -> [-1, 2, 3]
people = [("bo", 25), ("al", 30), ("cy", 25)]
sorted(people, key=lambda p: p[1])         # -> [('bo', 25), ('cy', 25), ('al', 30)]
sorted(people, key=lambda p: (-p[1], p[0]))  # -> [('al', 30), ('bo', 25), ('cy', 25)]
sorted(["bb", "a", "ccc"], key=len)        # -> ['a', 'bb', 'ccc']
intervals = [[5, 6], [1, 3]]
intervals.sort(key=lambda iv: iv[0])       # sort by start
square = lambda x: x * x                   # lambda = tiny unnamed function
square(4)                                  # -> 16

Sorting is stable: equal keys keep their order. Descending on one field, ascending on another: negate the numeric field.

Custom comparator (rare)

def compare(a, b):            # negative: a first, positive: b first
    return -1 if a + b > b + a else 1

sorted(["9", "30", "34"], key=cmp_to_key(compare))   # -> ['9', '34', '30']
"".join(sorted(["3", "30", "34", "5", "9"], key=cmp_to_key(compare)))  # -> '9534330'

Largest Number. Only reach for this when a key function can’t express the order.

Loops: enumerate, zip, range

for i, ch in enumerate("abc"):        # index + value
    pass
for i, ch in enumerate("abc", start=1):
    pass
for x, y in zip([1, 2, 3], "ab"):     # stops at the shorter one
    pass
list(zip([1, 2], [3, 4]))             # -> [(1, 3), (2, 4)]
list(zip(*[[1, 2], [3, 4]]))          # -> [(1, 3), (2, 4)]  transpose a matrix
list(range(5, -1, -2))                # -> [5, 3, 1]
list(range(3, -1, -1))                # -> [3, 2, 1, 0]  count DOWN to 0 inclusive
list(reversed([1, 2, 3]))             # -> [3, 2, 1]
any(x > 2 for x in [1, 3])            # -> True
all(x > 0 for x in [1, -3])           # -> False

Comprehensions & unpacking

[x * x for x in range(5) if x % 2 == 0]   # -> [0, 4, 16]
{x: x * x for x in range(3)}              # -> {0: 0, 1: 1, 2: 4}
{ch for ch in "hello"} == set("helo")     # -> True
[[r * 3 + c for c in range(3)] for r in range(2)]  # -> [[0, 1, 2], [3, 4, 5]]
flat = [x for row in [[1, 2], [3]] for x in row]
flat                                      # -> [1, 2, 3]
a, b = 1, 2
a, b = b, a                               # swap, no temp
a, b                                      # -> (2, 1)
first, *rest = [1, 2, 3]
rest                                      # -> [2, 3]
list(map(int, "1 2 3".split()))           # -> [1, 2, 3]
x = 7
"odd" if x % 2 else "even"                # -> 'odd'  ternary

itertools & functools

list(accumulate([1, 2, 3, 4]))            # -> [1, 3, 6, 10]  running sum
list(accumulate([3, 1, 4], max))          # -> [3, 3, 4]  running max
list(combinations([1, 2, 3], 2))          # -> [(1, 2), (1, 3), (2, 3)]
len(list(permutations([1, 2, 3])))        # -> 6
list(product("ab", repeat=2))             # -> [('a', 'a'), ('a', 'b'), ('b', 'a'), ('b', 'b')]
list(chain([1], [2, 3]))                  # -> [1, 2, 3]
[(k, len(list(g))) for k, g in groupby("aaabcc")]  # -> [('a', 3), ('b', 1), ('c', 2)]
reduce(lambda acc, x: acc * x, [1, 2, 3, 4])      # -> 24

@cache                         # memoize: each n computed once
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
fib(80)                        # -> 23416728348467685

@cache arguments must be hashable: pass tuples, not lists.

Numbers

7 // 2, -7 // 2       # -> (3, -4)  // floors toward -infinity
int(-7 / 2)           # -> -3  truncate toward zero
-7 % 3                # -> 2   result takes the divisor's sign
divmod(17, 5)         # -> (3, 2)
(7 + 3 - 1) // 3      # -> 3   ceil(7 / 3) with integers
ceil(7 / 3)           # -> 3
2 ** 100 > 10 ** 30   # -> True  ints never overflow
pow(2, 10, 1000)      # -> 24  (2^10) % 1000, fast
MOD = 10**9 + 7
isqrt(17), gcd(12, 18)   # -> (4, 6)
best = inf            # running minimum starts at infinity
min(best, 5)          # -> 5
0.1 + 0.2 == 0.3      # -> False  use math.isclose
math.isclose(0.1 + 0.2, 0.3)   # -> True

Bits

bin(5)                # -> '0b101'
bin(5).count("1")     # -> 2   set bits (or (5).bit_count() in 3.10+)
5 & 1                 # -> 1   odd check
6 >> 1, 3 << 2        # -> (3, 12)  divide / multiply by powers of 2
5 ^ 5                 # -> 0   x ^ x = 0
reduce(lambda a, b: a ^ b, [4, 1, 2, 1, 2])   # -> 4  pairs cancel
n = 12
n & (n - 1)           # -> 8   drops the lowest set bit

Python traps

Core

Bugs that cost people interviews. Each one runs as shown.

Mutable defaults & aliasing

def add_bad(item, items=[]):         # the [] is created ONCE and shared
    items.append(item)
    return items
add_bad(1)
add_bad(2)                           # -> [1, 2]  surprise

def add_good(item, items=None):
    if items is None:
        items = []
    items.append(item)
    return items
add_good(1)
add_good(2)                          # -> [2]

bad = [[0] * 2] * 2                  # both rows are ONE list
bad[0][0] = 9
bad                                  # -> [[9, 0], [9, 0]]
good = [[0] * 2 for _ in range(2)]
good[0][0] = 9
good                                 # -> [[9, 0], [0, 0]]

Return values & truthiness

nums = [3, 1, 2]
result = nums.sort()                 # sorts in place...
result                               # -> None  ...and returns None
fallback = 0 or 5                    # -> 5     0, "", [], None are falsy
count = {}
count.get("x") or 0                  # -> 0
x = 0
if x is not None:                    # check None explicitly when 0 is valid
    pass
a, b = [1, 2], [1, 2]
a == b, a is b                       # -> (True, False)  is = same object

Loops that change what they loop over

d = {"a": 0, "b": 1, "c": 0}
for k in list(d):                    # copy the keys first
    if d[k] == 0:
        del d[k]                     # deleting while iterating d itself raises
d                                    # -> {'b': 1}

nums = [1, 2, 2, 3]
nums = [x for x in nums if x != 2]   # build a new list instead of remove()
nums                                 # -> [1, 3]

Scope & copies

def counter():
    total = 0
    def bump():
        nonlocal total               # without it: UnboundLocalError
        total += 1
    bump(); bump()
    return total
counter()                            # -> 2

def collect():
    seen = []                        # mutating (append) needs no nonlocal
    def visit(v):
        seen.append(v)
    visit(1)
    return seen
collect()                            # -> [1]

import copy
grid = [[1, 2], [3, 4]]
shallow = grid[:]                    # new outer list, SAME inner lists
deep = copy.deepcopy(grid)           # fully independent
grid[0][0] = 99
shallow[0][0], deep[0][0]            # -> (99, 1)

Quick list of the rest

  • range(n) stops at n - 1. Count down to 0 with range(n - 1, -1, -1).
  • Recursion depth defaults to about 1,000. A 10⁴-node skewed tree or long path crashes: raise the limit or go iterative.
  • int(a / b) truncates toward zero but goes through a float, so it is wrong past 2⁵³. Exact: q = abs(a) // abs(b), then negate q if the signs differ.
  • Lists can’t be dict keys or set members. Convert with tuple(lst).
  • Heaps are min-heaps only. Negate values for a max-heap.
  • BFS: mark nodes visited when you add them to the queue, or they get added many times.
  • Backtracking: append path[:] (a copy), not path.

Decorators, context managers, generators

Senior

The everyday tools a senior backend engineer is expected to write without looking up.

Retry decorator with exponential backoff

import time
from functools import wraps

def retry(times=3, base_delay=0.01, exceptions=(Exception,)):
    def decorator(fn):
        @wraps(fn)                          # keep fn's __name__ and docstring
        def wrapper(*args, **kwargs):
            for attempt in range(times):
                try:
                    return fn(*args, **kwargs)
                except exceptions:
                    if attempt == times - 1:
                        raise               # out of attempts: re-raise the original
                    time.sleep(base_delay * 2 ** attempt)   # 0.01, 0.02, 0.04 ...
        return wrapper
    return decorator

attempts = []

@retry(times=3, exceptions=(ConnectionError,))
def connect_to_agent():
    attempts.append(1)
    if len(attempts) < 3:
        raise ConnectionError("transient")
    return "connected"

connect_to_agent()                          # -> 'connected'  on the 3rd try
len(attempts)                               # -> 3
connect_to_agent.__name__                   # -> 'connect_to_agent'

Production version: add random jitter to the delay so many clients don’t retry in lockstep, and only retry errors that are safe to repeat.

Context managers

import time
from contextlib import contextmanager

@contextmanager
def timed(label, log):
    start = time.perf_counter()
    try:
        yield                               # the body of the with-block runs here
    finally:                                # runs even if the body raises
        log.append((label, round(time.perf_counter() - start, 1)))

log = []
with timed("scan", log):
    time.sleep(0.01)
log                                         # -> [('scan', 0.0)]

class Resource:                             # the class form: __enter__ / __exit__
    def __enter__(self):
        self.open = True
        return self
    def __exit__(self, exc_type, exc, tb):
        self.open = False
        return False                        # False: don't swallow exceptions

with Resource() as r:
    r.open                                  # inside the block it's open
r.open                                      # -> False

Generators: stream instead of loading everything

def batches(items, size):
    batch = []
    for item in items:
        batch.append(item)
        if len(batch) == size:
            yield batch                     # hand back one batch, pause here
            batch = []
    if batch:
        yield batch

list(batches(range(7), 3))                  # -> [[0, 1, 2], [3, 4, 5], [6]]

squares = (x * x for x in range(10**12))    # generator expression: lazy, O(1) memory
next(squares), next(squares)                # -> (0, 1)

def read_lines(path):                       # works on files bigger than RAM
    with open(path) as f:
        for line in f:
            yield line.rstrip("\n")

Pair with cur.fetchmany(n) or a server-side cursor (conn.cursor(name="big")) to stream large query results.

Object-oriented design

Classes & OOP

Horizon3 round

Horizon3’s reported coding round is OOP-style: build a class with state and several methods. Know this syntax cold.

How to run a design / OOP round

  1. List every operation with inputs, outputs and the speed it needs (“get must be O(1)”).
  2. Ask about edge cases: missing key, duplicates, capacity 0, invalid input: raise, or return a sentinel?
  3. Pick one structure per need: dict for O(1) lookup, heap for min/max, deque for FIFO, sorted list + bisect for “latest at or before t”, dict + linked list for O(1) reordering.
  4. Write the skeleton first: __init__ state and method signatures, no logic yet.
  5. Fill one method at a time and say the invariant (“the map and the list always hold the same keys”).
  6. Walk an example through by hand, then the edge cases.
  7. State each method’s complexity and mention extensions: thread safety, persistence, expiry.

Class basics

class BankAccount:
    bank_name = "Acme"                 # class attribute: shared by all

    def __init__(self, owner: str, balance: int = 0):
        self.owner = owner             # instance attributes
        self._balance = balance        # leading _ = internal, by convention
        self.history = []              # mutable state: create it HERE

    def deposit(self, amount: int) -> None:
        if amount <= 0:
            raise ValueError("amount must be positive")
        self._balance += amount
        self.history.append(("deposit", amount))

    @property
    def balance(self) -> int:          # read like an attribute
        return self._balance

    def __repr__(self) -> str:         # shown by print() and the REPL
        return f"BankAccount({self.owner!r}, {self._balance})"

acct = BankAccount("ana")
acct.deposit(50)
acct.balance          # -> 50   no parentheses: it's a property
acct                  # -> BankAccount('ana', 50)

Inheritance & abstract base class

class Shape(ABC):
    @abstractmethod
    def area(self) -> float: ...        # subclasses must implement

    def describe(self) -> str:          # shared behaviour
        return f"{type(self).__name__} with area {self.area()}"

class Rect(Shape):
    def __init__(self, w, h):
        self.w, self.h = w, h
    def area(self):
        return self.w * self.h

class Square(Rect):
    def __init__(self, side):
        super().__init__(side, side)    # call the parent constructor

Square(3).area()                  # -> 9
Square(3).describe()              # -> 'Square with area 9'
isinstance(Square(3), Shape)      # -> True

@dataclass: less typing

@dataclass
class Point:
    x: int
    y: int = 0                    # default value

p = Point(1, 2)
p                                 # -> Point(x=1, y=2)  __repr__ for free
p == Point(1, 2)                  # -> True  __eq__ for free

@dataclass(order=True, frozen=True)   # order: < works; frozen: hashable
class Version:
    major: int
    minor: int

sorted([Version(1, 2), Version(1, 0)])[0]   # -> Version(major=1, minor=0)
{Version(1, 0): "ok"}[Version(1, 0)]        # -> 'ok'  usable as a dict key

@dataclass
class Team:
    members: list = field(default_factory=list)   # never `members: list = []`

Team().members                    # -> []

Dunder methods & heap ordering

class Task:
    def __init__(self, priority, name):
        self.priority, self.name = priority, name

    def __lt__(self, other):          # makes heapq / sorted work on Tasks
        return self.priority < other.priority

    def __eq__(self, other):
        if not isinstance(other, Task):
            return NotImplemented     # let Python try the other side, then fall back to `is`
        return (self.priority, self.name) == (other.priority, other.name)

    def __hash__(self):               # define WITH __eq__ to use in sets / dict keys
        return hash((self.priority, self.name))

h = []
heappush(h, Task(3, "deploy"))
heappush(h, Task(1, "test"))
heappop(h).name                  # -> 'test'
len({Task(1, "a"), Task(1, "a")})  # -> 1
Task(1, "a") == 5                # -> False

Easier alternative: push tuples like (priority, counter, task) and skip __lt__.

Dunder cheat list

MethodMakes this work
__init__(self, …)Thing(…)
__repr__ / __str__debug display / print(x)
__eq__ + __hash__==, set members, dict keys
__lt__<, sorted, heapq
__len__len(x), truthiness
__contains__item in x
__iter__for item in x
__getitem__x[i], x[key]

@classmethod & @staticmethod

class Temperature:
    def __init__(self, celsius):
        self.celsius = celsius

    @classmethod
    def from_fahrenheit(cls, f):      # alternate constructor: gets the class
        return cls((f - 32) * 5 / 9)

    @staticmethod
    def is_valid(celsius):            # plain helper: no self, no cls
        return celsius >= -273.15

Temperature.from_fahrenheit(212).celsius   # -> 100.0
Temperature.is_valid(-300)                 # -> False

Node classes (LeetCode definitions)

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

class Node:                              # graph node (Clone Graph)
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

root = TreeNode(2, TreeNode(1), TreeNode(3))
root.left.val                            # -> 1

LRU Cache: OrderedDict version

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()              # remembers order

    def get(self, key: int) -> int:             # O(1)
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)             # now most recent
        return self.cache[key]

    def put(self, key: int, value: int) -> None:   # O(1)
        self.cache[key] = value
        self.cache.move_to_end(key)
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)      # evict least recent (front)

Interviewers often say “now do it without OrderedDict”. That’s the next card.

LRU Cache: hash map + doubly linked list

class DNode:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCacheManual:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                              # key -> DNode
        self.head, self.tail = DNode(), DNode()    # sentinels, never removed
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):                    # front = most recent
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = DNode(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev                   # back = least recent
            self._remove(lru)
            del self.map[lru.key]                  # why DNode stores key

Design Underground System

class UndergroundSystem:
    def __init__(self):
        self.active = {}                            # id -> (station, time)
        self.trips = defaultdict(lambda: [0, 0])    # (start, end) -> [total, count]

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.active[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start, t0 = self.active.pop(id)
        stats = self.trips[(start, stationName)]
        stats[0] += t - t0
        stats[1] += 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        total, count = self.trips[(startStation, endStation)]
        return total / count

Store running totals, not every trip, so the average is O(1).

Time Based Key-Value Store

class TimeMap:
    def __init__(self):
        self.times = defaultdict(list)     # key -> timestamps (increasing)
        self.values = defaultdict(list)    # key -> values, same positions

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        times = self.times.get(key, [])     # .get: don't create an entry on a miss
        i = bisect_right(times, timestamp)  # first time > timestamp
        return self.values[key][i - 1] if i else ""

Key-value store with nested transactions

class TxnKV:
    _MISSING = object()                    # "key was absent", distinct from None

    def __init__(self):
        self.data = {}
        self.undo = []                     # one {key: old value} per open transaction

    def get(self, key):
        return self.data.get(key)

    def set(self, key, value):
        self._remember(key)
        self.data[key] = value

    def delete(self, key):
        self._remember(key)
        self.data.pop(key, None)

    def _remember(self, key):              # the first write in a transaction saves the old value
        if self.undo and key not in self.undo[-1]:
            self.undo[-1][key] = self.data.get(key, self._MISSING)

    def begin(self):
        self.undo.append({})

    def rollback(self):
        if not self.undo:
            raise RuntimeError("no transaction")
        for key, old in self.undo.pop().items():
            if old is self._MISSING:
                self.data.pop(key, None)
            else:
                self.data[key] = old

    def commit(self):                      # fold this level's undo log into its parent
        if not self.undo:
            raise RuntimeError("no transaction")
        top = self.undo.pop()
        if self.undo:
            for key, old in top.items():
                self.undo[-1].setdefault(key, old)

kv = TxnKV()
kv.set("a", 1)
kv.begin()
kv.set("a", 2)
kv.begin()
kv.delete("a")
kv.rollback()
kv.get("a")                                # -> 2
kv.rollback()
kv.get("a")                                # -> 1

Invariant to say out loud: undoing every log on the stack, top first, gives back the data as it was before the first begin. Writes cost O(1); a rollback costs O(keys written in that transaction).

Enums, exceptions, iterators

from enum import Enum

class Status(Enum):
    QUEUED = "queued"
    RUNNING = "running"
    DONE = "done"

Status("running")                       # -> <Status.RUNNING: 'running'>
Status.DONE.value                       # -> 'done'

class StoreError(Exception):            # one base class callers can catch
    pass

class KeyMissing(StoreError, KeyError):  # still a KeyError to code that expects one
    pass

issubclass(KeyMissing, KeyError)        # -> True

class Countdown:
    def __init__(self, start):
        self.start = start

    def __iter__(self):                 # a generator: every for-loop gets a fresh iterator
        n = self.start
        while n > 0:
            yield n
            n -= 1

list(Countdown(3))                      # -> [3, 2, 1]

@dataclass(slots=True) (3.10+) uses less memory and rejects misspelled attributes.

Test your class

import pytest

@pytest.fixture
def kv():
    return TxnKV()                      # a fresh object for every test

def test_rollback_restores_old_value(kv):
    kv.set("a", 1)
    kv.begin()
    kv.set("a", 2)
    kv.rollback()
    assert kv.get("a") == 1

def test_rollback_without_begin_raises(kv):
    with pytest.raises(RuntimeError, match="no transaction"):
        kv.rollback()

@pytest.mark.parametrize("key, value", [("a", 1), ("", None), ("k", [1, 2])])
def test_set_then_get(kv, key, value):
    kv.set(key, value)
    assert kv.get(key) == value

Time-dependent code: take the clock as a parameter (def __init__(self, clock=time.monotonic)) and pass a fake in tests, or patch it where it is looked up: unittest.mock.patch("store.time.monotonic", return_value=100.0).

Senior backend

Concurrency & async

Senior

Senior Python rounds probe this: when to use threads, processes or asyncio, and how to make shared state safe. The cards share the imports at the top of the first one.

Pick the tool

WorkloadUseWhy
Waiting on network / DB / disk (I/O-bound), tens to hundreds at once, blocking librariesThreadPoolExecutorThreads release the GIL while they wait on I/O. Works with sync libraries such as sync psycopg or requests.
Thousands of concurrent I/O tasks, async libraries availableasyncioOne thread, cooperative switching at each await; tasks are cheap. Needs async drivers (e.g. psycopg AsyncConnection).
CPU-bound Python (parsing, hashing, number crunching)ProcessPoolExecutor / multiprocessingSeparate processes, each with its own GIL: real parallelism. Arguments and results must be picklable.
A blocking call inside async codeawait asyncio.to_thread(fn, ...)Keeps the event loop responsive.

The GIL lets only one thread run Python bytecode at a time in default CPython (3.13 added an experimental free-threaded build; 3.14 supports it officially, but it is still a separate, opt-in build, python3.14t). The GIL does not make your code thread-safe: count += 1 is read, add, write, and threads can interleave between those steps.

Lock: protect read-modify-write

import threading, asyncio, time, queue, itertools
from concurrent.futures import ThreadPoolExecutor, as_completed

class SafeCounter:          # don't call it Counter: that shadows collections.Counter
    def __init__(self):
        self.value = 0
        self._lock = threading.Lock()

    def increment(self):
        with self._lock:              # acquire; released even if an exception happens
            self.value += 1           # read-modify-write: NOT atomic without the lock

counter = SafeCounter()

def work():
    for _ in range(10_000):
        counter.increment()

threads = [threading.Thread(target=work) for _ in range(8)]
for t in threads:
    t.start()
for t in threads:
    t.join()                          # wait for every thread to finish
counter.value                         # -> 80000

Check-then-act is the same bug in disguise: if key not in cache: cache[key] = load() needs the lock around both steps.

Two locks without deadlock

class Account:
    _ids = itertools.count()

    def __init__(self, balance):
        self.id = next(Account._ids)
        self.balance = balance
        self.lock = threading.Lock()

def transfer(src, dst, amount):
    if src is dst:                    # sorted([a, a]) would take one Lock twice: deadlock
        raise ValueError("cannot transfer to the same account")
    # Always take locks in one global order (by id). Thread A doing a->b and
    # thread B doing b->a would otherwise each hold one lock and wait forever.
    first, second = sorted([src, dst], key=lambda acct: acct.id)
    with first.lock, second.lock:
        if src.balance < amount:      # check AND act under the same locks
            raise ValueError("insufficient funds")
        src.balance -= amount
        dst.balance += amount

Other deadlock answers: hold one lock at a time, or use lock.acquire(timeout=1) and back off.

RLock, Semaphore, Event

rlock = threading.RLock()       # the SAME thread may acquire it again
with rlock:
    with rlock:                 # a plain Lock would deadlock here
        pass

db_slots = threading.Semaphore(5)   # at most 5 threads inside at once
with db_slots:
    pass                        # e.g. cap concurrent requests to a fragile host

shutdown = threading.Event()    # a one-way flag shared between threads
shutdown.is_set()               # -> False
shutdown.set()
shutdown.wait(timeout=1)        # -> True  returns at once when set

Condition: Design Bounded Blocking Queue

class BoundedBlockingQueue:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.items = deque()
        self.cond = threading.Condition()     # a lock + wait/notify

    def enqueue(self, item) -> None:
        with self.cond:
            while len(self.items) >= self.capacity:   # WHILE, not if: re-check after waking
                self.cond.wait()                      # releases the lock while asleep
            self.items.append(item)
            self.cond.notify_all()                    # wake waiting consumers

    def dequeue(self):
        with self.cond:
            while not self.items:
                self.cond.wait()
            item = self.items.popleft()
            self.cond.notify_all()                    # wake waiting producers
            return item

    def size(self) -> int:
        with self.cond:
            return len(self.items)

LeetCode 1188. In production code, queue.Queue(maxsize=n) already does this.

Producer-consumer with queue.Queue

def run_workers(jobs, num_workers=4):
    q = queue.Queue()                  # thread-safe FIFO
    results, results_lock = [], threading.Lock()

    def worker():
        while True:
            job = q.get()
            if job is None:            # sentinel: stop
                q.task_done()
                return
            out = job * job            # the real work goes here
            with results_lock:
                results.append(out)
            q.task_done()

    threads = [threading.Thread(target=worker) for _ in range(num_workers)]
    for t in threads:
        t.start()
    for job in jobs:
        q.put(job)
    for _ in threads:
        q.put(None)                    # one sentinel per worker
    q.join()                           # blocks until every item got task_done()
    return sorted(results)

run_workers(range(5))                  # -> [0, 1, 4, 9, 16]

ThreadPoolExecutor: map, submit, errors

def fetch(n):                          # stand-in for an HTTP or DB call
    time.sleep(0.05)
    if n == 3:
        raise ValueError("bad host")
    return n * 10

with ThreadPoolExecutor(max_workers=8) as pool:
    results = list(pool.map(fetch, [1, 2]))   # input order; raises the first error
results                                        # -> [10, 20]

with ThreadPoolExecutor(max_workers=8) as pool:
    futures = {pool.submit(fetch, n): n for n in [1, 2, 3]}
    ok, failed = {}, {}
    for fut in as_completed(futures):          # in order of COMPLETION
        n = futures[fut]
        try:
            ok[n] = fut.result()               # a worker's exception is re-raised here
        except ValueError as e:
            failed[n] = str(e)
ok, failed                                     # -> ({1: 10, 2: 20}, {3: 'bad host'})

Leaving the with block waits for all submitted work (shutdown(wait=True)).

ProcessPoolExecutor: CPU-bound work

from concurrent.futures import ProcessPoolExecutor

def crunch(n):                          # top-level function: must be picklable
    return sum(i * i for i in range(n))

if __name__ == "__main__":              # required with spawn (macOS, Windows; Linux from 3.14)
    with ProcessPoolExecutor() as pool:
        print(list(pool.map(crunch, [10**6] * 4)))

Lambdas and nested functions can’t be pickled, so they fail here. Each process has its own memory: share results by returning them.

asyncio basics: gather

async def fetch_async(n):
    await asyncio.sleep(0.05)          # await = pause here and let other tasks run
    return n * 10

async def main():
    # run all five concurrently; results come back in INPUT order
    return await asyncio.gather(*(fetch_async(n) for n in range(5)))

asyncio.run(main())                    # -> [0, 10, 20, 30, 40]  about 0.05s, not 0.25s

fetch_async(1) without await only creates a coroutine object; nothing runs.

asyncio: limit concurrency, timeouts, failures

async def fetch_all(items, limit=10):
    sem = asyncio.Semaphore(limit)      # at most `limit` requests in flight

    async def one(item):
        async with sem:
            return await fetch_async(item)

    # return_exceptions=True: one failure becomes a value instead of raising
    return await asyncio.gather(*(one(i) for i in items), return_exceptions=True)

async def with_timeout():
    try:
        async with asyncio.timeout(0.01):    # 3.11+; older: wait_for + asyncio.TimeoutError
            await asyncio.sleep(1)
    except TimeoutError:
        return "timed out"

asyncio.run(fetch_all(range(3)))        # -> [0, 10, 20]
asyncio.run(with_timeout())             # -> 'timed out'

TaskGroup, create_task, to_thread

async def structured():
    async with asyncio.TaskGroup() as tg:      # 3.11+: waits for all; one failure cancels the rest
        t1 = tg.create_task(fetch_async(1))
        t2 = tg.create_task(fetch_async(2))
    return t1.result() + t2.result()

def blocking_call():
    time.sleep(0.05)                            # e.g. a sync psycopg query
    return "done"

async def offload():
    return await asyncio.to_thread(blocking_call)   # runs in a thread; loop stays free

async def boom():
    raise ValueError("bad host")

async def failures():
    errors = []
    try:
        async with asyncio.TaskGroup() as tg:
            tg.create_task(asyncio.sleep(10))       # cancelled when boom() fails
            tg.create_task(boom())
    except* ValueError as group:                # errors arrive as an ExceptionGroup
        errors = [str(e) for e in group.exceptions]  # no `return` inside except*
    return errors

asyncio.run(structured())                       # -> 30
asyncio.run(offload())                          # -> 'done'
asyncio.run(failures())                         # -> ['bad host']

asyncio.Queue worker pool

async def worker_pool(jobs, n_workers=3):
    q = asyncio.Queue()
    for job in jobs:
        q.put_nowait(job)
    results = []

    async def worker():
        while True:
            job = await q.get()
            try:
                results.append(await fetch_async(job))
            finally:
                q.task_done()               # always, even if the job failed

    workers = [asyncio.create_task(worker()) for _ in range(n_workers)]
    await q.join()                          # until every job is task_done()
    for w in workers:
        w.cancel()                          # workers loop forever: stop them
    await asyncio.gather(*workers, return_exceptions=True)
    return sorted(results)

asyncio.run(worker_pool(range(6)))          # -> [0, 10, 20, 30, 40, 50]

Keep a reference to every task from create_task (or use a TaskGroup); an unreferenced task can be garbage-collected before it finishes.

Thread-safe rate limiter (token bucket)

class TokenBucket:
    """`rate` requests per second on average, bursts up to `capacity`."""

    def __init__(self, rate: float, capacity: int):
        self.rate = rate
        self.capacity = capacity
        self.tokens = capacity
        self.last = time.monotonic()        # monotonic: never jumps when the clock changes
        self.lock = threading.Lock()

    def allow(self) -> bool:
        with self.lock:                     # refill, check and take must be one atomic step
            now = time.monotonic()
            self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
            self.last = now
            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False

bucket = TokenBucket(rate=1, capacity=3)
[bucket.allow() for _ in range(4)]          # -> [True, True, True, False]

Per-client limits: a dict of buckets, with a lock around creating a missing bucket. Across many servers the state moves to Redis or Postgres.

Concurrency bugs interviewers look for

  • “The GIL makes it safe.” It doesn’t: x += 1 and check-then-act both need a lock.
  • Deadlock: two locks taken in different orders. Fix with one global order, or acquire with a timeout.
  • Slow work under a lock serialises every thread. Copy what you need, release, then do the I/O.
  • Condition.wait() in if instead of while: another thread can take the item first.
  • Blocking the event loop: time.sleep, requests or sync DB calls inside async def. Use await asyncio.sleep, async drivers, or asyncio.to_thread.
  • Forgetting await: the coroutine never runs (“coroutine was never awaited”).
  • State changing across an await: read, await, write is a race in asyncio too. Use asyncio.Lock, not threading.Lock.
  • Unbounded fan-out: 10,000 tasks hitting one host or DB at once. Cap with a semaphore or pool size.
  • Sharing one DB connection across threads for throughput: its queries run one at a time. Give each worker its own connection from a pool.

Postgres with psycopg 3

Senior

import psycopg is version 3; psycopg2 is the older driver, still common. The psycopg2 differences are in the last card. Every card here ran against PostgreSQL 17 with psycopg 3.2 and 3.3; conn, cur and inputs such as email are assumed.

Connect, query, fetch

import psycopg
from psycopg.rows import dict_row

DSN = "postgresql://app:secret@localhost:5432/nodezero"   # or "dbname=nodezero user=app"

with psycopg.connect(DSN) as conn:          # block end: COMMIT (ROLLBACK on error), then CLOSE
    with conn.cursor() as cur:
        cur.execute("SELECT id, ip FROM hosts WHERE subnet = %s", ("10.0.0.0/24",))
        first = cur.fetchone()              # a tuple, or None when there are no rows
        rest = cur.fetchall()               # list of tuples (fetchmany(n) for batches)

        cur.execute("SELECT id, ip FROM hosts")
        for host_id, ip in cur:             # iterate rows directly
            pass

    # shortcut: conn.execute() creates the cursor for you
    total = conn.execute("SELECT count(*) FROM hosts").fetchone()[0]

    # rows as dicts: {'id': 1, 'ip': IPv4Address('10.0.0.5')} from an inet column
    with conn.cursor(row_factory=dict_row) as cur:
        host = cur.execute("SELECT id, ip FROM hosts LIMIT 1").fetchone()

Parameters: never build SQL with f-strings

# WRONG: SQL injection, and quotes in the value break the query
cur.execute(f"SELECT * FROM users WHERE email = '{email}'")

# RIGHT: %s placeholders; psycopg 3 sends values separately from the SQL
cur.execute("SELECT * FROM users WHERE email = %s", (email,))   # (x,) is a 1-tuple
cur.execute(
    "SELECT * FROM users WHERE email = %(email)s AND org_id = %(org)s",
    {"email": email, "org": org_id},
)
cur.execute("SELECT * FROM hosts WHERE id = ANY(%s)", (host_ids,))  # list -> array; not IN %s
cur.execute("SELECT * FROM hosts WHERE name ILIKE %s", (f"%{term}%",))  # wildcards in the VALUE

# Table / column names can't be parameters: compose them with psycopg.sql
from psycopg import sql
query = sql.SQL("SELECT {col} FROM {table} WHERE id = %s").format(
    col=sql.Identifier(column_name),
    table=sql.Identifier(table_name),
)
cur.execute(query, (row_id,))

Transactions

with psycopg.connect(DSN) as conn:
    with conn.transaction():              # atomic: both updates or neither
        conn.execute("UPDATE accounts SET balance = balance - %s WHERE id = %s", (100, src))
        conn.execute("UPDATE accounts SET balance = balance + %s WHERE id = %s", (100, dst))
    # an exception inside the block rolls it back; a nested transaction() is a SAVEPOINT

# Long-running services: autocommit, plus explicit transaction() blocks where needed
conn = psycopg.connect(DSN, autocommit=True)   # each statement commits on its own
with conn.transaction():
    conn.execute("INSERT INTO scans (target) VALUES (%s)", (target,))

# Without autocommit, even a plain SELECT opens a transaction. After an error the
# connection refuses further queries until you call conn.rollback().

In read-modify-write code, lock the row first: SELECT … FOR UPDATE inside the transaction, or use a version column and UPDATE … WHERE version = %s (optimistic locking).

Upsert with RETURNING

cur.execute(
    """
    INSERT INTO findings (host_id, cve, severity)
    VALUES (%s, %s, %s)
    ON CONFLICT (host_id, cve)
    DO UPDATE SET severity = EXCLUDED.severity,
                  seen_count = findings.seen_count + 1
    RETURNING id, seen_count
    """,
    (host_id, "CVE-2024-3400", "critical"),
)
finding_id, seen_count = cur.fetchone()

ON CONFLICT (host_id, cve) needs a UNIQUE constraint or index on exactly those columns. EXCLUDED is the row you tried to insert.

Job queue: FOR UPDATE SKIP LOCKED

CLAIM_JOB = """
UPDATE jobs SET status = 'running', started_at = now()
WHERE id = (
    SELECT id FROM jobs
    WHERE status = 'queued'
    ORDER BY created_at
    LIMIT 1
    FOR UPDATE SKIP LOCKED
)
RETURNING id, payload
"""

def worker_loop(pool):
    while True:
        with pool.connection() as conn:           # commits when the block exits
            job = conn.execute(CLAIM_JOB).fetchone()
        if job is None:
            return                                # queue is empty
        job_id, payload = job
        result = run_job(payload)
        with pool.connection() as conn:
            conn.execute(
                "UPDATE jobs SET status = 'done', result = %s WHERE id = %s",
                (result, job_id),
            )

Each worker locks the row it claims, and other workers skip locked rows instead of waiting, so no two workers get the same job. Tested: while one session held job 1, a second session claimed job 2.

The claim commits before run_job, so a crashed worker leaves its job 'running'. Requeue stale rows (UPDATE jobs SET status = 'queued' WHERE status = 'running' AND started_at < now() - interval '15 minutes'), or, for short jobs, keep the claiming transaction open while the job runs so a crash rolls it back. Index (status, created_at).

Bulk inserts: executemany and COPY

rows = [("10.0.0.5", 22, "open"), ("10.0.0.6", 443, "open")]

with conn.cursor() as cur:
    cur.executemany(
        "INSERT INTO ports (ip, port, state) VALUES (%s, %s, %s)", rows
    )

    # COPY is the fastest way to load many rows
    with cur.copy("COPY ports (ip, port, state) FROM STDIN") as copy:
        for row in rows:
            copy.write_row(row)

If the with cur.copy(...) block raises, the rows sent so far are discarded.

Connection pool with threads

from psycopg_pool import ConnectionPool      # separate package: pip install "psycopg[pool]"

pool = ConnectionPool(DSN, min_size=2, max_size=10, open=True)

def save_finding(host_id, cve):
    with pool.connection() as conn:          # borrow; commit (or roll back); give it back
        conn.execute(
            "INSERT INTO findings (host_id, cve) VALUES (%s, %s)", (host_id, cve)
        )

with ThreadPoolExecutor(max_workers=10) as ex:   # each thread borrows its own connection
    list(ex.map(save_finding, host_ids, cves))

pool.close()                                 # at shutdown

Pool size: smaller than you think. Postgres caps total connections (max_connections), and every app instance has its own pool.

Async psycopg

import psycopg
from psycopg_pool import AsyncConnectionPool

async def count_hosts(dsn):
    # connect() is awaited first, then used as a context: `async with await`
    async with await psycopg.AsyncConnection.connect(dsn) as aconn:
        async with aconn.cursor() as cur:
            await cur.execute("SELECT count(*) FROM hosts")
            (n,) = await cur.fetchone()
            return n

async def main():
    async with AsyncConnectionPool(DSN, max_size=20) as apool:   # opens and closes the pool
        async with apool.connection() as aconn:
            await aconn.execute("INSERT INTO scans (target) VALUES (%s)", ("10.0.0.0/24",))

Rows stream with async for row in cur. On Windows, psycopg needs SelectorEventLoop, not the default Proactor loop.

Errors

from psycopg import errors

try:
    with conn.transaction():
        conn.execute("INSERT INTO users (email) VALUES (%s)", (email,))
except errors.UniqueViolation:
    pass                    # duplicate key: the transaction() block already rolled back
except psycopg.OperationalError:
    raise                   # lost connection, server down: retry with backoff upstream

Isolation levels and retrying

conn.isolation_level = psycopg.IsolationLevel.SERIALIZABLE

def run_serializable(conn, fn, attempts=5):
    for attempt in range(attempts):
        try:
            with conn.transaction():
                return fn(conn)
        except (errors.SerializationFailure, errors.DeadlockDetected):
            if attempt == attempts - 1:
                raise
            time.sleep(0.01 * 2 ** attempt)     # back off, then run the whole thing again

READ COMMITTED is the default. Lost updates need SELECT … FOR UPDATE, a version column, or SERIALIZABLE plus a retry loop like this one: the whole transaction is retried, not just the failing statement.

psycopg2 vs psycopg 3

Featurepsycopg2psycopg 3
Importimport psycopg2import psycopg
with conn:Ends the transaction; the connection stays openCommits or rolls back and closes the connection. Use conn.transaction() for transaction-only blocks.
ParametersMerged into the SQL on the clientSent to the server separately. No parameters in SET, NOTIFY or DDL: use psycopg.sql, set_config(%s, %s, false), pg_notify(%s, %s) or psycopg.ClientCursor.
List of valuesWHERE id IN %s with a tupleWHERE id = ANY(%s) with a list
AsyncNo asyncio support (only a low-level polling mode, used by aiopg)AsyncConnection, AsyncConnectionPool
Poolpsycopg2.pool.ThreadedConnectionPoolpsycopg_pool.ConnectionPool (separate package)
COPYcopy_from / copy_expert with a filecur.copy("COPY … FROM STDIN") + write_row()
Batchesextras.execute_valuesexecutemany (pipelined on libpq 14+)
Stored procedurescallproc()Removed: execute("CALL proc(%s)", …)
Prepared statementsBy handAutomatic after 5 runs of a query (prepare_threshold); set prepare_threshold=None behind PgBouncer’s transaction pooling

Algorithm templates

Arrays & strings templates

Core

Hash map: complement lookup (Two Sum)

def two_sum(nums, target):
    index_of = {}                        # value -> index seen so far
    for i, x in enumerate(nums):
        if target - x in index_of:
            return [index_of[target - x], i]
        index_of[x] = i
    return []

Two pointers: from both ends

def two_sum_sorted(nums, target):        # input is SORTED
    l, r = 0, len(nums) - 1
    while l < r:
        total = nums[l] + nums[r]
        if total == target:
            return [l, r]
        if total < target:
            l += 1                       # need a bigger sum
        else:
            r -= 1                       # need a smaller sum
    return []

def is_palindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        if not s[l].isalnum():
            l += 1
        elif not s[r].isalnum():
            r -= 1
        elif s[l].lower() != s[r].lower():
            return False
        else:
            l, r = l + 1, r - 1
    return True

Two pointers: same direction (read / write)

def move_zeroes(nums):                   # in place, keep order
    write = 0                            # next slot for a non-zero
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

def remove_duplicates(nums):             # sorted input, returns new length
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
    return write if nums else 0

Sliding window: fixed size k

def max_sum_of_k(nums, k):
    window = sum(nums[:k])
    best = window
    for r in range(k, len(nums)):
        window += nums[r] - nums[r - k]  # add the new, drop the old
        best = max(best, window)
    return best

Sliding window: variable size (the general template)

def longest_with_at_most_k_distinct(s, k):
    count = Counter()
    l = best = 0
    for r, ch in enumerate(s):
        count[ch] += 1                   # 1. expand: take s[r]
        while len(count) > k:            # 2. shrink while the window is invalid
            count[s[l]] -= 1
            if count[s[l]] == 0:
                del count[s[l]]
            l += 1
        best = max(best, r - l + 1)      # 3. s[l..r] is valid: record it
    return best

def length_of_longest_substring(s):      # no repeated characters
    last = {}                            # char -> last index seen
    l = best = 0
    for r, ch in enumerate(s):
        if ch in last and last[ch] >= l:
            l = last[ch] + 1             # jump past the repeat
        last[ch] = r
        best = max(best, r - l + 1)
    return best

Longest window: update the answer after shrinking. Shortest window: update it inside the while loop, before each shrink.

Sliding window maximum (monotonic deque)

def max_sliding_window(nums, k):
    q, out = deque(), []                   # indices; their values are decreasing
    for i, x in enumerate(nums):
        while q and nums[q[-1]] <= x:
            q.pop()                        # smaller items can never be the max again
        q.append(i)
        if q[0] <= i - k:
            q.popleft()                    # the front slid out of the window
        if i >= k - 1:
            out.append(nums[q[0]])
    return out

max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)   # -> [3, 3, 5, 5, 6, 7]

O(n): each index enters and leaves the deque once. For the minimum, flip the comparison to >=.

Prefix sum + hash map

def subarray_sum_equals_k(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                          # the empty prefix
    prefix = count = 0
    for x in nums:
        prefix += x
        count += seen[prefix - k]        # earlier prefixes that leave a sum of k
        seen[prefix] += 1
    return count

prefix = [0] + list(accumulate([3, 1, 4, 1]))
prefix                                   # -> [0, 3, 4, 8, 9]
prefix[3] - prefix[1]                    # -> 5  sum of nums[1:3]

Binary search: exact match

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                      # <= : one element is still a range
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Binary search on the answer

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi] where ok(x) is True. ok goes F, F, ..., T, T.
    Returns hi unchecked when nothing works: test ok(result) if that can happen."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid                     # mid works; maybe something smaller does
        else:
            lo = mid + 1
    return lo

def min_eating_speed(piles, h):          # Koko Eating Bananas
    def can_finish(speed):
        return sum((p + speed - 1) // speed for p in piles) <= h
    return first_true(1, max(piles), can_finish)

Ask: “if speed k works, does k+1 also work?” If yes, the condition is monotonic and this template applies.

Stack: matching pairs

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:                  # closing bracket
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack                     # nothing left open

Monotonic stack: next greater element

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []                           # indices; their temps are decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j            # day i is j's next warmer day
        stack.append(i)
    return answer

Intervals: merge, and rooms needed

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:      # overlaps the last one
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

def min_meeting_rooms(intervals):
    ends = []                                      # min-heap of end times
    for start, end in sorted(intervals):
        if ends and ends[0] <= start:
            heappop(ends)                          # a room freed up: reuse it
        heappush(ends, end)
    return len(ends)

Linked lists

Reverse a list

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next          # 1. save the rest
        cur.next = prev         # 2. flip the pointer
        prev, cur = cur, nxt    # 3. step forward
    return prev                 # new head

Dummy head (merge two sorted lists)

def merge_two_lists(a, b):
    dummy = tail = ListNode()   # dummy avoids "is the result empty?" checks
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b          # attach whatever is left
    return dummy.next

Fast & slow pointers

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow                 # second middle if length is even

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:        # `is`: same node object
            return True
    return False

Trees

Core

Recursive DFS: return info up

def max_depth(root):
    if not root:                     # base case: empty tree
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def diameter(root):                  # return one thing, track another
    best = 0
    def height(node):
        nonlocal best                # needed to REASSIGN an outer variable
        if not node:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)   # longest path through this node
        return 1 + max(left, right)      # what the parent needs
    height(root)
    return best

DFS: pass limits down (Validate BST)

def is_valid_bst(root, low=-inf, high=inf):
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and     # left: below me
            is_valid_bst(root.right, root.val, high))      # right: above me

Checking only a node against its children is the classic bug: every node must fit the bounds of all its ancestors.

BFS: level by level

def level_order(root):
    if not root:
        return []
    levels, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):          # exactly the nodes on this level
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        levels.append(level)
    return levels

def right_side_view(root):
    return [level[-1] for level in level_order(root)]

Iterative inorder (sorted order of a BST)

def inorder(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                  # go left as far as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)         # visit
        node = node.right
    return out

def kth_smallest(root, k):
    return inorder(root)[k - 1]      # or stop early at the kth visit

Traversal orders

OrderVisitUse it for
Preordernode, left, rightcopy / serialize a tree, pass values down
Inorderleft, node, rightBST in sorted order, kth smallest
Postorderleft, right, nodeheights, diameters, anything needing children first
Level orderBFS by depthright side view, min depth, per-level sums

Trie

Implement Trie

class TrieNode:
    def __init__(self):
        self.children = {}               # char -> TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def _walk(self, s):                  # follow s; None if the path breaks
        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: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

Heaps: top K & streams

Top K frequent / K closest

def top_k_frequent(nums, k):
    return [x for x, _ in Counter(nums).most_common(k)]

def k_closest(points, k):
    return nsmallest(k, points, key=lambda p: p[0] ** 2 + p[1] ** 2)

def kth_largest(nums, k):                # size-k min-heap: O(n log k)
    heap = []
    for x in nums:
        heappush(heap, x)
        if len(heap) > k:
            heappop(heap)                # drop the smallest
    return heap[0]

Kth Largest in a Stream (class)

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = []                   # min-heap of the k largest so far
        for x in nums:
            self.add(x)

    def add(self, val: int) -> int:
        heappush(self.heap, val)
        if len(self.heap) > self.k:
            heappop(self.heap)
        return self.heap[0]              # smallest of the top k = kth largest

Two heaps: running median

class MedianFinder:
    def __init__(self):
        self.low = []     # max-heap (negated): smaller half
        self.high = []    # min-heap: larger half

    def addNum(self, num: int) -> None:
        heappush(self.low, -num)
        heappush(self.high, -heappop(self.low))      # largest of low moves up
        if len(self.high) > len(self.low):
            heappush(self.low, -heappop(self.high))  # keep low the same size or 1 bigger

    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

Graphs & grids

Core

Graphs are my inference for Horizon3 (attack paths, Neo4j), not a reported question.

Build an adjacency list

edges = [[0, 1], [1, 2], [3, 4]]
graph = defaultdict(list)
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)          # drop this line for a DIRECTED graph
graph[1]                        # -> [0, 2]

weighted = defaultdict(list)    # weighted: store (neighbor, weight)
for u, v, w in [[0, 1, 4], [1, 2, 1]]:
    weighted[u].append((v, w))
weighted[0]                     # -> [(1, 4)]

DFS: connected components

def count_components(n, edges):
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    seen = set()

    def dfs(node):
        seen.add(node)
        for nei in graph[node]:
            if nei not in seen:
                dfs(nei)

    components = 0
    for node in range(n):
        if node not in seen:     # new, unvisited region
            dfs(node)
            components += 1
    return components

Iterative version (no recursion limit): stack = [start], then while stack: node = stack.pop() and push unseen neighbors.

BFS: shortest path, unweighted

def shortest_path(graph, start, goal):
    q = deque([(start, 0)])
    seen = {start}               # mark when ADDED, not when popped
    while q:
        node, dist = q.popleft()
        if node == goal:
            return dist
        for nei in graph[node]:
            if nei not in seen:
                seen.add(nei)
                q.append((nei, dist + 1))
    return -1

Grid DFS: Number of Islands

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
            return
        grid[r][c] = "0"                 # mark visited by sinking it
        for dr, dc in DIRS:
            sink(r + dr, c + dc)

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                sink(r, c)
                islands += 1
    return islands

If you may not modify the grid, use a seen set of (r, c) tuples instead.

Multi-source BFS: Rotting Oranges

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    q, fresh = deque(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))         # every source starts in the queue
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):          # one level = one minute
            r, c = q.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

Clone Graph: map old node → copy

def clone_graph(node):
    copies = {}                          # original -> copy (also the visited set)

    def dfs(n):
        if n in copies:
            return copies[n]
        copy = Node(n.val)
        copies[n] = copy                 # store BEFORE recursing: handles cycles
        copy.neighbors = [dfs(nei) for nei in n.neighbors]
        return copy

    return dfs(node) if node else None

Topological sort (Course Schedule I & II)

def find_order(num_courses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * num_courses
    for course, pre in prerequisites:
        graph[pre].append(course)        # pre must come before course
        indegree[course] += 1

    q = deque(i for i in range(num_courses) if indegree[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:       # all its prerequisites are done
                q.append(nxt)
    return order if len(order) == num_courses else []   # [] = cycle

def can_finish(num_courses, prerequisites):
    return len(find_order(num_courses, prerequisites)) == num_courses

Dijkstra: weighted shortest path

def dijkstra(graph, start):
    """graph[u] = [(v, weight), ...]  ->  {node: shortest distance}"""
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, node = heappop(heap)
        if d > dist.get(node, inf):
            continue                     # stale entry: already found shorter
        for nei, w in graph[node]:
            nd = d + w
            if nd < dist.get(nei, inf):
                dist[nei] = nd
                heappush(heap, (nd, nei))
    return dist

def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist = dijkstra(graph, k)
    return max(dist.values()) if len(dist) == n else -1

Weights must be non-negative. All weights equal? Plain BFS is enough.

Union-Find (disjoint sets)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))     # everyone is their own root
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # path compression
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # already connected: this edge makes a cycle
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra             # attach the shorter tree under the taller
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def find_redundant_connection(edges):
    uf = UnionFind(len(edges) + 1)
    for a, b in edges:
        if not uf.union(a, b):
            return [a, b]

Backtracking & DP

Lower priority

Lower priority for this interview, but here if you need it.

Backtracking: subsets & permutations

def subsets(nums):
    result, path = [], []
    def backtrack(start):
        result.append(path[:])           # COPY, or every entry is the same list
        for i in range(start, len(nums)):
            path.append(nums[i])         # choose
            backtrack(i + 1)             # explore
            path.pop()                   # undo
    backtrack(0)
    return result

def permute(nums):
    result, path, used = [], [], [False] * len(nums)
    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False
    backtrack()
    return result

DP: memoized recursion, then bottom-up

@cache
def climb_stairs(n):                     # top-down: recursion + cache
    if n <= 2:
        return n
    return climb_stairs(n - 1) + climb_stairs(n - 2)

def rob(nums):                           # bottom-up with two variables
    prev2 = prev1 = 0                    # best total up to i-2 and i-1
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)   # skip x, or take it
    return prev1

def coin_change(coins, amount):
    dp = [0] + [inf] * amount            # dp[a] = fewest coins that make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != inf else -1

def unique_paths(m, n):                  # 2-D grid DP
    dp = [[1] * n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[-1][-1]