Python

Overview

What this page is

A reference to scan in the middle of a problem or an incident, not a tutorial. The tables answer which container, what an operation costs and which call does the job. The animations show the mechanisms people get wrong, the workflow diagrams show Python in production, and 66 runnable cards hold the code. Every card checks itself with assert lines on Python 3.11, the version the Run button uses.

• Core language — 01 to 31 — syntax, strings, lists, dicts, functions, classes, errors, generators
• Standard library — 32 to 40 — Counter, defaultdict, deque, heapq, bisect, itertools, functools
• Templates — 41 to 44 — two pointers, sliding window, graphs, backtracking, bits
• Checks — 45 to 51 — infinity and NaN, gotchas, version fallbacks, regex, dates, testing, idioms
• Real-world problems — 52 to 63 — log parsing, rate limiting, caching, top-k streams, calendars, retries, batching, config, validation, parsing, concurrency, percentiles
• Production — 64 to 66 — memory, profiling, typing

• Costs — list over-allocation, pop(0) against deque.popleft, set hashing against a list scan
• Names and objects — [[0] * m] * n, alias against shallow and deep copy, the mutable default
• Scope — LEGB lookup, late-binding closures
• Laziness — the order in which a generator pipeline pulls values
• Workflows — import, packaging and release, a FastAPI service, a batch data pipeline

> [!NOTE] Numbers such as byte sizes and capacities on this page are CPython 3.11 on a 64-bit machine. Other versions and PyPy can differ; the reasons do not.

Pick the container by its main operation

Find the operation your loop repeats, then pick the container that does it in O(1) or O(log n).

What operations cost

These are average-case costs in CPython. Amortized means an occasional slow step (a resize) averaged over many fast ones.

• read x[i] — O(1) — O(1) at the ends, O(n) in the middle — O(1) by key — O(1), but only h[0] (the minimum) means anything
• add at the right — O(1) amortized — O(1) — O(1) — O(log n) push
• take from the right — O(1) — O(1) — not applicable — O(log n) pop of the minimum
• add or take at the left — O(n) — O(1) — not applicable — not applicable
• v in x — O(n) — O(n) — O(1) — O(n)
• delete a value — O(n) — O(n) — O(1) — O(n)
• build from n items — O(n) — O(n) — O(n) — O(n) with heapify

• xs[a:b], s[a:b] — O(b - a) — a slice copies
• sorted, list.sort — O(n log n) — stable; fast on data that is already partly sorted
• bisect_left, bisect_right — O(log n) — the list must already be sorted
• insort — O(n) — O(log n) search, then an O(n) shift
• "".join(parts) — O(total length) — the right way to build a string
• s += t in a loop — can be O(n²) — each step may copy the whole string
• Counter(xs) — O(n) — most_common(k) calls heapq.nlargest: O(n log k)
• hashing a string key — O(length) — a dict lookup is O(1) in the number of keys, not in key length

Two rows cause most slow Python answers: list.pop(0) in a BFS loop and v in some_list inside another loop.

Watch the costs happen

A list is an array of pointers with spare room. When append finds no room, list_resize in Objects/listobject.c asks for (n + (n >> 3) + 6) & ~3 slots, so capacity goes 0, 4, 8, 16, 24, 32, 40, 52, 64, 76. Each resize adds about an eighth more, so the total work over n appends stays O(n): amortized O(1) per append. You can watch it with sys.getsizeof, which is 56 bytes plus 8 per allocated slot on 64-bit CPython 3.11.

> [!NOTE] The formula is unchanged in CPython 3.14. In the free-threaded build, a resize allocates a new array and copies into it instead of calling realloc, so readers in other threads never see a freed array.

The other two tabs show why deque exists and why a set beats a list for in. list.pop(0) moves every remaining pointer one slot left; deque.popleft() only advances an index inside a 64-slot block. A set jumps to slot hash(x) & mask; when that slot is taken it probes onward, up to 9 neighbors in a row when the table has room, then by i * 5 + 1 + perturb. It grows when it is 3/5 full, so probes stay short.

Names, objects and copies

A Python name is a reference to an object. Assignment binds a name; it never copies. [[0] * m] * n copies a reference to one row n times, which is why one write shows up in every row.

• b = a — no — no — yes
• a[:], list(a), copy.copy(a), dict.copy() — yes — no — yes
• copy.deepcopy(a) — yes — yes — no
• [row[:] for row in grid] — yes — one level — no, for a grid of numbers

