Glossary

Every term used anywhere in this program, defined in one or two lines, with a pointer to where it is taught properly. Alphabetical within sections.

If a term appears in a guide and is not here, that is a bug — log it in STATE.md.

Table of Contents

Coding and Data Structures

Taught in tracks/coding/WARMUP.md

Amortized complexity — the average cost per operation over a long sequence, where an occasional expensive operation is paid for by many cheap ones. Lazy deletion plus a periodic rebuild is amortized O(1). §5.3

Arithmetic intensity — see Inference. Also the general idea: FLOPs per byte moved.

Backpressure — making a producer feel a consumer's slowness, so the signal propagates upstream to someone who can act. A bounded queue is the mechanism. §10.1

Bloom filter — a bit array plus k hashes. "Definitely absent" is exact; "possibly present" can be wrong. m = -n·ln(p)/(ln 2)² bits, k = (m/n)·ln 2 hashes. ~1.25 bytes/item at 1%. No false negatives, ever. §9.2

Carry buffer — the unconsumed tail of a chunk, prepended to the next one, so a token split across a boundary comes out whole. §6.1

Checkpoint (in a delta log) — a remembered position in the log, not a copy of state. Three integers. §2.2

Compaction — dropping versions no live reader can reach. Reachability from a pin set, exactly like a garbage collector's root set. §1.6

Consistent hashing — see Distributed.

Cuckoo filter — a Bloom-like filter that supports deletion, with better cache locality, at the cost of an insert path that can fail. §9.2

Delta log — recording what each operation changed rather than the resulting state. Deltas compose; snapshots do not. The representation that survives undo/redo/checkpoint requirements. §2.1

Eval breaker — see Python.

Fixed-delay vs fixed-rate — fixed-delay re-arms after a run finishes (never overlaps, schedule drifts). Fixed-rate fires on the original grid (can overlap; needs a catch-up policy). §5.4

Full / equal / decorrelated jitter — uniform(0, min(cap, base·2ⁿ)) · temp/2 + uniform(0, temp/2) · uniform(base, prev·3). AWS's simulation found full minimized both total work and completion time. §5.5

Head-of-line blocking — one slow item at the front stalling everything behind it, even when capacity is free. §4.1 (static batching), §10.2

Idempotency key — a stable identifier generated by the producer, unchanged across retries, that lets a consumer discard duplicates. Generate it at send time and dedupe silently does nothing. §9.1

Intrusive list — a linked list whose nodes are the payload objects, so a hash map can point directly at a node and unlinking is O(1). Requires double links. §3.1

Invariant-first — writing the assertion that pins the tricky property before implementing. The drill that stops you finding edge cases only when something breaks. §0.3

Lazy deletion — marking an element removed and skipping it when it surfaces, instead of finding and removing it. O(1) delete, with a rebuild threshold to bound the tombstone waste. §5.3

Leaky bucket — a queue drained at a constant rate; output is perfectly smooth, requests wait. Contrast token bucket, whose output is bursty and which rejects rather than queues. §4.5

Little's law — see Distributed.

LRU / LFU / TinyLFU — evict least-recently-used · least-frequently-used · admission control using a compact frequency sketch, which resists the scan-pollution that defeats LRU. §3.7

Lookahead window — a bounded forward search that makes a streaming diff O(1) amortized instead of needing the whole input. The price is that a skip longer than the window is misreported. §2.4

MVCC — Multi-Version Concurrency Control. Keep multiple versions per key; readers never block writers because writes only append. §1.7

Myers diff — the O(ND) shortest-edit-script algorithm git diff uses. Needs the whole input, which is why it cannot be used online. §2.4

Negative caching — caching the absence of a key for a short TTL. A DoS mitigation, not a performance optimization. §3.5

Postings list — for a term, the set of documents containing it. Intersect the smallest first. Text-index gate 1

Predecessor query — "the largest key ≤ X". Also called floor or as of. The tell that you need an ordered structure. §1.1

Sampled expiry — checking a small random sample for expiry on each write, instead of a full sweep. Redis's design. Lazy alone leaks; sampled bounds it in O(1) amortized. §3.3

Segment (index) — an immutable slice of an index. Writes accumulate in a mutable buffer; flush seals it; merge reclaims tombstoned space. Lucene's design. Text-index gate 4

Sentinel node — a permanent, dataless head/tail node that makes every real node have non-None neighbours, removing every linked-list edge case. §3.2

