Designing a Proximity Service ("Find Nearby Restaurants") for System Design Interviews

Designing a Proximity Service ("Find Nearby Restaurants") for System Design Interviews

"Design Yelp" or "find drivers near me" is a classic system design prompt. The core of the problem is one question: how do you answer "what is within 2 km of this point?" fast, for millions of points?

1. Requirements first

  • Functional: given latitude, longitude and a radius, return nearby businesses, ranked by distance or rating.

  • Non-functional: low latency reads (under 200 ms), very read-heavy (reads outnumber writes 100:1 or more), and business data changes slowly.

  • Scale estimate: 200 million businesses, 100k search QPS at peak.

2. Why a plain SQL query is not enough

WHERE lat BETWEEN a AND b AND lng BETWEEN c AND d with two separate indexes still scans a large strip of the planet. You need an index that understands two dimensions.

3. Option A: Geohash

Geohash encodes a point into a base32 string by repeatedly splitting the world in half (longitude, then latitude). Points that share a longer prefix are close together. Precision 6 gives cells of about 1.2 km x 0.6 km.

Search: compute the user's geohash at the right precision, then query that cell plus its 8 neighbors (neighbors matter because a point near a cell edge is close to points in the next cell). Filter by exact distance afterward.

Pros: it is just a string column with a normal B-tree index, easy to shard and cache. Cons: fixed cell sizes do not adapt to density (Manhattan versus a desert).

4. Option B: Quadtree

A quadtree recursively splits a region into four children until each leaf holds at most, say, 100 businesses. Dense cities get deep trees, empty areas stay shallow. The whole tree for 200 million points fits in a few GB of memory, so each search server can hold it.

Cons: rebuilding takes time on startup, and updates need care. Since business data changes slowly, a nightly rebuild plus incremental updates is usually fine.

5. Option C: Google S2 or H3

Mention that production systems often use S2 (Hilbert curve cells) or Uber's H3 (hexagons). You do not need deep detail, but knowing they exist shows breadth.

6. High-level architecture

  • Location service: stateless servers holding the geo index (geohash table or in-memory quadtree), behind a load balancer, read replicas for scale.

  • Business service: CRUD for business details, writes go to the primary database.

  • Cache: cache popular geohash cells to business ID lists in Redis.

  • For moving objects (drivers), switch to frequent location updates in an in-memory store and a short TTL.

7. How to close

Summarize the choice: "Geohash with neighbor lookup for simplicity and easy sharding, quadtree if density varies a lot, and a cache on hot cells." Then mention ranking, pagination, and what changes if objects move.

If you want to rehearse this out loud with feedback, AI tool for job interviews like the one I work on at Linkjob AI can run you through it as a mock round. Disclosure: I am part of the Linkjob AI team.