DEV Community

Cover image for Design a proximity service: the system design interview walkthrough
Gowtham Potureddi
Gowtham Potureddi

Posted on

Design a proximity service: the system design interview walkthrough

Design a proximity service: the system design interview walkthrough

The request to design a proximity service — "find the restaurants near me" — sounds like one SQL query away. Compute the distance from the user to every place, sort, take the closest ten. For a hundred places that works; for the two hundred million businesses a Yelp-scale service indexes, scanning them all on every search is a non-starter. The interview asks you to return the nearest places in milliseconds, for thousands of searches a second, across the whole globe, where a dense city block holds thousands of pins and a stretch of countryside holds none — and that is a geospatial indexing problem, not a distance formula. This is a classic system design interview prompt because the naive answer (loop over everything) is obviously wrong, and the real answer lives entirely in how you turn two-dimensional space into something you can index and look up.

The round turns on two decisions. First, the spatial index — how you encode latitude and longitude so that "near" becomes a cheap lookup instead of a full scan, and how that choice copes with wildly uneven density. Second, the query path — given a point and a radius, how you generate a small set of candidate places, filter them by exact distance, and rank them, without missing a place that sits just across an index boundary. This walkthrough follows the path a strong candidate draws on the whiteboard — requirements, estimate, API and data model, high-level design, then the deep dives — and at each step it names the follow-up the interviewer uses to tell a memorised answer from an engineer who understands the tradeoff.

Title card for a system design interview walkthrough on designing a proximity service, showing a map pin with a search radius over a grid of geospatial cells and the nearest places highlighted, on a dark citrus-and-lavender background.

How the proximity service round is actually run

A proximity service round runs about 45 minutes on a shared canvas — you draw the boxes and arrows while you talk, and the interviewer interrupts. It is a favourite search-and-discovery problem because the one-line brief hides exactly one deep idea done well: you cannot compute distance to every place, so you need a way to index space itself and only ever look at a handful of candidates. Get the geospatial index and the candidate-generation query clean and you have shown the whole system in one problem; everything else (the API, the places database, the cache) is ordinary.

The interviewer rarely lets "store lat/long and sort by distance" stand. "There are two hundred million businesses and a thousand searches a second — you are not scanning them all per query, so how does the database even find the candidates near a point before you compute any distance?" That question — candidate generation without a full scan — is the one a copied answer can never rehearse, and the one this round is really testing.

The rounds here are modelled on how the loop runs, not scraped from any candidate's recall. What matters for prep is the shape: a blank canvas, a clock, and a follow-up after every decision you make.

The five-step framework for any HLD round

Every high-level design answer fits the same spine. Say it out loud at the start so the interviewer knows you have a plan, then walk it:

  1. Clarify requirements — functional and non-functional, and what you are explicitly not building.
  2. Estimate — number of places, searches per second, and the read/write skew, to justify every later choice.
  3. High-level design — the boxes and arrows: client, search service, geospatial index, places store, cache.
  4. Deep dive — the one or two decisions that actually decide this system.
  5. Follow-ups — bottlenecks, failure modes, and what you would change at ten times the scale.

What the debrief measures

The score is not "right or wrong design." A good HLD debrief reads on four dimensions, and every move below maps to one: problem solving (did you reach for a spatial index instead of a scan, and handle the density problem), communication (did you explain the boundary problem — why you query neighbouring cells — in a sentence), technical execution (geohash or quadtree, cell-plus-neighbours candidate generation, exact distance filter, a read-heavy cached index), and time management (did you spend your 45 minutes on the index and the query, not on the business-details schema). Reading a walkthrough teaches the design; it does not teach you to deliver it on the clock while someone pushes back.

Step 1 — Requirements: what a proximity service must do

Spend the first few minutes here. Jumping to boxes before you have scoped the problem is the fastest way to design the wrong system.

