Practical coding rounds: key-value store, LRU cache, rate limiter, crawler

Before this lesson: lesson 01 (hash maps and their average $O(1)$ cost), lesson 03 (pointers, breadth-first search). Python classes, dict, collections.deque, and the basics of asyncio. Time: about 70 minutes, plus the notebook. Notation: $n$ is the number of keys or items; $C$ is a cache capacity.

---

Why this matters #

Some companies now test "practical" coding instead of short puzzles. A typical format is one project of 60–90 minutes with three or four parts, for example an in-memory database, where each part builds on your code. Other common tasks are an LRU cache, a time-based key-value store, a rate limiter, and a web crawler that starts sequential and must then fetch pages concurrently. Some companies also have a round where you work in a codebase you did not write, sometimes with an AI assistant allowed.

These rounds do not test rare algorithms. They test whether you turn a specification into correct, tested code quickly, and whether your design survives the next requirement. The same building blocks run ML systems: an LLM inference server evicts cached key-value blocks in least-recently-used order, LLM APIs limit clients with token buckets, and pretraining data comes from crawlers.

1. Predict first #

2. The picture #

One class that grows. Part 1 asks for the basic API. Part 2 adds a requirement (expiry, a query, concurrency). Part 3 adds another (transactions, retries, durability). The old tests must still pass. A design that copies all data in part 3, or reads the real clock in part 2, makes the next part slow or impossible to test.

A dict plus one more structure. Choose the state so that every operation is cheap, then write the invariant as a comment at the top of the class.

Task	State	Invariant	Cost per operation
key-value store	dict + a stack of undo maps	the dict is the current view; an undo map holds the value before its level first touched each key	$O(1)$ on average
LRU cache	dict key → node + doubly linked list	dict and list hold the same keys; list order = order of last use; size $\le C$	$O(1)$
token bucket	per client: tokens $\tau$ and the time $t_0$ of the last update	$0 \le \tau \le b$	$O(1)$
crawler	queue (the frontier) + set (seen)	a URL enters the queue at most once; fetches in flight $\le$ limit	$O(1)$ per URL, plus the fetch

The working loop for each part (about 15–25 minutes):

1. Read the part to the end. Restate the API. Ask about edge cases: a missing key? an overwrite? Does a key expire at $t \ge$ expiry or at $t >$ expiry?
2. Choose the state. Write the invariant as a comment.
3. Write the smallest code that passes. Use clear names and no clever tricks.
4. Run all tests, the old parts too. Add one test for the edge case you asked about.
5. Say the cost of each operation before you move on.

The LRU cache as a picture. A least recently used (LRU) cache keeps at most $C$ keys. When a new key arrives and the cache is full, it evicts (removes) the key that was used longest ago. The figure shows the two parts of its state: the dict on top points into a list that keeps the keys in order of use.

Interactive figure: loading…

3. Definitions and main results #

3.1 Inject time and I/O #

Expiry, rate limits and timeouts depend on time. With the real clock, a test must sleep, so it is slow and sometimes fails at random. So the constructor takes a clock argument: a function that returns seconds, by default time.monotonic. A test passes a fake clock and moves it by hand. A crawler receives its fetch function in the same way. This is dependency injection: the core logic does not know where time or data come from.

class FakeClock:
    """A clock that a test moves by hand; pass it where code expects time.monotonic."""
    def __init__(self, start: float = 0.0) -> None:
        self.t = start
    def __call__(self) -> float:
        return self.t
    def advance(self, dt: float) -> None:
        self.t += dt

clock = FakeClock()
clock.advance(2.5)
print(clock())   # 2.5

Measure durations with time.monotonic, not time.time. The wall clock (time.time) can jump backward or forward, for example after a network time correction; the monotonic clock never goes back.

3.2 A key-value store in levels #

• Level 1: a dict. get, set and delete cost $O(1)$ on average.