Single-flight — on a miss, exactly one caller runs the loader and the rest wait for that result. Prevents a cache stampede. §3.5

Sliding window counter — two fixed-window counts interpolated by how far into the current window you are. O(1), no boundary burst, ~1% error on real traffic. §4.3

Sliding window log — every request's timestamp, trimmed to the window. Exactly correct, O(limit) memory per key. The correctness baseline. §4.2

Stampede (cache / dogpile / thundering herd) — N concurrent misses on one key hitting the backing store simultaneously, at the moment the cache was supposed to protect it. §3.5

Three-colour DFS — WHITE unvisited / GREY on the current stack / BLACK done. Reaching GREY is a back edge, i.e. a cycle. Two states conflate "on my path" with "finished". §7.2

Time-to-first-passing-gate — the metric that predicts a gated coding round, because an unopened gate scores zero. §2.5 of the Track A README

Token bucket — tokens accrue at rate and cap at capacity; a request spends one. Separates sustained throughput from burst tolerance — the thing no window can express. §4.4

Tombstone — a marker recording that something was deleted, rather than removing it. Required whenever history or immutability matters. §1.4

Torn write — a partial record at the tail of a log after a crash. The expected post-crash state, not an error. §8.2

Walking skeleton — an end-to-end path working with the simplest possible everything, early. The take-home's hour-8 milestone. Track E §1.1

Write-ahead log (WAL) — append the intent durably before mutating the main structure, so recovery replays. [len][payload][CRC]. §8.1

Write skew — see Distributed.

Python Runtime

Taught in tracks/python-internals/WARMUP.md · QUIZBANK.md

aclosing — contextlib.aclosing, which guarantees an async generator's finally runs at scope exit. Without it, cleanup waits for loop.shutdown_asyncgens(), which under load is a connection leak. §3.6

Arena / pool / block — CPython's allocator hierarchy: 256 KB arenas → 4 KB pools (one size class each) → fixed blocks. An arena returns to the OS only when every pool in it is empty, which is why freeing does not lower RSS. §5.1

BaseException vs Exception — CancelledError, KeyboardInterrupt and SystemExit derive from BaseException, so except Exception deliberately misses them. §3.3

Bound method — what a function's __get__ returns: the function partially applied to the instance. self is the descriptor protocol, not magic. §6.2

Buffer protocol — the C-level interface for sharing memory without copying. What memoryview, socket.recv_into, struct.unpack_from and numpy use. §5.4

Cooperative cancellation — CancelledError is delivered at a suspension point, so a task with no await cannot be cancelled. §3.3

Coroutine / Task / Future — inert object from async def · a coroutine wrapped so the loop steps it concurrently · a placeholder for a later result (Task subclasses Future). §3.2

Cycle collector — generational mark-and-sweep over container objects, needed because refcounting cannot free mutual references. §1.4

Data vs non-data descriptor — defines __set__/__delete__ (outranks the instance dict) vs only __get__ (the instance dict outranks it). Explains why @property can't be shadowed and a method can. §6.2

Eval breaker — the flag that hands the GIL to another thread. Since CPython 3.10 it is checked only at specific instructions (backward jumps, calls), which is why the textbook lost-update demo often loses nothing. §4.3

ExceptionGroup / except* — how TaskGroup reports multiple simultaneous child failures. 3.11+. §3.4

Free-threaded build — CPython without the GIL. PEP 703 designed it, PEP 779 defined "supported", Phase II in 3.14: officially supported, not default. §4.4

Generational hypothesis — most objects die young, so collect the youngest generation most often. §1.4

GeneratorExit — thrown at a suspended yield by close(), which is how a generator's finally runs. Catching it and yielding again is a RuntimeError. §2.4

GIL — a mutex letting one thread execute CPython bytecode at a time. Protects interpreter internals, not your invariants. §4.1

Key-sharing dictionary (PEP 412) — instances of a class share the key layout, which already narrowed the __slots__ saving. Hence: measure. §5.2

Managed dict — since 3.11 the instance __dict__ is created lazily, so a class that could have one costs nothing until something is stored in it. §5.2

memoryview — a zero-copy view over a buffer. Slicing it allocates nothing; slicing bytes copies. A live view pins the underlying bytearray. §5.4

MRO / C3 linearization — the method resolution order, computed so a class precedes its bases, declaration order is preserved, and the result is monotonic. §6.4

