Loading...
A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match.
The question is a proximity server: given a point and a radius, return the places near it, ranked, out of 500 million. The trap is SELECT * FROM Places WHERE lat BETWEEN … AND long BETWEEN …. The interview is the reasoning that takes you from that query to an in-memory spatial index, and then to partitioning and rebuilding that index. Nearby Friends (people instead of restaurants) is the stretch question at the end. It breaks one assumption this design leans on.
Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):
Build incrementally while you talk. Trace one search ("50 highest-rated places within 5 km of me") end to end through your diagram. Argue the tradeoff, not "industry standard."
Read this before you go in. These are the decisions, and why they matter.
Ask how often a place's location changes. The answer is "rarely," and everything downstream leans on it. The index can live in memory, be expensive to build and cheap to query, take inserts one at a time, and be rebuilt from the database when lost. Asking this unprompted is a strong signal. It shows you know the Uber-shaped version of the question, where objects move every few seconds and a static index dies.
This is the core of the interview. You are graded on the progression, not on naming a product. Name each step's concrete failure before moving to the next.
GridID IN (G, G1 … G8). Cell IDs and neighbours are arithmetic on (lat, long). Held in memory as GridID → [LocationIDs] it costs about 4 GB. Why it fails: places are not uniform. A 10-mile cell over downtown San Francisco holds a huge number of places; one over the Pacific holds none. Queries in dense cells stay slow because the "shortened list" is not short.Geohash, S2, H3. Equally defensible if you can say why. A geohash interleaves latitude and longitude bits so shared prefixes mean nearby cells; a query is a prefix match on the user's cell plus eight neighbours. It has the fixed grid's density problem (you pick one precision) and a boundary problem (two adjacent points can have completely different hashes), so neighbour expansion and a true-distance post-filter are mandatory. H3 (Uber, hexagons) and S2 (Google) are the hierarchical alternatives. Naming PostGIS or Elasticsearch geo without this reasoning is what fails.
Not the 793-byte record. The tree caches (LocationID, lat, long, popularity), about 24 to 25 bytes per place: 12 GB for 500M places against roughly 400 GB of full rows. The index answers "which LocationIDs are near this point"; a cache and the database hydrate the winners. Keep the tree small so it fits in memory and rebuilds fast.
12 GB fits one server today. With 20% growth a year and 100K QPS, one server runs out of memory and read capacity within a few years, so you partition anyway. Say both halves.
By region (zip-code style) is intuitive and wrong. A hot region, Manhattan at lunch, saturates one server, and regions grow unevenly so the distribution drifts and you end up repartitioning.
By hash of LocationID is the default. Each server builds its own QuadTree over the places hashed to it. A query goes to every partition; each returns its nearby set and a stateless aggregator merges them. The partitions' trees have different shapes because they hold different places. That is not a bug: each tree is a local index, every partition is searched over the same radius, and the aggregator takes the union.
The cost is real. At 100K QPS with N partitions, each partition sees all 100K QPS. Read replicas per partition absorb it. A region-then-hash hybrid bounds fan-out at the price of reintroducing hotspot risk; mention it as a refinement, not the answer.
Primary and secondaries per partition. Writes go to the primary and reach secondaries within milliseconds; secondaries serve reads. Primary dies: a secondary takes over, nothing to rebuild.
Primary and secondary die together: the new server does not know which places it should hold. The brute-force answer is a full pass over the database, hashing every LocationID to filter. That scans hundreds of GB, and while it runs the partition serves nothing, so users silently miss places. The senior answer is a QuadTree Index: a reverse map from server number to the set of (LocationID, lat, long) it owns. Storing lat and long with the ID is deliberate; it is exactly what the server needs to rebuild without touching the database. The index server is replicated, and can itself be rebuilt by one database pass. Most candidates never draw this box.
Keep an aggregated popularity (average stars out of ten) in the database and in each tree entry, so partitions can rank locally. For the top 100 in a radius, each partition returns its local top 100; the aggregator picks the global top 100 from the union. Two caveats to raise yourself. Popularity in the tree lags the database, because you refresh it lazily instead of writing every review into the index (reviews are frequent, locations are not). And a minimum-distance sort needs a post-filter, because the index returns a bounding region, not a circle. Recall from the index, precision from the post-filter.
A new place is three writes: the database row, the leaf on the owning partition (split at 500), and the QuadTree Index set for that server. Visible on the primary immediately, on secondaries within milliseconds; promise "within a second." A closed restaurant is the same three in reverse. Leaves are not merged when they shrink; data rarely shrinks and splits are cheap. A location change (rare) is delete plus insert. The LocationID keeps its hash, so the owner does not change.
A famous restaurant is read far more than others. Put Memcached in front of the database with LRU eviction; aggregators check it before the database. Two load balancer layers: clients to aggregators, aggregators to backends. Round robin first: simple, and a dead server drops out of rotation for free. It ignores load, so move to a load-aware balancer when one box runs hot.
One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.
Rough numbers are fine; the method is what gets graded. Why a third? A full 4-ary tree with L leaves has (L − 1) ÷ 3 internal nodes: each split adds four children and removes one leaf, three net.
How the graph works: a search never touches the database first. The aggregator fans (lat, long, radius, k) out to every in-memory QuadTree partition, gets back short lists of LocationIDs with popularity, merges them, then hydrates the winners from cache or database. Writes go the other way: database row first, then the owning partition's tree, then the reverse index that makes rebuilds possible.
Web Client, Mobile Client
→ Load Balancer
→ Aggregation Service (stateless, mark distributed)
→ QuadTree Server 1…N (Service: in-memory tree per hash(LocationID) partition,
primary + secondaries, mark distributed) → returns (LocationID, lat, long, popularity)
→ Memcached (hot place records, LRU)
→ MySQL (Places, Reviews, Photos; sharded by LocationID)
→ Blob Store + CDN (photo bytes; rows store URLs)
→ Place Service (writes: addPlace, updatePlace, deletePlace, addReview)
→ MySQL, then the owning QuadTree Server, then the QuadTree Index
QuadTree Index (Service or Redis: server → set of (LocationID, lat, long))
→ rebuild feed into a replacement QuadTree Server
Cron → Worker (popularity refresh from MySQL into the trees)
Components:
user_location = (37.78, −122.41), radius_filter = 5000, maximum_results_to_return = 50, sort = highest rated.A new place opens: Place Service writes the 793-byte row to MySQL and gets a LocationID. It hashes the ID to find the owning partition and sends (LocationID, lat, long). The primary descends to the leaf and appends; if the leaf passes 500 it splits into four and redistributes. Secondaries apply the insert within milliseconds. The QuadTree Index adds the entry to that server's set, so a future rebuild includes it.
A partition dies: primary gone, a secondary takes over; same tree, nothing to rebuild. Primary and secondary gone together: allocate a new server, fetch its set from the QuadTree Index, rebuild the tree in memory, rejoin the fan-out. The alternative, a full scan of Places hashing every row, takes far longer, and the partition serves nothing meanwhile. Users searching that area silently miss places, which is why rebuild speed matters.
Dense downtown: the user's leaf may hold 12 places when they asked for 50. Expansion through neighbours continues until the count or the radius is satisfied. This is the case a fixed grid could not handle without one cell holding tens of thousands of places.
Places (793 B): location_id, name, lat, long, description, category, popularity
Reviews: location_id, review_id, user_id, text, rating, ts — keyed by location_id
Photos: photo_id, owner_type, owner_id, url — bytes in Blob Store
TreeEntry (~25 B): location_id, lat, long, popularity — in memory on the owning partition
QuadTreeIndex: server_id → set of (location_id, lat, long) — the rebuild source
Places sharded by location_id and replicated; Reviews keyed by location_id so a place's reviews co-locate
Tree partitions by hash(location_id); each partition has a primary and one or two secondaries
Popularity lives in both the row and the tree entry; the tree copy is refreshed lazily
Photos are URLs in the row; bytes in object storage behind a CDN
A geohash prefix index (Redis GEOSEARCH, Elasticsearch geo_point, PostGIS) instead of a QuadTree, if you explain the density and boundary problems. S2 or H3 cells. Cassandra or DynamoDB for Places instead of sharded MySQL. Region-then-hash sharding to bound fan-out, with the hotspot risk named. Kafka between Place Service and the index tier so inserts survive a partition restart. What matters is that you can argue the tradeoff.