"""Problem catalog for the progressive harness. Fifteen multi-stage problems, four gates each, ALL with automated gate tests. The taxonomy matches what these loops reportedly ask -- stateful data structures, versioning and MVCC, streaming and incremental algorithms, diffing, parsers and tokenizers, rate limiters, schedulers, caches, iterators and generators, concurrency primitives and backpressure. It is explicitly not a generic algorithm grind. Roughly a quarter of the set is deliberately OFF the source report (spreadsheet evaluation, symlink resolution, async crawling, object pooling). Those come from independently corroborated reports and exist so that one candidate account cannot narrow the preparation into a blind spot. See ../../../research/source-report.md section "The Anti-Narrowing Clause". Each entry carries a `chapter` link into ../../WARMUP.md, which teaches the pattern from first principles. Read it AFTER the timed run, never before. """ from __future__ import annotations import importlib import os HERE = os.path.dirname(os.path.abspath(__file__)) def _gate(title: str, brief: str) -> dict: return {"title": title, "brief": brief} CATALOG: list[dict] = [ # ----------------------------------------------------------------------- { "id": "versioned-kv", "title": "Versioned Key-Value Store", "module": "versioned_kv", "themes": ["state", "memory"], "budget_min": 45, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-1-predecessor-queries-and-versioned-state", "gates": [ _gate( "Point-in-time reads", "Build a key-value store where every write is stamped with a\n" "monotonically increasing version.\n\n" " put(key, value) -> version\n" " get(key) latest value, or None\n" " get(key, version=v) the value as of version v\n\n" "`get(key, version=v)` returns the value written by the largest\n" "version <= v. If the key did not exist at v, return None.\n" "Versions are global across all keys, not per-key.", ), _gate( "Deletes and history", "Add deletion and history inspection.\n\n" " delete(key) -> version a tombstone, not a removal\n" " history(key) -> [(version, value_or_DELETED), ...]\n" " keys(version=None) keys live as of that version\n\n" "A read at a version after the delete must return None; a read\n" "before it must still see the old value. Deleting a key that does\n" "not exist must still consume a version -- think about why an\n" "interviewer would care.", ), _gate( "Snapshots and compaction", "Add snapshot isolation and garbage collection.\n\n" " snapshot() -> Snapshot a stable read view\n" " Snapshot.get(key) reads at its pinned version\n" " Snapshot.release()\n" " compact() drop versions no snapshot can see\n\n" "compact() must never break an outstanding snapshot, and must\n" "reclaim history for keys with many superseded writes. Report how\n" "many versions it dropped.", ), _gate( "Transactions with conflict detection", "Add optimistic multi-key transactions.\n\n" " txn = store.begin()\n" " txn.get(k); txn.put(k, v); txn.delete(k)\n" " txn.commit() -> version raises ConflictError\n\n" "A transaction reads at its start version. On commit, if any key it\n" "READ was written by someone else since then, raise ConflictError\n" "and apply nothing. Writes are atomic: all or none. This is\n" "snapshot isolation -- be ready to say what anomaly it still permits.", ), ], }, # ----------------------------------------------------------------------- { "id": "token-stream-differ", "title": "Token-Level Streaming Differ with Rollback", "module": "token_stream_differ", "themes": ["streaming", "state", "memory"], "budget_min": 45, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-2-delta-logs--undo-redo-checkpoint", "gates": [ _gate( "Incremental prefix diff", "Tokens arrive one at a time and are diffed against a known\n" "baseline sequence, incrementally -- you never see the whole new\n" "stream at once.\n\n" " StreamDiffer(baseline)\n" " feed(token) -> [events emitted by this token]\n" " close() -> [trailing events]\n" " events -> the full event log so far\n\n" "Events are ('keep'|'insert'|'delete', token). Keep a cursor into\n" "the baseline: a token matching baseline[cursor] is a KEEP and\n" "advances it; anything else is an INSERT. close() emits a DELETE\n" "for every baseline token past the cursor.", ), _gate( "Deletion detection with bounded lookahead", "The stream can skip baseline tokens. Detect that instead of\n" "calling everything an insert.\n\n" " StreamDiffer(baseline, lookahead=8)\n\n" "If a token does not match baseline[cursor] but does match\n" "baseline[j] for some j in (cursor, cursor+lookahead], emit a DELETE\n" "for every baseline token in [cursor, j), then a KEEP, and set the\n" "cursor to j+1. Use the SMALLEST such j. If there is none, it is\n" "still an INSERT. The window is what keeps this O(1) amortized\n" "instead of a full edit-distance table.", ), _gate( "Named checkpoints and rollback", "The consumer needs to speculate and back out.\n\n" " checkpoint(label)\n" " rollback(label) restore differ state to that point\n" " labels() live checkpoint labels\n\n" "Rollback restores the cursor and truncates the event log to exactly\n" "what it was. Checkpoints taken AFTER the one you roll back to are\n" "invalidated. Rolling back to an unknown or invalidated label raises\n" "KeyError. Checkpoints must be O(1) -- you cannot snapshot the log.", ), _gate( "Step-wise undo/redo under a memory bound", "Add token-granular undo and redo.\n\n" " undo(n=1) revert the last n feed() calls\n" " redo(n=1) reapply them\n\n" "A new feed() after an undo discards the redo stack. undo() past the\n" "start, or redo() past the end, raises IndexError and changes\n" "nothing. close() ends the stream: feed/undo/redo after it raise\n" "RuntimeError.\n\n" "Hard constraint: per-feed bookkeeping must be O(1). Snapshotting\n" "state per feed passes the correctness tests and fails the memory\n" "test -- 20k feeds against a 3k-token baseline are asserted under a\n" "peak allocation bound.", ), ], }, # ----------------------------------------------------------------------- { "id": "rate-limiter", "title": "Rate Limiter: Bucket to Distributed", "module": "rate_limiter", "themes": ["state", "concurrency"], "budget_min": 40, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-4-rate-limiting--four-algorithms-and-their-lies", "gates": [ _gate( "Token bucket", " TokenBucket(capacity, rate, clock=time.monotonic)\n" " .allow(cost=1) -> bool\n" " .retry_after(cost=1) -> float seconds until it would succeed\n\n" "Lazy refill against the injected clock -- NO background thread.\n" "Tokens accrue at `rate` per second and cap at `capacity`, so an idle\n" "client may burst. capacity <= 0 or rate <= 0 raises ValueError.\n" "The clock is injectable because a limiter you cannot test\n" "deterministically is a limiter you cannot ship.", ), _gate( "Sliding windows", "Two more limiters, same clock convention.\n\n" " SlidingWindowLog(limit, window, clock).allow() -> bool\n" " Exactly correct. Never more than `limit` in ANY window of\n" " length `window`. O(limit) memory.\n\n" " SlidingWindowCounter(limit, window, clock).allow() -> bool\n" " O(1) memory. Keep the current and previous fixed-window\n" " counts and interpolate:\n" " weight = 1 - elapsed_in_current / window\n" " estimate = prev * weight + curr\n" " Admit while estimate < limit. This removes the fixed-window\n" " boundary burst; be ready to state the error it introduces.", ), _gate( "Per-key limiting, thread-safe", " ShardedLimiter(factory, shards=16)\n" " .allow(key, cost=1) -> bool\n\n" "One independent limiter per key, created lazily from `factory()`.\n" "Must be safe under concurrent callers. One global lock is correct\n" "and is the bottleneck, because EVERY call mutates state -- shard by\n" "hash(key) into independently-locked maps. A concurrency test asserts\n" "the total admitted count is exactly the limit under a real race.", ), _gate( "Distributed, with a shared store", " DistributedLimiter(store, limit, window, clock=...,\n" " fail_open=True, lease=1)\n" " .allow(key) -> bool\n\n" "`store` implements `incr(bucket_key, ttl, amount=1) -> int` returning\n" "the new count, and may raise StoreUnavailable.\n\n" " * Two limiters sharing a store must share the limit.\n" " * The bucket key must include the window, so counts roll over.\n" " * On StoreUnavailable: fail_open=True admits, False denies.\n" " Argue which is right for overload vs for billing.\n" " * lease > 1 claims that many permits per round trip and spends\n" " them locally, so store calls drop by ~lease. Precision for\n" " latency -- say which you traded.", ), ], }, # ----------------------------------------------------------------------- { "id": "lru-ttl-cache", "title": "LRU Cache to Size-Aware TTL Cache", "module": "lru_ttl_cache", "themes": ["state", "memory"], "budget_min": 40, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-3-the-intrusive-list--lru-and-friends", "gates": [ _gate( "LRU from scratch", " LRUCache(capacity)\n" " .get(key, default=None)\n" " .put(key, value)\n" " len(cache)\n\n" "O(1) get and put. Evict the least-recently-USED entry (a get counts\n" "as use) when over capacity. No OrderedDict and no\n" "functools.lru_cache -- they want the mechanism: an intrusive\n" "doubly-linked list plus a dict from key to node. A performance test\n" "asserts 200k operations complete in linear time.", ), _gate( "Per-entry TTL", " LRUCache(capacity, clock=time.monotonic)\n" " .put(key, value, ttl=None)\n\n" "An entry past its deadline reads as a miss and is removed. Expiry is\n" "LAZY on the read path, plus SAMPLED on write: on each put, check a\n" "small number of entries from the cold end and drop what has expired.\n" "Lazy alone never frees an entry that is never read again -- be ready\n" "to say why that makes lazy-only unshippable. Use the injected clock.", ), _gate( "Size-aware eviction", " LRUCache(capacity, max_bytes=None, clock=...)\n" " .put(key, value, ttl=None, cost=1)\n" " .total_bytes -> int\n\n" "Bound by BOTH entry count and total cost. Evict repeatedly until\n" "under both bounds -- a single eviction leaves you over budget when\n" "inserting something large. An entry whose cost exceeds max_bytes on\n" "its own raises ValueError rather than emptying the cache.", ), _gate( "Thread safety and single-flight", " .get_or_load(key, loader) -> value\n\n" "Thread-safe throughout. On a miss, exactly ONE caller runs `loader`;\n" "concurrent callers for the same key wait for that result rather than\n" "each calling the loader. Different keys must load concurrently, not\n" "serially. If the loader raises, every waiter sees that exception and\n" "the next call retries. This is stampede protection -- without it, a\n" "popular key expiring sends N concurrent misses at your backend at the\n" "moment the cache was supposed to protect it.", ), ], }, # ----------------------------------------------------------------------- { "id": "resumable-iterator", "title": "Resumable Iterator with Serializable State", "module": "resumable_iterator", "themes": ["state", "memory", "streaming"], "budget_min": 40, "automated": True, "chapter": "tracks/coding/WARMUP.md#02-representation-first-thinking", "gates": [ _gate( "Checkpoint and resume", " ResumableIterator(source_factory)\n" " iter/next protocol\n" " .state() -> JSON-serializable dict\n" " ResumableIterator.resume(source_factory, state)\n\n" "`source_factory` is a zero-argument callable returning a fresh\n" "iterable over the same deterministic sequence. resume() returns an\n" "iterator positioned after the last emitted item. The source must NOT\n" "be materialized -- a test counts how many items get pulled.", ), _gate( "Batching", " .batch(n) -> iterator of lists\n\n" "Lists of length n except possibly the last. n <= 0 raises\n" "ValueError. Must be LAZY: constructing it pulls nothing, and taking\n" "one batch must not read far beyond it. A checkpoint taken after a\n" "yielded batch resumes exactly at the next unemitted item.", ), _gate( "map and filter", " .map(fn) / .filter(pred) chainable, applied in declaration order\n\n" "Transforms are part of the iterator's identity, not of its state, so\n" "you re-declare them on the resumed object. Resume must be EXACT for a\n" "checkpoint taken at every position. The obvious design -- count\n" "emitted outputs, skip that many on resume -- is wrong here and the\n" "tests will catch it. Ask what the checkpoint must describe: a\n" "position in the SOURCE, or in the OUTPUT?", ), _gate( "flat_map and mid-group checkpoints", " .flat_map(fn) one item -> zero or more items\n\n" "Chains with map and filter in any order and depth. A checkpoint may\n" "land INSIDE an expanded group: resuming must not re-emit the\n" "sub-items already emitted from that group, nor skip the remainder.\n" "State stays JSON-serializable and O(1) in size -- asserted after\n" "20k items.", ), ], }, # ----------------------------------------------------------------------- { "id": "job-scheduler-inmem", "title": "In-Memory Job Scheduler", "module": "job_scheduler", "themes": ["scheduling", "concurrency", "state"], "budget_min": 45, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-5-heaps-and-deterministic-scheduling", "gates": [ _gate( "Delayed execution", " Scheduler(clock=time.monotonic)\n" " .schedule(fn, delay=0.0) -> job_id\n" " .cancel(job_id) -> bool\n" " .run_due() -> (ran, errors)\n" " .next_fire_time() -> float | None\n\n" "Heap-backed. run_due() executes everything due at the injected\n" "clock's current time and returns how many ran plus a list of\n" "(job_id, exception). Jobs scheduled for the SAME instant must fire\n" "in insertion order -- deterministically. Think about what heapq does\n" "when it compares two entries whose first elements are equal.", ), _gate( "Recurring jobs", " .schedule(fn, delay, period=P, mode='fixed_delay'|'fixed_rate',\n" " catch_up='run_latest_only'|'run_all'|'skip')\n\n" "fixed_delay re-arms P after the run FINISHES; it never overlaps and\n" "the schedule drifts. fixed_rate fires on the original grid\n" "regardless of run duration. When fixed_rate has fallen behind, the\n" "catch_up policy decides: run every missed occurrence, collapse them\n" "into one, or skip to the next future slot. Surfacing this as a\n" "per-job choice is the point -- a scheduler that silently fires 40,000\n" "overdue jobs after an outage has turned one outage into a worse one.", ), _gate( "Retries with backoff and jitter", " .schedule(..., max_attempts=5, base_backoff=0.2, cap_backoff=30.0)\n" " .dead_letters -> [(job_id, attempts, last_error), ...]\n\n" "A raising job is re-armed after full jitter -- uniform over\n" "[0, min(cap, base * 2**attempt)] -- until max_attempts, then it is\n" "dead-lettered and never runs again. A successful run resets the\n" "attempt counter. Seed the RNG from the constructor so the tests are\n" "deterministic. Be ready to say why jitter alone is not enough.", ), _gate( "Priorities, fairness, drain", " .schedule(..., priority=0, tenant=None, max_concurrency=None)\n" " .drain()\n\n" "Among jobs due at the same instant, lower `priority` runs first, and\n" "ties within a priority stay FIFO. A per-tenant concurrency cap limits\n" "how many of that tenant's jobs one run_due() may execute, so one\n" "tenant cannot consume the whole pass -- the rest stay due. Low\n" "priority must not starve: after N passes a waiting job is promoted.\n" "drain() refuses new schedules and lets already-due work finish.", ), ], }, # ----------------------------------------------------------------------- { "id": "streaming-parser", "title": "Incremental Tokenizer over a Chunked Stream", "module": "streaming_parser", "themes": ["parsing", "streaming", "memory"], "budget_min": 45, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-6-streaming-state-machines-and-chunk-boundaries", "gates": [ _gate( "Chunk-boundary-safe tokenizer", " Tokenizer(delimiters=' \\t\\n\\r,')\n" " .feed(chunk) -> [tokens emitted by this chunk]\n" " .close() -> [trailing tokens]\n\n" "Input arrives in arbitrary chunks. A token split across a boundary\n" "must come out WHOLE and exactly once. Events are tuples beginning\n" "(kind, text); here kind is 'bare'. Gate 3 extends the tuple, so the\n" "tests only compare the first two fields until then.\n\n" "This is the entire problem; everything after it is decoration. A\n" "regex will not do it -- it has no way to say 'no match YET'.", ), _gate( "Quoting and escapes", "Double-quoted strings emit ('string', text). Backslash escapes\n" "inside them: \\n \\t \\r map to those characters, anything else is\n" "itself (so \\\" is a literal quote). A chunk boundary may land\n" "between the backslash and the escaped character, and between any two\n" "characters of a string. close() while inside a string raises\n" "ValueError naming the offset.", ), _gate( "Nesting and offsets", "Emit ('open', ch, depth, offset) for [ and {, and\n" "('close', ch, depth, offset) for ] and }. Every event carries the\n" "absolute byte offset of where its token STARTED, counted across all\n" "chunks. close() with unclosed containers raises ValueError.\n" "Offsets cost one integer and turn 'invalid character' into something\n" "actionable at byte 4,821,993 of a stream.", ), _gate( "Error recovery and a bounded buffer", " Tokenizer(..., max_token_bytes=1<<20, recover=False)\n\n" "A token exceeding max_token_bytes raises ValueError -- unbounded\n" "buffering is a denial-of-service vector, and in this grammar a token\n" "that long is malformed by definition.\n\n" "With recover=True, an unterminated string at close() does not raise:\n" "the parser emits ('error', reason, depth, offset), discards the\n" "partial token, and continues. A ('gap',) marker is emitted whenever\n" "input was dropped, because a silent gap is a correctness bug the\n" "consumer cannot see.", ), ], }, # ----------------------------------------------------------------------- { "id": "spreadsheet-eval", "title": "Spreadsheet Formula Evaluation", "module": "spreadsheet_eval", "themes": ["parsing", "state"], "budget_min": 45, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-7-dependency-graphs-topological-order-cycles", "gates": [ _gate( "Cells and formulas", " Sheet()\n" " .set_cell(name, raw) raw is a number or a '=' formula\n" " .get_value(name)\n\n" "Formulas support + - * / and cell references like A1. A reference to\n" "an unset cell reads as 0. Division by zero yields '#ERROR'. Setting a\n" "cell recomputes whatever depends on it.", ), _gate( "Dependency graph and cycles", "A cycle yields '#CIRCULAR' for every cell in it -- not a\n" "RecursionError. Evaluate in dependency order.\n\n" " .cycle_for(name) -> [cells in the cycle] | None\n\n" "Reporting the actual path (A1 -> B1 -> C1 -> A1) is far more useful\n" "to a user than a flag. You need THREE visit states, not two: a\n" "'visited' set conflates 'on my current path' with 'already finished',\n" "so it either misses cycles or flags legal diamonds as cycles.", ), _gate( "Incremental recomputation", " .evaluations -> int cumulative cell evaluations\n\n" "Editing one cell recomputes ONLY its transitive dependents. The tests\n" "assert the evaluation COUNT, not just the values -- a test that only\n" "checks values passes even when you recomputed the whole sheet, so the\n" "optimization can regress silently. You need the reverse graph, and\n" "you must detach stale reverse edges when a formula changes.", ), _gate( "Ranges and volatile functions", " SUM(A1:A10) MIN(...) MAX(...) COUNT(...)\n\n" "Ranges expand across both rows and columns. A range dependency must\n" "trigger recomputation when ANY cell in it changes.\n\n" " .register_volatile(name, fn) e.g. TICK()\n\n" "A volatile function's value can change without any input changing, so\n" "any cell using one must be recomputed on every recalculation pass --\n" "and .recalc() forces one. Say what that does to your caching story.", ), ], }, # ----------------------------------------------------------------------- { "id": "path-resolver", "title": "Unix Path Resolution with Symlinks", "module": "path_resolver", "themes": ["state", "parsing"], "budget_min": 35, "automated": True, "chapter": "tracks/coding/WARMUP.md#03-the-three-questions-that-pick-the-structure", "gates": [ _gate( "Lexical resolution", " normalize(cwd, path) -> str\n\n" "Pure string resolution, no filesystem. Absolute paths ignore cwd;\n" "relative paths join to it. Collapse '.', apply '..' (and '..' at the\n" "root stays at the root, as the kernel does), squash repeated and\n" "trailing separators. The result is always absolute and never has a\n" "trailing slash except for '/' itself.", ), _gate( "Symlink following", " fs = FileSystem()\n" " fs.mkdir(path); fs.touch(path); fs.symlink(link_path, target)\n" " resolve(fs, cwd, path) -> str\n\n" "Resolve COMPONENT BY COMPONENT: after each component, if it is a\n" "symlink, replace it with its target (absolute targets restart from\n" "the root; relative ones resolve against the link's own directory) and\n" "continue with the remaining components. A missing component raises\n" "FileNotFoundError.", ), _gate( "Loop detection", "A symlink cycle must raise OSError with errno ELOOP after a bounded\n" "number of traversals (default 40, matching Linux's MAXSYMLINKS), not\n" "hang and not recurse forever.\n\n" "Be ready to say why a COUNTER rather than cycle detection: a path can\n" "legitimately traverse the same symlink more than once, so 'have I\n" "seen this link' produces false positives. The kernel bounds work, not\n" "repetition.", ), _gate( "Physical vs logical semantics", " resolve(fs, cwd, path, physical=True) -- like `cd -P`\n" " resolve(fs, cwd, path, physical=False) -- like `cd -L`\n\n" "Logical mode resolves '..' LEXICALLY against the path you typed;\n" "physical mode resolves symlinks first, so '..' moves up the real\n" "tree. Given /a/link -> /b/c, `cd /a/link; cd ..` lands in /a\n" "logically and /b physically. Shells implement logical by default and\n" "that surprises people -- explain which is 'correct' and why the\n" "question is ill-posed.", ), ], }, # ----------------------------------------------------------------------- { "id": "bounded-queue-backpressure", "title": "Async Pipeline with Backpressure", "module": "bounded_queue", "themes": ["concurrency", "streaming"], "budget_min": 45, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-10-backpressure-and-bounded-concurrency", "gates": [ _gate( "Bounded queue and workers", " Pipeline(handler, workers=4, max_queue=100)\n" " await .start()\n" " await .submit(item)\n" " await .shutdown() -> stats dict\n\n" "An asyncio.Queue with a REAL bound, and N worker tasks. stats counts\n" "accepted / done / failed. submit() on a full queue must block the\n" "producer -- that is backpressure, and a test asserts the producer\n" "actually waits rather than the queue growing.", ), _gate( "Graceful shutdown", "shutdown() must: stop accepting new work, DRAIN everything already\n" "queued, and be idempotent (calling it twice is not an error). Nothing\n" "queued before shutdown may be lost. Use one sentinel per worker so\n" "each exits exactly once after the queue empties.", ), _gate( "Timeouts and cancellation", " Pipeline(..., item_timeout=5.0)\n" " await .shutdown(drain_timeout=...)\n\n" "An item exceeding item_timeout is cancelled and counted in\n" "stats['timeout']; the worker survives and takes the next item. After\n" "drain_timeout, shutdown cancels whatever is still running as a hard\n" "deadline. CancelledError is a BaseException -- if you catch it, you\n" "must re-raise, or the worker becomes uncancellable and the deadline\n" "becomes a hang.", ), _gate( "Shedding and error aggregation", " await .submit(item, block=False) raises QueueFull -> shed\n" " .errors -> [exceptions from handlers]\n" " Pipeline(..., shed_after=0.25)\n\n" "With block=True, waiting longer than shed_after also sheds rather\n" "than waiting forever -- an unbounded wait turns a throughput problem\n" "back into an unbounded latency problem. stats['shed'] counts them.\n" "Handler exceptions are collected, not swallowed, and never kill a\n" "worker.", ), ], }, # ----------------------------------------------------------------------- { "id": "wal-store", "title": "Write-Ahead Log and Crash Recovery", "module": "wal_store", "themes": ["state", "memory"], "budget_min": 45, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-8-write-ahead-logs-and-crash-recovery", "gates": [ _gate( "Append-only log with replay", " WriteAheadLog(path)\n" " .append(payload: bytes) -> offset\n" " .replay() -> yields (offset, payload)\n" " .close()\n\n" "Frame each record so it can be read back: a 4-byte little-endian\n" "length, the payload, then a 4-byte CRC32 of the payload. Replay\n" "returns records in append order, across process restarts.", ), _gate( "Torn-write tolerance", "A crash mid-write leaves a PARTIAL record at the tail. That is the\n" "expected post-crash state, not an error.\n\n" "replay() must stop cleanly at the first record that is incomplete\n" "(short header, short payload) or whose CRC does not match, and return\n" "everything before it. .truncate_to_valid() drops the partial tail so\n" "the next append starts clean.\n\n" "The test truncates the file at EVERY byte offset and asserts recovery\n" "always returns a prefix of what was written. Without the CRC, a torn\n" "write whose length happened to be complete reads back as a\n" "valid-looking record full of garbage -- silent corruption.", ), _gate( "Checkpointing and compaction", " .checkpoint(blob: bytes) durable, atomic\n" " .load_checkpoint() -> (blob, offset) or None\n" " .replay(from_offset) only what is newer\n\n" "A checkpoint stores a state blob plus the log offset it covers, so\n" "recovery is 'load the newest checkpoint, replay what is after it'\n" "rather than replaying from the beginning of time.\n\n" "The checkpoint write must be crash-safe: write to a temp file, then\n" "atomically replace. A crash halfway must leave the OLD checkpoint\n" "intact, never a half-written one. The test kills it mid-write.", ), _gate( "Durability policy and group commit", " WriteAheadLog(path, fsync_policy='always'|'group'|'never',\n" " group_size=64, fsync=os.fsync)\n" " .fsync_count -> int\n\n" "'always' syncs per record; 'group' syncs once per group_size records\n" "and on flush()/close(); 'never' relies on the OS. The fsync function\n" "is injectable so the tests can count calls.\n\n" "Group commit is how real databases escape one disk round trip per\n" "commit. Be ready to say what write() guarantees (the kernel accepted\n" "the bytes) versus what fsync guarantees, and what each policy costs.", ), ], }, # ----------------------------------------------------------------------- { "id": "text-index", "title": "Inverted Index with Incremental Updates", "module": "text_index", "themes": ["state", "memory", "streaming"], "budget_min": 45, "automated": True, "chapter": "tracks/coding/WARMUP.md#85-interview-qa", "gates": [ _gate( "Build and query", " Index()\n" " .add(doc_id, text)\n" " .search_all(query) -> sorted doc_ids containing EVERY term\n" " .search_any(query) -> sorted doc_ids containing ANY term\n\n" "Tokenize on non-alphanumerics and lowercase. Build postings lists:\n" "term -> the set of documents containing it. Intersect the SMALLEST\n" "postings list first -- that ordering is most of the query performance\n" "and it is a thing to say out loud.", ), _gate( "Incremental delete", " .delete(doc_id)\n" " .doc_count -> int of LIVE documents\n\n" "Deletion is a tombstone plus a live-docs set, NOT removal from every\n" "postings list -- that would be O(terms in doc) with random access\n" "across the whole index. Searches filter against live docs. Re-adding\n" "a deleted id replaces it. Be ready to say what tombstones cost you\n" "and when they must be reclaimed.", ), _gate( "BM25 ranking", " .search(query, k=10) -> [(doc_id, score), ...] descending\n\n" "Score with BM25 (k1=1.5, b=0.75):\n" " idf = ln(1 + (N - df + 0.5) / (df + 0.5))\n" " tf_part = f * (k1 + 1) / (f + k1 * (1 - b + b * dl / avgdl))\n" "where f is the term frequency in the document, dl its length, avgdl\n" "the mean over live documents, N the live count, df the live document\n" "frequency. Ties break by doc_id ascending so results are\n" "deterministic. Derive it rather than importing it.", ), _gate( "Segments and merging", " .flush() seal the in-memory buffer into an immutable segment\n" " .merge() combine all segments into one, dropping tombstones\n" " .segment_count -> int\n\n" "Writes go to a mutable buffer; flush() seals it. Searches must span\n" "every segment plus the buffer, and a delete in a newer segment must\n" "mask a document from an older one. merge() reclaims tombstoned space.\n" "This is Lucene's actual design, and it is your home turf -- it should\n" "be your fastest problem.", ), ], }, # ----------------------------------------------------------------------- { "id": "event-dedupe", "title": "Exactly-Once Illusion: Windowed Deduplication", "module": "event_dedupe", "themes": ["state", "memory", "streaming"], "budget_min": 40, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-9-deduplication-and-probabilistic-structures", "gates": [ _gate( "Idempotency keys", " ExactDedupe()\n" " .is_duplicate(key) -> bool\n" " .seen_count -> int\n\n" "First sight of a key is new; every repeat is a duplicate. Exact, and\n" "deliberately unbounded. Be ready to explain why exactly-once DELIVERY\n" "is impossible, why at-least-once plus an idempotent consumer is what\n" "you can actually have, and why the key must be generated by the\n" "PRODUCER and stay stable across retries.", ), _gate( "Time-windowed dedupe", " WindowedDedupe(window_seconds, clock=time.monotonic)\n\n" "Bounded memory: forget keys older than the window. Exact WITHIN the\n" "window; a duplicate arriving later gets through, which is the\n" "correctness you traded for the bound. Eviction must be amortized\n" "O(1), not a scan of every key on every call.", ), _gate( "Probabilistic dedupe", " BloomFilter(capacity, error_rate=0.01)\n" " .add(item) / item in filter / .current_fpr()\n\n" "Size it: m = -n*ln(p)/(ln 2)^2 bits and k = (m/n)*ln 2 hashes. NO\n" "false negatives ever; false positives near the target rate; about\n" "1.25 bytes per item at 1%.\n\n" " SafeDedupe(capacity, exact_store, error_rate)\n\n" "For dedupe the error points the DANGEROUS way -- a false positive\n" "drops a real message, silently. So use the filter as a NEGATIVE cache\n" "in front of an exact store: 'definitely absent' is exact and needs no\n" "lookup, 'possibly present' consults the store. Then the filter saves\n" "lookups instead of losing data.", ), _gate( "Ordering and out-of-order arrival", " Reorderer(window, on_gap=None)\n" " .offer(key, seq, payload) -> [payloads now in order]\n" " .flush() -> [remaining, in order]\n\n" "Per-key sequence numbers starting at 0. Buffer out-of-order arrivals\n" "and release them once the gap fills. If the buffer for a key exceeds\n" "`window`, give up on the missing sequences, emit a gap notification,\n" "and continue -- unbounded reordering means unbounded memory, and a\n" "SILENT gap is a correctness bug the consumer cannot see. Duplicates\n" "of an already-released sequence are dropped.", ), ], }, # ----------------------------------------------------------------------- { "id": "async-crawler", "title": "Bounded-Concurrency Async Crawler", "module": "async_crawler", "themes": ["concurrency", "streaming"], "budget_min": 45, "automated": True, "chapter": "tracks/coding/WARMUP.md#chapter-10-backpressure-and-bounded-concurrency", "gates": [ _gate( "Bounded concurrent fetch", " Crawler(fetcher, concurrency=5)\n" " await .crawl(seeds) -> {url: result}\n\n" "`fetcher` is an async callable url -> (body, links). No real network.\n" "At most `concurrency` fetches may be in flight at once -- a test\n" "records the peak and asserts the bound. Fetches must actually run\n" "concurrently, not serially: the test asserts total wall time is far\n" "below the serial sum.", ), _gate( "Frontier, dedupe, depth", " Crawler(..., max_depth=2)\n\n" "Follow links discovered by the fetcher. Normalize before deduping:\n" "strip the fragment, drop a default port, drop a trailing slash on a\n" "non-empty path, lowercase the host. Fetch each normalized URL at most\n" "ONCE even when many pages link to it and even when two workers\n" "discover it simultaneously. Do not follow beyond max_depth.", ), _gate( "Per-host politeness", " Crawler(..., per_host=2)\n\n" "At most `per_host` in-flight fetches per host, in addition to the\n" "global bound. One slow host must NOT stall progress on other hosts --\n" "the test makes one host slow and asserts the others still complete\n" "quickly. That rules out a design that serializes the frontier behind\n" "a per-host lock.", ), _gate( "Retries, deadline, results stream", " Crawler(..., max_attempts=3, base_backoff=0.01, deadline=None)\n" " .failures -> {url: last_exception}\n" " async for url, result in crawler.stream(seeds): ...\n\n" "Retry transient fetch errors with exponential backoff plus jitter.\n" "After max_attempts, record it in failures and move on -- one bad URL\n" "must not fail the crawl. A total deadline stops the crawl cleanly,\n" "cancelling in-flight work and returning what completed. stream()\n" "yields results as they arrive so the consumer can throttle.", ), ], }, # ----------------------------------------------------------------------- { "id": "object-pool", "title": "Memory-Efficient Object Pool", "module": "object_pool", "themes": ["memory", "concurrency"], "budget_min": 35, "automated": True, "chapter": "tracks/python-internals/WARMUP.md#chapter-5-memory", "gates": [ _gate( "Acquire and release", " Pool(factory, size)\n" " with pool.acquire() as obj: ... returns on exit, even on error\n" " .available / .in_use\n\n" "Bounded: at most `size` objects exist. acquire() blocks when the pool\n" "is exhausted until something is returned, with an optional timeout\n" "raising PoolExhausted. Objects are created lazily. Release must be\n" "guaranteed by the context manager -- a raising body still returns the\n" "object.", ), _gate( "Slots and measured footprint", " Pooled a slotted class the pool hands out\n" " measure_footprint(cls, n) -> bytes via tracemalloc\n\n" "The pooled class must use __slots__ and therefore have NO __dict__ --\n" "the test asserts both, and asserts a slotted class measurably beats\n" "an unslotted one over 100k instances. Also assert the subclass trap:\n" "a subclass that omits __slots__ regains a __dict__ and loses the\n" "saving. Measure; do not claim.", ), _gate( "Buffer reuse without copying", " BufferPool(block_size, count)\n" " with bp.acquire() as view: ... a memoryview, zero-copy\n" " .backing -> the single bytearray behind every block\n\n" "One bytearray is allocated up front and carved into `count` blocks.\n" "acquire() returns a memoryview slice -- writes through it mutate the\n" "backing store, and a test asserts acquiring allocates essentially\n" "nothing under tracemalloc. Releasing must also release the view so\n" "the buffer can be resized later.", ), _gate( "Leak detection with weakrefs", " .leaked() -> int objects handed out and never returned,\n" " whose last user reference has been dropped\n" " .checkout_sites() -> {id: traceback-ish tag}\n\n" "Track handed-out objects with weakref.finalize so detection does NOT\n" "keep them alive -- a strong reference would make every leak\n" "undetectable by definition, and a test asserts the pool holds no\n" "strong reference. Be ready to say why weakref.finalize beats __del__\n" "here: ordering within a cycle is undefined, exceptions are swallowed,\n" "and the object can resurrect itself.", ), ], }, ] def load_problem(entry: dict) -> dict: """Attach gate test callables from the problem's module.""" if not entry.get("automated"): return entry module = importlib.import_module(f"problems.{entry['module']}") resolved = dict(entry) resolved["path"] = os.path.join(HERE, entry["module"]) resolved["gates"] = [ {**gate, "test": test} for gate, test in zip(entry["gates"], module.GATE_TESTS) ] return resolved for _entry in CATALOG: _entry.setdefault("path", os.path.join(HERE, _entry["module"] or "")) _entry.setdefault("chapter", "")