Find Available Deliveries - Match Dashers to Unassigned Orders

Question

## Round 1 - Coding

## Problem

Implement a delivery matching system. Given a list of unassigned orders and a list of available dashers, assign each order to the closest available dasher. Each dasher can carry at most one order at a time.

```python
def find_available_deliveries(
    orders: list[dict],   # [{"order_id": int, "pickup": (float,float), "dropoff": (float,float)}]
    dashers: list[dict]   # [{"dasher_id": int, "location": (float,float)}]
) -> list[dict]:
    # Returns [{"order_id": int, "dasher_id": int, "distance_to_pickup": float}]
    # Greedy: assign each order to the nearest unassigned dasher
    # Unassigned orders (no dasher available) are excluded from results
    ...

def euclidean(a: tuple, b: tuple) -> float: ...
```

```
Example:
orders = [
    {"order_id": 1, "pickup": (0,0), "dropoff": (5,5)},
    {"order_id": 2, "pickup": (3,3), "dropoff": (6,6)},
]
dashers = [
    {"dasher_id": 10, "location": (0,1)},
    {"dasher_id": 11, "location": (4,4)},
]
# Order 1 nearest to dasher 10 (dist ~1); Order 2 nearest to dasher 11 (dist ~1.4)
find_available_deliveries(orders, dashers) -> [
    {"order_id": 1, "dasher_id": 10, "distance_to_pickup": 1.0},
    {"order_id": 2, "dasher_id": 11, "distance_to_pickup": 1.414...},
]
```

## Follow-ups

1. Is greedy nearest-match globally optimal? When does it fail?
2. What algorithm gives the global optimal assignment (hint: Hungarian algorithm)?
3. How would you handle a dasher who is already on a delivery but will be free soon?
4. How would you scale this to 50K orders and 20K dashers in under 100ms?

Find Available Deliveries - Match Dashers to Unassigned Orders

Question Details

Full Details

Topics

More from DoorDash