"Leave now. You'll arrive at 9:12." That one line hides a lot. It needs a graph of every road on the continent, a shortest-path search that finishes in milliseconds, a live picture of how fast each road is moving right now, and a guess about how fast it will be moving when you get there in 40 minutes.
In this lab you'll design the routing and ETA part of a maps product, modelled on Google Maps. It's rated hard because three tough problems meet in it: graph algorithms at huge scale, stream processing of noisy GPS data, and predicting the future.
The brief
A driver types a destination. The app shows a few route options with arrival times. They pick one and start navigating. While they drive, the app follows them and, if a crash blocks the road ahead, offers a faster route.
Who uses it:
- Drivers asking for routes and navigating. Their phones also send anonymous location pings, which is where live traffic comes from.
- Other products (ride-hailing, delivery) that call the same routing API for ETAs.
For this lab:
- In: driving routes, ETAs, live traffic from phone pings, rerouting during navigation.
- Out: drawing the map (tiles are static files on a CDN), place search, public transit, walking and cycling, Street View.
Requirements
Functional
- Given an origin and destination, return up to 3 driving routes with a distance and an ETA.
- Routes and ETAs account for live traffic.
- During navigation, the phone sends its location, and the user gets a better route if one appears.
- Routes respect road rules: one-way streets, turn restrictions, closures.
Non-functional
- A route request returns within 500 ms at the 99th percentile, including cross-country routes.
- Traffic reflects reality within about 2 minutes. A crash at 8:30 should be slowing routes by 8:32.
- ETAs are accurate: for most trips, the actual arrival is within 10% of the predicted one.
- Location data is private. We use it for traffic in aggregate, never to track a person.
- Highly available. A broken route service strands people on the road.