Design Google Maps

1. Problem Statement

2. Architecture Discussion Map

Use this as one discussion aid, not a single correct answer. Your design should follow from the requirements, scale, and trade-offs you establish.

graph TD
    A[Mobile GPS] --> B(API Gateway)
    B --> E[Routing Service]
    E --> F[(RAM: A* Contraction Hierarchies Graph)]
    B --> G[ETA Service]
    G --> E
    H[Driver Telemetry] --> I[Traffic Aggregator]
    I -->|live edge weights| E

3. Key Focus Areas

• 1
  Graph Representation (Nodes/Edges/Segments)
• 2
  Shortest Path Algorithms (Dijkstra/A* on huge graphs)
• 3
  Graph Partitioning (Geographic Cells, QuadTrees, Hilbert Curves, or Min-Cut Partitions)
• 4
  ETA Calculation (Traffic prediction models)

4. What the Interviewer Looks For

The interviewer probes these areas, and the report grades the interview against them.

• Requirements and estimation
• Graph model and partitioning
• Routing algorithms and preprocessing
• Traffic ingestion and ETA
• Serving, reliability, and evolution