Orphaned task — a task left running after gather propagated a sibling's exception. A resource leak, not a style difference. §3.4

Priming (a generator) — advancing to the first yield with next() so send() has an expression to deliver into. §2.4

pymalloc — CPython's small-object allocator, used for allocations ≤512 bytes. §5.1

Refcounting — freeing an object the instant its count hits zero. Prompt and deterministic; cannot collect cycles. §1.3

Resurrection — a __del__ storing self somewhere and reviving an object mid-finalization. One of several reasons to prefer weakref.finalize. §1.5

__slots__ — replaces the per-instance __dict__ with fixed offsets. Removes weakref support too unless you add '__weakref__'. A subclass omitting it regains a __dict__. §5.2

Structured concurrency — no task outlives its scope. TaskGroup's guarantee, and why it is a bug fix rather than a style preference. §3.4

Suspended frame — what a generator object holds: locals, instruction pointer, evaluation stack. Why a generator is a state machine. §2.3

tee — itertools.tee, which buffers everything one branch has read that the other has not. Draining one branch materializes the whole stream. §2.6

tracemalloc — attributes real allocations to source lines. The right tool, since sys.getsizeof measures only an object's own footprint. §5.3

weakref.finalize — cleanup tied to an object's lifetime that does not keep it alive. Beats __del__: defined ordering, exceptions not swallowed, no resurrection. §1.5

yield from — delegates iteration, forwards send/throw/close, and makes the sub-generator's return value the value of the expression (PEP 380). §2.5

Distributed Systems

Taught in tracks/systems-design/WARMUP.md

Admission control — deciding at the edge what not to serve, cheaply, before it consumes a resource. §10.3

AIMD — additive increase, multiplicative decrease. TCP's congestion law, applied to application concurrency limits: +1 when healthy, ×0.8 on failure. Track A §10.4

Anti-entropy — a background process reconciling divergent replicas, usually with a Merkle tree so the comparison is O(log n) in the difference. §5.4

At-most-once / at-least-once / exactly-once — no retries (can lose) · retry until acked (can duplicate) · impossible for delivery; achievable for processing via an idempotent consumer. §9.1

Back edge — an edge to a node on the current DFS stack, i.e. a cycle. Coding §7.2

Blast radius — how much of the system a failure can affect. Bulkheads and cells shrink it by construction. §10.4

Bulkhead — separate resource pools per dependency, so exhaustion in one cannot starve others. Costs pooling efficiency (M/M/c). §10.4

CAP — when a partition occurs, choose consistency or availability. Only during a partition, and "available" means every non-failing node responds. See PACELC. §7.5

Cellular architecture — partitioning the whole stack into independent cells each serving a slice of users, so blast radius is 1/N. §10.4

Circuit breaker — closed → open (fail immediately) → half-open (a small number of probes). Threshold must be a rate over a minimum volume. §10.2

Clock skew — the difference between two machines' wall clocks. NTP holds a few ms on a good LAN — statistical, not a bound, and a node cannot know its own skew. §3.2

Commit-wait — Spanner deliberately waiting out the TrueTime uncertainty window before releasing locks, which is how timestamps become globally meaningful. §3.6

Consistent hashing — mapping keys and nodes onto a ring so adding or removing a node moves only K/N keys instead of ~80%. §8.2

CRDT — a data type whose merge is commutative, associative and idempotent, so replicas converge with no coordination. Convergence is not correctness: a CRDT counter for inventory can go negative. Ch. 11

Deadline propagation — passing the remaining time budget downstream so any hop with insufficient time fails immediately instead of starting work it cannot finish. §10.3

Dead-letter queue (DLQ) — where a message goes after N failures. Needs four things: the reason, a replay path, poison detection, and an alert on arrival rate. §9.4

Dual write — writing to two systems that fail independently (db.save then queue.publish). No ordering is safe. Fix with the outbox. §9.2

Fail-stop vs fail-slow — the node stops (easy) vs it keeps answering, slowly or wrongly (harder, and the common case). Detect fail-slow with latency percentiles vs peers. §2.2

Fencing token — a monotonically increasing number issued with each lease, checked by the resource, that makes a zombie's stale write rejected without anyone detecting the zombie. The highest-value item in the track. §4.3

FLP impossibility — in a fully asynchronous system with one faulty process, no deterministic algorithm guarantees consensus. Practical systems buy liveness with timeouts and keep safety unconditional. §6.1

Gray failure — see fail-slow.

