Skip to content

03. Proximity Service — Interview Q&A

~15 min read · Part 4 of 4 (Overview → HLD → LLD → Q&A)

These are the questions an interviewer actually asks once the map is on the whiteboard. Each answer is the strong version, followed by the wrong answer that quietly sinks candidates.

Q1. How do you find nearby places without scanning all 50 million? Index space, not just data. Assign every place a cell — a geohash prefix or a quadtree leaf — so a point-and-radius becomes "fetch the candidates in the ~9 cells the circle touches," a bounded in-memory lookup. Only after that reduction do you pay for exact distance (haversine) on the ~1,800 candidates, then filter and rank. A nearby query is not a distance-sort over all places; it is a bounded-cell fetch over a handful of cells, and the whole architecture exists to make that reduction cheap. Common wrong answer to avoid: "Compute distance from the user to every place and sort." That is O(50M) per query at 50,000 QPS — it never returns in 100 ms and there is no machine that saves it.

Q2. Geohash or quadtree — which spatial index, and why? They solve different halves. Geohash gives clean, prefix-based sharding and trivial neighbor math, but its fixed cell size is wrong for both a packed downtown and an empty county at once. A quadtree adapts: cap each leaf at ~100 places and dense regions subdivide into many small cells while sparse regions stay one big cell, so candidate fan-in is bounded by construction rather than by a cell size you guessed. The practical answer is to shard on geohash prefix and run a quadtree within each shard — clean sharding plus density-adaptivity. Google's S2 and Uber's H3 are the industrial versions of "one cell size doesn't fit the whole planet." Common wrong answer to avoid: "Just use latitude and longitude columns with a B-tree index." A B-tree on lat and separately on lng can range-scan one dimension but not a 2D circle efficiently; you need a structure that indexes both dimensions together.

Q3. Why precision-6 geohash cells specifically? The cell size must match the common query radius. A precision-6 cell is ~1.2 km × 0.6 km, so a 1 km query is covered by the cell plus 8 neighbors — 9 cells, holding ~1,800 candidates downtown, which distance-filters and ranks in tens of milliseconds. Go coarser to precision 5 (~5 km cells) and each cell holds ~25× the places, so a dense cell carries ~5,000 and the candidate set blows past 20,000 — 100 ms of wasted scanning. Go finer to precision 7 (~150 m) and a 1 km query needs ~49 cells, multiplying lookups and cross-shard fan-out. Precision follows the radius. Common wrong answer to avoid: "Use the finest cells possible for accuracy." Fine cells don't improve accuracy — the exact-distance filter does that — they just multiply the number of cells each query must gather.

Q4. The catalog is 50 million places — is this a big-data storage problem? No, and saying so is the tell that you've mis-scoped it. Full records at ~2 KB are 100 GB — a normal database. The searchable index needs only ~40–100 bytes per place (id, lat/lng, a couple of ranking fields), so 50M fits in ~2–5 GB, comfortably in RAM on one large node and trivially across a small sharded cluster. The index fitting in memory is precisely what makes sub-50 ms queries possible. This is a read-latency-and-skew problem, not a storage-volume problem. Common wrong answer to avoid: "We'll need a massive distributed database for 50M places." The data is small; the interesting scaling is the 50,000 read QPS and its spatial skew, not the bytes.

Q5. How do you handle 50,000 QPS when every user's coordinates are different? Cache, but key the cache on the cell the user falls in, not their exact coordinates. Snap the raw lat/lng to a geohash cell (and bucket the radius and a coarse time window) before building the cache key, so every user standing within the same ~1 km cell issuing the same query shares one cached ranked page. In a downtown lunch crowd that collapses thousands of distinct requests into one entry — a ~70% hit ratio drops the index tier from 50,000 to ~15,000 QPS. Snapping to a coarser cell would lift the ratio toward 85% and halve index load again, at the cost of results centered on the cell rather than exactly on the user. Common wrong answer to avoid: "Cache by lat/lng." Raw coordinates vary by meters between users, so the hit ratio is near zero and the cache does nothing.

