Sign in to keep reading
“Google Maps” is free with an account. Your progress and bookmarks follow you across devices.
Sign in to continueDesign Google Maps - This system design covers route planning with graph partitioning, real-time traffic integration, shortest path algorithms at scale, and turn-by-turn navigation.
“Google Maps” is free with an account. Your progress and bookmarks follow you across devices.
Sign in to continueThink Beyond the Happy Path
Could you answer these today? Tick what you already know.
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:
Each geo-based system has its own unique technical challenges:
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:
| Algorithm Comparison | |
|---|---|
| Name | Description |
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.
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:
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. |
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:
Swipe to see all columns
| 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). |
Road Network — Graph Within a Cell
The Road Network contains the detailed graph structure within a cell, including all road segments and intersections.
Swipe to see all columns
| 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). |
Road — Individual Road Segment
A Road represents a single road segment (edge) in the graph, connecting two nodes (intersections or waypoints).
Swipe to see all columns
| Road Table | |||
|---|---|---|---|
| Field | Type | Key | Description |
road_id | BIGINT | PK | Unique road segment identifier. |
cell_id | BIGINT | FK → cells(cell_id) | Containing cell. |
| 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:
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). |
exit_points| NODE[] |
| NOT NULL |
| Border crossing points with adjacent cells. |
precomputed_distances | JSONB | NULLABLE | Cached distances between exit points. |
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. |