OpenAI Interview: Design a Nearby Places Search (Yelp)

Part of the OpenAI system design question bank. The question is representative of the round. The analysis and solution are this site's own.

Problem statement

A user opens the app and sees nearby places, optionally filtered by category, sorted by distance or rating. The service stores hundreds of millions of places worldwide and answers location queries in well under 100 ms. Owners edit details; new places appear; closed places disappear.

This prompt has several reported variants: a basic location search, exact K nearest, index sharding, freshness of updates, and deep dives into geohash or quadtree internals. The solution below covers all of them.

Clarifying questions

• How many places? For practice: 500 million worldwide.
• Query rate? 100,000 per second at peak, read-heavy.
• Latency? Under 100 ms at p95.
• Query shape? Within a radius, such as 2 km, or the K nearest, such as 10, with optional category filters.
• Update rate? Detail edits are frequent; moves and new places are rare.
• Freshness? Detail edits visible within a minute; new places within minutes.

What makes location search hard

A normal database index sorts values along one dimension. A location has two: latitude and longitude. An index on latitude finds everything in a horizontal band around the world; an index on longitude, a vertical band. "Near this point" is neither.

So the core problem is turning two-dimensional proximity into something a one-dimensional index can find. Geohashes and quadtrees are the two standard answers. Each maps nearby points to nearby keys, most of the time. The words "most of the time" are where the interview goes deep: points just across a cell boundary are close in space and far apart in the index.

The second problem is density. Manhattan has thousands of restaurants per square kilometer; the Sahara has none. A fixed grid is too coarse in one place and too fine in the other.

So the driving tension is index simplicity versus adaptivity to density, with boundary correctness required in both.

flowchart LR
  U([User at lat, lng]):::user --> API[Search API]:::svc
  API --> GI[Geo index<br/>cell -> place IDs]:::store
  GI -->|candidates| API
  API --> DET[(Place details)]:::store
  API -->|sorted by distance| U
  classDef user fill:#e6efec,stroke:#315e55,color:#171717;
  classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717;
  classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717;

Key idea. A geo index maps two-dimensional nearness to one-dimensional keys. It is almost right; the design must handle the "almost."

Key concepts

Geohash

Divide the world in half by longitude and write a bit: 0 for west, 1 for east. Then halve by latitude: 0 for south, 1 for north. Keep alternating. Group the bits in fives and encode each group as one base-32 character. Each extra character narrows the cell. Points in the same cell share a prefix, so a prefix range scan finds a cell's points.

Quadtree

Start with one node for the whole map. When a node holds more than a set number of places, such as 100, split it into four children for its four quadrants. Dense areas become deep with small cells; empty areas stay shallow with big cells.

Haversine distance

The great-circle distance between two points on a sphere. Cheap to compute and accurate enough for ranking nearby results.

Separating index from details

The index needs only place ID, location, and a few filter fields. Details such as hours, photos, and reviews are larger and change more often. Keep them in separate stores so each can scale on its own.

Key idea. Geohash: fixed cells, prefix keys, easy to store and shard. Quadtree: adaptive cells, in-memory tree. Both need neighbor searches at boundaries.

1. Requirements

Before reading on. Write requirements for both query shapes. What property would a user notice first if it broke?

1.1 Functional requirements

• Find places within a radius of a point, optionally by category.
• Find the exact K nearest places to a point.
• Show place details: name, address, hours, rating.
• Let owners update details; add and remove places.

1.2 Non-functional requirements

• Latency under 100 ms at p95.
• Throughput 100,000 queries per second at peak.
• Correctness near boundaries: no nearby place missed because it sits in a neighboring cell.
• Freshness: detail edits within a minute; index changes within minutes.
• Availability 99.99% for search.

1.3 The constraint versus the property

Correct nearest results are the property. A search that misses the café across the street fails the user. Read latency at 100,000 QPS is the constraint. It pushes the index into memory and details into caches.

1. Back-of-the-envelope estimation

