Design a real-time proximity service that returns available drivers near a passenger's current location. Drivers move continuously and report a new location about every four seconds. Query density varies sharply between dense city centers and suburbs. Results must respect a search radius and driver state, and should not make vehicles appear to jump erratically on the client. ### Constraints & Assumptions - Current location and availability are latency-sensitive; historical trajectories have a different durability requirement. - Most searches are local to one city, so cross-city queries are exceptional. - The design may use a grid, quadtree, geohash, S2 cells, or another spatial index, but must explain boundary handling. - Exact capacity and QPS figures should be derived from clarified driver counts and update rates rather than assumed. ### Clarifying Questions to Ask - How many drivers are online per city, and what update loss or staleness is acceptable? - Is the query a fixed radius, nearest `k`, or both, and how many candidates may be returned? - Must distance mean straight-line distance, estimated travel time, or an exact route-service result? - How quickly must an accepted trip remove a driver from search results? ```hint Make the cell size part of the design A cell that is too large produces too many candidates; one that is too small increases the number of neighboring cells each query must inspect. ``` ### What a Strong Answer Covers - A partitioning and spatial-index strategy, including neighboring-cell lookup and uneven-density hot spots. - A high-write current-location store separated from asynchronous historical trajectory storage. - Update ingestion, stale-driver expiry, availability transitions, deduplication, and city-level routing. - Candidate retrieval, exact filtering, optional route-distance refinement, client smoothing, scaling, and failure recovery. ### Follow-up Questions - How would you handle two nearby drivers that fall on opposite sides of a geohash boundary? - What happens when a downtown cell becomes far hotter than neighboring cells? - How would you prevent an already matched driver from briefly reappearing because a location update arrived late?