Design a Proximity Service

Where an interviewer pokes next

Getting the boxes right is the easy half. These are the questions that separate a candidate who drew the diagram from one who has run the thing. Answer each one out loud before you open it.

Show all answers

1. 01

   Why can't a normal database index answer "what's near me" efficiently?

   Show the answer

   Because standard indexes (B-trees) are one-dimensional: they order rows along a single key and answer range queries on that one dimension. Nearness is inherently two-dimensional — it depends on latitude and longitude together — and indexing the two columns separately doesn't help, because a point that's close in 2D can be far apart in either single dimension's ordering. So a query like "within 2km of this point" can't prune effectively with ordinary indexes; the database ends up applying the distance formula to a huge fraction of the table, which is a full scan per query and collapses at millions of pins. Spatial indexes exist precisely to fix this by mapping 2D space onto a structure where "near in space" corresponds to "near in the index" — a geohash prefix, a quadtree leaf, or an S2 cell — so a nearby query becomes a cheap cell lookup that returns a small candidate set, and the exact distance math runs only on those few candidates.

2. 02

   How does a geohash turn 2D coordinates into a locality-preserving 1D key?

   Show the answer

   A geohash recursively bisects the world: it alternately splits the longitude range and the latitude range in half, emitting a bit each time for which half the point falls in, and interleaves those latitude and longitude bits into one binary string (usually rendered in base32). The key property is that this preserves spatial locality — two points that are close together on the map agree on more of their leading bisections, so they share a longer prefix, whereas a plain hash would scatter nearby points to distant values and a naive concatenation of lat and lng wouldn't keep 2D neighbors adjacent. Because proximity now corresponds to prefix similarity, a geohash effectively defines a grid of cells (a prefix of a given length is a cell of a known size — six characters is roughly a 1.2km cell), and "find nearby" becomes a prefix/range lookup on any ordinary sorted index or key-value store. To search around a point you look up its cell plus its eight neighboring cells (to handle the boundary problem) and then refine by exact distance.

3. 03

   Geohash vs quadtree — when do you pick each?

   Show the answer

   They both map 2D space to a fast lookup, but they differ in how they carve space and thus how they handle uneven density. A geohash (or any fixed grid) uses cells of a uniform size determined by prefix length, which is dead simple, works on any sorted KV store, and is easy to shard — but it's a poor fit when data is skewed, because a single fixed cell size is simultaneously too coarse in a dense downtown (one cell returns tens of thousands of candidates) and too fine in the countryside (mostly empty cells). A quadtree instead subdivides adaptively: it splits a region into four quadrants only where the number of objects exceeds a threshold, recursing so that dense areas end up with many small cells and sparse areas remain a single large cell, and every leaf holds a bounded number of objects. That adaptivity makes quadtrees (and Google's S2, which builds a hierarchy of cells over the sphere to also avoid geohash's rectangular distortion near the poles) much better for highly non-uniform data and for keeping per-cell candidate counts balanced. The tradeoff is complexity: geohash is trivial to implement and store, while quadtrees/S2 need tree maintenance. So you pick geohash for simplicity and uniform-ish data, and quadtree/S2 when density varies a lot or you need global spherical accuracy.

4. 04

   What is the boundary problem and how do you avoid missing nearby objects?

   Show the answer

   The boundary problem is that cell edges are arbitrary lines that have nothing to do with actual distance, so if your query point happens to sit near the edge of its cell, the closest object might be just across that edge in an adjacent cell — and if you only searched the point's own cell you'd miss it entirely, returning a worse "nearest" result than reality. The fix is to always search the point's cell plus its neighboring cells (the eight surrounding cells for a geohash grid, or the adjacent leaves for a quadtree), which guarantees that any object within roughly a cell's distance is included in the candidate set regardless of which side of a boundary it fell on. The subsequent exact-distance refinement step then simply discards the extra candidates that are actually outside the requested radius. To keep this efficient you size cells close to the typical search radius, so "cell plus neighbors" reliably covers the query without dragging in an excessive candidate set — too-large cells return too many candidates, too-small cells force you to gather too many neighbor cells.

5. 05

   How do static places and moving objects lead to different designs?

   Show the answer

   They violate opposite assumptions, so they get opposite treatments. Static places (restaurants, ATMs) essentially never move and are queried far more than they change, which makes the workload read-heavy and cache-friendly: you build the spatial index once, keep it very stable, and aggressively cache the nearby-lists of hot, dense cells (a downtown cell's answer is valid for hours), invalidating only on the rare new/closed place. Moving objects (drivers, users sharing live location) flip this: each object emits a position update every few seconds, so the index is write-heavy and constantly changing, which means you must cheaply reindex on every update (recompute the object's cell key and move its single entry — Redis's geospatial commands do exactly this in memory) and you cannot cache results aggressively because they go stale almost immediately. Both, however, geo-shard cleanly, because geography itself is the partition key: a proximity query only concerns a bounded area, so you partition the index by region and route each query to the shard(s) covering its search box, with cross-shard work needed only at region borders. So the same coarse-index-then-refine core is tuned two ways: heavy indexing plus caching for static data, and lightweight in-memory constant reindexing with little caching for moving data.