• Places: 500 million × about 1 KB of details = 500 GB for details. Sharded storage handles it.
• Index entries: 500 M × (8-byte cell key + 8-byte place ID + a few bytes of category) ≈ 10 GB. That fits in memory on one machine, so every search replica can hold the whole index.
• Queries: 100,000 per second at peak. If one replica serves 5,000 per second from memory, about 20 replicas, plus headroom and spread across regions.
• Detail fetches: 100,000 queries × 20 results = 2 million detail reads per second; a cache with a high hit rate absorbs most of them, because popular places repeat.
• Updates: say 1 million detail edits a day (about 12 per second) and 100,000 new or moved places a day. Trivial write load.

Key idea. The index is small enough to replicate everywhere; details are larger and cached. Reads dominate by orders of magnitude.

1. API design

Before reading on. Should the search response include full place details?

Include what the results list shows: name, category, rating, distance, and a thumbnail. Load full details, such as hours and photos, when the user opens a place. That keeps the search response small and the details cache focused.

GET /v1/places/search?lat=37.7749&lng=-122.4194&radius_m=2000&category=cafe&limit=20
GET /v1/places/nearest?lat=37.7749&lng=-122.4194&k=10&category=cafe
  -> {results: [{place_id, name, category, rating, distance_m, thumb_url}]}

GET   /v1/places/:id
PATCH /v1/places/:id        (owner)   {hours?, phone?, ...}
POST  /v1/places            (owner or admin) {name, lat, lng, category, ...}
DELETE /v1/places/:id

1. Data model

places (place_id, name, lat, lng, geohash6, category, rating, rating_count,
        address, hours_json, phone, updated_at, status)
        primary key place_id; sharded by place_id

geo_index (in memory on search replicas, rebuilt from places + change stream)
   geohash -> sorted list of (place_id, lat, lng, category, rating)
   or quadtree nodes with the same leaf payload

change_stream  (place_id, op, new_lat, new_lng, category, ts)   -- feeds replicas

Copying latitude and longitude into the index lets the search replica compute exact distances without a details lookup.

1. High-level design

5.1 A SQL range query on latitude and longitude

SELECT * FROM places
WHERE lat BETWEEN :lat - d AND :lat + d
  AND lng BETWEEN :lng - d AND :lng + d;

With separate indexes, the database picks one dimension and scans a band around the world, then filters the other. At 500 million rows and 100,000 QPS it is far too slow.

5.2 Fix 1: index by geohash

Store each place's geohash and index it. A query computes the user's geohash at a precision whose cells are near the search radius, and scans that prefix. Now the scan covers one small cell.

5.3 Fix 2: search the neighbors

A place 20 meters away can sit across a cell edge with a completely different prefix. Search the user's cell and its eight neighbors, compute exact distances, filter to the radius, and sort.

flowchart TB
  subgraph Grid["Geohash cells around the user"]
    direction LR
    NW[NW neighbor]:::svc --- N[N neighbor]:::svc --- NE[NE neighbor]:::svc
    W[W neighbor]:::svc --- C["user's cell"]:::store --- E[E neighbor]:::svc
    SW[SW neighbor]:::svc --- S[S neighbor]:::svc --- SE[SE neighbor]:::svc
  end
  classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717;
  classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717;

5.4 Fix 3: an in-memory index service

Move the index out of the details database into search replicas that hold it in memory. Details live in their own store and cache.

5.5 Fix 4: a change stream for freshness

Place changes publish events. Search replicas apply index changes within seconds; the details cache invalidates on detail edits.

5.6 The composed design

sequenceDiagram
  autonumber
  actor U as User
  participant A as Search API
  participant I as Search replica (in-memory index)
  participant C as Details cache
  participant D as Places DB
  U->>A: nearest k=10 near (lat, lng), cafe
  A->>I: query
  I->>I: user cell + 8 neighbors at precision p
  I->>I: exact distance, filter category, sort
  alt fewer than 10 within guaranteed radius
    I->>I: lower precision (bigger cells), repeat
  end
  I-->>A: 10 place IDs + distances
  A->>C: batch get summaries
  C-->>A: hits
  A->>D: misses
  A-->>U: results

