Bird
Raised Fist0

Design Google Maps - Road Graph, Routing Algorithm, ETA Computation

HLDhardInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design Google Maps - Road Graph, Routing Algorithm, ETA Computation
45 min · senior
senior

Design a system to serve 50 million daily active users with real-time routing and ETA computation. The system must handle a global road graph with frequent updates, provide sub-200ms P99 latency for routing queries, and support encrypted data in transit and at rest. Offline map delivery for limited connectivity areas is required. The system should scale to handle peak loads during rush hours and support multi-modal routing (car, bike, walking).

Constraints
  • P99 latency for routing queries must be under 200ms globally
  • All data in transit and at rest must be encrypted (TLS + AES-256)
  • Offline map and routing support for limited connectivity regions
  • Road graph updates arrive continuously and must be reflected within 5 minutes
  • System must handle 50M DAU with peak QPS 10x average
  • Multi-modal routing support (car, bike, walking) with different speed profiles
📋
Guided Steps
1/5
Step 1
Road Graph Data Modeling and Storage
How would you model and store the global road graph to support efficient routing and frequent updates?
💡 Hint
Consider graph databases or specialized storage optimized for spatial queries and incremental updates.
Key Decision
Use a distributed graph database like Neo4j Aura or Amazon Neptune with spatial indexing and versioned edge properties to model roads and intersections, enabling efficient shortest path queries and incremental updates.
Interviewer Expectation
Mid: Names Neo4j or Neptune for graph storage. Senior: Explains spatial indexing, versioning edges for live updates, and why relational DBs or flat files fail at scale.
⚠️Common Wrong Answer
Using a relational database with adjacency lists - leads to slow graph traversals and poor update performance at global scale.
Step 2
Routing Algorithm and Query Processing
Which routing algorithm and infrastructure would you choose to compute routes with sub-200ms P99 latency at 50M DAU scale?
💡 Hint
Think about precomputing routes, hierarchical routing, and distributed query serving with caching.
Key Decision
Implement Contraction Hierarchies (CH) with preprocessed graph overlays stored in Redis clusters for ultra-fast shortest path queries, combined with a stateless routing API layer behind AWS Elastic Load Balancers.
Interviewer Expectation
Mid: Mentions Dijkstra or A* with caching. Senior: Explains CH preprocessing, Redis for low-latency lookups, and why pure A* or on-demand Dijkstra fails at 50M DAU with 200ms P99.
⚠️Common Wrong Answer
Running Dijkstra on raw graph per request - causes high latency and cannot meet P99 SLA under peak load.
Step 3
ETA Computation and Real-Time Updates
How would you compute and update ETAs dynamically considering traffic and multi-modal speeds?
💡 Hint
Consider streaming traffic data ingestion and incremental ETA recalculations with pub/sub messaging.
Key Decision
Use Apache Kafka to ingest real-time traffic and sensor data streams, process with Apache Flink for incremental ETA updates, and push updates via WebSocket APIs to clients for live ETA adjustments.
Interviewer Expectation
Mid: Names Kafka for streaming. Senior: Details Flink stateful processing for incremental ETA, Kafka partitioning by region, and WebSocket for low-latency client updates.
⚠️Common Wrong Answer
Polling traffic data periodically and recomputing ETA from scratch - leads to stale ETAs and high compute cost.
Step 4
Offline Map and Routing Support
How would you enable offline map and routing capabilities for users with intermittent connectivity?
💡 Hint
Think about region-based map tile packaging, local routing engines, and secure sync mechanisms.
Key Decision
Package offline map tiles and preprocessed routing graphs per region using Protobuf format, store on device with RocksDB, and sync updates securely over HTTPS with TLS and AES-256 encryption.
Interviewer Expectation
Mid: Suggests offline map tiles. Senior: Explains local routing engine using preprocessed graphs, RocksDB for efficient local queries, and secure incremental sync with encryption.
⚠️Common Wrong Answer
Downloading raw map data without preprocessing - causes large storage and slow local routing.
Step 5
API Design for Routing System
Design 3 core API endpoints for route requests, ETA updates, and offline map sync.
💡 Hint
Consider REST or gRPC endpoints with request/response schemas and streaming capabilities.
Key Decision
Define RESTful POST /route with origin, destination, mode; WebSocket /eta-stream for incremental ETA updates; and GET /offline-map?region= for encrypted offline map data download with versioning.
Interviewer Expectation
Mid: Names REST endpoints. Senior: Details request/response schemas, streaming ETA updates via WebSocket, and secure offline map sync with versioning and encryption.
⚠️Common Wrong Answer
Single monolithic endpoint for all operations - leads to poor client flexibility and scalability.
🔌
API Design Challenge
Sketch 3 core API endpoints for the routing system: how clients request routes, receive ETA updates, and sync offline maps.
Hints
  • How does the client specify origin, destination, and mode of transport?
  • How does the client receive incremental ETA updates during a trip?
  • How does the client request and verify offline map data for a region?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of a distributed graph database with spatial indexing for road graph storage
  • Preprocessing routing graph with Contraction Hierarchies and caching in Redis for low-latency queries
  • Streaming architecture with Kafka and Flink for real-time ETA updates
  • Offline map support with local storage and secure incremental sync
  • Clear API design separating route requests, ETA updates, and offline map sync
