Design Nearest-Pickup Search with Time
Capital OneSoftware Engineer · Online Assessment
Last updated
Design efficient nearest-pickup search for latitude-longitude data and a time-aware extension while clarifying distance, ties, result order, and temporal ranking.
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?
Hints
Hint 1
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.
Follow-up questions
- How would frequent new pickup events affect the index design?
- When might a grid or geohash index be preferable to a tree-based spatial index?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.