Key idea. Geohash prefix scans on an in-memory index, always with neighbors, exact distances to finish, and a change stream to stay fresh.

1. Deep dives

6.1 Geohash in detail

Before reading on. Encode a point by hand to the first few bits, then explain why nearby points usually share a prefix, and when they do not.

Take San Francisco, about 37.77° N, 122.42° W. Longitude first: is −122.42 in the east half [0, 180] or west half [−180, 0]? West: bit 0. Now halve [−180, 0]: −122.42 is in [−180, −90]: bit 0. Then latitude: 37.77 in [0, 90]: bit 1. And so on, alternating. Every five bits become one base-32 character; San Francisco starts with 9q8y.

Points share a prefix exactly as long as they fell on the same side of every split so far. Two points close together usually do. But the splits are fixed lines. Two points a meter apart on either side of a split line differ at that bit, and at every bit after it, so their prefixes diverge early. The worst case is the prime meridian or the equator: points meters apart have geohashes that differ in the first character. That is why every geohash search includes the neighbor cells.

Precision choice: pick the precision whose cell is at least as large as the search radius, so the 3 × 3 block of cells covers the whole circle. For a 2 km radius, precision 5 (about 4.9 km cells) works; precision 6 cells (about 1.2 km by 0.6 km) would be too small.

Edge cases: cells shrink in width toward the poles, because longitude lines converge, so a fixed precision covers less area at high latitude. Neighbor computation must wrap across the 180° meridian. Mention both.

6.2 Quadtree in detail

Before reading on. Build a quadtree for the world with a leaf capacity of 100. How deep does it get over Manhattan, and how do you store it?

Start with the world as the root. Any node with more than 100 places splits into four. Over the ocean, the root's quadrant stays a single leaf. Over Manhattan, it keeps splitting until each leaf covers perhaps a block or two. The depth adapts to density, which is the point.

Search: descend to the leaf that contains the user. Collect its places. If the search circle crosses into neighboring leaves, visit them too: check each nearby node's bounding box against the circle, and descend only into boxes that intersect it.

Storage: 500 million places in leaves of up to 100 means at least 5 million leaves and a few million internal nodes. The whole tree, with place IDs and coordinates, fits in memory in a few tens of gigabytes. Build it at startup from the places table, and apply changes from the stream. Persist snapshots so a replica restarts fast. A quadtree can also be stored in a database, keyed by a node path such as 0231, which makes it look much like a geohash.

6.3 Geohash or quadtree

A good answer names the tradeoff and picks: geohash in a database for simplicity and easy sharding, or a quadtree in memory when density varies extremely and exact K-nearest queries matter. Either is defensible. Some systems use hierarchical cell systems that combine both ideas.

6.4 Exact K nearest

Before reading on. The user wants the 10 nearest cafés. You search the 3 × 3 cells and find 12. Are the 10 closest of those guaranteed to be the true 10 nearest?

Not necessarily. The 3 × 3 block is a square, and the true 10th nearest café might lie just outside it while one of your 12 lies in its far corner. The guarantee holds only up to the distance from the user to the nearest edge of the searched block.

The correct loop:

1. Search the user's cell and neighbors at some precision.
2. Sort the candidates by exact distance.
3. Let r be the distance from the user to the nearest boundary of the searched block. Any candidate within r is guaranteed correct.
4. If at least K candidates are within r, return the K closest.
5. Otherwise, drop one character of precision (cells four to eight times larger) and repeat.

With a quadtree, the same guarantee comes from a best-first search: keep a priority queue of nodes ordered by their minimum possible distance to the user, and stop when the K-th candidate is closer than the next node's minimum distance.

6.5 Sharding and caching

The index fits in memory, so the simplest scaling is replication: every search replica holds the whole index, and a load balancer spreads queries. Place replicas in several regions near users.

If the index grows too large for one machine, shard by geohash prefix. A query touches the shards that own its cells, usually one, sometimes two at a shard boundary. Hot areas, such as a big city, get finer shard splits and more replicas.

Cache popular queries by cell and category with a short time-to-live, such as 60 seconds: many users in the same neighborhood search for coffee at 8 AM. Cache place summaries by place ID. Invalidate a summary when its place changes.

