Worked solutions

Read the warning before you read the solutions.

These are not answer keys. There is no correct answer to a system design question — there is only a defended answer, and an answer you did not derive yourself cannot be defended under follow-up questions.

An interviewer will go three levels deeper than anything written here. If your design is recalled rather than reasoned, the third question exposes it, and the round is worse than if you had never seen the problem — because now you sound confident and shallow.

How to use this file

1. Run the problem yourself first: 45 minutes, spoken, timed, per the framework in 03-system-design-curriculum.md.
2. Write your self-critique in 05-practice-log.md before opening this.
3. Then read, and diff the reasoning. Where did this one commit to something you left vague? What did it reject, and why?
4. Re-run the same problem a week later, cold. The second run is the one that tells you whether you learned anything.

Each solution below is written as a compressed transcript — roughly what a strong 45-minute answer covers, in the order it would be covered. They are compressed: spoken, each of these is 45 minutes of talking.

Where a solution says “I’d ask”, that is a real question to put to the interviewer, not a rhetorical device. The answer may change the design, and that is the point of asking.

Contents

Tier 1 — foundational

1. URL shortener
2. Rate limiter
3. Web crawler
4. Search autocomplete

Tier 2 — the classics 5. News feed 6. Chat / messaging 7. Distributed cache 8. Video streaming

Tier 3 — Google-flavored 9. Google Drive / Dropbox 10. Distributed job scheduler 11. Metrics and monitoring 12. Ad click aggregator

1. URL shortener

Scope (0–5)

I’d ask: custom aliases? analytics? expiry? authenticated users or public?

Functional: create a short link for a long URL; redirect; optional custom alias; per-link click analytics. Out of scope: auth, abuse/malware scanning, billing. I’d name them so the interviewer can pull one back in.

Non-functional: read-heavy by a wide margin; redirect p99 under 50 ms; availability matters much more than consistency — a link that 500s is worse than a link whose click count is a few seconds stale; links are effectively permanent.

Estimate (5–10)

100M new links/day → ~1,200 writes/sec. At 100:1 read/write (I’d state this as an assumption) → ~120K reads/sec, peak ~350K.

Storage: ~500 bytes/link × 100M/day ≈ 50 GB/day, ~18 TB/year.

That number changes a decision: 18 TB/year does not fit one machine comfortably over a five-year horizon, so I’m sharding for capacity — but the working set is far smaller. Link popularity is heavily skewed, so caching the hot few percent serves most reads. That is the single biggest latency lever here.

Key space: base62, 7 characters → 62⁷ ≈ 3.5 × 10¹² — decades of headroom.

API and data model (10–15)

POST /links        { longUrl, customAlias?, expiresAt? } -> { shortUrl }
GET  /{code}       -> 302 redirect
GET  /links/{code}/stats -> { clicks, byDay, byCountry }

Entity: code (PK) | longUrl | ownerId | createdAt | expiresAt.

Only access pattern on the hot path is point lookup by code. No joins, no ranges, no secondary index needed. That is a key-value store, and I’d say so explicitly — the access pattern chose the storage, not the scale.

High-level design (15–30)

Split read and write paths: they have completely different scaling profiles (100:1) and different availability requirements. This is one of the few cases where splitting early is genuinely justified rather than cargo-culting.

ID generation — three options, and this choice carries the round:

I’d pick the counter, sharded in blocks. Each server leases a range of 10,000 IDs from a coordination service and hands them out locally — that removes the per-write round trip while keeping codes short. To fix enumerability I’d scramble the counter through a fixed permutation (a Feistel network or simple XOR-shift) before base62 encoding, so codes are non-sequential without needing collision handling. That’s cheap and kills the obvious objection.

Redirect: 302, not 301. 301 is cacheable indefinitely, which means the browser stops asking us and analytics silently stop working. 302 costs a round trip and keeps every click observable. If analytics were dropped from scope I’d switch to 301 and let the CDN absorb everything.

Analytics are strictly off the hot path: the redirect emits an event to a queue and returns immediately. Counting must never be able to slow down or break a redirect.

Deep dive (30–40) — read latency

Layered: CDN/edge for the hottest links → distributed cache → KV store. Cache hit rate should exceed 95% given the popularity skew.

A cold-start or cache-node loss causes a stampede onto storage. Mitigations: request coalescing so one miss recomputes while the rest wait, jittered TTLs so keys don’t expire together, and negative caching for codes that don’t exist — otherwise GET /whatever is a free cache bypass and a trivial DoS.

Sharding by code is naturally uniform because the codes are effectively random after the permutation. No hot shard by construction — worth pointing out, since it is a consequence of the earlier ID decision.

Failures and wrap (40–45)

• Cache tier down: storage absorbs the load. It must be provisioned to survive that, or the cache is a single point of failure wearing a disguise.
• Storage down: redirects fail. Multi-region replication, async — a few seconds of RPO is fine for immutable links.
• ID coordination service down: servers keep serving from their leased block. With a 10,000-ID block, an outage of minutes is invisible. Graceful degradation by design.
• Expiry: a background sweep, not a foreground check. Deleting 100M rows/day needs to be a batch job with throttling.

With more time: malware scanning on creation, per-owner rate limits, and a reserved-word list so /admin can’t be claimed.

2. Rate limiter

Scope (0–5)

I’d ask: limiting what — users, API keys, IPs? Is this a shared library or a service? Must the limit be exact? What happens when the limiter itself fails?

That last question is the most important one and almost nobody asks it.

Functional: per-key limits, multiple tiers, correct 429 with Retry-After. Non-functional: adds < 5 ms to p99 (it sits on every request, so its own latency is a tax on everything); must not be a single point of failure; approximate is acceptable.

Estimate (5–10)

1M req/sec peak across 10M distinct keys. Per-key state is tiny — a token count and a timestamp, ~50 bytes → 500 MB for all 10M keys.

That estimate changes the design: it fits in memory on a single Redis node, so I do not need a distributed counter scheme. I’d say that explicitly, because the instinct is to over-engineer this.

API and data model (10–15)

check(key, cost=1) -> { allowed, remaining, retryAfterMs }

State per key: { tokens, lastRefillMs }.

High-level design (15–30)

Enforce at the API gateway, before authentication for IP limits and after it for user limits. Two layers, because you cannot authenticate a request you are trying to cheaply reject.

