Think Beyond the Happy Path
Real production systems aren't just about finding shortest paths — they're about graph-scale optimization, real-time data integration, and low-latency computation.
Before diving into the material, take a moment to ask yourself:
- Do you know why standard Dijkstra's or A* algorithms can't be directly applied to a road network with billions of edges?
- Do you know how to partition a massive graph into manageable "cells" for parallel processing?
- Do you know how to incorporate real-time traffic conditions into route planning without recomputing the entire graph?
- Do you know how to dynamically re-route users when traffic conditions change mid-journey?
You don't need to answer all of these right away. A Senior/Staff+ Engineer doesn't stop at basic functionality — they anticipate edge cases, design for resilience, and push for production-grade reliability.
But great systems start with great questions. What would you ask next?
Problem Statement
Design a navigation system like Google Maps that allows users to search for locations, plan optimal routes between two points, and receive turn-by-turn navigation instructions. The system should:
- Support location search with address resolution.
- Compute optimal routes considering real-time traffic conditions.
- Provide real-time navigation with dynamic re-routing. And the scale is billions of road segments with sub-second route computation.
What makes Google Maps unique compared to Yelp and Uber?
Each geo-based system has its own unique technical challenges:
- Design Yelp: Efficient proximity search — finding businesses based on location using spatial indexing (QuadTree, GeoHash).
- Design Uber: Handling massive scale real-time location updates from drivers and ensuring consistent driver-rider matching.
- Design Google Maps faces its own unique challenges:
- Computing optimal routes with low latency on an extremely large road network graph (billions of vertices and edges)
- Calculating accurate ETAs by combining static graph data with real-time traffic conditions
- Dynamic re-routing when conditions change during navigation
Understanding Shortest Path Algorithms
In a system design interview for Google Maps, the focus isn't on explaining algorithms like Dijkstra's, A*, or Bellman-Ford. While knowing these algorithms is valuable, the real challenge is how to apply shortest path algorithms efficiently to an enormous road network with:
- Billions of road segments (edges)
- Millions of intersections (vertices)
- Real-time traffic conditions
- Sub-second response requirements
| Algorithm Comparison | |
|---|---|
| Name | Description |
Dijkstra's | O((V + E) log V) | Best for: Guaranteed shortest path | Limitation: Explores all directions equally; slow for large graphs. |
A* | O(E) with good heuristic | Best for: Directed search toward goal | Limitation: Requires admissible heuristic; still slow at scale. |
Bellman-Ford | O(V × E) | Best for: Handles negative weights | Limitation: Too slow for real-time routing. |
Contraction Hierarchies | O(log V) query time | Best for: Pre-processed static graphs | Limitation: Expensive preprocessing; hard with dynamic weights. |
The key is to discuss system-level optimizations and techniques that make these algorithms practical at scale, such as:
- Graph partitioning into cells/tiles
- Hierarchical routing (cell-level then road-level)
- Pre-computation and caching of common routes
- Parallel processing across graph partitions
Functional Requirements
FR1 – Location Search
Users can search for locations and receive corresponding physical addresses (geocoding and reverse geocoding).
FR2 – Route Planning
Users can request and receive optimal routes between two locations, considering distance, time, and traffic conditions.
FR3 – Navigation
Users can obtain turn-by-turn navigation instructions for their selected route, with dynamic re-routing when conditions change.
Non-Functional Requirements
NFR1 – Low Latency
The system should recommend routes and calculate ETAs with low latency (p99 < 3 seconds).
NFR2 – Accuracy
The routes and ETAs must be accurate. Specifically:
- Routes should be "traversable" (no invalid road segments or turns).
- ETAs should be within ±10% of actual travel time for 90% of trips.
NFR3 – High Availability
The system should maintain 99.99% uptime.
NFR4 – Scalability
The system should scale horizontally to support millions of concurrent users, with the ability to handle increased traffic during peak periods.
Requirement Summary
| Functional Requirements (FRs) | |
|---|---|
| Name | Description |
1. Location Search | Search locations and receive physical addresses (geocoding). |
2. Route Planning | Compute optimal routes between two locations with traffic awareness. |
3. Navigation | Turn-by-turn instructions with dynamic re-routing. |
| Non-Functional Requirements (NFRs) | |
|---|---|
| Name | Description |
1. Low Latency | Route computation p99 < 3 seconds. |
2. Accuracy | Traversable routes; ETAs within ±10% for 90% of trips. |
3. High Availability | 99.99% uptime. |
4. Scalability | Support millions of concurrent users with peak handling. |
Core Entities
To tie these requirements together into a coherent architecture, we begin with the foundational data structures that model the road network.
Cell — Geographic Partition
A Cell represents a bounded geographical area containing a manageable portion of the road network. Cells enable:
- Parallel processing of route computation
- Efficient memory management
- Hierarchical routing (cell-level then road-level)
| Cell Table | |||
|---|---|---|---|
| Field | Type | Key | Description |
cell_id | BIGINT | PK | Unique identifier for the cell. |
coordinates | POLYGON | NOT NULL | Geographic boundaries (NW, NE, SW, SE corners). |
adjacent_cells | BIGINT[] | NOT NULL | IDs of neighboring cells. |
exit_points | JSONB | NOT NULL | Border crossing points with adjacent cells. |
zoom_level | INT | NOT NULL | Hierarchical level (higher = more detail). |
Road Network — Graph Within a Cell
The Road Network contains the detailed graph structure within a cell, including all road segments and intersections.
| RoadNetwork Table | |||
|---|---|---|---|
| Field | Type | Key | Description |
cell_id | BIGINT | FK → cells(cell_id) | Reference to containing cell. |
graph | GRAPH | NOT NULL | Detailed road network (nodes + edges). |
exit_points | NODE[] | NOT NULL | Border crossing points with adjacent cells. |
precomputed_distances | JSONB | NULLABLE | Cached distances between exit points. |
Road — Individual Road Segment
A Road represents a single road segment (edge) in the graph, connecting two nodes (intersections or waypoints).
| Road Table | |||
|---|---|---|---|
| Field | Type | Key | Description |
road_id | BIGINT | PK | Unique road segment identifier. |
cell_id | BIGINT | FK → cells(cell_id) | Containing cell. |
source_node | NODE | NOT NULL | Starting intersection/waypoint. |
target_node | NODE | NOT NULL | Ending intersection/waypoint. |
distance_meters | INT | NOT NULL | Physical length of road segment. |
base_travel_time | INT | NOT NULL | Travel time at speed limit (seconds). |
speed_limit | INT | NOT NULL | Speed limit in km/h. |
road_type | ENUM | NOT NULL | highway/arterial/residential/toll. |
traffic_level | ENUM | NOT NULL | none/light/medium/heavy. |
traffic_multiplier | FLOAT | NOT NULL DEFAULT 1.0 | Current traffic weight. |