• Expiry (TTL, "time to live"), a common level 2. Store (value, expires_at). A key is alive while now < expires_at. Check expiry lazily: on every read, and delete the key if it has expired. If memory matters, also keep a heap of (expires_at, key) and pop expired entries from time to time. Skip a heap entry whose time no longer matches the stored one: the key was overwritten later.

• Queries. count(value) in $O(1)$ needs a second dict that counts values. Every set and delete updates it, and so does every rollback (so a rollback must use the same code path). scan(prefix) may sort the matching keys, $O(n \log n)$.

• Nested transactions. begin starts a transaction, rollback undoes it, commit keeps it, and transactions can be nested. begin must be $O(1)$, so it must not copy the data. Instead keep a stack of undo maps. The undo map of a level stores, for each key the level has written, the value before this level first touched it, or a marker MISSING if the key did not exist.

  • On a write, record the old value only if the key is not yet in the top undo map (first touch).
  • rollback writes the top undo map back into the data (MISSING means: delete the key) and pops it.
  • commit pops the top map and merges it into the parent map with one rule: copy a key into the parent only if the parent has no entry for it. At the outermost level there is no parent: drop the map, because the data already holds the result.

  Reads stay $O(1)$, because the data dict is always the current view. A write costs $O(1)$; rollback and commit cost $O(\text{keys in the top map})$. No cost depends on the depth.

Why the commit rule is right. The parent's entry for a key is the value from before the parent first touched it. A later rollback of the parent must restore exactly that value. The child's entry is only the value from before the child touched the key, which may already contain the parent's own write. So the parent's entry wins. If the parent has no entry, the parent never wrote the key, so the value before the child is also the value before the parent: copy it up.

Interactive figure: loading…

The other design: overlays. Keep a stack of overlay dicts that hold the new writes of each level, with a delete marker. begin is also $O(1)$, and commit merges the top overlay into the one below. But a read must search the stack from the top down, so a read costs $O(\text{depth})$. Say both designs in an interview, and choose undo maps when reads are frequent.

Durability: an append-only log

To survive a crash, append one line per committed batch to a log file: a single write outside a transaction, or a whole outermost transaction. Write the line with one write, then call flush and os.fsync. One line per batch keeps a transaction atomic on disk. On start, replay the log. A last line without "\n" is a torn write (the process died while writing it): ignore it. To compact the log, write a snapshot to a temporary file and move it into place with os.replace, which is atomic on POSIX file systems, so a reader sees either the old file or the new one, never half of it.

3.3 The LRU cache #

State. A dict from key to node, and a doubly linked list of the nodes in order of use. Two sentinel nodes, head and tail, sit at the ends: the least recently used (LRU) node is right after head, the most recently used (MRU) node is right before tail. A "use" is a get that finds the key, or any put.

• get(k): find the node in the dict, unlink it, insert it before tail. $O(1)$.
• put(k, v): update or create the node and move it before tail. If the size is now $C + 1$, unlink the node after head and delete its key from the dict. $O(1)$.
• Why doubly linked: to unlink a node you need its predecessor. A singly linked list must search for it, which costs $O(n)$.
• Why the node stores its key: on eviction you hold the node, and you must delete its key from the dict.
• Why sentinels: the list is never empty, so insert and unlink need no special cases.

class Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=None, val=None):
        self.key, self.val, self.prev, self.next = key, val, None, None

class LRUCache:
    """dict: key -> node; list: head <-> ... <-> tail, LRU next to head, MRU next to tail."""
    def __init__(self, capacity: int):
        self.cap, self.map = capacity, {}
        self.head, self.tail = Node(), Node()           # sentinels: the list is never empty
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, n):
        n.prev.next, n.next.prev = n.next, n.prev

    def _push_mru(self, n):                              # insert just before tail
        n.prev, n.next = self.tail.prev, self.tail
        self.tail.prev.next = n
        self.tail.prev = n

    def get(self, key):
        n = self.map.get(key)
        if n is None:
            return None
        self._unlink(n); self._push_mru(n)               # a hit makes the key most recent
        return n.val

    def put(self, key, val):
        n = self.map.get(key)
        if n is not None:
            n.val = val; self._unlink(n)
        else:
            n = self.map[key] = Node(key, val)
        self._push_mru(n)
        if len(self.map) > self.cap:
            lru = self.head.next                         # least recently used
            self._unlink(lru); del self.map[lru.key]     # the node must know its key