Algorithm: token bucket. It allows legitimate bursts, which matters — a client that batches five calls on page load is not abusive, and a strict leaky-bucket smoother would reject them. Configuration is two numbers (capacity, refillRate) which is easy to reason about and to explain to customers.

Rejected alternatives, stated with reasons:

• Fixed window — permits 2× the limit across a boundary. labs/ contains a test that demonstrates this precisely.
• Sliding window log — exact, but stores a timestamp per request. At 1M req/sec that is unaffordable.
• Sliding window counter — a good compromise; I’d choose it if bursts had to be suppressed rather than tolerated.

Refill is lazy, computed from elapsed time on access. A timer per key does not scale to 10M keys; lazy refill is O(1) per request with no background work.

Deep dive (30–40) — distributed correctness

The whole problem is that N gateway instances share one limit.

Option A — central Redis. Exact. Costs a network round trip per request, and the update must be atomic or concurrent requests lose updates. A Lua script does read-modify-write in one round trip server-side. Redis becomes a dependency on every request.

Option B — local buckets, limit/N each. Zero latency, no dependency. Wrong whenever traffic is uneven across instances — and with sticky sessions or uneven LB hashing, it always is. A customer legitimately under their limit gets throttled, which is worse than letting a few extra requests through.

Option C — local buckets with async reconciliation. Each instance enforces locally and periodically publishes its consumption; instances adjust their local share toward observed demand. Approximate, converges, no per-request hop.

I’d pick C for high-volume tiers and A for low-limit tiers where exactness matters (a 5/minute limit cannot tolerate ±30%; a 10,000/minute one can). Saying “different tiers get different mechanisms” is a stronger answer than picking one globally.

Hot keys: the largest customers concentrate on single keys. Shard a hot key into key#0..N sub-buckets with the quota divided, and have each gateway pick a sub-bucket — the same key-splitting trick from the caching section.

Failures and wrap (40–45)

Fail open or fail closed when Redis is down? The decision, not the mechanism, is what is being scored.

I’d fail open for ordinary API traffic: a rate limiter outage should not become a total outage, and briefly unlimited traffic is survivable. I’d fail closed for expensive or destructive operations, where unlimited access is worse than unavailability. And I’d fall back to conservative local limits rather than truly unlimited — degraded, not off.

Also: always return Retry-After. Without it, clients guess, and they guess by retrying immediately, which turns a throttle into a stampede.

With more time: per-endpoint cost weighting, and distinguishing abusive traffic from a legitimate spike, which is really an anomaly-detection problem rather than a rate-limiting one.

3. Web crawler

Scope (0–5)

I’d ask: how many pages, and how fresh? Are we rendering JavaScript? Is this seeded from a known list or discovering the open web?

JavaScript rendering is the question that changes the cost model by an order of magnitude, and it is the one people forget.

Functional: crawl from seeds, respect robots.txt, store raw pages, extract links, re-crawl based on change rate. Non-functional: 1B pages/month; politeness is a hard constraint, not a nicety; the crawler must be restartable without losing the frontier.

Estimate (5–10)

1B pages/month ≈ 400 pages/sec sustained. At ~100 KB/page that is 40 MB/sec ingest and 100 TB/month raw.

Frontier: if each page yields ~10 links, the URL set reaches tens of billions. At ~60 bytes/URL, holding them in memory would be ~1 TB+ — too much.

That estimate drives the central decision: exact URL dedup in memory is off the table. A bloom filter at ~9.6 bits/URL holds 10B URLs in ~12 GB, which fits on one machine. The cost is a ~1% false-positive rate, meaning we occasionally skip a page we have not crawled. For a crawler that is acceptable — and that asymmetry is exactly why a bloom filter is the right structure here. (labs/src/bloom-filter.js implements this; its tests measure both the bits-per-item and the degradation from overfilling.)

API and data model (10–15)

Not a public API — internal queues and stores:

frontier:  priority queue, partitioned by domain
pageStore: objectStorage[ urlHash ] -> { html, fetchedAt, headers }
metadata:  url | lastFetched | etag | changeFreq | failures

High-level design (15–30)

seeds -> frontier -> scheduler -> fetchers -> parser -> {store, new URLs}

Partition the frontier by domain, not by URL. This is the decision that carries the problem. One worker owning a domain means politeness (crawl delay, robots.txt, connection reuse) is enforced locally, with no coordination. Partitioning by URL hash would require a distributed lock per domain to avoid hammering it — dramatically more complex for no benefit.

robots.txt is fetched once per domain and cached with a TTL. Respecting it is non-negotiable; a crawler that ignores it gets the whole IP range blocked.

Politeness is a per-domain delay (default ~1 s, or whatever Crawl-delay says), which means throughput comes from breadth across domains, not depth within one. Worth stating — it is why the design is domain-partitioned rather than simply parallel.

Two-level dedup:

• URL-level: bloom filter, as above.
• Content-level: different URLs often serve identical or near-identical content. Exact duplicates → checksum. Near-duplicates (a page with a rotating ad) → SimHash, comparing by Hamming distance. Different problem, different tool; conflating them is a common miss.

Deep dive (30–40) — traps and re-crawl

Crawler traps are the failure mode to raise unprompted:

• Infinite calendars (/events?date=2099-12-31 forever) → cap URL depth and per-domain page budget.
• Session IDs in URLs generating infinite distinct URLs for one page → canonicalise by stripping known session parameters, and rely on content-level dedup as backup.
• Deliberate tarpits serving slow, endlessly-linked pages → per-domain budget plus aggressive timeouts.

Notice all three are solved by the same pair: per-domain budgets and content dedup. Pointing that out shows you see the structure rather than a list.

Re-crawl prioritisation: estimate each page’s change frequency from observed history and schedule proportionally. A news homepage gets hourly; an archived page gets monthly. Use ETag/If-Modified-Since so unchanged pages cost a 304 instead of 100 KB — a large saving for near-zero complexity.

Failures and wrap (40–45)

