CSE Roadmap

Specialist tier · about 5 hours · 7 parts

Part 6 of 7 · 2 min read

Trade-offs

What to say out loud.

Trade-offs and what to say

Choice Gain Cost
Batch location updates 15 times fewer requests Up to 15 seconds of delay
Pre-built tiles on a CDN Cheap and fast 100 PB of storage, rebuild when the map changes
Client computes tile URLs One less call A change needs an app update
Tile service returns URLs Flexible An extra service and call
Vector tiles Smaller, smooth zoom More work on the phone
Routing tiles in object storage Cheap, simple Tile loading on demand, cache needed
Three levels of detail Fast long routes Links between levels to maintain
ML ETA Better estimates Models and data to run
WebSocket for reroutes Two-way, light Stateful servers

Extension. Multi-stop trips for delivery drivers: choose the best order of stops using live traffic (a hard problem, close to the travelling salesman problem), then navigate between them.

Interview angle

Answer in your head first, then open it.

How do you store the map?

Pre-built image or vector tiles by geohash and zoom, in object storage behind a CDN.

How is a route found on a huge graph?

Routing tiles with three levels of detail, and A*.

How is traffic known?

From the stream of users' location updates.

How do you cut the location traffic?

Batch on the phone and slow down in traffic.

How does rerouting scale?

Store a tile chain per user, check only the largest tile, and push through WebSocket.

One follow-up to try. "Offline maps." A good reply: let the user download the tiles and routing tiles of one region. Tiles are static files, so this is a package of a region. The phone runs A* on local routing tiles. The trade-off is device storage (tens to hundreds of MB), staleness of road data, and no live traffic.

Check yourself: 1. What are the costs of batching? 2. Why is the offline follow-up easy for tiles? 3. What is the main trade-off of vector tiles?

Words you will meet

Word Meaning
Geocoding Turning an address into coordinates
Geohash A short string that names a grid cell
Map tile A small square picture of part of the map
Routing tile A small piece of the road graph
ETA The predicted time of arrival
Point of presence (POP) A CDN location near users
Vector tile A tile of shapes drawn by the phone