How Google Maps works

The Problem Statement

Interviewer: "You open Google Maps and type in a destination. Within a second, it shows you a route with traffic overlay and an ETA. The world road network has hundreds of millions of nodes. How does Google compute a shortest path that fast, and how does the traffic layer stay current?"

This question tests three things: whether you understand that raw Dijkstra is too slow for a global road graph, whether you know the preprocessing trick (Contraction Hierarchies) that makes routing queries O(milliseconds), and whether you can explain how billions of Android phone GPS pings turn into the red, yellow, and green traffic overlay.

I like this question because it spans algorithms, data infrastructure, and real-time systems. A weak answer says "they use Dijkstra." A strong answer explains Contraction Hierarchies, the probe-data pipeline, and how map tiles reach your screen so fast from tile servers halfway across the world.

Clarifying the Scenario

You: "Good question. I want to make sure I cover the right scope."

You: "When you say 'how does Google compute a shortest path that fast,' do you want me to focus on the routing algorithm itself, or also the infrastructure that delivers the map tiles and traffic data to the client?"

Interviewer: "Both. I want the full picture: rendering, routing, and traffic."

You: "Got it. And should I talk about just driving directions, or also transit, walking, and cycling?"

Interviewer: "Focus on driving. That has the most interesting infrastructure."

You: "One more thing: should I include offline maps and how they work without a network?"

Interviewer: "Mention it briefly, but the primary focus is the online experience."

You: "OK. I will structure my answer in three parts: how the map gets on your screen (tile delivery), how the route gets computed so fast (Contraction Hierarchies), and how traffic data is collected and layered onto the map in real time."

My Approach

I break this into four parts:

1. Map tile delivery: The quad-tree tile system, vector vs. raster tiles, and the CDN infrastructure that makes pan-and-zoom feel instant.
2. Contraction Hierarchy routing: The preprocessing algorithm that turns a graph of 200 million nodes into a query that completes in 2-5 milliseconds.
3. Real-time traffic: How Google collects GPS probe data from 3+ billion Android and Google Maps users, aggregates it into traffic segments, and updates ETAs every 30-60 seconds.
4. Geocoding and place search: How typing "coffee near me" resolves to a set of lat/lng coordinates with ranked results.

The core insight: Google Maps is not one system. It is four systems layered on top of each other (tiling, routing, traffic, places), each solving a different problem at a different scale.

Here are the numbers that make the scale tangible. The road graph has roughly 200 million nodes and 700 million edges. The tile store holds billions of pre-generated vector tiles. The traffic pipeline ingests billions of GPS data points per day. And the places index covers 200+ million businesses and points of interest globally. Each of these layers is a system design problem on its own, and Google Maps combines all four into a product that responds in under a second.

The Architecture

Here is the high-level view of what happens when you type a destination and tap "Navigate."

Let me walk through this top to bottom.

The user types a destination. The geocoding service converts that string into coordinates. The routing engine computes a path using Contraction Hierarchies with real-time traffic weights. The client requests vector tiles for the visible map area and renders them with WebGL. The blue route line is drawn as an overlay. The traffic colors (green/yellow/red) come from the traffic service, which continuously ingests GPS speed data from Android phones.

The key latency targets: geocoding under 100ms, routing under 200ms, tile delivery under 50ms from CDN cache. The user experiences all of this as "instant."

Geocoding is the first step and deserves a quick mention. When you type "123 Main St, Austin," the geocoding service parses the string into components (house number, street name, city, state), normalizes abbreviations ("St" to "Street"), and matches against a structured address database. Fuzzy matching handles typos. The result is a latitude/longitude pair that becomes the input to the routing engine.

Place search ("coffee near me") uses a geospatial index, typically based on S2 cells (Google's own hierarchical spatial indexing system). The index partitions the earth into cells at multiple resolutions. A proximity query finds all place cells within a radius, then ranks results by distance, rating, relevance to the query, and business status (open now vs. closed). This is why "pizza" at 8 PM shows nearby open pizzerias first, not the highest-rated place that closed an hour ago.

Contraction Hierarchy Routing

This is the algorithmic core of Google Maps. The world road network has roughly 200 million intersections (nodes) and 700 million road segments (edges). Running Dijkstra from scratch on this graph takes 5-10 seconds per query. Google Maps returns routes in under 200 milliseconds. The trick is Contraction Hierarchies (CH).

How preprocessing works. Every node gets an importance score. Highway intersections that connect cities are very important. Dead-end residential streets are unimportant. The algorithm processes nodes from least to most important. When it removes (contracts) a node, it checks: does removing this node disconnect shortest paths between its neighbors? If yes, it adds a "shortcut" edge that preserves the shortest path cost without going through the removed node.

After processing all nodes, you have the original graph plus a set of shortcut edges at higher levels. The total edge count roughly doubles (from 700M to about 1.4B), but the query structure changes dramatically.

How queries work. Instead of exploring the entire graph, the query runs two simultaneous Dijkstra searches: one forward from the source, one backward from the destination. Both searches only move "up" the hierarchy (toward more important nodes). This means the forward search quickly rises from residential streets to arterials to highways. The backward search does the same from the destination. They meet somewhere in the middle, typically at a highway-level node.

The critical speedup: instead of exploring millions of nodes, each search explores only 500-2,000 nodes. A query that takes 5 seconds with plain Dijkstra completes in 2-5 milliseconds with Contraction Hierarchies.