• Fetcher dies: its leased URLs time out and are reassigned. At-least-once, so a page may be fetched twice — harmless, since storing is idempotent by URL hash.
• Frontier must be durable. Losing it means restarting a month of crawling. Persistent queue with checkpointing.
• A domain goes down: exponential backoff with a failure counter; drop after N consecutive failures rather than retrying forever.
• Bloom filter fills up: its false-positive rate degrades as it fills, so it must be sized for the real n and rotated/rebuilt periodically. This is a genuine operational gotcha and a good thing to volunteer.

With more time: JavaScript rendering for SPA-heavy sites (an order of magnitude more expensive per page — I’d apply it selectively based on whether the raw HTML looks content-free), and politeness beyond robots.txt such as backing off when a site’s latency rises.

4. Search autocomplete

Scope (0–5)

I’d ask: personalised or global? How fresh must new queries be? Typo tolerance? Which languages?

Functional: top 5–10 completions for a prefix, ranked by popularity. Non-functional: p99 under 50 ms end to end — including network, so the server budget is ~20 ms; extremely read-heavy; stale-by-hours is fine for ranking.

Estimate (5–10)

The latency budget is the binding constraint, and it should be computed first.

5B searches/day, ~4 keystrokes each after debouncing → 20B requests/day ≈ 230K QPS, peak ~700K.

Index size: ~100M distinct queries × ~30 bytes ≈ 3 GB, plus top-K lists at each trie node — call it 10–20 GB.

That number decides the architecture: the index fits in memory on a handful of machines. At 20 ms of server budget there is no time to consult a database, so everything is served from RAM, and ranking must be precomputed.

API and data model (10–15)

GET /suggest?q=goo&limit=10 -> { suggestions: [{text, score}] }

Trie where each node stores its own precomputed top-K descendants. A lookup is then: walk the prefix (O(length)), read the list. No traversal, no sorting at request time.

High-level design (15–30)

The key structural point is the offline/online split, and I’d draw the line explicitly.

Offline (hourly or daily): aggregate query logs → count and rank → build the trie with top-K at each node → publish a versioned, immutable index → serving nodes load and hot-swap it.

Online: stateless servers holding the trie in memory behind a load balancer.

Immutable versioned indexes are the detail worth stating: no locking, atomic swap, instant rollback to the previous version if a build is bad.

Sharding by prefix, with the caveat volunteered: prefix distribution is heavily skewed — far more queries start with a than z. So shard by prefix ranges balanced on traffic, not alphabetically. Or replicate the first two levels of the trie everywhere (tiny) and shard below that.

Client-side: debounce ~50 ms and cancel in-flight requests. This cuts backend load by a large factor for zero server cost, and mentioning it shows you are thinking about the whole system rather than just the server.

Deep dive (30–40) — freshness

The tension: ranking must be precomputed for latency, but a breaking-news query must appear within minutes, not on tomorrow’s build.

Two-tier index. The large base index rebuilds daily. A small real-time layer ingests a streaming count of the last few hours and holds only the top few thousand trending queries — small enough to rebuild every few minutes. Serving merges the two lists at query time; merging two short sorted lists is microseconds.

This is a clean example of a hybrid, like the news feed’s push/pull. I’d say that connection out loud: “same shape as fan-out — precompute the bulk, handle the exceptional tail separately, merge at read.”

Personalisation, if in scope, is another merge: a small per-user history list blended with global results. I’d push it to the client where possible, since the client already has the user’s history and this avoids per-user server state entirely.

Failures and wrap (40–45)

• Index build fails: serving nodes keep the previous version. Immutability makes this free. Never hot-swap without validating the new index first.
• A shard dies: degrade to returning fewer suggestions rather than erroring. Autocomplete is an enhancement; the user can still press Enter.
• Hot prefix: replicate the busiest shards more heavily. Traffic is known offline, so replication can be planned rather than reactive.
• Abuse: query logs are user input. A coordinated campaign can inject an offensive suggestion, so the pipeline needs filtering and minimum-distinct-user thresholds before a query is eligible. Worth raising — it is a real incident that has happened publicly to major search engines.

5. News feed

Scope (0–5)

I’d ask: chronological or ranked? How many followers can one account have? Must a post appear instantly for the author? Media, or text only?

The follower-count question is the one that matters — it is where the whole problem lives.

Functional: post; view a feed of followed accounts; paginate. Non-functional: feed load p99 < 200 ms; heavily read-skewed (~100:1); eventual consistency is fine for others’ posts, but the author must see their own post immediately (read-your-writes).

Estimate (5–10)

500M DAU, 10 feed loads/day → ~58K feed reads/sec, peak ~200K. 100M posts/day → ~1,200 writes/sec.

Average 200 followers → fan-out on write = 1,200 × 200 = 240,000 feed insertions/sec. Large but tractable.

Then the tail: one account with 100M followers generates 100M insertions from a single post. At 240K/sec of normal capacity, that one post consumes ~7 minutes of the entire fan-out budget.

That single calculation is what justifies the hybrid, and doing it out loud is worth more than knowing the answer.

API and data model (10–15)

POST /posts          { text, mediaIds[] } -> { postId }
GET  /feed?cursor=   -> { posts[], nextCursor }
POST /follow/{userId}

posts:     postId | authorId | text | createdAt
follows:   followerId | followeeId        (indexed both ways)
feedCache: userId -> [postId, ...]        (bounded, e.g. 500 entries)

Cursor pagination, not offset. The feed mutates while the user reads it; offsets would skip and repeat items. The cursor encodes (timestamp, postId) so it remains stable against insertion. I’d state this as a correctness issue rather than a performance one, because that is what it is.

High-level design (15–30)

The whole problem is one decision.

Fan-out on write (push). On posting, insert the post ID into every follower’s feed list. Reads are a single lookup — trivially fast. Writes are O(followers) and celebrities are catastrophic.

Fan-out on read (pull). Store the post once; at read time, gather posts from everyone the user follows and merge. Writes are O(1); reads are O(following) with a scatter-gather and are slow.

Hybrid — the actual answer. Push for normal accounts, pull for celebrities. At read time, merge the precomputed feed with a live pull of the handful of celebrity accounts the user follows.

Why this works: the distribution is extremely skewed. The vast majority of accounts have few followers, where push is cheap. The tiny number with millions of followers are also a small number to pull from at read time. Each strategy handles the case the other is bad at.

The threshold (say 100K followers) is a tunable, and I’d say I’d tune it from measurement rather than assert a number.

