13 system design interview questions on top K, metrics, web crawlers and typeahead, each with the correct answer and a full explanation.
Top 100 videos by views over the last hour, billions of events, approximate counts acceptable, memory must be bounded. Which approach?
Show answer
Answer
Count-min sketch for counts plus a min heap of size 100
A count-min sketch gives bounded memory frequency estimates and the heap tracks the current top K. An exact map of every id may not fit and is not bounded. Sorting billions of events hourly is slow and late. HyperLogLog counts distinct items, not how often each occurs.
A game has 10 million players and needs live score updates and each player's rank on demand. What fits?
Show answer
Answer
A Redis sorted set with ZINCRBY and ZREVRANK
Sorted sets keep members ordered by score with O(log n) updates and rank lookups. COUNT of higher scores on every request scans a large range. A heap gives the top but not an arbitrary player's rank. A hash map has no order.
Events are partitioned randomly across 10 workers. Each sends its local top 10 and you merge them. Is the result the exact global top 10?
Show answer
Answer
No: an item just below the cut on every worker can be globally top; partition by item id instead
With random partitioning an item's count is split across workers and can miss every local list while its total is high. Partitioning by item id puts each item's full count on one worker, so merging local top K is exact. Exact local counts do not help a split item. More workers split counts further.
Ad clicks drive billing and must be exact. Dashboards need counts within a minute. What architecture fits?
Show answer
Answer
A streaming pipeline for near real time counts plus batch reconciliation from the raw log for billing
Streaming gives fast numbers, while reconciliation over the immutable raw log (with click id dedupe) corrects late, duplicate or replayed events before billing. Streaming alone can drift with late and duplicate events. Batch only misses the minute requirement. In memory counts are lost on crash.
A metrics system ingests millions of points per second, and users chart 1 year of data at 1 hour resolution. How do you store it?
Show answer
Answer
Keep raw points for a short retention and roll up to coarser resolutions for long ranges
Downsampled rollups keep year long queries cheap while raw data serves recent detailed views; time series databases also compress heavily (Gorilla). Aggregating raw data at query time over a year is slow and storage grows forever. A row per point at millions per second overwhelms a general purpose database. Random sampling loses spikes, the thing you monitor for.
An engineer adds a user_id label to a request latency metric with 50 million users. What happens?
Show answer
Answer
Each user creates a new time series, blowing up memory and index size; use logs or traces for per user data
Every unique label combination is a separate series, so 50 million users means at least 50 million series per metric. Prometheus guidance says not to use unbounded labels like user ids. Labels are not free. More series makes queries slower. In memory indexes grow with series count.
A crawler must remember billions of seen URLs in memory. Occasionally skipping a new URL is acceptable. Which structure?
Show answer
Answer
A Bloom filter
A Bloom filter answers "seen?" in a few bits per URL with a tunable false positive rate, which here means rarely skipping a new page. A hash set of full URLs needs hundreds of GB. A database lookup per URL is slow at crawl rates. HyperLogLog estimates how many distinct URLs, not whether a given one was seen.
Your crawler hammers some sites with hundreds of requests per second and gets blocked. What fixes it?
Show answer
Answer
Per host queues with a delay between requests, and obey robots.txt
Mapping each host to one queue with a minimum delay bounds the load per site, and robots.txt states the site's rules. A global FIFO keeps sending bursts of the same host's links. More threads hit sites harder. Rotating IPs to evade blocks is abuse, not politeness.
Many different URLs return identical pages (tracking parameters, mirrors). How do you avoid storing and parsing them repeatedly?
Show answer
Answer
Store a content fingerprint (checksum or simhash) and skip pages already seen
Fingerprints catch duplicate content under different URLs in one lookup, and simhash also catches near duplicates. URL dedupe misses different URLs with the same content. Byte comparison with every page is quadratic. Duplicates waste crawl budget and fetch capacity, not just storage.
Requirements: polite, scalable, robust to traps and bad HTML, freshness.
Estimates: 1B per month is about 400 pages per second, times page size for bandwidth and storage.
Components: URL frontier (prioritized, per host queues), DNS cache, fetchers, parser, URL filter and seen set (Bloom filter), content dedupe, blob store.
Deep dives: politeness and robots.txt, crawler traps (depth limits), distributing the frontier by host hash, recrawl scheduling.
Search autocomplete at 100k QPS must return the top 5 suggestions for a prefix in under 50 ms. Which approach?
Show answer
Answer
A trie with the top 5 completions precomputed at each prefix node
Precomputing top K per node makes each lookup O(prefix length), and the trie is rebuilt offline from query logs. LIKE with ordering at 100k QPS is far too slow. Walking a short prefix's subtree touches millions of nodes. Full text search answers a different question and is slower.
