How to Design a Mapping Service Like Google Maps
Learn how to design Google Maps: tile serving via CDN, spatial indexing, road-graph routing, and real-time traffic ingestion.
Expected Interview Answer
A Google-Maps-like service divides the world into pre-rendered map tiles served via a CDN for fast panning and zooming, indexes places and roads with geospatial data structures (quadtrees, geohashes, or R-trees) for fast proximity queries, and runs a separate routing service that pathfinds over a road-graph using algorithms like A* or contraction hierarchies, all backed by continuously ingested real-time traffic data.
Map imagery is pre-rendered into tiles at multiple zoom levels and cached at CDN edges, so panning and zooming just fetch cached image or vector tiles instead of rendering the whole map live per request. Points of interest and geocoding queries use a spatial index — a quadtree or geohash-based index lets “find nearby” queries run in roughly logarithmic time instead of scanning every point. Routing runs on a separate service holding the road network as a weighted graph, using a fast shortest-path algorithm — plain Dijkstra is too slow at planet scale, so real systems use A* with a good heuristic or precomputed contraction hierarchies to answer route queries in milliseconds. Live traffic is ingested continuously from phones reporting GPS pings (crowd-sourced speed/location data) into a stream-processing pipeline that updates edge weights on the road graph, so routing reflects current congestion rather than static road speeds; ETAs are recomputed periodically as a trip progresses.
- Pre-rendered, CDN-cached tiles make panning and zooming near-instant regardless of load
- Spatial indexing (quadtree/geohash) makes proximity search scale to billions of points
- Precomputed contraction hierarchies make route queries fast even across a planet-scale road graph
- Continuous crowd-sourced traffic ingestion keeps routing and ETAs accurate in real time
AI Mentor Explanation
Designing a mapping service is like a broadcaster pre-rendering the stadium’s field graphics at several zoom levels — full ground, half, close-up on the crease — and caching them at regional relay towers instead of redrawing the graphic from scratch every time a viewer zooms in. Finding the nearest fielder to a hit ball uses a pre-built spatial index of fielding positions instead of checking every player’s coordinates one by one. Working out the fastest relay throw from boundary to keeper is like route-finding on a graph, using a precomputed set of good throw paths rather than evaluating every possible trajectory live. And a live feed of fielder positions constantly updates that graph, just like real-time traffic updating a road network.
Step-by-Step Explanation
Step 1
Pre-render and cache map tiles
The world is divided into tiles at multiple zoom levels, rendered ahead of time, and served from CDN edges for fast pan/zoom.
Step 2
Index places with a spatial structure
A quadtree or geohash index over points of interest enables fast “nearest N” and bounding-box queries.
Step 3
Compute routes over a road graph
A separate routing service holds the road network as a weighted graph and uses A* or contraction hierarchies for fast shortest-path queries.
Step 4
Ingest live traffic continuously
Crowd-sourced GPS pings stream into a pipeline that updates road-graph edge weights so routes and ETAs reflect real conditions.
What Interviewer Expects
- Separates tile rendering/serving, spatial search, and routing into distinct subsystems
- Names a concrete spatial index (quadtree, geohash, R-tree) and why naive scanning does not scale
- Explains why plain Dijkstra is too slow at planet scale and names a faster alternative (A*, contraction hierarchies)
- Describes how real-time traffic data flows into the road graph to keep routing current
Common Mistakes
- Proposing to render the whole map live for every request instead of pre-rendered, cached tiles
- Using linear scans for “find nearby” instead of a spatial index
- Suggesting plain Dijkstra over the full global road graph without addressing its cost at scale
- Forgetting real-time traffic ingestion, treating road weights as static
Best Answer (HR Friendly)
“To design something like Google Maps, I would pre-render the map into small cached image tiles so panning and zooming feel instant, use a spatial index so “find nearby places” queries are fast even with millions of points, and run routing as its own service using a fast pathfinding algorithm over a precomputed road network rather than recalculating everything from scratch. I would also stream in live traffic data from phones so routes and ETAs reflect what is actually happening on the roads right now.”
Code Example
import geohash2
def index_place(spatial_index, place_id, lat, lng):
key = geohash2.encode(lat, lng, precision=7)
spatial_index.setdefault(key, []).append(place_id)
def find_nearby(spatial_index, lat, lng, precision=7):
center = geohash2.encode(lat, lng, precision=precision)
neighbors = geohash2.neighbors(center) # 8 surrounding cells + center
candidates = []
for cell in neighbors + [center]:
candidates.extend(spatial_index.get(cell, []))
return candidates # then rank by exact haversine distance
def fastest_route(road_graph, start_node, end_node):
# A* with a straight-line-distance heuristic over a precomputed
# contraction hierarchy is used in production; naive Dijkstra
# over the full planet graph is too slow for interactive queries.
return a_star_search(road_graph, start_node, end_node, heuristic=haversine)Follow-up Questions
- How would you design tile pre-rendering to update quickly when map data changes (new roads, buildings)?
- What is a contraction hierarchy and why does it speed up shortest-path queries so much?
- How would you compute and continuously update real-time traffic from crowd-sourced GPS data?
- How would you support turn-by-turn navigation with re-routing as a driver goes off-route?
MCQ Practice
1. Why are map tiles pre-rendered and cached instead of rendered live on every request?
Rendering each tile once and caching it at CDN edges means most requests are served instantly from cache instead of expensive live rendering.
2. Why is a spatial index like a quadtree or geohash needed for “find nearby places” queries?
Spatial indexes group nearby points into cells so proximity queries only examine a small relevant subset instead of the entire dataset.
3. Why do production routing systems avoid plain Dijkstra over the entire road graph?
Plain Dijkstra explores too much of a planet-scale graph to be interactive; heuristics (A*) or precomputation (contraction hierarchies) make queries fast enough for real-time use.
Flash Cards
Why pre-render map tiles? — So CDN caching makes panning and zooming near-instant instead of rendering the map live per request.
What does a spatial index (quadtree/geohash) enable? — Fast “find nearby” queries over millions/billions of points without linear scanning.
Why not use plain Dijkstra for routing at scale? — It is too slow over a planet-scale graph; A* or contraction hierarchies make route queries fast enough.
How does real-time traffic factor in? — Crowd-sourced GPS data streams into a pipeline that updates road-graph edge weights continuously.