Good to Have - 30%
  • Encryption in transit and at rest using TLS and AES-256
  • Multi-modal routing support with different speed profiles
  • Versioning of road graph data to support incremental updates within 5 minutes
  • Use of WebSocket for pushing incremental ETA updates
Bonus - 10%
  • Handling peak load with autoscaling routing API layer behind AWS ELB
  • Use of RocksDB for efficient local offline routing queries
  • Partitioning Kafka topics by geographic region for traffic data
Anti-patterns to Avoid
Using relational databases for graph storage - causes slow traversals and poor update performance at global scale, making real-time routing infeasible
Running Dijkstra or A* on raw graph per request - leads to high latency and inability to meet 200ms P99 SLA under peak load
HTTP polling at 50M DAU: 50 million reconnects per minute just to check for messages - collapses under load and wastes resources
Downloading raw map data without preprocessing - causes large storage requirements and slow local routing performance
✅
Model Answer
▼ Reveal

The system uses a distributed graph database (Neo4j Aura or Amazon Neptune) with spatial indexing and versioned edges to model the global road graph. Routing queries are served using Contraction Hierarchies preprocessing with Redis clusters for caching, enabling sub-200ms P99 latency at 50M DAU. Real-time ETA updates are computed via streaming ingestion of traffic data using Apache Kafka and incremental processing with Apache Flink, pushing updates to clients over WebSocket. Offline map support is enabled by packaging Protobuf-encoded map tiles and preprocessed routing graphs stored locally in RocksDB, with secure incremental sync over HTTPS using TLS and AES-256 encryption. The API design includes RESTful endpoints for route requests, WebSocket streaming for ETA updates, and secure GET endpoints for offline map downloads with versioning.

Key Decisions
  • Use Neo4j Aura or Amazon Neptune for scalable graph storage with spatial indexing and versioned edges to support frequent updates
  • Preprocess routing graph with Contraction Hierarchies and cache overlays in Redis clusters to achieve sub-200ms P99 latency at scale
  • Ingest real-time traffic data via Apache Kafka streams partitioned by region for scalability and ordering guarantees
  • Process streaming data with Apache Flink for incremental ETA computation and push updates via WebSocket for low latency
  • Package offline map tiles and routing graphs in Protobuf format, store locally in RocksDB, and sync securely over HTTPS with TLS and AES-256
  • Design separate RESTful and WebSocket API endpoints to maximize client flexibility and scalability
  • Neo4j Aura or Amazon Neptune for distributed graph storage with spatial indexing and versioned edges to support incremental updates
  • Contraction Hierarchies preprocessing combined with Redis clusters for sub-200ms P99 shortest path queries at 50M DAU scale
  • Apache Kafka for ingesting real-time traffic data streams partitioned by geographic region
  • Apache Flink for stateful stream processing to compute incremental ETA updates dynamically
  • WebSocket APIs for pushing live ETA updates to clients with low latency
  • Protobuf-encoded offline map tiles and preprocessed routing graphs stored locally in RocksDB for efficient offline routing
  • Secure sync of offline map data over HTTPS with TLS and AES-256 encryption to meet data protection constraints
  • RESTful API design with separate endpoints for route requests, ETA streaming, and offline map downloads to maximize scalability and client flexibility

Practice

(1/5)
1. In the request flow, at Step 4 the Context Manager retrieves the conversation history before invoking the LLM. What happens if the context window exceeds the maximum token limit at this step?
easy
A. The Context Manager truncates the oldest messages to fit the token limit before sending to the LLM
B. The Context Manager sends the entire conversation history, causing the LLM to reject the request
C. The Context Manager splits the conversation into multiple requests to the LLM in parallel
D. The Context Manager caches the full history and waits for manual intervention

