Requirements and Scale
Functional: turn-by-turn navigation, ETA estimation, real-time traffic updates, points of interest search, route alternatives. Non-functional: 1B daily active users, 5M concurrent navigation sessions, ETA accuracy within 10% (P90), route recalculation in < 500ms on traffic change, map tile serving at < 50ms globally. The map data problem: road network graph has 100M+ nodes (intersections) and 200M+ edges (road segments). Cannot fit in single-machine memory for global routing. Must partition geographically.
Road Network Graph and Storage
Road network modeled as a directed weighted graph: nodes = intersections, edges = road segments. Edge attributes: distance, speed_limit, road_type (MOTORWAY/ARTERIAL/LOCAL), turn_restrictions, one_way flag. Partitioned by geographic region (H3 hexagons at resolution 4, ~2,000 partitions globally). Each partition fits in memory (~500MB). Cross-partition edges: border edges stored in both partitions with remote endpoint metadata. Storage: custom binary format for fast memory-mapped loading (not a general-purpose DB). Graph updates: map changes applied nightly in batch (new roads, speed limit changes). Real-time traffic weights applied as overlays on top of static graph.
Shortest Path: A* for Single Route
import heapq
def astar(graph: dict, start: int, end: int,
heuristic: callable) -> tuple[list[int], float]:
# graph[node] = [(neighbor, weight), ...]
# heuristic(node, end) = estimated remaining cost (haversine distance)
dist = {start: 0}
prev = {}
heap = [(heuristic(start, end), 0, start)] # (f, g, node)
while heap:
f, g, u = heapq.heappop(heap)
if u == end:
# Reconstruct path
path = []
while u in prev:
path.append(u); u = prev[u]
path.append(start)
return path[::-1], dist[end]
if g > dist.get(u, float('inf')):
continue # stale entry
for v, w in graph[u]:
new_g = g + w
if new_g float:
lat1, lng1 = get_coords(node)
lat2, lng2 = get_coords(end)
# Haversine formula returns km; convert to time estimate
dist_km = haversine(lat1, lng1, lat2, lng2)
max_speed = 130 # km/h motorway speed
return (dist_km / max_speed) * 3600 # secondsContraction Hierarchies for Fast Global Routing
A* on a 100M-node graph is too slow for long-distance routes. Contraction Hierarchies (CH) precompute shortcuts: node importance is ordered (local streets < arterials < highways). During preprocessing: iteratively contract least important nodes – add shortcut edges between neighbors to preserve shortest paths. Query time: bidirectional Dijkstra that only relaxes edges going "upward" in importance hierarchy. Result: query time of 10-100ms even on global road networks (vs minutes for plain Dijkstra). Google Maps and Waze use CH or similar techniques (Arc Flags, HL). Preprocessing is expensive (hours) but done offline. Live traffic changes are applied as time-dependent edge weights without full recomputation.
ETA and Real-Time Traffic
ETA components: (1) Route distance and speed limits (static). (2) Historical traffic patterns by time of day and day of week (ML model per road segment). (3) Live traffic events: accidents, road closures ingested from user reports + sensors + partner feeds. (4) Current congestion: speed readings aggregated from GPS traces of active navigation sessions. ETA model: predicted_travel_time = sum over route segments of (segment_length / predicted_speed). predicted_speed = f(speed_limit, historical_pattern, current_congestion). Live traffic propagation: when an accident is reported on segment X, increase edge weight for X. Recompute affected routes within a geographic radius. Push route update to active navigation sessions if new ETA differs by > 2 minutes or new route is > 5% faster.
Uber system design interviews cover routing and ETA computation. Review maps design patterns for Uber interview: maps routing and ETA system design.
Lyft system design rounds include routing and navigation. See design patterns for Lyft interview: navigation and routing system design.
Snap system design covers location-based features. Review maps system design for Snap interview: location and maps system design.