Design Nearby places
Design Yelp's "near me" search in a 45-minute interview: geohash, quadtree, S2/H3 and PostGIS compared, read-heavy caching, rating aggregation and ranking.
On this page
How to use this page
This page follows the order of a real system design interview. At each step there is a Your turn box: write your own answer first (it stays in your browser), then open ours and compare. Reading a finished design feels easy; producing one under time pressure is the skill you are practising.
| Phase | Time in a 45-min interview | What you produce |
|---|---|---|
| 1. Clarify requirements | 5 min | Functional list, non-functional targets, what's out of scope |
| 2. Estimate | 5 min | Searches/s, index size, write rate |
| 3. API | 5 min | The search call and the few write calls |
| 4. Data model | 5 min | Places, reviews, the geo index and the cache |
| 5. High-level design | 10 min | Boxes and arrows, the search path and the update path |
| 6. Deep dives | 10–15 min | Geo indexing, cell boundaries, density, ranking, freshness |
| 7. Wrap up | 2–3 min | Bottlenecks, failures, what you would monitor |
Users search for places near a location, optionally by category (restaurants, cafés) and radius, and see results ranked by distance, rating or relevance, with details for each place. Users can rate and review places. Business owners can add or update their place; changes may take a few minutes to appear. Skip photos, reservations and turn-by-turn directions.
1. Clarify the requirements
The interviewer says: "Design Yelp." Write down what you would ask, then 4–6 functional requirements, 4–5 non-functional requirements with a target, and 2–3 things you would put out of scope.
Compare with our answer
The questions that matter most: How many places and users? What radius range? Do results sort by distance, rating or "best match"? Are reviews in scope? How quickly must an owner's edit appear? Do places move (food trucks)? Then write the agreed list on the board, as below.
Functional: what it must do
- Search nearby: Location + radius (500 m – 20 km), optional category
- Sort and filter: Distance, rating, open now
- Place details: Name, address, hours, rating
- Rate and review: 1–5 stars and text; the average rating updates within minutes
- Add or edit a place: By owners; can appear after a delay
Out of scope
Photos and menusReservationsTurn-by-turn directions
Non-functional: how well it must work
| Quality | Target | Why |
|---|---|---|
| Search latency | < 200 ms (p99) | Used on the move |
| Availability | 99.99% | |
| Read-heavy | ~1,000 searches per place update | Optimise reads above all |
| Freshness | Edits visible within minutes | Owners can wait a little |
| Scale | 200 M places, 100 M daily users | Dense cities and empty deserts |
2. Back-of-the-envelope estimates
Assume 100 M daily users, 5 searches each per day, 200 M places, a 100-byte index entry per place (id, latitude, longitude, category, rating), 2 KB of details per place, and 2 M reviews written per day. Work out searches per second (average and peak), the size of the geo index, the size of the full place data, and the review write rate.
Compare with our answer
- Searches: 100 M × 5 = 500 M/day. ÷ ~86,400 ≈ 5,800/s average; lunch and evening peaks are about 3×, so plan for ~17–20 K/s.
- Geo index: 200 M × 100 B = 20 GB. That fits in the RAM of one ordinary server.
- Full place data: 200 M × 2 KB = 400 GB. A normal database with a cache in front.
- Reviews: 2 M ÷ 86,400 ≈ 23 writes/s. At ~1 KB each, about 2 GB/day, ~730 GB/year.
- Ratio: thousands of searches for every write. This is a read problem.
A strong answer mentions: searches/s with a peak factor · index size small enough for memory · details stored separately from the index · a write rate tiny next to the read rate · the conclusion "replicate, don't shard".
Assumptions: daily active users 100 M; searches per user per day 5; places 200 M; index entry per place 100 B; reviews written per day 2 M.
| Number | Estimate | Why it matters |
|---|---|---|
| Searches per second | 5.79 K / s | ≈ 5,800/s average; plan ~3× for peaks. |
| Geo index size | 20 GB | ≈ 20 GB: it fits in memory on one machine, so replicate it rather than shard it. |
| Full place data | 400 GB | ~2 KB per place with details: in a normal database with a cache. |
| Review writes per second | 23.1 / s | ≈ 23/s: writes are tiny next to searches, so one sharded SQL cluster is plenty. |
- The whole geo index fits in RAM, so the scaling strategy is read replicas of the index, not sharding.
- Searches cluster in cities: cache results per cell and category.
The surprise in the numbers is the index. Two hundred million places sounds like a big-data problem, but a compact entry per place is only 20 GB, which fits in memory. So the scaling plan is copy the whole index onto several machines and spread searches across them, not split it into shards. Sharding becomes worth it only if the index outgrows one machine (for example, if you add per-place embeddings for search) or if you need per-region data isolation.
3. API
Write the search call with every parameter it needs, then the calls for details, reviews and owner edits. What does pagination look like when results are ranked rather than sorted by an ID?
Compare with our answer
A strong answer mentions: latitude, longitude and radius on the search call · optional category, sort and open-now filters · a cursor rather than page numbers · details as a separate cacheable call · a review write that returns before the average updates · owner edits that are applied asynchronously.
The search endpoint is the hot path; everything else is ordinary CRUD (create, read, update, delete).
| Call | Request | Response | Notes |
|---|---|---|---|
GET /v1/search/nearby?lat=&lng=&radius=&category=&sort=&cursor= | – | { places[{ id, name, distance, rating }], nextCursor } | The hot endpoint |
GET /v1/places/{id} | – | { name, address, hours, rating, … } | Cached |
POST /v1/places | { name, lat, lng, category, hours } | 201 { placeId } | Owner adds a place |
PATCH /v1/places/{id} | { fields } | 200 | Owner edits; index updated asynchronously |
Two additions that interviewers like to hear:
POST /v1/places/{id}/reviewswith{ stars, text }returns201 { reviewId }. The place's average rating is updated asynchronously, within minutes, so the review write stays cheap.- Pagination uses a cursor. Ranked results can shift between requests as ratings change. The cursor encodes the query plus the last
(score, place_id)returned, so page 2 continues from where page 1 stopped instead of skipping or repeating places. Most users never go past the first page or two, so cap it (for example 10 pages).
4. Data model
What is the source of truth, what is derived from it, and where does each piece live? Where does a place's average rating come from, and how is it kept up to date?
Compare with our answer
A strong answer mentions: a places table as the source of truth · reviews keyed by place with one review per user per place · a rating sum and count rolled up on the place · a separate in-memory geo index built from the places table · a results cache keyed by cell and category · the index and cache being derived data that can be rebuilt.
places Relational (PostgreSQL) + cache
place_id, name, addresslat, lng, category, hoursrating_sum, rating_count (rolled up from reviews)updated_at
Source of truth for details; modest size, rarely written.
reviews Relational (PostgreSQL), sharded by place_id
review_id, place_id, user_idstars (1–5), text, created_atUNIQUE (place_id, user_id)
Small write rate; all reviews of a place sit together for paging and re-aggregation.
geo index In-memory (geohash prefix map or quadtree), replicated
geohash (e.g. “tdr1w”) → [place_id, …]or quadtree: node → children / place ids
Built from the places table; answers “who is in these cells?” in microseconds.
search cache Redis
(geohash cell, category) → candidate ids + rating (TTL minutes)exact distance and final order computed per request
Popular areas and categories repeat constantly.
The key idea is one source of truth, several derived copies. The places and reviews tables in PostgreSQL are the truth. The geo index and the results cache are both built from them, can be thrown away and rebuilt, and are allowed to be a few minutes behind.
Three details worth saying out loud:
- Store
rating_sumandrating_count, not just an average. Adding a review is thenrating_sum += stars, rating_count += 1, and editing a review from 2 to 5 stars israting_sum += 3. With only an average stored, you cannot apply an edit without re-reading every review. UNIQUE (place_id, user_id)stops one account from reviewing the same place twice, which is the first and cheapest defence against review spam.- Reviews are sharded by
place_id, so all reviews of one place sit together: paging through them and recomputing a place's totals is a single-shard query.
5. High-level design
Sketch the boxes: how does a search find candidates, where do details come from, and how does an owner's edit reach the index? Then step through ours.
Compare with our answer
The architecture, then the search path and the update path
- The architecture is read-optimised. A stateless search service queries replicas of an in-memory geo index and a results cache. The place service and database are the source of truth, and a change stream rebuilds the index replicas in the background.
- A search converts the user’s location into a geohash cell, adds the eight neighbouring cells so places just across a border aren’t missed, collects candidate places from the in-memory index, filters by exact distance and category, ranks, and fetches details for the top results.
- An owner edits their café’s hours. The change is saved in the places database and flows through a change stream to an index builder, which updates every index replica within a few minutes.
| Component | What it does |
|---|---|
| Search service | Stateless; geohash maths, filtering, ranking |
| Geo index replicas | The whole index in memory on each replica; add replicas for more QPS |
| Results cache | Hot (cell, category) combinations |
| Places & reviews service + DB | Details, owner edits and reviews; rolls ratings up into rating_sum / rating_count |
| Change stream + index builder | Propagates edits to the index within minutes |
Trace the search out loud, one hop at a time:
- The phone sends
lat=40.7580, lng=-73.9855, radius=1000, category=cafe. The load balancer picks any search instance; they are stateless. - The search service computes the geohash cell of the location and its neighbours, then asks the results cache for
(cell, cafe). - On a miss, it asks a geo index replica for the places in those cells: perhaps 140 candidates in a dense area.
- It computes the true distance to each candidate, drops those outside 1 km and those that are closed if
openNowis set, ranks the rest and takes the top 20. - It fetches details for those 20 (from a details cache, falling back to the places database) and returns them.
The update path runs the other way, asynchronously: the owner's edit or a new review is written to PostgreSQL; change data capture (CDC, a process that reads the database's write-ahead log and turns each committed change into an event, for example Debezium) publishes it to a stream; the index builder applies it to every replica.
6. Deep dives
Before reading on, write two or three sentences on each: how would you index 200 M points so "within 1 km of here" is fast? What goes wrong at a cell boundary? How do you cope with Manhattan and the Nevada desert in the same index? How would you rank a 5.0 with 2 reviews against a 4.6 with 3,000?
Compare with our answer
A strong answer mentions:
- A spatial index (geohash, quadtree, S2/H3 or an R-tree) that turns a 2-D range into a few lookups, and why two B-tree range conditions don't.
- Searching neighbouring cells and filtering by true distance; choosing a cell size from the radius.
- Adaptive cells or expanding the search until enough candidates are found.
- Two-stage retrieval then ranking, with a smoothed (Bayesian) rating.
Geo indexing: how do we find places within 1 km quickly?
The naive query is WHERE lat BETWEEN a AND b AND lng BETWEEN c AND d. A normal B-tree index (the sorted index most databases use by default) on (lat, lng) can use only the first range: it finds every place in a thin horizontal stripe of latitude that circles the whole planet, then checks longitude for each one. Two independent indexes don't help either; the database must intersect two huge lists. What we need is an index where nearby on the map means nearby in the index.
| Option | How | Good at | Catch |
|---|---|---|---|
| PostGIS (GiST / R-tree) | The database indexes bounding boxes in a tree; ST_DWithin and the <-> nearest-neighbour operator use it | Exact, simple, transactional; one system to run | Each query does real work on the database; at ~20 K searches/s you need many replicas |
| Geohash | Interleave the bits of longitude and latitude, encode in base 32; places sharing a prefix are in the same cell | Plain strings: works in any key-value store, sorted set or cache key; trivially cacheable | Fixed grid ignores density; cells are rectangles that shrink in width away from the equator; boundary problem |
| Quadtree | Split the world into 4 squares, and split again any square holding more than K places (say 100) | Adapts to density: tiny cells in Manhattan, huge ones in the desert | Lives in memory and must be built and kept in step; finding neighbours is trickier |
| S2 (Google) / H3 (Uber) | Hierarchical cells over the sphere: S2 projects onto a cube and orders cells along a Hilbert curve (64-bit ids, 31 levels); H3 uses hexagons at 16 resolutions | Better geometry than geohash, no pole or date-line oddities; H3 hexagons have 6 equidistant neighbours | Needs a library; H3 children don't exactly tile their parent, so roll-ups are approximate |
Geohash precision is what you tune. Cell sizes at the equator (width shrinks with latitude: at New York's 41° N a cell is about 76% as wide):
| Length | Cell size | Typical use |
|---|---|---|
| 4 | 39 km × 19.5 km | Region |
| 5 | 4.9 km × 4.9 km | Town, 5–20 km searches |
| 6 | 1.2 km × 0.61 km | Neighbourhood, ~1 km searches |
| 7 | 153 m × 153 m | Street |
Choice: an in-memory geohash (or S2) index on replicated search nodes, built from the places table. It answers in microseconds, needs no special database, and the same cell ids become cache keys. PostGIS is the right first version and the right answer for a smaller product; say so, then explain that at 20 K mostly repeated searches a second a purpose-built in-memory index is far cheaper per query. Elasticsearch and OpenSearch (geo_point, stored in BKD trees) and Redis GEOSEARCH (a 52-bit geohash in a sorted set) are other off-the-shelf options worth naming.
-- PostGIS: the simple first version
CREATE INDEX places_geog_idx ON places USING GIST (geog); -- geog geography(Point, 4326)
SELECT place_id, name,
ST_Distance(geog, ST_MakePoint(-73.9855, 40.7580)::geography) AS metres
FROM places
WHERE category = 'cafe'
AND ST_DWithin(geog, ST_MakePoint(-73.9855, 40.7580)::geography, 1000) -- uses the index
ORDER BY metres
LIMIT 20;# In-memory geohash index (uses the python-geohash package)
import math
from collections import defaultdict
import geohash
PRECISION = 6
index = defaultdict(list) # "dr5ru7" -> [Place, ...]
def add(place):
index[geohash.encode(place.lat, place.lng, PRECISION)].append(place)
def metres(lat1, lng1, lat2, lng2): # haversine distance
r = 6_371_000
p1, p2 = math.radians(lat1), math.radians(lat2)
dp, dl = p2 - p1, math.radians(lng2 - lng1)
a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
return 2 * r * math.asin(math.sqrt(a))
def nearby(lat, lng, radius_m, category):
cell = geohash.encode(lat, lng, PRECISION)
cells = [cell] + geohash.neighbors(cell) # 9 cells
hits = []
for c in cells:
for p in index.get(c, []):
if p.category == category:
d = metres(lat, lng, p.lat, p.lng)
if d <= radius_m:
hits.append((d, p))
hits.sort(key=lambda t: t[0])
return hitsCell boundaries: why check the neighbours?
The boundary problem, and the 3×3 fix
Two places a few metres apart can sit in different cells, and across some boundaries (the equator, the prime meridian) they share no prefix at all. So the search always reads the user's cell plus its 8 neighbours, then filters by true distance.
Dense cities and empty countryside
One length-6 cell in Midtown Manhattan can hold thousands of places; one in Nevada holds none. A fixed grid gives too many candidates in one and too few in the other.
| Option | How | Catch |
|---|---|---|
| Fixed cell size | Same precision everywhere | Thousands of candidates to score in cities; empty results in the countryside |
| Expand until enough | Start small; if fewer than ~50 candidates, move to the parent cell (drop one geohash character) and retry | Extra round trips in sparse areas, but each is microseconds in memory |
| Quadtree / S2 adaptive cells | Split a cell only when it holds more than K places | Neighbour finding is more complex; the tree must be rebuilt or updated as places change |
| Cap per cell | Keep each cell's list pre-sorted by quality; read only the top N per cell | The best place just outside the top N of a dense cell is never considered |
Choice: expand-until-enough on a geohash/S2 index, plus a per-cell cap in the densest cells. If the interviewer prefers a quadtree, the arithmetic is reassuring: 200 M places at up to 100 per leaf is about 2 M leaves, a few hundred megabytes of tree on top of the 20 GB of entries, built in minutes at start-up.
Ranking: which café comes first?
Retrieval and ranking are two separate stages. Retrieval finds a few hundred candidates by location and hard filters (category, open now). Ranking orders them with a score and returns the top 20.
| Option | Catch |
|---|---|
| Sort by distance | Fine as a user-chosen sort, but the nearest place is often not the one people want |
| Sort by average stars | A 5.0 from 2 reviews (perhaps the owner's friends) beats a proven 4.6 from 3,000 |
| Weighted score with a smoothed rating, distance, popularity and open-now | Weights need tuning; later, a model trained on clicks and visits can replace hand-written weights |
The smoothed rating is a Bayesian average: pretend each place starts with C imaginary reviews at the global mean m. With m = 3.8 and C = 20:
- 5.0 from 2 reviews: (20 × 3.8 + 10) ÷ 22 = 3.91
- 4.6 from 3,000 reviews: (20 × 3.8 + 13,800) ÷ 3,020 = 4.59
The proven café wins, and a new place with a handful of great reviews still climbs as reviews accumulate. A simple score is then something like 0.5 × rating_score + 0.3 × distance_score + 0.2 × popularity_score, each normalised to 0–1, with distance decaying (a place twice as far away is not half as good).
Personalisation and "open now"
Personalisation (cuisines you like, price levels you pick) is a re-ranking step on the top few hundred candidates, so it never touches the geo index. Keep the features in a per-user profile cache.
Open now is surprisingly fiddly: hours are stored in the place's local time zone, a place can close after midnight (18:00–02:00 belongs to the previous day), and holidays override the normal schedule. Store hours as (day, open, close) in local time plus the place's time-zone name, and evaluate them at query time in that zone; never precompute an "open" flag that goes stale every hour.
Reviews and rating aggregation
A review write inserts a row and must change the place's rating_sum and rating_count. Options:
| Option | How | Catch |
|---|---|---|
| Recompute on read | AVG(stars) over all reviews on every search | Absurd at 20 K searches/s |
| Same transaction | Insert the review and update the place's totals together | Simple and exact at 23 writes/s; a very popular place makes its row a lock hot spot |
| Asynchronous roll-up | Insert the review; a consumer of the change stream adds it to the totals, which flow to the index like any edit | The rating lags by seconds to minutes, which the requirements allow |
Choice: insert the review, roll up asynchronously, and run a nightly job that recomputes totals from the reviews table to repair any drift. The index carries the rating so ranking never touches the database.
Freshness: how do edits reach the index?
An owner changes opening hours; a new review moves the rating. Updating every replica synchronously on each write would make writes slow and couple them to every search node. Instead, writes go to PostgreSQL; CDC publishes each change to a stream such as Kafka; each index replica (or a builder feeding them) applies changes in order.
New replicas start from a snapshot (a full dump of the index taken at a known stream offset) and then replay the stream from that offset. A nightly full rebuild from the database catches anything the stream path got wrong, and is swapped in atomically.
Caching a read-heavy service
Searches cluster heavily: lunchtime café searches in central London repeat thousands of times with nearly identical inputs. But the exact location differs per user, so caching final results by raw coordinates gives almost no hits.
- Cache candidates per
(cell, category), not final results. Distance and the final order are computed per request from the cached candidates, which is cheap. - Details cache per
place_idwith a TTL of minutes, deleted when the place changes. - CDN for photos and static assets; search responses are personalised and short-lived, so they mostly bypass it.
- A busy cell like Times Square is a hot key; keep the top cells in each search instance's local memory for a few seconds as well (see caching).
7. Bottlenecks, failures and monitoring
Scaling bottlenecks
| Bottleneck | Fix |
|---|---|
| Read QPS | Add index replicas behind the load balancer; cache hot cells |
| Hot areas (Times Square) | Results cache by (cell, category, sort) |
| Index rebuilds | Build a new index in the background and swap atomically |
| Global latency | Deploy replicas in several regions; route to the nearest |
When things fail
| Failure | What happens |
|---|---|
| An index replica dies | LB stops sending it traffic; others serve; a new replica loads a snapshot |
| Index builder lags | Searches use slightly stale data; alert on lag |
| Places DB down | Searches still work from the index + cache; edits wait |
What to monitor
Search latency (p99)Results per query (too many / too few)Index freshness lagCache hit ratioReplica memory and QPS
8. Follow-up questions
Answer these three in order before opening ours. 1) Food trucks change location every few hours, and delivery couriers every few seconds. Does the design still work? 2) The product team wants "search along my route" for a road trip. What changes? 3) A competitor floods your newest restaurants with one-star reviews from fresh accounts. What do you do?
Compare with our answer
A strong answer mentions:
- Food trucks are fine as normal edits if minutes of lag are acceptable; couriers are not: fast-moving objects need a separate in-memory index updated every few seconds (as in Uber), kept apart from the static places index.
- Cover the route's polyline with cells (S2 can cover a buffered line), search those cells, and rank by detour time rather than straight-line distance.
- Rate-limit and score reviews by account age, history and network; hold suspicious reviews out of the average until they pass checks; subtract removed reviews from the totals; and alert on sudden rating drops.
How do you stop fake reviews?
Limit one review per user per place, weight reviews by account age and history, detect bursts from new accounts or one network, and hide (not delete) suspect reviews from the average.
How would you handle moving things, like food trucks?
Frequent location updates → keep those in a separate fast-changing index (like Uber’s) rather than the static places index.
Geohash vs quadtree vs H3?
Geohash: simple strings, easy to cache. Quadtree: adapts to density. H3/S2: hierarchical cells with nicer geometry; used by Uber and Google.
More senior follow-ups
- Multi-region. The index is only 20 GB, so every region keeps a full copy and serves its own users; the places database has one primary region, and CDC fans changes out to every region's index. An edit takes slightly longer to reach far regions.
- Exact nearest-k instead of a radius. "The 10 closest petrol stations" has no radius; search the user's cell, expand outwards ring by ring until you have k results and the next ring is farther than the k-th result.
- Polygon areas. A national park or an airport is an area, not a point; store its polygon and index it under every cell it overlaps (S2 coverings do this well).
- Search by name or text. "Joe's pizza near me" combines a text match with a location filter; that is a search engine job (Elasticsearch/OpenSearch with
geo_distancefilters), see search.
- Numbers: ~5,800 searches/s average, ~20 K/s peak; 200 M places × 100 B = 20 GB index (fits in RAM); 400 GB details; ~23 review writes/s.
- Scale by replication, not sharding: every search node holds the whole index.
- Index: geohash or S2 cells in memory; PostGIS (GiST) is the right smaller-scale answer; quadtree adapts to density.
- Boundaries: search the cell + 8 neighbours, or cover the radius's bounding box; then filter by true distance. Cells must be at least the radius in both dimensions.
- Density: expand to the parent cell until enough candidates; cap per cell in dense areas.
- Ranking: retrieve a few hundred, re-rank by score; use a Bayesian average, not raw stars.
- Ratings: store
rating_sumandrating_count; roll up asynchronously and idempotently; nightly recompute. - Freshness: PostgreSQL → CDC → stream → index replicas; snapshot + replay for new replicas; drop lagging replicas.
- Cache candidates per
(cell, category), details per place; local cache for hot cells.
1. Your places table has a B-tree index on (lat, lng). Why is WHERE lat BETWEEN … AND lng BETWEEN … still slow for a 1 km search?
A composite B-tree is sorted by latitude first, so it narrows to a latitude stripe and then checks longitude row by row. A spatial index (geohash, S2, R-tree) keeps nearby points nearby in the index.
2. A user stands 30 m from the edge of geohash cell dr5ru7 and searches for cafés within 300 m. The search reads only dr5ru7. What happens?
Nearby points can fall in different cells (and may share no prefix). Reading the 8 neighbours and filtering by true distance fixes it. Returning far places is avoided by the distance filter, not by the cell choice.
3. The geo index is 20 GB and peak load is 20,000 searches per second. What is the best way to scale it?
It fits in memory, so each node can answer any query alone; replicas scale reads with no routing and no cross-shard queries. Sharding only pays once the index outgrows one machine.
4. Café A has 5.0 stars from 2 reviews; café B has 4.6 from 3,000. Both are 300 m away. Which ranking rule handles this best?
A Bayesian average gives A about 3.9 and B about 4.6, so B wins, yet A rises naturally as reviews arrive. Sorting by count alone buries every new place.
5. The rating roll-up consumer reads review events from a stream and adds each to the place's rating_sum. It crashes after an update but before committing its offset. What is the risk and the fix?
Streams deliver at least once, so a replay double-counts unless the update is idempotent. A nightly recompute from the reviews table repairs any drift that slips through.
6. A design uses length-6 geohash cells (1.2 km × 0.61 km) and the 3×3 neighbour block for 1 km searches. What is wrong?
Nine cells cover the radius only if each cell is at least the radius in both directions. Either use a coarser precision or cover the radius's bounding box with all overlapping cells.
7. An owner edits opening hours. Which update path fits the requirements?
Edits may take minutes to show, so an asynchronous stream keeps writes cheap and searches fast. Synchronous updates couple writes to every replica; a rebuild per edit is far too slow.
Score 60% or more and the lesson is marked complete.