Solution

  1. Step 1: Understand Context Manager role at Step 4

    It must prepare input within the LLM's token window limit to avoid rejection.

  2. Step 2: Analyze behavior on exceeding token limit

    Sending full history (B) causes LLM errors; splitting requests (C) breaks context continuity; caching and manual intervention (D) is impractical. Truncation (A) preserves recent context within limits.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Context Manager truncates oldest messages to fit token window [check]
Hint: Truncate oldest context to fit token window, not entire history [check]
Common Mistakes:
2. A company wants to decouple rapid feature deployments from the risk of impacting the entire system. Which architectural approach best supports this requirement?
easy
A. A microservices architecture with independently deployable services
B. A layered monolith with a shared database and common deployment
C. A monolithic architecture with modular codebase and feature flags
D. A serverless architecture with tightly coupled functions

Solution

  1. Step 1: Identify deployment isolation needs

    Decoupling feature deployments requires independent service lifecycles, which microservices provide.

  2. Step 2: Evaluate alternatives

    Monoliths (A and C) share deployment units, risking system-wide impact. Serverless (D) can be tightly coupled if functions share state or deployment.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Microservices enable independent deploys and reduce blast radius [check]
Hint: Independent deploys need microservices, not just modular code [check]
Common Mistakes:
3. A web application receives millions of HTTP requests per second and needs to distribute them evenly across multiple backend servers to avoid overload. Which component is primarily responsible for this task?
easy
A. A DNS server that resolves domain names to IP addresses
B. A caching proxy that stores frequently accessed responses
C. A load balancer that routes requests based on server health and capacity
D. A message queue that buffers incoming requests for asynchronous processing

Solution

  1. Step 1: Identify the component that distributes traffic

    A DNS server (A DNS server that resolves domain names to IP addresses) only resolves domain names and does not balance load dynamically. A caching proxy (A caching proxy that stores frequently accessed responses) serves cached content but does not distribute load evenly. A message queue (A message queue that buffers incoming requests for asynchronous processing) buffers requests asynchronously but does not route live HTTP requests to backend servers.

  2. Step 2: Understand load balancer role

    A load balancer (A load balancer that routes requests based on server health and capacity) routes incoming requests to backend servers based on health checks and capacity, preventing overload and ensuring even distribution.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Load balancer routes requests evenly based on server health [check]
Hint: Load balancer routes live traffic evenly [check]
Common Mistakes:
4. At 10x scale, which component in the real-time leaderboard system is most likely to fail first, and why?
hard
A. The Redis cluster because sorted sets require in-memory storage and cannot shard scores efficiently
B. The API Gateway because it cannot handle the surge in client connections
C. The Ranking Worker because it cannot process the increased event stream fast enough
D. The database because it cannot handle the increased write throughput

Solution

  1. Step 1: Analyze Redis Sorted Sets scaling limits

    Sorted Sets require in-memory storage and have limited sharding options, making Redis cluster memory the bottleneck.

  2. Step 2: Compare other components

    Databases can be scaled horizontally; Ranking Workers can be parallelized; API Gateways scale with load balancers.

  3. Step 3: Identify Redis cluster as first failure point

    Memory pressure and inability to shard sorted sets efficiently cause Redis cluster to fail first under 10x load.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    Redis Sorted Sets memory and sharding limits cause first failure at scale [check]
Hint: Redis Sorted Sets memory limits break first at scale [check]
Common Mistakes:
5. At 10x scale, which component in a chat system fails first and why?
hard
A. The database fails first due to write amplification and disk I/O bottlenecks
B. The load balancer fails first because it cannot handle the increased connection count
C. Chat servers fail first because WebSocket connections are stateful and cannot be resharded easily
D. The message queue fails first due to partition leader overload

Solution

  1. Step 1: Analyze stateful components at scale

    Chat servers maintain WebSocket connections statefully; scaling requires connection migration or sticky sessions.

  2. Step 2: Identify bottleneck

    At 10x scale, chat servers hit connection limits and cannot shard existing connections, causing failure before DB or load balancer.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful WebSocket servers -> scaling bottleneck due to connection affinity [check]
Hint: Stateful WebSocket servers block scaling before DB or load balancer [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard