Bird
Raised Fist0

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

HLDhardInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
▶
Request Trace
Step 1/7
API Gateway

Receives user route and ETA request

User sends origin and destination via REST API

Protocol:HTTP REST
BeforeNo active request for this user
AfterRouting Service request initiated with user parameters
Routing Service

Checks Redis Cache for recent route and ETA

Queries Redis with origin-destination key

Protocol:Redis GET
BeforeNo cached route data for this query
AfterCache miss detected, triggers graph and traffic queries
Road Graph Storage

Executes shortest path query on road graph

Finds optimal path ignoring live traffic

Protocol:Internal DB query
BeforeRouting Service waiting for graph data
AfterBase route path returned to Routing Service
Traffic Service

Provides live traffic speeds for route segments

Fetches latest traffic data to adjust ETA

Protocol:Internal service call
BeforeRouting Service has base route without traffic
AfterRouting Service receives traffic speeds for ETA calculation
Routing Service

Computes ETA using graph and live traffic data

Combines base route with traffic delays

Protocol:In-memory computation
BeforeRouting Service has route and traffic data
AfterFinal ETA computed and cached in Redis
Redis Cache

Stores computed route and ETA for future requests

Caches result with TTL for quick reuse

Protocol:Redis SET
BeforeNo cached result for this route
AfterRoute and ETA cached with expiration
API Gateway

Returns route and ETA response to user

Sends JSON with path and estimated time

Protocol:HTTP REST Response
BeforeRouting Service completed computation
AfterUser receives route and ETA data
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────┐
│  API Gateway  │
└───────┬───────┘
        │ HTTP Request (REST)
        ▼
┌───────────────┐
│ Routing Srv   │
│ (compute ETA) │
└───────┬───────┘
        │ Redis GET (cache lookup)
        ▼
┌───────────────┐
│ Redis Cache   │
└───────┬───────┘
        │ Cache miss or stale data
        ▼
┌───────────────┐
│ Road Graph DB │
│ (graph storage│
│  & queries)   │
└───────┬───────┘
        │ Request live traffic data
        ▼
┌───────────────┐
│ Traffic Srv   │
│ (live traffic │
│  updates)     │
└───────┬───────┘
        │ Publish traffic updates
        ▼
┌───────────────┐
│ Kafka Topics  │
└───────┬───────┘
        │ Subscribe for updates
        ▼
┌─────────────────────────────┐
│ Batch ETL & Graph Updater   │
│ (update graph & traffic)    │
└─────────────────────────────┘
Design Rationale

This architecture shows a vertical flow from the API Gateway receiving user requests down to the Batch ETL & Graph Updater maintaining the road graph and traffic data. The Routing Service first attempts to retrieve cached route and ETA from Redis Cache to reduce latency. On cache miss, it queries the Road Graph Storage for the base route and then requests live traffic data from the Traffic Service to adjust ETA. Traffic updates are streamed asynchronously via Kafka Topics to keep the graph and traffic info fresh, processed by the Batch ETL & Graph Updater. This design balances fast response times with up-to-date routing by combining caching, live data, and batch updates in a scalable pipeline.

Primary Focus

✓

Practice

(1/5)
1. A distributed key-value store must evenly distribute keys across nodes and handle node failures without massive data reshuffling. Which component primarily enables this?
easy
A. Gossip protocol to propagate membership and failure information
B. Vector clocks to resolve conflicting versions of data
C. Consistent hashing to assign keys to nodes with minimal remapping
D. Quorum-based replication to ensure data durability

Solution

  1. Step 1: Identify the role of consistent hashing

    Consistent hashing distributes keys to nodes such that when nodes join or leave, only a small subset of keys need reassignment, minimizing reshuffling.

  2. Step 2: Eliminate other components

    Vector clocks handle version conflicts but do not distribute keys. Gossip protocol manages cluster membership but not key distribution. Quorum replication ensures durability but does not affect key assignment.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Consistent hashing minimizes key remapping on node changes [check]