The Copies tab traces all three on one structure, and the Mutable default tab shows def add(item, basket=[]): the default list is built once, when def runs, and lives in add.defaults.

Scope: LEGB and closures

A name is looked up in four scopes, in order: Local, Enclosing functions, Global (the module), Built-in. The search stops at the first scope that binds the name. Shadowing a built-in such as len or id at module level silently changes every use below it.

The compiler decides a name's scope from the function body: if a function assigns to x anywhere, every x in that function is local. Reading it before the assignment raises UnboundLocalError: cannot access local variable 'x' where it is not associated with a value, even when a global x exists. Use global x or nonlocal x only when you really mean to rebind the outer name.

The Late binding tab shows closures: a lambda made in a loop stores the variable's cell, not its value, so every lambda sees the last value. Bind the value with a default argument, lambda i=i: i.

Laziness: generators and pipelines

Calling a generator function runs none of its body; it returns a paused generator. A chain such as keep_even(parse(read(lines))) pulls one value at a time from the end: the consumer asks the last stage, which asks the stage before it, all the way down. One item is in flight at any moment, so the pipeline reads a 50 GB log in constant memory.

> [!WARNING] Anything that needs all values at once, such as sorted(), list(), len() on a list, or max() with no streaming alternative, ends the laziness. A generator is also one-shot: a second loop over it gets nothing.

Standard library calls worth knowing by name

• Counter(xs).most_common(k) — top k by count — O(n log k) — 32
• defaultdict(list) — groups without key checks — O(1) per add — 33
• deque.popleft() — queue pop for BFS — O(1) — 34
• OrderedDict.move_to_end(k) — mark as recently used — O(1) — 35
• heapq.heappush, heappop — min-heap on a list — O(log n) — 36
• heapq.nlargest(k, xs) — top k without a full sort — O(n log k) — 36
• bisect_left(xs, v) — first index where v fits — O(log n) — 37
• accumulate(xs, initial=0) — prefix sums — O(n) — 38
• combinations(xs, r) — every r-subset, lazily — O(C(n, r)) — 38
• @cache — memoize a pure function — one call per state — 39
• cmp_to_key(cmp) — use a two-argument comparator — adapter — 10

Two lookups traced

bisect on xs = [1, 3, 3, 5, 7]. The left and right answers differ only when the value is present.

• 3 — 1 — 3 — 3 appears 3 - 1 = 2 times
• 4 — 3 — 3 — absent; 5 is the first value above it
• 0 — 0 — 0 — smaller than everything
• 9 — 5 — 5 — larger than everything; index equals len(xs)

heapq with tuples (priority, tiebreak, task). The counter settles ties, so tasks are never compared.

• 1 — push (2, 0, "b") — [(2,0,b)]
• 2 — push (1, 1, "a") — [(1,1,a), (2,0,b)]
• 3 — push (2, 2, "c") — [(1,1,a), (2,0,b), (2,2,c)]
• 4 — pop — [(2,0,b), (2,2,c)] — (1,1,a)
• 5 — pop — [(2,2,c)] — (2,0,b): tie on 2, the lower counter wins

Concurrency: the GIL, threads, asyncio and processes

• threading, ThreadPoolExecutor — no: one thread holds the GIL at a time — blocking I/O; the GIL is released while waiting — shared state still needs locks
• asyncio — no: one thread, one event loop — many concurrent sockets — one blocking call stalls every task
• multiprocessing, ProcessPoolExecutor — yes: one interpreter per process — CPU-bound pure Python — arguments and results are pickled; start-up cost
• C extensions (NumPy, hashlib on large inputs) — yes, when the extension releases the GIL — heavy array or byte work — depends on the library

The GIL makes each bytecode step atomic, not your statement. count += 1 compiles to a load, an add and a store (LOAD_NAME, BINARY_OP, STORE_NAME on 3.11), and a thread switch between them loses an update. Protect shared state with a Lock, or share nothing and pass messages through a queue.Queue.

> [!IMPORTANT] Python 3.13 added an experimental free-threaded build with the GIL disabled: a separate executable, usually python3.13t, with a substantial single-threaded slowdown. Python 3.14 makes it officially supported (PEP 779), with the What's New quoting a single-threaded penalty of roughly 5 to 10%. The default build still has the GIL, and sys._is_gil_enabled() (3.13+) reports what the running process does.

