During a senior software engineering virtual onsite, you are given **three independent, traditional system design prompts**. Treat each one as a separate design exercise. For every prompt you should clarify requirements, propose an API and data model, sketch the high-level architecture, and discuss the scalability, consistency, and reliability trade-offs. The three prompts are: 1. A **real-time Top-K service** that ingests high-volume events and returns the top $K$ items by a metric (such as views or clicks) over selectable time windows. 2. A **distributed web crawler** that starts from seed URLs, discovers pages, avoids duplicates, respects crawl politeness rules, and stores crawled content and metadata. 3. An **online chess service** where two players play real-time games, legal moves are enforced by the server, clocks are supported, users can reconnect, and game history is stored. The Parts below break out each prompt with its own scoping hints. Work them one at a time; the interviewer is looking for breadth across all three plus depth in at least one. ### Constraints & Assumptions State your own numbers and confirm them with the interviewer; reasonable senior-level defaults: - **Top-K**: peak ingest on the order of $10^5$–$10^6$ events/sec; query p99 latency target in the tens of milliseconds; freshness of seconds to a few minutes; tens of millions of distinct items per metric; a small fixed menu of supported windows. - **Crawler**: billions of pages over time, on the order of thousands of pages/sec sustained; respect each site's `robots.txt` and crawl-delay; refetch on a freshness policy; store raw content in object storage. - **Chess**: real-time games with sub-200 ms perceived move latency; strong consistency *within* a game, only eventual consistency across unrelated games; standard time controls (bullet/blitz/rapid); full game history retained. - Assume each system is its own service with its own datastore; you are not asked to unify them. ### Clarifying Questions to Ask - **Top-K**: Is approximate ranking acceptable, or must the top $K$ be exact? Which windows and dimensions must be supported, and is $K$ bounded (e.g. $\le 1000$)? - **Crawler**: Is the goal broad web-scale crawling or a bounded set of allowed domains? Do we need to render JavaScript, or is static HTML sufficient? What is the freshness/recrawl requirement? - **Chess**: Do we need spectators and chat, or just the two players? Is matchmaking/rating in scope? What time controls must we support, and how strict is the latency budget? - **Cross-cutting**: What scale (QPS, data volume, users) should I design for, and what are the latency and availability SLOs? ### Part 1 — Real-Time Top-K Service Design a service that ingests a high-volume stream of events (item views, clicks, likes, purchases) and answers queries of the form "give me the top $K$ items by metric $M$ over the last window $W$ (e.g. 1 minute / 1 hour / 24 hours / 7 days), optionally filtered by dimensions such as country or category." Reads must be low-latency; writes must absorb a large, bursty firehose. ```hint Where to start Separate the **ingest/aggregate** path from the **query** path. Events flow into a durable log and are aggregated into small fixed time buckets; queries merge the buckets that overlap the requested window. Decide up front whether the answer must be exact or whether an approximate trending list is acceptable — that single choice drives the whole design. ``` ```hint Data structure To pick the top $K$ from $N$ candidate counts, think about a bounded-size structure that keeps only the current best $K$ rather than sorting everything. When cardinality is so high you cannot afford a counter per item, ask what you'd trade exactness for — a sub-linear-memory frequency estimator plus a bounded candidate set of likely "heavy hitters" is one direction worth weighing against exact counting. ``` ```hint Scaling and hot keys Partition the event stream (by item, dimension, or metric) and compute a **local Top-K per shard, then merge** into a global Top-K. Beware a single hot item dominating one partition — think about how to spread that one item's load without losing count accuracy. Use **watermarks** so late-arriving events land in the correct bucket. ``` #### What This Part Should Cover - A clean **read-path vs write-path** separation, with a durable log as the source of truth feeding precomputed or queryable aggregates. - An explicit **exact-vs-approximate** decision and its memory/accuracy trade-off, with a named bounded-Top-K mechanism (a size-$K$ heap, or a sketch plus a heavy-hitters structure). - A **time-bucketing** scheme that answers multiple windows from one stored granularity, plus event-time handling (watermarks) for late data. - Shard-local Top-K → global merge, with a concrete **hot-key** mitigation that preserves count accuracy. ### Part 2 — Distributed Web Crawler Design a crawler that takes seed URLs, fetches pages, extracts and follows links, deduplicates both URLs and content, obeys `robots.txt` and per-host politeness/crawl-delay rules, and persists content + metadata + the link graph. It must scale horizontally, tolerate worker crashes, and avoid abusing target sites or falling into traps. ```hint Where to start The heart of a crawler is the **URL frontier**: a prioritized, politeness-aware queue of what to fetch next, partitioned **by host** so politeness and rate limits are enforced per domain. Model the pipeline as frontier → fetch → parse → dedup → store, with new links flowing back into the frontier. ``` ```hint Dedup and politeness Separate two dedup problems: have-I-seen-this-*URL* (after canonicalizing it) versus have-I-seen-this-*content* — and note that exact-match and near-duplicate content need different tools. For the URL side, weigh a memory-cheap membership test against the cost of false positives. Enforce one (or few) concurrent fetches per host and honor crawl-delay; think about how a single giant domain skews a host-partitioned design. ``` ```hint Reliability and traps Workers should **lease** frontier URLs with a visibility timeout so a crashed worker's URLs return to the queue automatically. Defend against crawler traps (infinite calendars, parameter explosions, redirect loops) and SSRF (block internal IP ranges, cap response size/redirects). ``` #### What This Part Should Cover - A host-partitioned **frontier** with a clear priority/scheduling policy and the frontier → fetch → parse → dedup → store loop. - Two distinct dedup layers: **URL** canonicalization + membership test, and **content** exact + near-duplicate detection. - **Politeness** enforcement (per-host concurrency, `robots.txt`, crawl-delay, backoff) and how host skew is handled. - **Fault tolerance** via leases/visibility timeouts, plus crawler-trap and **SSRF** defenses. ### Part 3 — Online Chess Service Design a service where two authenticated players play a real-time chess game. The **server** is authoritative for legal-move validation; clocks tick server-side; players can disconnect and reconnect mid-game; and every completed game is stored for replay. Move delivery must feel instant, and a single game must stay strongly consistent. ```hint Where to start Make the **server authoritative** and never trust the client board. Give each active game a **single writer** (an in-memory game actor / sharded by `game_id`) so move ordering and turn enforcement are trivially consistent. Use a persistent **move log** (event sourcing) as the source of truth. ``` ```hint Real-time and consistency Use a **WebSocket** (or similar push channel) per game for low-latency move broadcast, with the API gateway stateless and routing to the owning game actor (sticky/location service). Make move submission **idempotent** (include `move_number` / game `version`) so retries and out-of-turn/duplicate moves are rejected via optimistic concurrency. ``` ```hint Reconnect and recovery On reconnect, the client requests a **snapshot** (position, move list, clock state, version) then resubscribes and replays any missed events from the move log. On actor crash, rebuild from the latest snapshot + replayed moves. Compute clocks and timeout-wins from server-side timestamps, persisting each accepted move *before* broadcasting it as final. ``` #### What This Part Should Cover - A **single-writer per game** model (an actor sharded by `game_id`) with **server-authoritative** rule validation and an event-sourced move log as the source of truth. - **Low-latency push** (WebSocket) with a stateless gateway and a routing/location mechanism to the owning writer. - **Idempotent, optimistic-concurrency** move submission that rejects stale, duplicate, and out-of-turn moves. - **Reconnection** via snapshot + replay, server-side clocks/timeouts, and crash recovery (snapshot + log replay) with persist-before-broadcast ordering. ### What a Strong Answer Covers These dimensions span all three parts — the interviewer wants to see them recur regardless of which prompt you go deep on: - A short **requirements-clarification** pass (functional + non-functional) before any design, for each prompt. - Sensible **APIs and data models**, with named storage choices justified by their fit (a durable log, an in-memory cache, a wide-column store, object storage) rather than brand-dropping. - A durable, replayable **log as the source of truth**, with the write path separated from the read path. - Explicit **trade-offs** (cost vs latency vs accuracy vs consistency) and a concrete **failure-and-recovery** story for each system. ### Follow-up Questions - **Top-K (Part 1)**: A single item suddenly receives 50% of all traffic (a hot key). How does your aggregation avoid a bottleneck and still return correct counts? - **Crawler (Part 2)**: How do you keep the link graph and content fresh — what triggers a recrawl, and how do you avoid re-fetching unchanged pages? - **Chess (Part 3)**: A player's connection drops with 3 seconds left on their clock. Walk through exactly what the server does to their clock, the game state, and the opponent's view. - **Cross-cutting**: For each system, what is the single most likely production failure mode, and what observability (metrics/alerts) would catch it first?