Deep dive (30–40) — the celebrity merge

Read path:

1. Fetch precomputed feed from cache — one lookup.
2. Fetch the user’s celebrity follow list (small, cacheable).
3. Pull recent posts from those accounts — hot, so cached globally and shared across all their followers, which is the efficiency that makes pull affordable.
4. Merge, rank, paginate.

Ranking runs after the merge and is a separate service with its own scaling and failure profile. If it times out, serve reverse-chronological and flag it in the response. Deciding in advance what degraded looks like — and that degradation is a normal state rather than an error — is the senior move.

Feed cache is bounded (say 500 entries). Nobody scrolls further; if they do, fall back to a pull. Unbounded per-user lists are a slow-growing storage disaster.

Fan-out is async via a queue. The post write returns as soon as the post is durable; distribution happens behind it. The author’s own feed is updated synchronously so they see their post immediately — that is the read-your-writes requirement from scoping, and pointing back at a numbered requirement is exactly what makes the scoping look deliberate.

Failures and wrap (40–45)

• Fan-out workers back up: feeds go stale, reads still work. Degradation, not outage. Monitor queue lag as an SLI.
• Feed cache lost: rebuild from posts + follows on demand. Slow but correct — the cache must be reconstructible, never the only copy.
• Thundering herd on a viral post: everyone requests it at once. Global cache with request coalescing.
• New follow: backfill the new followee’s recent posts into the follower’s feed, or just let the next pull pick them up. I’d backfill lazily on next read.
• Deleted post: filter at read time rather than scrubbing millions of cached feeds. Tombstone and let it age out.

With more time: media handling (object storage + CDN, never through the feed service) and ranking signal freshness.

6. Chat / messaging

Scope (0–5)

I’d ask: 1:1 only or groups, and how large? Message history retention? Delivery receipts and typing indicators? End-to-end encryption?

E2E encryption is worth asking about because it removes server-side search and changes the whole design.

Functional: send/receive in near real time; offline delivery; ordering within a conversation; read receipts; presence. Non-functional: delivery p99 < 500 ms; messages must never be lost once acknowledged; ordering must be consistent for all participants.

Estimate (5–10)

50M concurrent connections, 100M messages/day → ~1,200 msg/sec average, peak ~5,000.

The message rate is not the hard part. 50M concurrent connections is. At ~10 KB of kernel and application memory per connection, that is ~500 GB of RAM across the fleet, and at ~100K connections per gateway node, ~500 gateways.

Saying “the connections are the scaling problem, not the messages” is the insight; the message rate is almost trivially small by comparison.

API and data model (10–15)

WebSocket: connect, send(convId, text, clientMsgId), ack(seq), typing
REST:      GET /conversations/{id}/messages?before=seq

messages:      convId | seq | senderId | body | createdAt
conversations: convId | participants[] | lastSeq
userInbox:     userId -> undelivered [convId, seq]
connections:   userId -> gatewayId        (ephemeral)

High-level design (15–30)

client --WS--> gateway --> message service --> store
                  ^                |
                  |          connection registry
                  +----------------+

Gateways are stateful — they hold the WebSocket. Everything behind them is stateless. That separation is the design.

The connection registry maps userId -> gatewayId, so the message service knows where to route. It is ephemeral, high-churn, and read on every message: that is a Redis-shaped workload, not a database one.

Ordering comes from a per-conversation sequence number, assigned server-side. Not wall-clock timestamps — client clocks drift, are trivially spoofed, and two messages in the same millisecond have no defined order. A monotonic per-conversation counter gives a total order everyone agrees on, which is what participants actually need. (This is the applied version of §4 in 10-distributed-systems-theory.md: wall-clock time cannot order distributed events.)

Delivery: message persisted → acked to sender → looked up in the registry → pushed to the recipient’s gateway. If the recipient is offline, it stays in their inbox until their device acks. Acknowledgement is per-device, since one user has several.

Deep dive (30–40) — connection state

This is where the interesting failure modes are.

A deploy drops every connection. 50M clients reconnect at once — a self-inflicted DDoS. Mitigations: drain gateways gradually rather than simultaneously, and have clients reconnect with exponential backoff plus jitter. Without jitter they synchronise and hammer in waves. This is the same retry-storm problem as everywhere else, and naming it as such is good.

Resumption: on reconnect the client sends its last-seen seq per conversation and gets the delta. No full resync, no duplicates. This is why a sequence number rather than a timestamp matters operationally, not just theoretically.

Presence is the O(n²) trap: naively, every status change notifies every contact, and in a 10,000-member group a single user’s flicker is 10,000 notifications. Fixes: only publish presence to people currently viewing that conversation; batch and debounce updates (nobody needs sub-second presence); and for large groups, drop per-member presence entirely and show a member count.

Large groups also break fan-out: a 100,000-member group multiplies every message. Same hybrid as the news feed — push to active members, let inactive members pull on open.

Failures and wrap (40–45)

• Gateway dies: its connections drop, clients reconnect elsewhere, registry entries expire by TTL. Undelivered messages remain in the inbox — nothing is lost because nothing was acked.
• Registry stale: the message service routes to a dead gateway, gets no ack, re-resolves and retries. Retries need idempotency on clientMsgId or a network hiccup duplicates the message.
• Store unavailable: refuse to ack the sender. Never ack a message you have not durably stored — the user sees a retry indicator, which is honest.
• Duplicate sends: dedup on client-generated clientMsgId. At-least-once plus idempotency, again.

With more time: E2E encryption (and that it removes server-side search and complicates multi-device key management), and media attachments via pre-signed object storage URLs.

7. Distributed cache

Scope (0–5)

I’d ask: is this a cache or a datastore — can we lose data on a node failure? Do we need replication? Eviction policy configurable per key?

The first question is the important one: if losing data is unacceptable it is not a cache, and the design changes completely.

Functional: get/set/delete with TTL; horizontal scaling; nodes join and leave without a full remap. Non-functional: p99 < 5 ms; loss on failure is acceptable (it’s a cache); availability over consistency.

Estimate (5–10)

1M ops/sec, 100 GB working set, average value 1 KB.

100 GB across nodes with 64 GB RAM each → ~2 nodes for data, but at 1M ops/sec and ~100K ops/sec per node, throughput needs ~10 nodes, not capacity.