Card 62 measures the I/O case: five 0.2-second waits take about 1 second in a loop and about 0.2 seconds in a thread pool or with asyncio.gather. CPU timings are not deterministic enough to assert on a shared runner, so the page does not quote them.

Memory and profiling

• How big is this object itself? — sys.getsizeof(x) — the object only, not what it references: a list is 56 bytes plus 8 per slot
• How much does this structure keep alive? — a deep size walk (card 64) — the object plus everything reachable, each object counted once
• Which line allocated the memory? — tracemalloc snapshots — bytes and counts by file and line, before and after
• Where does the time go? — python -m cProfile -s cumulative app.py — calls and time per function
• Is A faster than B? — timeit.repeat(..., repeat=5), take the min — the least noisy timing of a small snippet
• Why is start-up slow? — python -X importtime -c "import app" — microseconds per import, self and cumulative

• 0, 1 — 28 bytes
• 2**30 — 32 bytes: ints grow by 30-bit digits
• "", "a" — 49, 50 bytes
• () — 40 bytes
• {} — 64 bytes
• set() — 216 bytes

Most memory surprises are many small objects. A million instances of a class with a dict each pay for their own dict; @dataclass(slots=True) (3.10+) or slots drops it. Strings that compare equal are not necessarily one object, so a deep size can count the same text several times or once, depending on how it was built.

Imports and packaging

• A local file named random.py, json.py or requests.py — it shadows the real module: the script's directory is first on sys.path — rename it; check module.file
• Circular imports — the second module sees a half-initialized first module and raises ImportError or AttributeError — move the shared code to a third module, or import inside the function
• Installing into the system Python — breaks OS tools; Debian and Ubuntu now refuse with "externally-managed-environment" — one virtual environment per project (uv venv, python -m venv)
• Loose requirements in an app — a new release of a dependency breaks production — pin with a lockfile (uv.lock, pip-tools) for apps; keep ranges for libraries
• Tests import the source folder, not the installed package — a missing file in the wheel is only found by users — use the src/ layout and install the package before testing
• Re-uploading a fixed build with the same version — PyPI rejects a filename it has ever seen, even after a delete — bump the version

A Python service in production

• gunicorn -w — start near the number of CPU cores and measure — each worker is a process with its own GIL and memory
• worker class — uvicorn_worker.UvicornWorker for ASGI apps — uvicorn.workers is deprecated in favor of the uvicorn-worker package
• DB pool per worker — workers × pool size below PostgreSQL max_connections (100 by default) — every process opens its own connections
• --timeout — longer than your slowest legitimate request — gunicorn kills and restarts workers that stop responding
• background work — Celery or another queue — keeps slow work out of the request path
• errors — Sentry or another error tracker — stack traces with request context

A daily batch pipeline

Batch jobs fail, get retried and get rerun for old dates. Make every task idempotent: process exactly one interval, write to a path named after it, and overwrite instead of append. Then a retry or a backfill gives the same result as the first run.

Typing for production code

• list[int], dict[str, int] — built-in generics in annotations — 3.9
• int \ — None — optional values — 3.10
• Protocol — "anything with a .close()": structural typing, no inheritance — 3.8
• TypedDict — the shape of a dict from JSON or a database row — 3.8
• TypeVar + Generic[T] — containers and functions that keep the item type — 3.5
• typing.Self — methods that return their own class — 3.11
• class Page[T]:, type Alias = ... — the new generic syntax (PEP 695) — 3.12, not on this page's runner

Annotations do nothing at run time: TypedDict builds a plain dict, and a wrong type is only caught by a checker such as mypy or pyright in CI. Card 66 shows all three in one runnable file.

Types at a glance

• int, float, bool — 42, 3.14, True — no — yes — not a container
• str, bytes — "hi", b"hi" — no — yes — yes
• tuple — (1, 2) — no — yes, if its items are — yes
• list — [1, 2] — yes — no — yes
• dict — {"a": 1} — yes — no — insertion order (3.7+)
• set, frozenset — {1, 2}, frozenset({1}) — set yes, frozenset no — set no, frozenset yes — no

f-string format spec

