hard google · part of Practice Questions · Senior SWE Roadmap
Requirements to clarify
- Functional: render maps, compute shortest/fastest routes between two points, provide real-time ETA and traffic-aware routing.
- Non-functional: map data is huge (needs tiling/partitioning), routing must be fast even over huge road networks, traffic conditions change continuously.
Core components
- Map tiling: the world is divided into small square tiles at multiple zoom levels; only the tiles in view are fetched/rendered — this is what makes rendering a global map tractable client-side.
- Road network as a graph: intersections = nodes, road segments = weighted edges (weight = travel time, which depends on distance and current traffic).
- Shortest path computation: Dijkstra is the theoretical base, but real systems use precomputation-heavy variants (contraction hierarchies, A* with a good heuristic) since plain Dijkstra is too slow over a continent-scale graph at query time.
- Real-time traffic pipeline: aggregated location data from users’ devices feeds back into edge weights, updated continuously — a large-scale streaming data pipeline in its own right.
Key tradeoffs
- Precomputing route information (contraction hierarchies) trades significant upfront computation and storage for dramatically faster live queries — necessary at this scale since naive Dijkstra per query would be far too slow.