Stating that the cluster is throughput-bound, not capacity-bound changes the sharding conversation and is a genuinely useful observation.

API and data model (10–15)

get(key)                -> value | null
set(key, value, ttlMs)  -> ok
delete(key)             -> ok

Flat key-value. No ranges, no scans — a deliberate constraint that keeps placement simple.

High-level design (15–30)

Client-side routing. A smart client library hashes the key and connects directly to the owning node — no proxy hop, so p99 stays low. The cost is that clients must know cluster membership, which becomes the interesting problem. (A proxy tier is the alternative: simpler clients, one extra hop, another thing to operate. I’d name the tradeoff and pick client-side for latency.)

Consistent hashing with ~150–200 virtual nodes per physical node.

I would give the numbers, because they are the justification:

• Plain hash % N: adding one node to four remaps ~80% of keys — a near-total cache miss storm, which hits the database at exactly the moment you were trying to add capacity.
• Consistent hashing: ~20% move — i.e. 1/N, as theory predicts.
• Virtual nodes are what make the load even: with one point per node, worst-node deviation is ~110%; with 200 it is ~7%.

(These are measured, not recalled — labs/test/consistent-hash.test.js asserts them. That lab also surfaced a real subtlety: the numbers only hold if the hash avalanches. Raw FNV-1a on short similar labels left a 34% imbalance despite 200 virtual nodes; adding a finalization mix fixed it. “Use consistent hashing with virtual nodes” is only half the advice.)

Replication: each key on N=2 or 3 nodes, walking the ring clockwise to the next distinct physical node. With virtual nodes, adjacent ring positions are frequently the same machine, and placing both replicas there defeats the purpose — a subtle bug worth calling out.

Membership via gossip. Nodes exchange state periodically; membership converges without a central coordinator. Alternatively a coordination service holds authoritative membership — simpler and strongly consistent, but now it is a dependency. I’d use gossip for a cache, where brief disagreement is survivable.

Deep dive (30–40) — rebalancing under load

When a node joins, it must take ownership of keys while traffic is flowing.

For a cache there is a shortcut worth naming: you don’t have to move anything. Let the new node start empty; the keys it now owns simply miss and get populated from the database. Correct, trivial — but it produces a miss burst on the database, which is the actual risk here. Mitigate by warming the new node before it joins the ring, or by adding it gradually (introduce its virtual nodes in batches so the miss rate rises smoothly rather than as a step).

For a datastore the same shortcut is unavailable and you need the full double-write, backfill, verify, cut-over dance. Contrasting the two shows you know why the cache case is easier rather than just that it is.

Hot keys remain the hard problem. Consistent hashing balances keys, not traffic; one viral key can exceed a single node’s capacity no matter how good the distribution is. Fixes, in order of preference: a small client-side cache in front (often sufficient alone), replicating hot keys to multiple nodes, or splitting a key into key#0..N.

Failures and wrap (40–45)

• Node dies: its keys are now misses; the ring routes to the next node. Database load spikes. This is the real risk — the cache tier’s failure mode is a database outage. Provision accordingly, or keep replicas.
• Network partition: with gossip, both sides may accept writes for the same key and diverge. For a cache, acceptable — TTLs converge it.
• Cache stampede after mass expiry: jittered TTLs and request coalescing.
• Client with stale membership writes to the wrong node: the key is unreachable until membership converges. Bounded by gossip interval.

8. Video streaming

Scope (0–5)

I’d ask: upload and playback, or playback only? Live, or on-demand? DRM? Which devices — the device matrix drives the transcoding ladder.

Functional: upload, transcode to multiple bitrates, adaptive playback, metadata and search. Non-functional: playback starts < 2 s; buffering is the metric users actually feel; uploads may be huge and must be resumable; storage dominates cost.

Estimate (5–10)

500 hours uploaded/minute. 1B watch-hours/day.

Storage: 500 h/min × 60 × 24 = 720,000 h/day. At ~1 GB/hour for the source plus ~2 GB for the transcoded ladder, that is ~2 PB/day.

Bandwidth is the dominant cost: 1B watch-hours/day at ~3 Mbps average ≈ ~1.4 Tbps sustained. This is why the answer is “CDN” before anything else — serving that from origin is not economically possible.

A second estimate that changes the design: view counts follow a brutal power law. Most uploads are watched almost never. Transcoding every upload into every bitrate eagerly wastes an enormous amount of compute on videos nobody will watch.

API and data model (10–15)

POST /uploads              -> { uploadId, presignedUrl }
PUT  <presignedUrl>        (direct to object storage, chunked, resumable)
POST /uploads/{id}/complete
GET  /videos/{id}          -> { metadata, manifestUrl }
GET  <manifestUrl>         -> HLS/DASH manifest

videos:   videoId | ownerId | title | status | duration | createdAt
renditions: videoId | bitrate | resolution | manifestPath

Bytes live in object storage. Metadata lives in a normal database. Never store blobs in the database — I’d say this explicitly because it is a real and common mistake.

High-level design (15–30)

Upload goes directly from client to object storage via a pre-signed URL. Bytes never pass through our service. This detail signals real experience: it removes our servers from the bandwidth path entirely and makes resumable chunked uploads straightforward.

Completion emits an event to a transcoding queue.

Transcoding pipeline:

1. Split the source into segments (a few seconds each).
2. Transcode segments in parallel across the bitrate ladder — this is a DAG of independent tasks, and parallelism is why a 1-hour video doesn’t take an hour.
3. Each task must be idempotent, keyed by (videoId, segment, rendition), so a failed or straggling segment is retried alone rather than restarting the job.
4. Assemble manifests, mark the video ready.

Straggler handling: run a backup copy of a slow segment and take whichever finishes first — straight out of the MapReduce paper, and naming that provenance is worth a little credit.

Playback: client fetches the manifest, then requests segments from the CDN, measuring its own throughput and choosing the next segment’s bitrate. Adaptive bitrate is a client-side decision — the server just offers options. People often get this backwards.

Deep dive (30–40) — the cost asymmetry

Given the power-law view distribution, eager full-ladder transcoding is mostly waste.

Tiered approach:

• On upload, eagerly produce one widely-compatible mid-tier rendition (say 480p). The video is playable immediately.
• Generate the rest of the ladder lazily on first view, or once views cross a threshold. The first viewer of an unpopular video gets slightly lower quality; nobody else notices.
• For the small set of popular videos, pre-generate everything including high-efficiency codecs (AV1 costs far more CPU to encode but saves bandwidth — worth it only when amortised over many views).

That is a genuine engineering tradeoff with numbers behind it, which is exactly what the deep dive is scored on.

Storage tiering: recent and popular content on fast storage; the long tail on cold/archival tiers with higher retrieval latency. Also: delete or refuse to keep renditions nobody requests.

CDN strategy: popular content pushed proactively to edges; the long tail pulled on demand. Cache keys must include the rendition. Origin shielding — a mid-tier cache between edges and origin — prevents many edges all missing to origin simultaneously.

Failures and wrap (40–45)

• Transcoding fails for one segment: retry that segment. Idempotency makes this safe. After N failures, mark the video failed and notify the uploader.
• Transcoding backlog: uploads queue and publishing is delayed. Prioritise by uploader tier rather than pure FIFO.
• CDN edge down: DNS/anycast routes to another. This is transparent by design.
• Object storage regional outage: cross-region replication for metadata and popular content; the long tail may be briefly unavailable — an explicit, cost-driven tradeoff.
• Thundering herd on a premiere: everyone requests segment 1 simultaneously. Pre-warm edges before a scheduled event.

9. Google Drive / Dropbox

Scope (0–5)

I’d ask: file size limits? Sharing and permissions? Offline editing? Versioning and how far back?

Functional: upload/download, sync across devices, sharing, version history, conflict handling. Non-functional: sync latency of seconds; never silently lose a user’s data — this is the dominant non-functional requirement and dwarfs the others; bandwidth-efficient on mobile.

Estimate (5–10)

100M users, 100 GB average → 10 EB nominal. Deduplication matters enormously at that scale: shared files (a widely-distributed PDF, a popular installer) may be stored once instead of millions of times.

50M file changes/day → ~600 changes/sec. Modest.

The estimate that changes the design: most edits change a tiny fraction of a file. Re-uploading a 100 MB file because one byte changed is unacceptable on mobile. So: chunking, and sync at chunk granularity.

API and data model (10–15)

GET  /delta?cursor=      -> { changes[], nextCursor }
POST /files/{id}/chunks  { chunkHashes[] } -> { missingHashes[] }
PUT  /chunks/{hash}      (only for missing chunks)
POST /files/{id}/commit  { chunkHashes[], baseVersion }

files:  fileId | ownerId | path | currentVersion | deleted
versions: fileId | version | chunkHashes[] | createdAt | deviceId
chunks: hash -> { objectStorageKey, refCount }

The POST chunks → missingHashes round trip is the heart of it: the client says what it has, the server replies with only what it needs. That is dedup and delta sync in one exchange.

High-level design (15–30)

Content-addressed chunking. Split files into ~4 MB chunks and name each by its hash. This gives, for free:

• Dedup — identical chunks stored once, globally.
• Delta sync — a changed byte re-uploads one chunk.
• Integrity — the hash verifies the content.

Fixed vs content-defined chunking is worth raising: fixed-size boundaries mean inserting one byte at the start shifts every subsequent boundary and invalidates the whole file. Content-defined chunking (rolling hash, à la rsync) picks boundaries from the content, so an insertion only affects nearby chunks. More CPU, dramatically better dedup on edited files. I’d choose content-defined and say why.

Sync is a metadata problem, not a bytes problem. Clients hold a cursor and long-poll /delta for changes since that cursor. The notification path carries metadata only; bytes are fetched separately from object storage.

Metadata is the bottleneck, not storage — 10 EB of blobs is “just” object storage, while hundreds of billions of file and chunk rows with transactional requirements is the hard part. Shard metadata by user, keeping a user’s files together so their common operations stay single-shard.

Deep dive (30–40) — conflicts

Two devices edit while offline. Both come back. Now what?

Detect with version vectors, not timestamps. A per-file version vector identifies whether one version descends from the other or whether they are genuinely concurrent. Wall-clock timestamps cannot distinguish these, and last-write-wins would silently discard one user’s work — unacceptable given the “never lose data” requirement from scoping. (§4 of 10-distributed-systems-theory.md covers why.)