6.6 Freshness of updates

Most updates change details, not location. An hours change updates the places table, then invalidates the details cache entry. No index change is needed.

A new place, a closed place, or a moved place changes the index. The write goes to the places table, which emits a change event. Every search replica consumes the stream and applies the change to its in-memory index within seconds. Nobody needs a new restaurant searchable within a millisecond; within a minute is fine.

Keep a periodic full rebuild of the index from the places table, such as nightly, as a safety net against missed events.

6.7 Radius search, step by step

Before reading on. Write the steps for "cafés within 1 km of the user," including how you pick the precision and what you do with results in the corners.

1. Pick the precision. The 3 × 3 block must cover the circle, so each cell must be at least as tall and wide as the radius. At 1 km, precision 6 cells are 1.2 km by 0.6 km: too short in one direction. Use precision 5 (4.9 km), or search precision 6 with a 5 × 5 block. The second reads fewer points in dense cities.
2. Compute the cells. Encode the user's point, then compute its neighbors, handling wraparound at the 180° meridian.
3. Scan each cell's prefix in the in-memory index, filtered by category.
4. Compute exact distances with the haversine formula.
5. Drop points outside the radius. The block is square; the search area is a circle. Points in the block's corners can lie well beyond the radius and must be removed.
6. Sort and limit. By distance, or by a score that mixes distance and rating.

For practice: in central Manhattan, a precision-5 cell might hold 20,000 places, so a 3 × 3 block is 180,000 points to check; a 5 × 5 block of precision-6 cells covers a much smaller area and might hold a few thousand. Choosing precision by density, not only by radius, keeps the scan small in cities.

6.8 A quadtree variant with a database

If the interviewer asks how to store a quadtree in a database: give each node a path key built from its quadrant choices, such as 0, 02, 021, 0213. Store leaves as rows keyed by path with their places. A range scan on a path prefix returns a whole subtree. That is almost exactly a geohash with adaptive depth, which is a good point to make: the two ideas converge.

Splitting a leaf rewrites its rows under four new keys in one transaction. Reads that raced the split see either the old leaf or the new children, never both, if the split replaces rows atomically.

1. Variants

7.1 Ranking beyond distance

Real results mix distance, rating, popularity, and whether the place is open now. Retrieve candidates by location first, then score them. Precompute open-now per place in the index for a fast filter.

7.2 Moving objects

Drivers or delivery couriers move every few seconds. Updates dominate instead of reads. Keep their locations in an in-memory store keyed by cell, and move an object between cells as it crosses boundaries.

7.3 Search by text and place

"Pizza near me" combines text search with location. Use a search engine with geo filtering, or retrieve by location and filter by text when the candidate set is small.

7.4 At ten times the queries

At a million queries per second, replicate the index to more regions and more replicas per region; the index itself does not grow with queries. The details cache becomes the heavier tier. Cache whole result lists for popular cells and categories with short lifetimes, since many users in one neighborhood search the same thing at the same time.

1. The transferable pattern

Location search is a spatial key that makes neighbors adjacent, plus a correction for when they are not. The same pattern applies to any multi-dimensional nearness problem: time and value ranges, embeddings with quantized cells, and IP ranges. Map to a one-dimensional key, search the neighborhood, and verify exact distances before returning.

Review: the 30-second answer

• Index small, details separate. About 10 GB of index in memory on every replica; 500 GB of details cached.
• Geohash prefix scans with neighbors. Precision from the radius; the 3 × 3 block every time.
• Quadtree when density varies. Adaptive leaves, best-first search for exact K nearest.
• Exact K nearest needs a guarantee radius. Expand until K results lie within it.
• Change stream for freshness. Details via cache invalidation; locations via index updates within seconds.

Quiz

Sources and further reading

• Geohash covers the encoding, precision table, and edge cases.
• Quadtree describes point quadtrees and their search.
• S2 Geometry documents a hierarchical cell system on the sphere used in production location services.
• The same read-heavy, cache-first thinking appears in a simpler form in the URL shortener.