2022-03-31

Interview patterns in Python

Not necessarily fastest, but hopefully neatest. Recursive problems can be generically converted to while loops to circumvent recursion limit.

Variable naming conventions.

x  y  z      # values
i  j  k      # corresponding indices
xs ys zs     # lists of values
t            # a target to aim for
w            # the path to something
a            # something we accumulate
f            # a function used for recursion
n            # a node in a tree or graph
b            # a place to mark things we've already done
l            # an input list
s            # an input string
p            # an input pattern
.v .l .r .n  # the value, left, right, next of a node in a tree
.._prev      # the previous of something
.._next      # the next of something
.._new       # a new version of something

Imports required to run the examples.

from __future__ import annotations
from collections import defaultdict
from dataclasses import dataclass
from functools import cache  # a lot of the `f(...)` below can be memoized
from itertools import count
from types import SimpleNamespace