Q6. "Restaurants within 1 km, open now, ranked" at 50,000 QPS — walk the request. Snap the coordinates at the gateway and check the result cache; ~70% of the 50,000 land here and return a ranked page in one lookup. On a miss, cover the circle with 9 precision-6 cells, scatter-gather ~1,800 candidates from 1–2 in-memory shards, haversine-filter to the ~1,200 truly within 1 km, apply category and open-now (open-now computed from each candidate's stored hours bitmap against the current clock, never from the index) to reach ~400, rank those by a distance-plus-quality blend, take the top 20, and cache the page for 45 s. The ~15,000 misses × 9 cells is ~135,000 in-memory cell fetches/second across the shards — and no step ever scans the catalog. Common wrong answer to avoid: "Query the database for all restaurants, filter by distance and hours, sort by rating." That is the full scan again, plus it puts open-now and ranking on a store that can't sustain the QPS.

Q7. Why isn't "open now" stored in the index? Because it changes every minute and would force a continuous index rewrite, while location — what the index is actually for — essentially never changes. Split attributes by volatility: static location lives in the index; slow-drifting rating and review count are lagged aggregates the index tolerates being minutes stale; and the one fast-changing attribute, open-now, is derived at query time from stored hours and the current clock. Open now is not an index dimension; it is a query-time filter. Baking it in would trade a rare, cheap index update for a constant, expensive one. Common wrong answer to avoid: "Add an is_open boolean to each place and update it on a schedule." Now you're rewriting millions of rows every few minutes to track something a query-time comparison computes for free.

Q8. Sharding is by geohash prefix — doesn't that create hot shards? Yes, and that's the accepted cost of prefix sharding: geographically-close cells share a prefix, which is what makes neighbor lookups cheap, but it also means all of a downtown lands on one shard and gets hammered at lunch. The result cache absorbs ~70% before the index sees anything, and the hot shards get extra read replicas so the residual load spreads across copies rather than forcing a re-partition. Queries that straddle a shard boundary become a scatter-gather across two shards — fine when rare, worth watching when a boundary runs through a busy district. The alternative, sharding by a hash of place_id, spreads load evenly but destroys locality, turning every 9-cell query into a 9-shard fan-out. Common wrong answer to avoid: "Shard by hashing place_id for even load." Even load, but every neighbor query now scatters across many shards — you've traded a hot-shard problem for a fan-out problem on every single query.

Q9. A geo-index shard dies — what happens? Queries whose cells live on that shard fail over to a replica; if there's no replica ready, rebuild the shard from the place store. Because the index is a derived structure of only a few gigabytes, a rebuild is minutes, not hours — that's a direct payoff of keeping durability in the place store and treating the index as disposable. During the gap, cached pages for that region keep serving, and scatter-gather queries can return partial results from the surviving shard rather than erroring, since a slightly-incomplete nearby list beats a blank map. Common wrong answer to avoid: "We lose that region's data." The index holds no source-of-truth data; it's rebuildable from the place store, so a shard loss is a capacity and latency event, never data loss.

Q10. Why rank by more than distance, and how do you keep ranking off the hot store? Because the nearest place is often not the one the user wants — a 4.6★ spot at 300 m beats a 2★ one at 50 m. Ranking blends normalized proximity, rating dampened by review-count confidence (so a 4.9★/3-review place doesn't beat a 4.5★/2,000-review one), and a small open-now boost. Every field the scorer reads — lat/lng, rating, review count, hours — is projected into the in-memory index entry, so scoring the ~400 survivors is a few hundred multiply-adds with zero place-store reads. Ranking inputs are allowed to lag minutes because ordering is best-effort, not a correctness contract. Common wrong answer to avoid: "Sort by distance ascending." That's the naive nearest-first list users complain about; distance is one input, not the sort key.

Q11. The result cache goes down at peak — does the system survive? It degrades rather than falls over if it's sized for it. Losing the cache pushes the full 50,000 QPS onto the index tier — roughly 3× its normal 15,000 — so the index must run with enough headroom and replicas to take that, and single-flight coalescing on identical cell keys ensures a cold cache doesn't turn into thousands of duplicate fan-outs for the same cell. Cluster the cache with replicas so a single node loss is a blip. The read path stays alive on the in-memory index; latency rises, availability holds. Common wrong answer to avoid: "Nearby search goes down." The cache is an accelerator; the index tier is the actual system of record for queries and must be able to serve without it, just slower.

Q12. How fresh are results, and where does staleness bite? Freshness is deliberately tiered. Location edits propagate through the streaming index path in seconds; a new place is searchable within seconds to a minute. Rating and review count lag minutes behind by design, affecting only ranking order, never correctness. Open-now is exact to within the 45 s cache TTL, because it's computed at query time from static hours — the only staleness is how long a cached page lives, so a place closing at 15:00 might show open until 15:00:44 in the worst case. If a use case can't tolerate even that, recompute open-now on the cached candidate set post-cache rather than baking it into the page. Common wrong answer to avoid: "Everything is strongly consistent and always current." That would force synchronous index writes on every rating change and per-minute open-now rewrites — enormous cost to eliminate staleness the product doesn't care about.

Deeper follow-ups

  • How would you support arbitrary polygon or viewport queries (a rectangular map bounds) instead of a fixed radius?
  • How would you handle a mobile user panning the map continuously — debouncing, prefetching adjacent cells, or client-side caching?
  • If places had a delivery radius (DoorDash: "who can deliver to me"), how does the query invert, and can the same index serve it?
  • How would you A/B test a new ranking function without doubling index-tier load?
  • What changes when the indexed entities move (nearby drivers, nearby users on a dating app) — how does index-update frequency reshape the design?
  • How would you make the geohash grid degrade gracefully at the poles and the ±180° meridian, where cell geometry distorts?

How this round is scored

Interviewers use the proximity service to see whether you reduce the search space before you compute. The strong signal is reaching for a spatial index in the first two minutes and articulating why a full scan is hopeless at 50,000 QPS against 50M places — and then choosing cell granularity against the query radius with actual numbers, not vibes. Seniority shows in the three tradeoff discussions the problem is built around: index granularity versus query fan-in (coarse cells scan too much, fine cells look up too much), read-heavy caching keyed on cells rather than coordinates, and update-lag versus accuracy that lands "open now" at query time. The failure-mode section — hot shards from prefix sharding, a rebuildable index that makes shard loss a non-event, cache-loss headroom — separates candidates who have run spatial systems from those who have only drawn a grid. Doing the fan-in math out loud (9 cells, ~1,800 candidates, ~15,000 backend QPS after cache) and using it to justify precision-6 over precision-5 is what pushes the answer from "correct" to "senior."