Design Google Maps

Problem Design the core of a maps/navigation system: model the road network as a graph, compute fastest routes, and expose navigation features — working code expected for the routing core.

Requirements

• Model intersections/road segments with travel costs; route(source, destination) → fastest path; incorporate one-way streets and (as an extension) live traffic weights; nearest-POI search as a probe.

Core design

• Graph: Node(id, lat/lng), directed Edge(from, to, length, speed → weight = time); adjacency-list Graph class with addNode/addEdge; RoutingService with shortestPath(src, dst).
• Routing: Dijkstra with a priority queue (code this cleanly — the usual ask); A* as the informed upgrade using straight-line-distance/max-speed as an admissible heuristic — explain admissibility and why it preserves optimality.
• Supporting classes: MapService (tile/viewport queries — quadtree or geohash spatial index), LocationService (snap GPS point to nearest edge), NavigationSession (turn-by-turn from the edge sequence, reroute on deviation).

Discussion points

• Dijkstra vs A* vs BFS (why BFS fails on weighted graphs); complexity O(E log V) and what breaks at continent scale — mention hierarchical techniques (contraction hierarchies) exist without needing details.
• Live traffic: edge weights as time-varying inputs — recompute vs incremental updates; separating static topology from dynamic weights.
• Testing the routing code: small fixture graphs, unreachable destinations, zero-length edges, ties.