Hint: Consistent hashing minimizes key remapping on node changes [OK]
Common Mistakes:
2. In a consistent hashing system with virtual nodes, at Step 4 the request router receives a key and must find the responsible physical node. What happens at this step?
easy
A. The router hashes the key, finds the closest virtual node clockwise, then maps to its physical node
B. The router hashes the key and assigns it to a random physical node to balance load
C. The router queries a centralized metadata service for the node responsible for the key
D. The router hashes the key and assigns it to the first physical node in the list

Solution

  1. Step 1: Trace request router behavior at Step 4

    The router uses the key's hash to find the closest virtual node clockwise on the ring.

  2. Step 2: Map virtual node to physical node

    Each virtual node maps to a physical node; the router routes the request accordingly.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Consistent hashing uses clockwise virtual node lookup to find physical node [check]
Hint: Hash key -> closest clockwise virtual node -> physical node [check]
Common Mistakes:
3. Without the segment manifest (playlist) update mechanism, what exactly breaks in the adaptive bitrate HLS streaming workflow?
medium
A. Clients will download all bitrate variants simultaneously, wasting bandwidth
B. Clients will fail to discover new segments, causing playback stalls or infinite buffering
C. Clients will continue playing old segments indefinitely without switching bitrates
D. Clients will switch bitrates too frequently, causing playback instability

Solution

  1. Step 1: Role of manifest updates in HLS

    Manifest updates inform clients about new segments and available bitrates, enabling selective fetching.

  2. Step 2: Consequence of missing manifest updates

    Without updates, clients cannot know which segments to fetch next, leading them to request all variants to avoid stalls, wasting bandwidth.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Missing manifest updates cause clients to fetch all variants, wasting bandwidth [check]
Hint: No manifest updates -> clients fetch all bitrates, wasting bandwidth [check]
Common Mistakes:
4. For a system requiring minimal latency on shard lookup and dynamic shard scaling, which architecture is best suited?
medium
A. Distributed consistent hashing with local hash ring replicas updated asynchronously
B. Centralized shard mapping service queried synchronously on every request
C. Client-side static shard mapping with manual updates on shard changes
D. Range-based partitioning with a global metadata service for shard boundaries

Solution

  1. Step 1: Evaluate latency and scaling constraints

    Centralized service (Centralized shard mapping service queried synchronously on every request) adds latency and single point of failure; client-side static mapping (Client-side static shard mapping with manual updates on shard changes) is inflexible and error-prone; range partitioning (Range-based partitioning with a global metadata service for shard boundaries) struggles with hotspots and dynamic scaling.

  2. Step 2: Assess distributed consistent hashing

    Distributed consistent hashing with local replicas (Distributed consistent hashing with local hash ring replicas updated asynchronously) provides low-latency shard lookup and supports dynamic shard scaling with minimal coordination.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Local hash ring replicas enable fast, scalable shard lookup [check]
Hint: Local hash ring replicas enable fast, scalable shard lookup [OK]
Common Mistakes:
5. For billing in a multi-tenant SaaS platform, which architecture best supports accurate usage tracking with minimal latency impact on tenant requests?
medium
A. Asynchronous event-driven usage aggregation via a message queue and batch processing
B. Embedding billing logic directly in the tenant service to update counters in-memory
C. Periodic polling of tenant usage logs by the billing service every hour
D. Synchronous billing updates on every tenant API call to the billing database

Solution

  1. Step 1: Analyze latency and accuracy trade-offs

    Synchronous updates (Synchronous billing updates on every tenant API call to the billing database) add latency; polling (Periodic polling of tenant usage logs by the billing service every hour) delays billing data; in-memory counters (Embedding billing logic directly in the tenant service to update counters in-memory) risk data loss.

  2. Step 2: Evaluate asynchronous event-driven approach

    Asynchronous event-driven usage aggregation via a message queue and batch processing decouples billing from tenant requests, ensuring accurate aggregation with minimal latency impact.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Event-driven async billing -> accurate, low-latency tenant requests [check]
Hint: Async event-driven billing decouples latency [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