Type Requirement
Functional Given a user location and a radius (or a "nearest K"), return the closest places; filter by type (restaurant, hotel) and return their details; add, update and remove places.
Functional (optional) Rank results by more than distance (rating, popularity, open-now); search moving objects (nearby drivers/friends); autocomplete — call these out, then scope most of them for later.
Non-functional Read-heavy (far more searches than place edits); low-latency search (sub-100ms); places data is mostly static (businesses rarely move); correct across cell boundaries and dense areas; highly available; horizontally scalable.

The sentence that earns points: "This is a read-dominated search over mostly-static data, so the whole design is a geospatial index that generates a small candidate set near a point without scanning, backed by a cached, replicated places store — the write path is almost an afterthought." Say that and you have framed the entire design before drawing a box.

Step 2 — Capacity estimation (back of the envelope)

Estimation here is about proving one thing: the hard axis is candidate generation on a read-heavy, mostly-static dataset, not write throughput or storage.

Quantity Assumption Result
Places ~200M businesses globally fits a sharded index comfortably; much of it cacheable in memory
Searches ~100M users × a few/day ~thousands of searches/sec at peak → the read path is the system
Place edits new/updated/closed businesses rare — a trickle of writes → update the index asynchronously
Read:write searches ≫ edits ~100:1+ → optimise reads; the index is static enough to cache and replicate heavily

Two conclusions fall out, and you should say both out loud. First, you never scan — thousands of searches a second over two hundred million places means candidate generation must be an index lookup that returns a handful of nearby places, then you compute exact distance only on those. Second, the data is static and read-heavy — businesses almost never move, so the index can be heavily cached and replicated, and writes (a new or closed business) just update the index in the background. You have now pointed the interview at the geospatial index and the query — the real deep dive — before anyone asked.

Step 3 — API and data model

The interface is a single search call plus simple place CRUD; the design lives in the index behind the search, not in the API surface.

Call Operation
search(lat, lng, radius, filters) → places[] generate candidates from the geospatial index near the point, filter by exact distance and type, rank, return top K
getPlace(id) → place fetch a place's full details from the places store
addPlace / updatePlace / removePlace write to the places store and update the geospatial index (asynchronously)

The data model is the place, its full details, and the geospatial index that maps space to places:

Entity Notes
place id, name, lat, lng, type, plus denormalised details (rating, hours). The source of truth.
geo_index maps a geospatial cell (a geohash string, or a quadtree/S2/H3 cell id) → the list of place ids in that cell. This is what makes "near a point" a lookup.
place_details the heavy read-mostly blob served when a user opens a place; cached aggressively.

Step 4 — High-level design: the read-heavy search path

Now the boxes. A proximity service is a read-dominated search fronted by caches, with the geospatial index at its heart:

  • Client → search service: the client sends a location, radius and filters; the search service orchestrates candidate generation, filtering and ranking.
  • Geospatial index: the search service computes the user's cell (geohash/quadtree/S2 id), reads the place ids in that cell and its neighbours, and hands back candidates — this is the one non-obvious box and the heart of the design.
  • Places store + cache: candidate ids are expanded to place details from a store (sharded by region), fronted by a heavy cache because the data is static and hot areas are read constantly.
  • Ranking: candidates are filtered by exact distance and radius, then ranked (distance first, optionally blended with rating/popularity), and the top K are returned.
  • Write path (async): adding, updating or closing a business writes the place and updates the geospatial index out of band — writes are rare and never on the hot search path.

Say explicitly that the geospatial index turns "near a point" into an indexed lookup, not a scan, and that the whole system is read-heavy over static data, so caching and read replicas carry the load while the write path stays simple. Naming candidate generation and the read/write skew unprompted is a signal the interviewer is listening for.

A proximity service architecture diagram showing a client sending a location and radius to a search service, the search service computing a geospatial cell and reading place ids from a geospatial index for that cell and its neighbours, expanding candidates to details from a cached places store sharded by region, filtering by exact distance and ranking, and a separate asynchronous write path that updates places and the index when a business changes.

