Compute nearest courier for each customer
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
You are given two sets of 2D points: customers `C = {c1..cn}` and active couriers (dashers) `D = {d1..dm}`. Each customer `i` has coordinates `(xi, yi)`. Each courier `j` has coordinates `(aj, bj)` and an integer `id`. For every customer, return the `id` of the nearest courier by distance; on ties (equal distance), return the smallest `id`.
Work through the following parts:
1. Implement a correct brute-force solution and state its time and space complexity.
2. Design and implement (or outline) an approach that beats the `O(n * m)` brute force when `n` and `m` are large (up to `1e5`). Discuss appropriate spatial data structures such as a k-d tree, R-tree, or uniform grid (spatial hashing), and analyze the time and space complexity of your chosen approach.
3. Specify which distance metric you assume — Euclidean on a plane vs. great-circle distance on latitude/longitude — and explain how the choice affects correctness and your data structures.
4. Handle the edge cases: tie-breaking by smallest `id`, duplicate courier locations, and floating-point precision issues when comparing distances.
5. Follow-ups:
- How does your approach change if courier locations update frequently (insert, delete, move)?
- How would you support large batches of customer queries efficiently?
- How would you enforce a constraint such as a maximum pickup radius (a customer with no courier within the radius returns "no courier")?
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute nearest courier for each customer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given two sets of 2D points: customers and active couriers (dashers).
- `customers` is a list of points `[x, y]`.
- `couriers` is a list of `[a, b, id]`, where `(a, b)` is the courier's location and `id` is a unique integer id.
For every customer (in input order), return the `id` of the nearest courier by **Euclidean** distance. On ties (equal distance), return the **smallest** `id`. If there are no couriers, return `-1` for that customer.
Return a list of ids, one per customer, in the same order as `customers`.
Tips for a strong answer (beyond the executable core):
- Compare **squared** distances `(cx-ax)^2 + (cy-ay)^2` to avoid `sqrt` cost and precision loss.
- The brute force is `O(n*m)`; for `n, m` up to `1e5` build a spatial index over the couriers (uniform grid / spatial hash for `O(n+m)` expected, k-d tree for `O((n+m) log m)`, R-tree for dynamic updates + radius queries).
- For real lat/lng geography use great-circle (haversine) distance; planar Euclidean is only an approximation over a small projected region.
Constraints
- 0 <= number of customers, couriers <= 1e5
- Courier ids are integers; ids may repeat across distinct locations in adversarial inputs but tie-breaking still selects the smallest id at minimum distance
- Coordinates fit in 32-bit signed integers; squared distances fit in 64-bit
- Compare squared distances (no sqrt) for exactness with integer inputs
- If couriers is empty, every customer maps to -1
Examples
Input: ([[0, 0], [5, 5]], [[1, 1, 10], [4, 4, 20], [10, 10, 30]])
Expected Output: [10, 20]
Explanation: Customer (0,0) is closest to courier 10 at (1,1) (d^2=2). Customer (5,5) is closest to courier 20 at (4,4) (d^2=2).
Input: ([[2, 2]], [[0, 0, 7], [4, 4, 3]])
Expected Output: [3]
Explanation: Both couriers are at squared distance 8 from (2,2); the tie is broken by the smaller id, so courier 3 wins.
Hints
- Start with the brute force: for each customer scan all couriers and keep the running minimum, comparing the pair (squared_distance, id) lexicographically so ties go to the smallest id.
- Use squared distance (cx-ax)^2 + (cy-ay)^2 instead of the actual distance — it preserves ordering, avoids sqrt, and stays exact for integer coordinates.
- To beat O(n*m) for large inputs, build a spatial index over the couriers once (uniform grid / spatial hash, or a k-d tree) and query it per customer; expand grid rings outward and stop once the next ring cannot beat your best candidate.
- Edge cases: no couriers -> -1; duplicate courier locations -> the id tie-break makes the result deterministic; for real lat/lng use haversine, not planar Euclidean.