Happens-before (→) — Lamport's causal ordering. If neither a→b nor b→a, the events are concurrent, which is a real relationship, not an unknown. §3.3

HLC (hybrid logical clock) — a physical component tracking wall clock plus a logical counter. Close to real time, respects causality, O(1) size. Cannot detect concurrency. §3.5

Idempotent — an operation whose repetition has no additional effect. What makes at-least-once tolerable. §9.1

Lamport timestamp — one counter per node, max(local, received)+1 on receive. Gives a total order consistent with causality; cannot detect concurrency. §3.3

Lease — a lock with a timeout, so a dead holder does not block forever. Renew at lease/3. §4.1

Linearizability — the system behaves as if there were one copy and each operation took effect atomically at some instant between invocation and response. A recency guarantee about single objects. §7.1

Little's law — L = λW. Concurrency = arrival rate × time in system. Needs almost no assumptions, which is why it applies everywhere. §1.1

Load shedding — rejecting work to protect the rest. Shed by priority, and shed the oldest queued item. §10.3

Log matching — Raft's invariant: two logs with the same index+term are identical up to that point. What makes recovery simple. §6.3

Merkle tree — a hash tree over a key range; equal roots mean identical data, so comparison costs one hash in the common case. §5.4

Outbox pattern — insert the event into an outbox table in the same transaction as the state change; a relay publishes it with FOR UPDATE SKIP LOCKED. Solves the dual write. §9.3

PACELC — if Partition then A or C, Else Latency or Consistency. The more useful framing, because it names the tradeoff you make every day. §7.5

Quorum — W + R > N forces the read set and write set to overlap. §5.2

Raft term — a logical clock; at most one leader per term; seeing a higher term makes you step down. §6.2

Read repair — writing the newest value back to stale replicas discovered during a read. Cheap, but never repairs cold data. §5.4

Retry budget — capping retries at a fraction of base traffic, so amplification is bounded no matter how bad things get. The primary fix, before circuit breakers and before jitter. §10.1

Retry storm — retries multiplying offered load onto a dependency that is already failing. ~2.85× at a 95% failure rate with 3 attempts. §10.1

Serializability — the outcome equals some serial order of the transactions. An isolation guarantee about transactions, saying nothing about real time. §7.2

Sloppy quorum — accepting writes at any W reachable nodes during a partition, which breaks the overlap guarantee. Dynamo does this deliberately. §5.3

Snapshot isolation — every transaction reads a consistent snapshot; commits validate. Permits write skew. §7.4 and Coding §1.7

Split brain — two nodes both believing they hold authority. Prevented by fencing, not by detection. §4.2

SSI (serializable snapshot isolation) — tracks read-write dependencies and aborts dangerous structures. Postgres's SERIALIZABLE. §7.3

Strict serializability — serializable and respecting real time. The most expensive guarantee; Spanner. §7.3

Timer wheel — O(1) insert and O(1) tick scheduling, used by the Linux kernel and Kafka's purgatory. The 100× answer for a polling scheduler. d01 §9

TrueTime — Spanner's clock API returning an interval guaranteed to contain the true time, narrowed by GPS and atomic clocks. §3.6

Two Generals — the impossibility argument behind exactly-once delivery. §9.1

Vector clock — one counter per node, compared element-wise. Detects concurrency, at O(nodes) size and with subtle pruning. §3.4

Virtual node — many ring positions per physical node. Evens load and, more importantly, spreads a failed node's range across many successors instead of dumping it on one. §8.3

Write skew — two transactions read overlapping data, write disjoint keys, both commit, and jointly violate an invariant neither violated alone. The anomaly snapshot isolation permits. §7.3

Zombie (lease holder) — a process that paused past its lease, woke, and writes as if no time passed. Undetectable — fencing is the answer. §4.2

Inference and GPU

Taught in tracks/ml-infra/WARMUP.md

Activations — transient per-forward-pass memory. Reserve a few GB per GPU; a real number comes from profiling. §3.4

Arithmetic intensity — FLOPs per byte moved. Below machine balance (P/B) you are memory-bound; above it, compute-bound. §2.1

Chunked prefill — splitting a long prefill across scheduler steps so decode never stalls for a whole prefill. Trades a little prefill throughput for much better TTFT/TPOT tails. Sarathi-Serve. §4.4

Continuous / in-flight batching — scheduling at iteration granularity, so a finished sequence's slot refills on the next forward pass. Orca. The single biggest throughput lever. §4.2