Deep dive: the geospatial index — geohash vs quadtree

This is the decision that decides the round. The whole problem is turning two-dimensional space into something an index can look up, and there are two families of answers.

Geohash (and its cousins S2, H3). A geohash encodes a latitude/longitude into a short string by recursively halving the world into a grid; nearby points share a prefix, so a prefix match pulls everything in a cell, and because the encoding follows a space-filling curve, a range scan sweeps up a neighbourhood in one shot. The huge practical win: a geohash is just a string on an ordinary database index — no special spatial database required — so writes are cheap and candidate generation is fast. You pick a precision (string length) whose cell size roughly matches your search radius. Google's S2 is the spherical version that behaves better near the poles (a fixed geohash cell is a fat square at the equator and a thin sliver up north), and Uber's H3 uses hexagons so every neighbour is the same distance away — all three are 64-bit hierarchical cell ids you index and range-scan.

Quadtree. A quadtree recursively splits space into four quadrants, subdividing a cell only until it holds at most N points — so dense Manhattan becomes a deep tree and an empty lake stays one coarse cell. That adaptivity is its strength: it handles uneven density gracefully where a fixed-precision geohash does not. The cost is that it is an in-memory pointer structure that is harder to put on disk and to rebalance as points move.

Which to use. For "find nearby," you care more about cheap writes and fast candidate generation than about heavy geometry, so a geohash/S2/H3 value on an ordinary index is the common production answer; reach for a quadtree when density is extreme and the index lives in memory. Saying why — the density tradeoff and the ordinary-index win — is what separates a strong answer from "I'd use geohashing."

"Dense cities have thousands of places per block and the countryside has none — how does your index cope with that, and why geohash over a quadtree (or the reverse)?" A fixed-precision geohash is simple and lives on an ordinary index but must pick one cell size; a quadtree subdivides only where it is dense, adapting to the skew, at the cost of an in-memory tree. Name the density tradeoff and the ordinary-index win.

A geospatial index comparison diagram, two cards. Left card geohash: latitude and longitude encoded to a string whose shared prefix means nearby, cells laid along a space-filling curve so a range scan sweeps a neighbourhood, stored on an ordinary index with cheap writes, but a fixed cell size at the chosen precision. Right card quadtree: space recursively split into four quadrants, dense areas becoming a deep tree and empty areas staying one coarse cell, adapting to density but living in memory as a pointer structure.

Deep dive: the nearby query — cells, boundaries and ranking

This is the decision most candidates under-think, and it is where the subtle bug lives. Generating candidates is not just "read my cell" — a place can sit a metre away but across a cell boundary, so reading only your own cell silently misses it.

Pick a precision, then read the neighbourhood. You choose a cell size (geohash length) whose cell roughly matches the search radius, compute the user's cell, and then read that cell plus its surrounding neighbours — the classic nine-cell (centre plus eight) query for a grid — so a place just over the edge is still a candidate. Too coarse a cell and you pull far too many candidates; too fine and you must union many neighbour cells to cover the radius; matching precision to radius is the balance.

Filter and rank. The index hands back a small candidate set — place ids near the point, not necessarily within the radius — so you compute the exact distance (haversine) to each, drop anything outside the radius, and sort by distance, optionally blending in rating or popularity for the final order. Return the top K. The pattern to name is cheap candidate generation from the index, then exact filtering on a handful of results — the index narrows millions to dozens, and precise geometry runs only on the dozens.

"A restaurant is ten metres away but just across a geohash boundary — does your query find it, and how?" Yes: you read the user's cell and its eight neighbours, so a place just over the edge is still a candidate; then you compute exact distance and filter by radius. Name the boundary problem, the neighbour-cell read, and the exact-distance second pass.

A nearby-query diagram showing a user pin at the center of a three-by-three grid of geospatial cells with a search radius circle crossing cell boundaries, the center cell and its eight neighbours read as candidates, a place just across a boundary still included, then an exact-distance filter dropping candidates outside the radius and a final top-K ranked by distance.