The spec after the colon is [[fill]align][sign][#][0][width][,][.precision][type].

• .2f — 3.14159 — 3.14
• 8.3f — 3.14159 — 3.142
• , — 1234567 — 1,234,567
• .1% — 0.256 — 25.6%
• *^9 — "Ada" — *Ada*
• 08.2f — 42 — 00042.00
• +d — 42 — +42
• #x, b, o — 255 — 0xff, 11111111, 377
• = (debug, 3.8+) — f"{pi=}" — pi=3.14159

Gotchas that give wrong answers

None of these raise an error. Card 46 proves each one with an assert.

• def f(acc=[]) — one list shared by every call — acc=None, then build inside
• [[0] * m] * n — every row is the same list — [[0] * m for _ in range(n)]
• copy = grid[:] — inner lists still shared — [row[:] for row in grid]
• removing from xs while looping over it — items get skipped — loop over list(xs) or rebuild
• [lambda: i for i in range(3)] — every lambda sees the last i — lambda i=i: i
• a is b on values — depends on object caching — a == b
• 0.1 + 0.2 == 0.3 — False — math.isclose or Decimal
• -7 // 2 — -4 (floors), not -3 — int(-7 / 2) when you want truncation
• dd[k] on a defaultdict to test a key — inserts k — k in dd
• zip(a, b) of unequal lengths — extra items dropped — zip(a, b, strict=True) (3.10+)
• xs = xs.sort() — xs becomes None — xs.sort() or xs = sorted(xs)
• round(2.5) — 2: ties go to the even neighbor — math.floor(x + 0.5) for half-up on positives
• len = 3 at module level — every later len(x) in the module fails — never reuse built-in names

Which version added what

Judges and servers can lag behind the latest Python. Card 47 shows the portable forms for the features you are most likely to type.

• 3.8 — :=, positional-only /, f"{x=}", math.comb, math.isqrt — a separate assignment line
• 3.9 — list[int], dict \ — dict, removeprefix, functools.cache, math.lcm — typing.List, {a, b}, lru_cache(maxsize=None)
• 3.10 — match/case, int \ — None, zip(strict=True), pairwise, bit_count, bisect key=, Counter.total, dataclass(slots=True) — if/elif, Optional[int], zip(xs, xs[1:]), bin(x).count("1")
• 3.11 — except* groups, typing.Self, tomllib, StrEnum; 10 to 60% faster than 3.10 — plain except, a string annotation
• 3.12 — same quotes nested inside f-strings, type aliases, class C[T]:, itertools.batched — other quotes; TypeVar; islice in a loop
• 3.13 — new interactive shell; experimental free-threaded build (no GIL); sys._is_gil_enabled() — none needed
• 3.14 — heapq.heappush_max and other max-heap helpers, template strings t"...", deferred annotations; free-threaded build officially supported — negate values for a max-heap

Real-world problems

Each card states the task in its description, solves it, and checks the solution with asserts. Read the reasoning, then change the input and run it.

• 52 — top IPs and status mix from an nginx access log — re, Counter
• 53 — per-key sliding-window rate limiter — deque, an injected clock
• 54 — LRU cache with a hit rate — OrderedDict
• 55 — the k slowest requests from a stream — heapq, generators
• 56 — merge calendars and find free slots — sorting, intervals
• 57 — retry with exponential backoff and jitter — decorators, injected sleep
• 58 — bulk insert in batches — islice, generators
• 59 — layered config from defaults, a file and the environment — dict merge, ChainMap
• 60 — validate a signup payload — dataclass, __post_init__
• 61 — parse CSV and JSON lines, reporting bad rows — csv, json, Decimal
• 62 — overlap I/O with threads and asyncio — ThreadPoolExecutor, asyncio.gather
• 63 — p50 and p95 latency per endpoint — statistics.quantiles

What you will be able to do

• Pick a container by the operation your loop repeats, and explain its cost from how CPython stores it.
• Predict aliasing, copy, scope and closure behavior before running the code.
• Build lazy pipelines that process more data than fits in memory.
• Choose threads, asyncio or processes from where the time goes, and say what the GIL does and does not protect.
• Measure memory and time before optimizing.
• Ship Python: imports, packaging, a production web service and an idempotent batch job.
• Solve the everyday production tasks in cards 52 to 63 with the standard library alone.

When to use it

• You know the algorithm and need the exact call: bisect_left or bisect_right, heapq.nlargest, Counter.most_common
• You are choosing a container and want its cost to justify the choice
• You are porting a C++ or Java answer and hit Python rules: floor division, no overflow, no tail calls, comparators
• The answer is right but too slow, and you are looking for a hidden O(n²)
• The answer is wrong with no error, and you want to rule out the known silent bugs
• The judge runs an older Python and you need to know which syntax it accepts

More Quick References topics

• Bash & Shell
• Git
• SQL