Find nearest courier for each customer
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given two sets of 2D points: customers C = {c1..cn} and active couriers D = {d1..dm}, return for every customer the nearest courier by geographic distance (assume Euclidean or great-circle; specify which). Provide an algorithm beyond the O(n*m) brute force, discuss appropriate spatial data structures (e.g., k-d tree, R-tree, uniform grid hashing), and analyze time and space complexity. Address tie-breaking, handling duplicate locations, and precision issues. Follow-ups: how would you support frequent dynamic updates to courier locations, batch queries, or constraints like maximum pickup radius?
Quick Answer: This question evaluates competence in spatial algorithms and data structures, specifically nearest-neighbor search, spatial indexing, numerical robustness, tie-breaking and complexity analysis for large-scale 2D point sets.