Find Uber: Locate the Nearest Available Driver to a Rider Using a Geospatial Index

Question

## Problem

You have a set of available drivers, each with a (lat, lon) position. Given a rider's position, find the nearest available driver. Implement the system with support for drivers going online/offline and position updates.

```python
class DriverRegistry:
    def __init__(self): ...
    def update_driver(self, driver_id: str, lat: float, lon: float) -> None: ...
    def remove_driver(self, driver_id: str) -> None: ...
    def nearest_driver(self, lat: float, lon: float) -> str | None: ...
```

**Example:**
```
reg = DriverRegistry()
reg.update_driver("D1", 37.77, -122.41)
reg.update_driver("D2", 37.78, -122.42)
reg.nearest_driver(37.775, -122.415)  -> "D1"  # closer by Haversine
reg.remove_driver("D1")
reg.nearest_driver(37.775, -122.415)  -> "D2"
```

## Follow-ups

1. What spatial index structure (k-d tree, geohash grid, R-tree) would you use for sub-millisecond nearest-neighbor queries with frequent updates?
2. Geohash encodes a location as a string where longer prefixes = smaller cells. How does it enable proximity searches with SQL `LIKE` queries?
3. How would you scale this to 1 million active drivers across a city using sharding by geographic cell?
4. What is the trade-off between Euclidean distance (fast) and Haversine distance (accurate) when ranking nearby drivers?

Find Uber: Locate the Nearest Available Driver to a Rider Using a Geospatial Index

Question Details

Full Details

Topics

More from Uber