Cruxly › System design › Design Exercises

Proximity Search

indexing a plane instead of a key space

Prompt: design a "find nearby" service — given a user's coordinates, return the 20 closest points of interest (restaurants, drivers, listings) out of hundreds of millions, in well under 100ms.

40 minutes first. A normal database index sorts one dimension. This needs two, at once, and 'nearby' is a range that has no natural boundary.

Applying the four moves: Scope — return the 20 nearest points of interest to a coordinate, under 100ms, out of hundreds of millions; routing and live traffic out. Estimate — query rate and dataset size, plus how often points move (static restaurants versus moving drivers are different problems). Sketch — a spatial index (geohash, quadtree, or S2 cells) that turns a 2D proximity query into lookups on a 1D key. Deep dive — "nearby" has no natural boundary: a point just across a cell edge is closer than one inside the same cell, so the query has to search neighbouring cells and expand outward until it has enough results.

Why a normal index can't answer 'what's near me'

Scope. In scope: nearest-N query given a coordinate, insertion/update of point locations (a driver moving, say, once every few seconds), a radius-bounded variant ("within 5km"). Out of scope: routing/ETA calculation, points-of-interest content/reviews, this exercise is purely about the spatial index.

A standard B-tree index sorts one dimension. An index on latitude lets you efficiently find "all points between lat 40.70 and 40.75" — but among those, you still need every one that also falls in the right longitude band, and a naive combination (index on lat, then filter longitude in application code) degrades to scanning a strip that can be arbitrarily wide east-to-west, containing far more candidates than the actual nearby set. Two independent single-dimension indexes don't compose into an efficient two-dimensional query — this is the entire reason a dedicated spatial indexing scheme exists at all, and naming precisely why a straightforward index fails is the strongest opening move here.

Geohashing: folding 2D into a sortable 1D string

A geohash is a good proxy for proximity almost everywhere, and a deliberately-handled bad proxy exactly at cell boundaries.

Geohashing recursively bisects the map: split the world in half by longitude, record a bit for which half the point falls in, then bisect by latitude, record another bit, and repeat — interleaving longitude and latitude bits produces one string (usually base32-encoded) where a longer shared prefix generally means two points are physically closer. This turns a 2D query into a 1D range/prefix query, which a standard database index handles natively: WHERE geohash LIKE '9q8yy%' finds everything in that cell using an ordinary index range scan.

The boundary problem is the detail that separates a real answer from a memorized one. Two points a few meters apart, sitting just on opposite sides of a bisection boundary, can end up with almost entirely different geohash prefixes despite being nearly adjacent — the recursive-bisection structure that makes nearby points share long prefixes most of the time breaks exactly at cell edges. The fix is querying the target cell plus its 8 neighboring cells, not just an exact-prefix match — a real nearby- search implementation always expands the candidate set this way, and saying so explicitly is what shows the boundary case was actually understood rather than glossed over.

Alternative: quadtrees and H3, and when they're the better fit

A quadtree recursively subdivides space into four quadrants, but only where point density requires it — a sparse rural area stays one large cell, a dense city block subdivides many levels deep. This adapts cell size to data density automatically, unlike a fixed-precision geohash where every cell at a given hash length is the same physical size regardless of how many points it contains — useful when point density varies enormously across the service area (which, for anything covering both cities and rural areas, it always does).

H3 (Uber's hexagonal hierarchical index) uses hexagonal cells instead of geohash's rectangular ones specifically because a hexagon has uniform distance to all six neighbors, while a rectangle's diagonal neighbor is farther away than its edge neighbor — this makes "check the target cell plus its neighbors" a more uniform approximation of a true circular search radius. Naming H3 by name, and explaining specifically why hexagons over squares (uniform neighbor distance, not just "it's what Uber uses"), is worth doing precisely because interviewers can tell the difference between "I've heard of this" and "I understand why it exists."

Handling movement, and the honest edges

A geohash isn't a value that's assigned once — for moving points (drivers, in the classic version of this problem), every location update means recomputing the geohash and re-indexing. At high update frequency (a driver's location pushed every few seconds, times hundreds of thousands of active drivers), this is itself a non-trivial write load — the same write-amplification concern as any frequently-updated index, which argues for an in-memory spatial index (many real systems keep active driver locations in Redis using its native geospatial commands, which are geohash-based internally) rather than a durable on-disk index that pays a full write cost on every few-second location ping.

Radius queries versus nearest-N queries are subtly different requests. "Everything within 5km" is a fixed geohash-prefix-length lookup; "the nearest 20, whatever the radius turns out to be" requires expanding the search radius progressively (check the immediate cell and neighbors, and if fewer than 20 results are found, expand to the next ring of cells) — conflating the two, or assuming a fixed radius always contains enough results, is a common and avoidable mistake.

Sparse regions can return too few or zero results at a small fixed radius (a rural point of interest search that finds nothing within its starting cell) — the expanding-ring approach above handles this naturally, but it's worth naming as a real product-visible failure mode: the first version of a "nearby" feature that only checks the exact cell will silently return empty results in low-density areas, which reads to a user as a bug rather than as "there's genuinely nothing near you."

How to say it in the interview

"A B-tree index sorts lexicographically on one key, and latitude/longitude are two independent keys, so the entire exercise is choosing a way to fold two dimensions into one sortable key without destroying the notion of nearby in the process."

Checklist

Explained precisely why two single-dimension indexes don't compose into an efficient 2D query
Used geohashing to fold two dimensions into one sortable, index-friendly string
Named the boundary problem — physically adjacent points can have very different geohash prefixes
Queried the target cell plus its 8 neighbors rather than an exact-prefix match alone
Named H3's hexagonal cells and explained why hexagons over squares specifically
Distinguished a fixed-radius query from a nearest-N query as genuinely different search strategies
Chose an in-memory spatial index for high-frequency location updates rather than a durable on-disk index
Named sparse-region zero-result queries as a real, user-visible failure mode of a fixed-radius-only design

Practice this interactively