System Design
HLD · Search & discovery · 45 min
Design a proximity service out loud, with follow-ups

Practise on Zynter →

Deep dive: scaling a read-heavy, mostly-static index

This is the decision that proves you know where this system actually spends its resources. Businesses barely move, so the index is almost static and overwhelmingly read — which makes scaling mostly a caching and replication story, not a write story.

Cache and replicate. Because the data is static and searches concentrate on dense, popular areas (a city centre at dinner time), you cache hot cells and place details aggressively and serve reads from replicas; the index itself is small enough to shard by region and keep much of it in memory. Updates are asynchronous — a new, moved or closed business updates the place record and the geospatial index out of band, and a brief staleness in "is this place still open" is acceptable, so the write path never contends with search.

The moving-objects variant. Worth one sentence to show range: if the "places" are moving — nearby drivers or friends who ping their location every few seconds — the picture flips to write-heavy, and you keep an in-memory grid updated per location ping with short TTLs instead of a durable, cached index. For a business proximity service the data is static, which is exactly why caching wins; naming the contrast shows you know when it would not.

"What actually breaks at scale here — and what if the places were moving drivers instead of static restaurants?" For static businesses, nothing about writes breaks; the load is reads, so you cache hot cells, replicate, and shard the index by region. For moving objects you flip to a write-heavy in-memory grid updated per ping with TTLs. Name the read-heavy caching story and the moving-objects contrast.

System Design
HLD · Search & discovery · 45 min
Defend the geospatial index and query out loud

Practise on Zynter →

The follow-ups that decide the proximity service round

Scan the probes from each deep dive and they rhyme. Master these five and you are ready for a version of the question that is not drawn exactly like this one.

  • "Two hundred million places, a thousand searches a second — how do you find candidates without a scan?" → A geospatial index: encode the point to a cell (geohash/quadtree/S2) and read that cell's place ids, turning "near" into a lookup. (problem solving)
  • "Dense city vs empty countryside — geohash or quadtree?" → Geohash on an ordinary index is simple and cheap but fixed-precision; a quadtree subdivides only where dense, adapting to skew at the cost of an in-memory tree. (technical execution)
  • "A place is just across a cell boundary — do you find it?" → Yes: read the user's cell plus its eight neighbours, then compute exact distance and filter by radius. (communication)
  • "What carries the load?" → Reads over static data — cache hot cells and details, replicate, shard the index by region; the write path is asynchronous and rare. (problem solving)
  • "What changes if the objects move (drivers, friends)?" → Flip to a write-heavy in-memory grid updated per location ping with TTLs, instead of a cached static index. (technical execution)

Each maps to a debrief dimension. Reading this list teaches you the answers; it does not teach you to deliver them while someone interrupts — that only comes from saying them out loud.

How to prepare: a one-week plan

You do not need fifty systems. You need this one cold and the framework automatic, so the next "design X" is just new nouns in the same five steps.

  • Days 1–2: Learn the five-step framework until it is reflex. Do the proximity service end to end on paper — requirements, estimate, data model, the client → search service → geo-index → places store/cache path.
  • Days 3–4: Drill the geospatial index: geohash encoding and prefixes, the space-filling curve, quadtree subdivision and density, S2/H3, and why one lives on an ordinary index. Say each tradeoff in one sentence.
  • Days 5–6: Own the query and scaling — matching precision to radius, the boundary problem and the nine-cell read, exact-distance filtering and ranking, caching/replication, and the moving-objects variant. Answer each of the five follow-ups out loud.
  • Day 7: A full timed 45-minute round, narrating the whole way, with someone (or something) interrupting. This is the rep that counts.

This post is the deep walkthrough behind one row of the broader Top 25 system design interview questions — once the proximity design is automatic, the same spine carries the rest of the list.

Frequently asked questions

How do I design a proximity service step by step?