Decode — generating tokens one at a time, each depending on the last. Memory-bandwidth-bound. Determines TPOT. §1.3

Disaggregated prefill/decode — running the two phases on different machines with different hardware, transferring the KV cache. DistServe. §5.5

Expert parallelism (EP) — placing MoE experts on different GPUs. Needs an all-to-all per MoE layer; expert load imbalance is the hot-partition problem again. §5.4

GQA / MQA — Grouped- / Multi-Query Attention: several query heads share one KV head. 8× smaller KV cache for Llama-70B. The architectural decision that makes long context affordable. §3.3

KV cache — cached K and V per token per layer, so generating token n is O(1) new work instead of O(n). The object in LLM serving, and the binding capacity constraint. §1.2

Machine balance — peak dense FLOP/s ÷ bandwidth. ~295 FLOP/byte on an H100 (989.5 TFLOP/s ÷ 3.35 TB/s). The datasheet's 1,979 TFLOP/s is the with-2:4-sparsity figure and does not apply to dense LLM weights. §2.1

Model parallelism — see TP / PP / EP. §5.4

PagedAttention — KV cache in fixed-size non-contiguous blocks with a per-sequence block table. Virtual-memory paging applied to the cache; removes internal and external fragmentation and enables copy-on-write prefix sharing. vLLM. §4.3

Pipeline parallelism (PP) — splitting layers across GPUs. Tolerates slower interconnect, works across nodes, introduces bubbles, does not improve single-request latency. §5.4

Prefill — processing the prompt, all tokens in parallel. Compute-bound. Determines TTFT. §1.3

Prefix caching — reusing KV blocks for shared prompt prefixes. Turns a 20-turn conversation's O(n²) prefill into O(n). Must be tenant-scoped or it is a cross-tenant leak. §5.1

Quantization — fewer bits per weight (or per KV entry). Helps decode twice: fewer bytes to read and more room for batch. Degradation is workload-specific — evaluate, don't assume. §5.3

RadixAttention — SGLang's radix-tree organization of the prefix cache, so partial matches are found efficiently. §5.1

Roofline — the model that says performance is bounded by min(compute, bandwidth × intensity). Williams et al., 2009. Ch. 2

Speculative decoding — a draft model proposes k tokens, the target verifies all k in one pass, and the output distribution is provably identical. Wins at low batch; loses at high batch because there is no spare compute. §5.2

Tensor parallelism (TP) — splitting each layer's matrices across GPUs. All-reduce every layer → needs NVLink → within a node. Improves latency. §5.4

TTFT / TPOT — time to first token (set by prefill and queueing) / time per output token (set by decode). They trade against each other, which is the whole scheduling problem. §1.3

Process and Interviewing

Anti-narrowing clause — the rule that one candidate account must not narrow preparation into a blind spot: ~25% off-report material, a six-component onsite, company-agnostic core. source-report.md

Confident-wrong — an answer you were sure of and got wrong. Scored separately because it is a landmine, not a study item: you will assert it and be corrected. RUBRIC.md

Decision log — a running decisions.md written while building: decision, alternatives with numeric reasons, assumptions, would-revisit-if, and not-tested. Track E §2

DTAO — Decision, Tradeoff, Alignment, Outcome. Replaces STAR, which buries the decision. Track F

Epistemic ladder — confirmed (primary/verifiable) · reported (candidate accounts, prep vendors) · inference (mine, labelled). Only the first is safe to assert. findings.md

Gate — one stage of a progressive coding problem. Gate N+1 stays closed until gate N passes. Track A

Hire-bar scale — no hire / hire (senior) / strong hire (senior) / hire (staff) / strong hire (staff). Every mock is scored on this, calibrated to Staff. mocks/

L0–L3 — the per-track level from the diagnostic: foundations missing · correct but slow · interview-passable at senior · staff-altitude. Drives hour allocation. RUBRIC.md

Leech — a review item that has reset to the 1-day interval three or more times. A comprehension problem, not a memory one — stop drilling and re-learn the mechanism. review/

Progressive format — the reported onsite coding round: ~4 gates, each gated on the previous working, reported pass bar 2 (assume 3). findings.md

Spaced repetition — resurfacing at 1, 3, 7, 21 days. Wrong at any interval resets to 1. review/

Time-to-first-passing-gate — the metric that predicts a gated round, because an unopened gate scores zero. Track A

References