c = LRUCache(2)
c.put("a", 1); c.put("b", 2); c.get("a"); c.put("c", 3)
print(c.get("b"), c.get("a"), c.get("c"))               # None 1 3

In Python, collections.OrderedDict with move_to_end(key) and popitem(last=False) gives the same behaviour in a few lines. Say so, but expect the interviewer to ask for the hand-written list.

3.4 Rate limiters and the token-bucket bound #

A rate limiter decides, for each request of a client, whether to allow or reject it. A token bucket has a capacity $b$ (tokens) and a refill rate $r$ (tokens per second). For each client it stores two numbers: the tokens $\tau$ and the time $t_0$ of the last update. A request with cost $c$ at time $t$ does:

1. refill: $\tau \leftarrow \min(b,\ \tau + r\,(t - t_0))$, then $t_0 \leftarrow t$;
2. decide: if $\tau \ge c$, set $\tau \leftarrow \tau - c$ and allow; otherwise reject and take nothing.

No timer thread is needed: the refill is computed when a request arrives (lazy refill). The capacity $b$ is the largest burst; the rate $r$ is the long-run limit.

Theorem (burst bound). If every request costs 1 token, a token bucket allows at most $b + rT$ requests in any time window $[s, s + T]$.

Proof.

1. At time $s$, after the refill and before any request of the window, the bucket holds $\tau(s) \le b$ tokens.
2. During the window, the refill adds at most $rT$ tokens. (The cap at $b$ can only remove tokens.)
3. Each allowed request removes one token, and $\tau$ never goes below 0.
4. So the number of allowed requests is at most $\tau(s) + rT \le b + rT$. $\blacksquare$

The bound is reached: with $b = 4$ and $r = 1$, send 4 requests at $t = 0$ and one at each of $t = 1, \dots, 5$. All 9 pass, and $b + rT = 4 + 5 = 9$ for $T = 5$.

Interactive figure: loading…

The other common limiters, for a limit of $N$ requests per window of length $W$:

Limiter	State per client	Behaviour
fixed window	one counter for the current window	cheap; allows up to $2N$ requests in a short time around a window boundary
sliding-window log	timestamps of the last $N$ requests	exact; memory $O(N)$ per client
sliding-window counter	counters of the current and the previous window	estimate $=$ previous $\times$ (part of the previous window still inside) $+$ current; close to exact, $O(1)$
leaky bucket (as a queue)	a queue drained at a constant rate	smooth output; adds delay
token bucket	$\tau$, $t_0$	bursts up to $b$, long-run rate $r$

3.5 A concurrent crawler #

• Part 1, sequential BFS. A queue (deque) holds the frontier, and a set holds the URLs seen. Normalize a URL before the check: resolve relative links, drop the #fragment, lowercase the scheme and the host. Mark a URL as seen when you discover it, not when you fetch it; otherwise the same URL can enter the queue many times. Follow only links on the start host.
• Part 2, concurrency. Fetching waits on the network (it is I/O-bound), so run many fetches at once with asyncio (or threads). Limit them with an asyncio.Semaphore, or with $N$ worker tasks that read from an asyncio.Queue: await queue.join(), then cancel the workers.
• Why the seen check needs no lock in asyncio. The event loop runs one task at a time and switches tasks only at an await. With no await between if url not in seen and seen.add(url), the pair runs without interruption. With threads it is not safe: another thread can run between the two lines, so use a lock.
• Part 3, failures. Catch errors per page, set a timeout per attempt (asyncio.timeout in Python 3.11+), retry a few times with backoff (wait longer after each failure), and record the failed URLs. Never catch BaseException: it also catches asyncio.CancelledError, and then cancellation stops working. One blocking call (time.sleep, requests.get) inside a coroutine stops every task; move it to a thread with asyncio.to_thread.

