System Design Problems
Design Google Maps
Google Maps provides turn-by-turn navigation, real-time traffic, and points of interest for over 1 billion users. The system must compute optimal routes across a graph with 100M+ nodes in milliseconds using algorithms like Dijkstra's and contraction hierarchies.
- Route Computation — Find shortest/fastest path in a massive road network
- Real-time Traffic — Incorporate live traffic data into routing
- Map Rendering — Serve vector map tiles at multiple zoom levels
The road network is a graph with 100M+ nodes and 200M+ edges. Computing a route from New York to Los Angeles requires exploring billions of possible paths—but smart algorithms make this possible in milliseconds.
Requirements
Functional Requirements
- Get directions between two points (driving, walking, transit, cycling)
- Real-time traffic conditions and ETA
- Turn-by-turn navigation
- Search for points of interest (restaurants, gas stations)
- Multiple route alternatives with estimated time
- Offline maps for areas without connectivity
Non-Functional Requirements
- Latency: Route computed in < 500ms
- Scale: 1 billion map requests/day, 100M navigation sessions
- Accuracy: ETA within 10% of actual travel time
- Availability: 99.99% uptime
- Freshness: Traffic updates every 2 minutes
Back-of-the-Envelope Estimation
Graph Algorithms
Contraction Hierarchies
Real-time Traffic
Incorporate GPS data from phones to estimate traffic speeds:
High-Level Architecture
Map Tile System
Practice Exercises
-
Algorithm: Implement Dijkstra's algorithm for a small graph (10 nodes). What is the time complexity with and without a priority queue?
-
Scale: If the road network has 100M nodes and 200M edges, estimate the memory needed for the contraction hierarchy preprocessing.
-
Real-time: Design a system to incorporate real-time traffic data from 10M GPS sources every 2 minutes. What are the latency and throughput requirements?
-
Offline: How would you implement offline maps that allow routing without internet connectivity? What data would you pre-download?
What to Learn Next
-> Design Proximity Service Finding nearby businesses and points of interest.
-> Design Search Autocomplete Location-based typeahead suggestions.
-> CDNs Serving map tiles from edge locations.
-> Design Realtime Analytics Real-time traffic data processing.
-> Caching Strategies Caching map tiles and route computations.
-> Databases Geospatial indexes and tile storage.