Follow the five-step HLD framework. Clarify requirements (return the nearest places to a location within a radius, filter and fetch details, CRUD places — read-heavy, mostly-static data, low latency); estimate to show the hard axis is candidate generation over hundreds of millions of static places at thousands of searches a second, not writes; define the search API and the place/geo_index model; draw the read-heavy path (client → search service → geospatial index → cached places store), with an asynchronous write path; then deep-dive the decisions that matter — the geospatial index (geohash vs quadtree vs S2/H3), the nearby query with cell-plus-neighbour candidate generation and exact-distance filtering, and scaling a read-heavy static index with caching and replication.

Geohash vs quadtree — which should I use in a proximity service?

Both turn 2D space into a searchable index, but they trade off differently. A geohash encodes a point into a string whose shared prefix means "nearby," lays cells along a space-filling curve so a range scan sweeps a neighbourhood, and — crucially — lives on an ordinary database index with cheap writes; its weakness is a fixed cell size at the chosen precision, which is coarse in dense areas and fine in empty ones. A quadtree subdivides space into four quadrants only where points are dense, so it adapts to uneven density beautifully, but it is an in-memory pointer structure that is harder to persist and rebalance. For "find nearby" you usually care more about cheap writes and fast candidate generation, so a geohash (or S2/H3) on an ordinary index is the common choice; reach for a quadtree when density is extreme and the index is in memory.

How does a nearby query avoid missing places across a cell boundary?

By reading more than one cell. You pick a cell size (geohash precision) that roughly matches the search radius, compute the user's cell, and then read that cell plus its eight surrounding neighbours — the nine-cell query — so a place that sits just across a boundary is still a candidate. The index returns a small candidate set of place ids near the point, not necessarily within the radius, so you then compute the exact (haversine) distance to each candidate, drop anything outside the radius, and sort by distance (optionally blending rating or popularity). The index narrows millions of places to a few dozen candidates, and precise geometry runs only on those.

Why is a proximity service read-heavy and how does that shape the design?

Because businesses barely change — a restaurant's location is set once and rarely edited — while users search constantly, so searches outnumber edits by orders of magnitude. That static, read-dominated profile means the index and place details can be cached aggressively and served from read replicas, and the index (small enough to shard by region) can live largely in memory; updates to places run asynchronously out of band, and a little staleness is acceptable. The design therefore spends its effort on fast candidate generation and caching, and almost none on the write path — the opposite of a write-heavy system like a logging pipeline or a vote counter.

How would the design change for moving objects like nearby drivers?

It flips from read-heavy to write-heavy. Static businesses let you build a durable, cached index because the data rarely changes; moving drivers or friends ping their location every few seconds, so the dominant cost becomes absorbing a flood of location updates. You keep an in-memory grid (still cell-based) that you update per ping, with short TTLs so a stale position expires quickly, and you accept approximate freshness; a durable, heavily-cached index no longer fits because it would be constantly invalidated. The geospatial indexing idea carries over, but the storage and update strategy inverts — which is why naming the static-vs-moving distinction shows the interviewer you understand why caching wins for Yelp-style search.

How do I practise a system design interview out loud?

Reading a walkthrough is not the same as defending a design while someone interrupts. On Zynter, the HLD track runs live voice rounds modelled on how real system design loops run — you talk through a shared design on the canvas, and a voice interviewer pushes with the follow-ups above one at a time, then gives you a debrief on problem solving, communication, technical execution, and time management. The score is a practice signal, not a hiring decision.

Practise it on Zynter

You can write the distance formula. The round is won on the geospatial index and the boundary query.

Pick the Proximity Service round, draw the read-heavy search path on the canvas, and defend it out loud to a voice interviewer that keeps asking "how do you find candidates without a scan?" and "what about the place just across the boundary?" — then read the debrief. Zynter.ai is on-demand mock interviews modelled on real company loops, with 150+ rounds across 20 companies including the HLD system design track (Sep 2026).

Practise the Proximity Service round →
Browse all interview tracks

Top comments (0)