import asyncio

LINKS = {"/": ["/a", "/b"], "/a": ["/b", "/c"], "/b": ["/a", "/c"], "/c": ["/"]}

async def fake_fetch(url):
    await asyncio.sleep(0.01)                            # pretend network delay
    return LINKS.get(url, [])

async def crawl(start, fetch, n_workers=3):
    seen, queue, order = {start}, asyncio.Queue(), []
    queue.put_nowait(start)

    async def worker():
        while True:
            url = await queue.get()
            try:
                for link in await fetch(url):
                    if link not in seen:                 # no await between check and add:
                        seen.add(link)                   # this pair cannot be interrupted
                        queue.put_nowait(link)
                order.append(url)
            finally:
                queue.task_done()

    workers = [asyncio.create_task(worker()) for _ in range(n_workers)]
    await queue.join()                                   # every queued URL is done
    for w in workers:
        w.cancel()
    await asyncio.gather(*workers, return_exceptions=True)
    return order

print(sorted(asyncio.run(crawl("/", fake_fetch))))      # ['/', '/a', '/b', '/c']

The number of workers is the concurrency limit: at most n_workers fetches are in flight.

3.6 Unfamiliar code, with or without an AI assistant #

1. Run the tests first. See what passes and what fails before you read anything.
2. Find the entry points (main, the public classes) with a text search, and follow one request from end to end through the files.
3. Reproduce a bug with a failing test, fix it, and keep the test.
4. Make the smallest change that does the job, then run the whole test suite again.
5. With an AI assistant: ask narrow questions ("where is X parsed?", "write a test for Y"), read every line it returns, and run it. Check the edge cases it may skip. The interviewer grades how you solve the problem and how you verify the result, not your prompts. Never let a tool change the tests to make them pass; check the diff of the test folder (git diff tests/) before you accept a change.

Answers to section 1. (1) None, a miss. get(a) made a the most recent key, so put(c) evicted b. (2) 5 pass at $t = 0$, and the bucket is empty. At $t = 3$ it holds $\min(5, 0 + 3 \cdot 1) = 3$ tokens, so 3 pass.

4. Worked example #

Nested transactions, step by step. The store starts as {a: 1}. U1 and U2 are the undo maps of depth 1 and 2; – means MISSING (the key did not exist).

Step	Data after the step	Undo stack after the step
begin()	{a: 1}	U1 = {}
set(a, 2), set(b, 5)	{a: 2, b: 5}	U1 = {a: 1, b: –}
begin()	{a: 2, b: 5}	U1, U2 = {}
set(a, 3), delete(b)	{a: 3}	U1, U2 = {a: 2, b: 5}
rollback()	{a: 2, b: 5}	U1 = {a: 1, b: –}
begin(), set(a, 4)	{a: 4, b: 5}	U1, U2 = {a: 2}
commit()	{a: 4, b: 5}	U1 = {a: 1, b: –}
rollback()	{a: 1}	empty

Step by step:

1. set(a, 2) is the first write to a at depth 1, so U1 records a: 1. set(b, 5) records b: –, because b did not exist.
2. At depth 2, set(a, 3) records the current value a: 2 in U2, and delete(b) records b: 5.
3. rollback() writes U2 back: a becomes 2 and b becomes 5 again. U2 is popped.
4. A new U2 records a: 2 for set(a, 4).
5. commit() merges U2 = {a: 2} into U1 = {a: 1, b: –}. U1 already has a, so it keeps a: 1 and drops a: 2.
6. The last rollback() writes U1 back: a becomes 1 and b is deleted. The store is {a: 1}, as before the first begin().

