Design Nearest-Pickup Search with Time

# Design Nearest-Pickup Search with Time Given historical trip-origination locations and an arbitrary query point expressed as latitude and longitude, explain how to find the `k` nearest pickup points efficiently. Then extend the design to account for pickup time so it could support real-time ride-sharing matching. ### Constraints & Assumptions - The geographic distance function, tie policy, and returned trip fields must be agreed before implementation. - Latitude and longitude are not automatically Cartesian coordinates. - The time-aware extension needs a defined time window or combined ranking objective. ### Clarifying Questions to Ask - Should distance use great-circle distance, an approved local projection, or another metric? - If several pickups have the same distance at the cutoff, which results and ordering are required? - Does time act as a filter, a secondary key, or part of a weighted space-time score? ```hint Separate filtering from ranking A time window can first select eligible pickups, after which a spatial index or bounded heap can answer the distance query. ``` ### What a Strong Answer Covers - A correct baseline scan and size-`k` heap after the metric is defined. - Spatial-index choices, coordinate treatment, exactness, and data-update costs. - A source-faithful time-aware extension with its ranking semantics made explicit. - Time, space, skew, cutoff ties, and real-time refresh trade-offs. ### Follow-up Questions 1. How would frequent new pickup events affect the index design? 2. When might a grid or geohash index be preferable to a tree-based spatial index?