TOUGH TONGUE AI
  • Home
    LogoTOUGH TONGUE AI

    RESOURCES

    Loading...

    HomeLibrarySD Mock · Design Yelp / Nearby Friends

    SD Mock · Design Yelp / Nearby Friends

    Overview

    Design Yelp's nearby-places search on a live architecture board — drag components, wire them up, and defend your spatial index, partitioning, and rebuild story to an expert interviewer who watches every move.

    Your Instructions

    Design Yelp: nearby places

    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):

    • Notepad. Shared notes. Requirements, capacity math, schema, and end-of-session feedback live here. You can type in it too.
    • Architecture board. Your design canvas. Drag typed components, wire them, label edges, mark scaled tiers as distributed. If it is not on the board, it is not in your design.

    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."

    Design choices interviewers probe

    Read this before you go in. These are the decisions, and why they matter.

    The assumption the whole design rests on

    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.

    The spatial index: SQL, then a fixed grid, then a QuadTree

    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.

    • Step 1, two indexed columns. Store latitude and longitude, index both, query a bounding box with two BETWEEN clauses. A box instead of a circle is an accepted simplification. Why it fails: the latitude index alone returns every place in a band that circles the globe, and so does the longitude index. Intersecting two enormous lists is slow. The fix has to shorten the lists, which means the key itself must encode two-dimensional locality.
    • Step 2, fixed grid. Divide the map into cells. Each place gets a 4-byte GridID; index that. Make the cell size equal the query radius. Then every match is in the user's cell or one of its eight neighbours, and the query becomes 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.
    • Step 3, QuadTree (dynamic grid). Cap each cell at 500 places. When a cell exceeds the cap, split it into four equal quadrants and redistribute; repeat recursively. Downtown ends up covered by many tiny cells; the ocean stays one huge cell. Mechanics you must be able to state: every node has four children; only leaves hold places; point-to-leaf is a descent from the root (about 10 levels for 1M leaves); neighbours come from either a doubly linked list threading all leaves or parent pointers (siblings one hop away, cousins by walking up); search finds the leaf, then expands outward through neighbours until it has enough places or has exhausted the radius. The tree yields LocationIDs. Full records come from the database.

    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.

    What the index holds

    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.

    Partitioning the tree

    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.

    Replication and the rebuild problem

    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.

    Ranking: scatter-gather top-k

    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.

    Freshness, inserts, deletes

    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.

    Cache and load balancing

    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.

    Reference solution

    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.

    Requirements (lock these or take the defaults)

    • Add, update, delete places; add reviews (text, photos, star rating)
    • Given (lat, long) and a radius, return nearby places, up to a maximum count
    • Sort modes: best match (default), minimum distance, highest rated
    • 500M places, 100K search QPS, reads vastly outnumber writes, 20% growth a year in both
    • Places rarely move
    • A bounding box is an acceptable stand-in for a circle
    • Real-time search with minimum latency; a new place visible within seconds
    • Out of scope unless asked: free-text search over names, the photo pipeline, reservations

    Capacity

    • Place record: 8 (LocationID) + 256 (name) + 8 (lat) + 8 (long) + 512 (description) + 1 (category) = 793 B; × 500M ≈ 397 GB of rows, so full records cannot live in the index
    • Fixed-grid index: 8 B × 500M LocationIDs = 4 GB; 200M sq mi ÷ (10 mi × 10 mi) = 2M cells × 4 B ≈ 8 MB of keys (Grokking prints 20M cells; either way the keys are noise next to 4 GB)
    • QuadTree: 24 B (ID + lat + long) × 500M = 12 GB of leaf data; 500M ÷ 500 per leaf = 1M leaves; internal nodes ≈ leaves ÷ 3 ≈ 333K × 4 pointers × 8 B ≈ 10 MB; total ≈ 12 GB, fits one server today
    • Growth: 20% a year doubles the data in about 4 years (1.2⁴ ≈ 2.1), and 100K QPS lands on every partition once you hash-shard. Partition anyway.

    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.

    Components to put on the board

    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:

    • Clients (Web, Mobile). Send (lat, long, radius, max results, sort, filters) over plain HTTP. Nothing persistent; every search is one request.
    • Load Balancer. Spreads searches across the stateless aggregators. A second layer sits between aggregators and backends. Round robin to start; it drops dead servers for free but ignores load, so go load-aware when one box runs hot.
    • Aggregation Service (stateless, mark distributed). The brain of one search: validate the API key and quota, fan out to every QuadTree partition in parallel, merge the per-partition top-k, post-filter by true distance when sorting by distance, hydrate winners from Memcached then MySQL, page the result. Stateless, so scale by adding boxes.
    • QuadTree Servers (Service, stateful, mark distributed). Each holds an in-memory QuadTree over the places hashed to it: (LocationID, lat, long, popularity) in leaves capped at 500, internal nodes with four child pointers, leaves threaded for neighbour walks. The primary takes writes; secondaries serve reads with millisecond lag. This is the only tier that answers "what is near here." Without it you are back to intersecting globe-spanning index ranges.
    • QuadTree Index (Service, or Redis sets). Reverse map: server number → HashSet of (LocationID, lat, long). Updated on every insert and delete. When a partition loses primary and secondary, the replacement asks this server for its set and rebuilds without a database scan. Replicated; itself rebuildable by one pass over Places.
    • Memcached. Hot place records in front of the database, LRU eviction. Aggregators hydrate from here first. Sized to the observed hot set. Without it every popular restaurant is a database read on every search.
    • MySQL (or Postgres, or Cassandra). System of record: Places (793 B rows), Reviews keyed by LocationID so a place's reviews co-locate, Photos holding URLs. Sharded by LocationID and replicated. Everything the index caches is derived from here.
    • Blob Store + CDN. Photo bytes for places and reviews. Rows store URLs only; the CDN serves thumbnails so aggregators never ship image bytes.
    • Place Service. Handles addPlace, updatePlace, deletePlace, addReview. Writes the row, hashes the LocationID to find the owning partition, inserts into its tree, updates the QuadTree Index. A review updates the popularity aggregate in the database only.
    • Cron + Worker (popularity refresh). Periodically copies updated popularity from the database into the tree entries, so ranking stays roughly current without write-storming the index on every review.

    Walk one search: 50 highest-rated places within 5 km

    1. The client calls search with user_location = (37.78, −122.41), radius_filter = 5000, maximum_results_to_return = 50, sort = highest rated.
    2. The Load Balancer routes to an Aggregation Service instance, which validates the API key and checks the caller's quota.
    3. The aggregator sends (lat, long, radius, k = 50) to every QuadTree Server in parallel, hitting a read replica of each partition rather than the primary.
    4. Each partition descends from its root to the leaf containing the point, collects that leaf's places, then expands outward through neighbouring leaves (linked list or parent pointers) until it has 50 candidates or has exhausted 5 km. It returns its local top 50 by popularity as (LocationID, lat, long, popularity).
    5. The aggregator merges the per-partition lists into a global top 50. For a distance sort it computes true distance here (haversine, or Pythagorean at city scale) and re-ranks, because the index returned a bounding region, not a circle.
    6. For each winning LocationID the aggregator reads the full record from Memcached; on a miss it reads MySQL and fills the cache.
    7. It returns the JSON list (name, address, category, rating, thumbnail URL on the CDN) plus a page token for the next page.

    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.

    Schema

    • 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

    Scaling and wrap-up

    • Aggregators scale horizontally behind the load balancer; QuadTree partitions scale by memory (20% a year); replicas scale by read load (every partition sees every query)
    • Add partitions with consistent hashing so only a fraction of places move; the QuadTree Index makes the moved set explicit
    • Memcached absorbs hot-place reads; the CDN absorbs photo bytes
    • First metrics: search p99, slowest-partition latency (the fan-out tail), rebuild time after a double failure, tree memory per partition, empty-result rate
    • If time: Nearby Friends (moving objects, the Uber inversion), geohash and H3, text plus geo, cache warming after a rebuild, the antimeridian and the poles

    Equally defensible variants

    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.

    More in System Design Interview Prep: AI Coach Edition

    • SD Coach · Transactional Systems
    • SD Mock · Design Ticketmaster
    • SD Coach · Batch and Stream Pipelines
    • SD Coach · Real-Time Chat and Collaboration
    • SD Mock · Design Facebook Messenger
    • SD Mock · Design Uber Backend
    • SD Coach · Media Streaming
    • SD Mock · Design YouTube / Netflix
    • SD Mock · Design Instagram
    • SD Coach · Agentic AI
    • SD Coach · Agentic AI Architectures (Slides)
    • SD Mock · Design ChatGPT
    View the full course (43 sessions) →