Before you read on: if commit() had copied a: 2 into U1, what would the last rollback() give? It would give {a: 2}: the outer transaction would not undo its own write set(a, 2).

The token bucket in numbers ($b = 5$, $r = 1$ token/s, full at $t = 0$):

• $t = 0$: 10 requests. 5 pass; $\tau = 0$.
• $t = 2.5$: refill to $\min(5,\ 0 + 1 \cdot 2.5) = 2.5$. Of 3 requests, two pass ($\tau = 1.5$, then $0.5$) and the third is rejected, because $0.5 < 1$. It could pass after $(1 - 0.5)/r = 0.5$ s.
• $t = 10$: refill to $\min(5,\ 0.5 + 1 \cdot 7.5) = 5$. One request passes; $\tau = 4$.
• Check the theorem: 7 requests passed in $[0, 2.5]$, and the bound is $b + rT = 5 + 2.5 = 7.5$. ✓

5. In code #

The Python standard library has real versions of two of these ideas, so you can check the hand work above. SQLite savepoints are nested transactions:

import sqlite3

db = sqlite3.connect(":memory:", isolation_level=None)   # we control the transactions
run = db.execute
run("CREATE TABLE kv (k TEXT PRIMARY KEY, v INTEGER)")
run("INSERT INTO kv VALUES ('a', 1)")
def put(k, v): run("INSERT OR REPLACE INTO kv VALUES (?, ?)", (k, v))
def show(): print(dict(run("SELECT k, v FROM kv ORDER BY k")))

run("SAVEPOINT t1"); put("a", 2); put("b", 5); show()                 # {'a': 2, 'b': 5}
run("SAVEPOINT t2"); put("a", 3); run("DELETE FROM kv WHERE k = 'b'"); show()   # {'a': 3}
run("ROLLBACK TO t2"); run("RELEASE t2"); show()                      # {'a': 2, 'b': 5}
run("SAVEPOINT t2"); put("a", 4); run("RELEASE t2"); show()           # {'a': 4, 'b': 5}
run("ROLLBACK TO t1"); run("RELEASE t1"); show()                      # {'a': 1}

RELEASE is the commit of a savepoint. ROLLBACK TO undoes it but keeps it open, so a RELEASE follows. functools.lru_cache replays question 1 of section 1: each call is a get, and a miss also does a put.

from functools import lru_cache

loads = []                                  # keys that missed and were loaded

@lru_cache(maxsize=2)
def load(key):
    loads.append(key)
    return key.upper()

for key in ["a", "b", "a", "c", "b"]:
    load(key)
print(loads)               # ['a', 'b', 'c', 'b']: the second 'b' missed
print(load.cache_info())   # CacheInfo(hits=1, misses=4, maxsize=2, currsize=2)

The notebook asks you to write LRUCache, TokenBucket, the transactional KVStore and crawl yourself, and tests each one against a simple reference on random inputs.

6. Where it shows up #

• LLM serving. Inference servers such as vLLM cache the key-value blocks of earlier requests (prefix caching). When memory runs out, they evict a block that no running request uses, least recently used first (lesson 13).
• APIs. LLM APIs limit requests and tokens per minute per client. A token bucket is the usual model: capacity refills continuously instead of resetting at fixed times. A client needs retries with backoff and should respect the retry-after header of a rejected request.
• Data pipelines. Pretraining corpora come from crawlers: URL normalization, deduplication, a rate limiter per host (to be polite to the site), and retries.
• ML for science and HPC. Climate and seismic data portals limit requests per user, so a download script needs a limiter and retries. Expensive, deterministic simulator calls are cached with lru_cache. A training checkpoint is written to a temporary file and moved into place with os.replace, so a job that the scheduler kills never leaves a half-written checkpoint (the same idea as the log compaction in 3.2).

7. Common mistakes #

