How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Compute nearest courier for each customer

Quick Overview

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.

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.

Input: ([[0, 0]], [])

Expected Output: [-1]

Explanation: No couriers exist, so the customer maps to the -1 sentinel.

Input: ([[3, 0]], [[0, 0, 1], [6, 0, 2]])

Expected Output: [1]

Explanation: Both couriers are 3 units away (d^2=9), so the smaller id (1) is returned.

Input: ([], [[0, 0, 1]])

Expected Output: []

Explanation: There are no customers, so the result is empty regardless of couriers.

Input: ([[0, 0], [0, 0]], [[1, 0, 5], [-1, 0, 5], [0, 1, 9]])

Expected Output: [5, 5]

Explanation: All three couriers are at squared distance 1 from (0,0); the smallest id at minimum distance is 5, returned for both identical customers.

Input: ([[-3, -4]], [[0, 0, 100], [-3, 0, 50]])

Expected Output: [50]

Explanation: Courier 100 is at d^2=25, courier 50 at d^2=16; courier 50 is strictly closer.

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.

Quick Overview