Resolve by keeping both. Create report (conflicted copy from Alice's laptop).docx and let the human decide. This looks like a cop-out and is in fact the correct engineering decision: automatic merging of arbitrary binary formats is impossible in general, and a wrong merge is far worse than an extra file.

I’d contrast: Google Docs can merge, because it controls the format and operates on structured operations (OT/CRDT). A general file sync service cannot. That contrast is the thing to say — it shows you know why the constraint exists rather than just accepting it.

Small files are the other trap. A node_modules directory is 50,000 tiny files: metadata operations dominate and per-file overhead destroys throughput. Batch metadata updates, and pack small files together rather than doing 50,000 independent round trips.

Failures and wrap (40–45)

• Upload interrupted: chunks already uploaded are retained; resume only sends missing ones. Content addressing makes resumption trivial.
• Commit fails after chunks upload: orphaned chunks, reclaimed by a reference-counting garbage collector. GC must be conservative — deleting a still-referenced chunk is unrecoverable data loss.
• Two devices commit simultaneously: compare-and-swap on baseVersion. The loser re-reads and creates a conflicted copy.
• Deletion: soft-delete with a retention window. Users delete things by accident constantly; permanent immediate deletion is a support nightmare.
• A malicious client claims to hold a chunk hash it doesn’t — a real attack that could grant access to another user’s data. Verify possession, or scope dedup per-user for sensitive content.

10. Distributed job scheduler

Scope (0–5)

I’d ask: cron-style recurring, one-off, or DAGs with dependencies? What’s the scale of a single job — seconds or hours? Multi-tenant? Is at-least-once acceptable, or must it be at-most-once?

That last question determines everything.

Functional: schedule recurring and one-off jobs; execute reliably; retries; visibility into runs. Non-functional: jobs start within seconds of their scheduled time; at-least-once execution; one tenant must not starve others.

Estimate (5–10)

10M scheduled jobs, 100K executions/minute → ~1,700 executions/sec. Average job 30 s → ~50,000 concurrently running → with 10 per worker, ~5,000 workers.

Due-job scan: at 1,700/sec, scanning a 10M-row table every second is not viable. The schedule store needs an index on next-run-time and must read only the head of the queue — a time-ordered structure, not a table scan. That realisation belongs in the estimate phase.

API and data model (10–15)

POST /jobs      { schedule: "*/5 * * * *", payload, maxRetries, timeout }
GET  /jobs/{id}/runs
POST /jobs/{id}/pause

jobs:  jobId | tenantId | schedule | payload | nextRunAt | paused
runs:  runId | jobId | state | workerId | leaseExpiresAt | attempt | startedAt

High-level design (15–30)

A single scheduler leader, elected via a consensus-backed lock (Chubby/etcd style), with hot standbys watching the lock.

Why a single leader: deciding what is due is a small, coordination-heavy task, and two schedulers disagreeing means duplicate runs. Why it’s acceptable: the leader only enqueues; it is not on the execution path, so it is not a throughput bottleneck. Both halves of that justification matter.

The leader holds a lease and must renew it. If it cannot renew, it demotes itself before expiry, so there is a safety gap rather than an overlap — the lease reasoning from §3 of the theory file.

Workers lease tasks and heartbeat. A worker claims a task with a time-bounded lease and renews while running. If it dies, the lease expires and the task is reassigned.

This means a task may run twice. A worker can be partitioned — still running, still working — while the scheduler concludes it is dead and reassigns. There is no way to prevent this in an asynchronous system without giving up availability (FLP again). Therefore execution must be idempotent, and I’d make that a documented contract of the platform rather than a hope. labs/src/idempotency.js is the pattern.

If a user genuinely needs at-most-once, they need fencing tokens and a transactional side effect — and they should be told the cost.

Deep dive (30–40) — cron semantics and fairness

Missed runs. The scheduler was down 09:00–10:00; a 5-minute job should have run 12 times. Options:

• Skip them — correct for “refresh the cache”, wrong for billing.
• Run all 12 immediately — a thundering herd, and probably meaningless.
• Run once and move on — usually the right default.

There is no universal answer, so it should be per-job policy (catchUp: none | one | all). Recognising that this is a product decision rather than a technical one is itself the senior answer.

Also: timezones and DST. A daily 02:30 job runs twice on one day a year and zero times on another. This is a genuine, classic source of production incidents; storing schedules in UTC with an explicit timezone and documenting the DST rule is the fix.

Fairness. One tenant enqueueing a million jobs must not starve everyone else. A single FIFO queue does exactly that. Instead: per-tenant queues with weighted round-robin, and per-tenant concurrency caps. Without this, the platform’s reliability is at the mercy of its noisiest customer.

Stragglers. A task far exceeding its expected runtime: launch a backup copy and take the first result. Requires idempotency — which we already have. Naming this as MapReduce’s technique is worth a moment.

Long jobs vs short jobs should not share a worker pool — a bulkhead. A flood of hour-long jobs otherwise blocks every 1-second job behind it.

Failures and wrap (40–45)

• Leader dies: standby acquires the lock and resumes. A gap of seconds, so jobs may start slightly late — acceptable against the scoped requirement.
• Worker dies mid-task: lease expires, task reassigned, idempotency prevents double effect.
• Task never completes (hangs): an execution timeout distinct from the lease, after which it is killed and retried. Without this, one hung task holds a worker slot forever.
• Poison task fails every time: bounded retries with exponential backoff, then a dead-letter queue and an alert. Infinite retry of a doomed task burns a worker indefinitely.
• Queue backs up: jobs start late. Alert on scheduling lag, which is the SLI that actually matters to users.

11. Metrics and monitoring

Scope (0–5)

I’d ask: metrics only, or logs and traces too? Retention? Who queries it — dashboards, alerts, or ad-hoc exploration? Self-hosted or multi-tenant?

Functional: ingest metrics from every host; query by time range and label; evaluate alert rules; dashboards. Non-functional: ingest must never be the bottleneck that takes down the systems it monitors; query p99 seconds; must remain available precisely when everything else is failing.

That last requirement is the one that shapes the design, and it is worth stating as a first-class constraint.

Estimate (5–10)

100K hosts × 1,000 series each = 100M active series. At a 10 s scrape interval → 10M datapoints/sec.

Naive storage: 10M/sec × 16 bytes × 86,400 = ~14 TB/day. Unsustainable.

Compressed (delta-of-delta on timestamps, XOR on values — the Gorilla technique) gets to ~1.5 bytes/point, giving ~1.3 TB/day. Still large, which is why downsampling and tiered retention are not optional — they are the core of the design, not an optimisation.

API and data model (10–15)

POST /write   (batched, compressed)
GET  /query?expr=rate(http_requests_total{job="api"}[5m])&start=&end=

Series identity is metricName + sorted(labels), hashed to a series ID. Storage is seriesId -> compressed chunks of (timestamp, value).

High-level design (15–30)

agents -> ingest (sharded by series ID) -> TSDB -> query/alerting

Push vs pull is worth raising. Pull (Prometheus-style) gives the monitoring system control over rate and gives you target liveness for free. Push scales better to ephemeral and NAT’d workloads. Large systems end up hybrid: pull within a cluster, push aggregated data upward. I’d name the tradeoff rather than asserting one.

Shard by series ID, so all points for one series land on one node — that is what makes a range query a sequential read rather than a scatter-gather.

LSM-backed storage, because the workload is append-heavy with essentially no updates. Recent data stays in memory, flushed to immutable time-ordered blocks. Compaction merges blocks and applies downsampling in the same pass.

Tiered retention:

• Raw 10 s resolution: hours to days
• 1-minute rollups: weeks
• 1-hour rollups: a year or more

Queries pick the tier from the requested range. Nobody plots a year at 10-second resolution — the screen doesn’t have the pixels.

Deep dive (30–40) — cardinality

Cardinality is the failure mode nobody expects, and it is the deep dive worth choosing.

Series count is the product of label value counts. Add a user_id label with 1M values to a metric with 10 endpoints and 5 status codes, and you have created 50 million series from one instrumentation line. Memory and index size explode, queries slow, and the monitoring system falls over — usually during an incident, because that is when someone adds a debug label.

Defences, layered:

• Reject at ingest. Per-tenant series limits, and refuse new series past the cap. Rejecting one metric is far better than losing the cluster.
• Detect and attribute. Track series growth per metric and per label, and alert on the rate of new series, not just the total.
• Educate through the API: high-cardinality dimensions (user ID, request ID, full URL) belong in logs or traces, which are built for it. Metrics are for aggregates. That distinction — right tool per signal — is the real answer.

Alerting must not depend on the pipeline it monitors. If alert evaluation reads from the same overloaded ingest path, then when the system is in trouble the alerts go quiet — the worst possible failure mode, because silence is indistinguishable from health. Run alert evaluation on an independent path, with its own storage for the small set of series alerts actually need, and alert on the monitoring system’s own health from somewhere else entirely. Dead-man’s switch: an alert that fires when it stops receiving a heartbeat.

Failures and wrap (40–45)

• Ingest node down: agents buffer locally and retry with backoff. Some gap is acceptable; blocking the monitored application is not. Agents must drop data rather than block — the monitoring must never take down the monitored.
• Query overload: a user plots a year of raw data. Per-query limits on series touched and points scanned, and reject early with a clear error.
• Storage full: enforce retention aggressively and drop the oldest tier first.
• Clock skew on agents: points arrive with timestamps in the future or far past. Clamp to an acceptable window and count the rejects as a metric.

With more time: exemplars linking a metric spike to a trace, which is the practical bridge between the three signals.

12. Ad click aggregator

Scope (0–5)

I’d ask: what is the number used for — dashboards or billing? What latency do advertisers expect? How late can an event legitimately arrive? Is fraud detection in scope?

Billing vs dashboards is the pivotal question. If advertisers are charged from this number, “approximately right” is not acceptable and the design must include a reconciliation path.

Functional: ingest click events, aggregate by ad/campaign/time, serve dashboard queries, support billing. Non-functional: dashboard freshness within a minute; billing numbers must be auditable and exactly right; events may arrive late or duplicated.

Estimate (5–10)

10B clicks/day → ~120K events/sec, peak ~500K.

At ~200 bytes/event: 2 TB/day raw, ~730 TB/year. Aggregates are tiny by comparison — 1M campaigns × 1,440 minutes × ~50 bytes ≈ 72 GB/day, and far less once rolled up.

The asymmetry drives the architecture: raw events are huge and immutable; aggregates are small and queried constantly. Keep raw events in cheap object storage for recomputation and audit; serve from the small aggregate store.

API and data model (10–15)

POST /click   { eventId, adId, campaignId, userId, timestamp, signature }
GET  /stats?campaignId=&from=&to=&granularity=minute

rawEvents:   partitioned log, keyed by adId, archived to object storage
aggregates:  (campaignId, minute) -> { clicks, uniqueUsers }
dedupIndex:  eventId -> seen (TTL'd)

eventId is client-generated and is what makes dedup possible. Without it, at-least-once ingestion makes correct counting impossible.

High-level design (15–30)

Lambda architecture, and this is one of the few problems where it is genuinely justified rather than fashionable:

Speed layer — stream processing over a partitioned log keyed by adId. Aggregates in event-time windows, dedups on eventId, writes to the serving store within seconds. Approximate.

Batch layer — a nightly job recomputes from the raw archive with full knowledge of late events, and overwrites the speed layer’s numbers. This is the authoritative result used for billing.

Why justified here: the two layers have genuinely different requirements — fast and approximate for the advertiser’s dashboard, slow and exact for invoicing. Maintaining two code paths is a real cost, and I’d acknowledge it; the usual argument against lambda is exactly that duplication. Here, money makes it worth paying.

Partitioning by adId keeps all events for one ad in one partition, so ordering and aggregation are local. The risk is a hot ad exceeding a partition’s throughput — split it into adId#0..N sub-keys and sum at read time.

Deep dive (30–40) — counting correctly

Three distinct problems, routinely conflated:

1. Duplicates. At-least-once delivery means retries. Dedup on eventId within the aggregation window, using a bloom filter or a TTL’d key store. Note the window is bounded — a duplicate arriving a week later will not be caught by the stream layer, which is one reason the batch layer exists.

2. Late events. A phone offline for hours uploads its clicks later. Aggregate on event time, not processing time. A watermark asserts “events older than T have probably arrived” and lets a window close. Allowed lateness defines what happens after that: either drop, or re-open the window and emit a correction. I’d emit corrections, since downstream consumers must handle restatement anyway for the batch overwrite.

3. “Exactly-once”. There is no such thing end to end. What we have is at-least-once delivery plus idempotent aggregation: keyed by (eventId, window), applying the same event twice has no effect. That is the precise claim, and phrasing it precisely is exactly what distinguishes a senior answer here.

Unique users is a separate, harder problem — an exact distinct count needs the full user set per campaign. HyperLogLog gives ~2% error in ~1.5 KB per counter and merges across windows, which is the right tradeoff for dashboards. For billing, if uniqueness matters, exact counting in the batch layer.

Failures and wrap (40–45)

• Stream processor dies: consumer offsets are durable; it resumes from the last committed offset. Idempotent aggregation makes reprocessed events safe. This is precisely why a replayable log rather than a queue.
• Aggregate store unavailable: the log buffers. Retention sets how long an outage can last before data loss, so retention is a recovery-time decision, not just a cost one.
• Bad deploy corrupts aggregates: recompute from the raw archive. Keeping immutable raw events is what makes every other mistake recoverable — I’d call this the single most valuable property of the design.
• Click fraud inflates counts. Out of scope for the pipeline but worth naming: bot detection, per-user rate limiting, signed click tokens so an event can’t be forged, and a separate scoring pass before billing. Raising it unprompted shows product awareness.
• Reconciliation mismatch between stream and batch: alert on the divergence percentage. A growing gap is the early signal that something in the stream path is wrong, and it should page someone before an advertiser notices.

After you read one of these

Do not move on. Re-run the same problem cold, a week later, and compare against your first attempt rather than against this file.

The measurement that matters is not “did I cover what the solution covered” — it is “did I derive it this time?” Log both attempts in 05-practice-log.md with the self-score rubric.

And if reading a solution made the problem feel easy, that feeling is the warning sign. Recognition is not the same as derivation, and only one of them survives the third follow-up question.