• A design that blocks the next part. Copying the whole dict in begin ($O(n)$ per transaction), or reading the global clock instead of an injected one.
• Not running the old tests after a new part.
• LRU. A get that does not update the order of use; a node without its key; a singly linked list; the insertion order of a plain dict used as the order of use, without moving the key on every use.
• Token bucket. A refill without the cap $b$; taking tokens from a rejected request; time.time() instead of time.monotonic().
• Transactions. A commit that overwrites the parent's entries; a rollback that does not update a value counter.
• Crawler. Marking URLs as seen at fetch time; no normalization (/a and /a#top fetched twice); no concurrency limit; except BaseException; a blocking call inside a coroutine.
• AI assistant. Accepting code without running it; letting it edit the tests.
• Silent errors. Returning None for a bad input without saying so. Decide early whether the API raises an exception or returns a value, and write it in the docstring.

8. Check yourself #

1. Why does an LRU cache use a doubly linked list, and why does each node store its key?
   Answer

   Unlinking a node in $O(1)$ needs its predecessor, which a singly linked list can only find by a scan. On eviction you hold the LRU node and must delete its key from the dict, so the node must know its key.
2. A token bucket has $b = 10$, $r = 2$ tokens/s and starts full. What is the largest number of unit-cost requests it can allow in $[0, 5]$ s? Give a sequence that reaches it.
   Answer

   $b + rT = 10 + 2 \cdot 5 = 20$. It is reached by 10 requests at $t = 0$, then 2 requests at each of $t = 1, 2, 3, 4, 5$.
3. A fixed-window limiter allows 100 requests per minute, and the windows start at whole minutes. How many requests can it allow within one interval of 60 seconds?
   Answer

   200: 100 at the end of one window (say at 0:59.9) and 100 at the start of the next (1:00.0), so 200 within 0.1 s.
4. In an asyncio crawler, two tasks find the same URL at almost the same time. Why is if url not in seen: seen.add(url); queue.put_nowait(url) safe? When is it not safe?
   Answer

   The event loop switches tasks only at an `await`, and there is none between the check and the add, so no other task runs in between. It is not safe with threads, or if an `await` that can suspend sits between the check and the add (for example `await fetch(url)`, or `await queue.put(url)` on a full bounded queue, before `seen.add(url)`).
5. Your store has count(value) in $O(1)$ with a counter dict. After begin, set(a, 7), rollback, count(7) returns 1, but a no longer has the value 7. What is the bug?
   Answer

   The rollback writes the old values straight into the data dict and does not update the counter. Make rollback use the same internal `set`/`delete` path as the public methods (without recording undo entries), so the counter stays equal to the counts of the values in the data.
6. An AI assistant returns a patch that makes all failing tests pass. What do you check before you accept it?
   Answer

   That the diff does not touch or weaken the tests; that you read and understand every changed line; that the whole suite passes again; that a test reproduces the original bug; and the edge cases it may have skipped (empty input, errors, limits).

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What is the state of an LRU cache, and what do get and put cost?

   Show answer

2. Why does an LRU cache need a doubly linked list?

   Show answer

3. Why does each LRU node store its key?

   Show answer

4. Write the token-bucket update for a request at time $t$.

   Show answer

5. How many unit-cost requests can a token bucket allow in a window of length $T$?

   Show answer

6. What is the weakness of a fixed-window rate limiter with limit $N$?

   Show answer

7. What does the undo map of a transaction level store?

   Show answer

8. What is the commit rule for nested undo maps?

   Show answer

9. Why inject the clock into a class with expiry or rate limits?

   Show answer

10. Why does if url not in seen: seen.add(url) need no lock in asyncio, but a lock with threads?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

Which structure for which wording.

The problem says …	Try …
"evict the least recently used", "cache with capacity"	dict + doubly linked list (or OrderedDict)
"at most N requests per …", "allow bursts"	token bucket per client, with an injected clock
"expires after t seconds"	(value, expires_at) with a lazy check; a heap of expiry times if memory matters
"begin / commit / rollback", "undo"	stack of undo maps (or overlays)
"value of key at timestamp t"	dict of lists sorted by time, then bisect
"count keys with value v"	a second dict that counts values, updated on every write
"visit every page once", "in parallel"	BFS + seen set (mark at discovery) + semaphore or worker tasks
"must survive a crash"	append-only log, fsync per commit, replay on start

The routine to say aloud for each part. "Let me restate the API … I will ask two edge cases … The state is … and the invariant is … Here is the smallest version … I run all tests, the old ones too … Each operation costs …"

Typical questions and short model answers.

• "Make the LRU cache thread-safe." Put one lock around every method, get too, because get changes the order. If there is too much contention, shard the cache by a hash of the key, with one lock and one list per shard. The cost is that the LRU order is then only per shard.
• "Run the rate limiter on 50 servers." Either keep one bucket per key in a shared store with an atomic update (for example a Redis script that does refill and decide in one step), or give each server a local bucket with rate $r/50$. The shared store is exact but adds latency and a central point of failure; local buckets are fast but inexact when the load is uneven.
• "The crawler must handle $10^9$ URLs." The seen set no longer fits in memory. Store 8-byte hashes of normalized URLs, or use a Bloom filter (a false positive skips a page; there are no false negatives). Partition the URLs by host over machines, so each host has one rate limiter.
• "Make the store survive a crash." Append-only log, fsync per commit, replay on start, ignore a torn last line, compact with a snapshot and os.replace.
• "Add a TTL to the LRU cache." Store the expiry time in the node; a get of an expired key deletes it and returns a miss. Eviction order stays LRU; for "expire first", keep a heap of expiry times with lazy deletion.

Typical follow-ups. What happens at capacity 0 or 1? Which exception does commit raise without an open transaction? Is a key alive at exactly expires_at? What is the memory per client of each limiter? How do you test the concurrent crawler (a fake fetch that records how many calls are in flight)?

10. Practice #

The notebook for this lesson runs in Colab. Each exercise has a check cell and a folded solution:

1. LRUCache with a dict and a doubly linked list, tested against a slow list-based model on random operations.
2. TokenBucket with an injected fake clock, tested on the worked example and on the $b + rT$ bound for random arrival times.
3. KVStore with nested transactions (undo maps), tested against a copy-based reference on random operation sequences.
4. crawl: a sequential BFS with an injected fetch on a small in-memory link graph, with URL normalization; the concurrent version is an optional extension.

Timed practice (25 minutes each), problem names from public lists: LRU Cache (146), LFU Cache (460), Time Based Key-Value Store (981), Design Hit Counter (362), Logger Rate Limiter (359), Web Crawler Multithreaded (1242), Snapshot Array (1146).

Say it aloud (3 minutes): explain to an imaginary interviewer the commit rule for nested undo maps, with the example parent {a: 1} and child {a: 2, c: MISSING}, and why the parent's entry wins.

11. Watch and read #

LRU Cache - Twitch Interview Question - Leetcode 146NeetCode · 18 min

The dict plus doubly linked list with two sentinel nodes, drawn and coded step by step.

Rate Limiter System Design: Token Bucket, Leaky Bucket, ScalingByteByteGo · 8 min

The common limiters side by side, and how to run a limiter on many servers.

Intro to async Python | Writing a Web CrawlermCoding · 14 min

A concurrent crawler with asyncio, a queue of URLs and worker tasks.

• Stripe engineering blog, Scaling your API with rate limiters: the token bucket in production, the concurrent-request limiter and load shedding.
• Cloudflare blog, How we built rate limiting capable of scaling to millions of domains: the sliding-window counter and its error.
• Python documentation: asyncio queues (with a worker-pool example), asyncio synchronization primitives (Semaphore, Lock), collections.OrderedDict, functools.lru_cache and time.monotonic.
• SQLite documentation, SAVEPOINT: nested transactions with SAVEPOINT, RELEASE and ROLLBACK TO.