# Low Level Design: Turn-by-Turn Navigation Service

Source: https://www.techinterview.org/post/3233471612/lld-turn-by-turn-navigation/
Updated: 2026-06-30 · techinterview.org

## What Is Turn-by-Turn Navigation?

A turn-by-turn navigation service accepts an origin and destination, computes an optimal route through the road network, and delivers step-by-step maneuver instructions updated in real time as the user moves. Unlike a simple shortest-path query, navigation must handle live traffic, rerouting, and continuous GPS position updates at low latency.

## Data Model

  - **Road graph:** same node/edge schema as the mapping service, augmented with `(edge_id, timestamp, travel_time_s FLOAT)` rows in a `live_traffic` table updated every 30–60 seconds from probe data.

  - **Route:** `(route_id UUID, user_id BIGINT, origin_lat DOUBLE, origin_lon DOUBLE, dest_lat DOUBLE, dest_lon DOUBLE, created_at TIMESTAMP, edge_sequence BIGINT[], maneuvers JSONB)`

  - **Maneuver:** a JSON object containing `instruction` (human-readable text), `distance_m`, `bearing`, and `road_name`.

  - **Position update:** `(session_id UUID, lat DOUBLE, lon DOUBLE, bearing FLOAT, speed_mps FLOAT, recorded_at TIMESTAMP)` — stored in a time-series store (InfluxDB or TimescaleDB) for live tracking and probe data aggregation.

## Core Algorithm: A* with Contraction Hierarchies

Vanilla Dijkstra is too slow for continental-scale graphs. Production navigation stacks use **Contraction Hierarchies (CH)**:

  - **Preprocessing:** nodes are ranked by importance. Less-important nodes are contracted: virtual shortcut edges replace paths through them, reducing query graph size by orders of magnitude.

  - **Query:** bidirectional A* runs simultaneously from origin and destination on the contracted graph. When the two search frontiers meet, the shortest path is extracted and expanded back to real road segments.

  - **Traffic overlay:** live edge weights (travel_time_s) override static speed limits. The CH is rebuilt periodically (hourly) for the base graph; traffic adjustments are applied as a thin overlay without full rebuild.

### Rerouting

The device streams position updates every 1–5 seconds. A server-side deviation detector compares the current position against the planned edge sequence. If the user is more than 50 m off-route, a new A* query is triggered from the snapped current position to the destination, and the updated maneuver list is pushed to the client within 500 ms.

### Map Matching

Raw GPS coordinates have 5–15 m of noise. A Hidden Markov Model (HMM) map-matcher projects noisy GPS observations onto the most probable road segment sequence, enabling accurate instruction triggering (e.g., announcing a turn exactly 300 m before the intersection).

## Failure Handling

  - **Routing service unavailable:** the mobile client caches the last computed route and continues offline navigation using cached map tiles. Re-sync when connectivity returns.

  - **Traffic data staleness:** fall back to historical speed profiles (time-of-day averages) when live probe data is older than 5 minutes.

  - **Position update loss:** dead-reckoning using last known speed and bearing maintains position estimate for up to 30 seconds before alerting the user.

  - **Reroute storm:** if a road closure sends many users into rerouting simultaneously, a request queue with client-side exponential backoff prevents server overload.

## Scalability Considerations

  - Route computation is CPU-intensive. A fleet of stateless routing workers auto-scales behind a load balancer; the contracted graph is loaded into shared memory (mmap) so workers share a single copy per host.

  - Live traffic ingestion uses a Kafka topic per geographic region; consumers update the in-memory traffic overlay without locking the routing graph.

  - Session state (active navigation, position history) is stored in Redis with a TTL; no sticky sessions are required.

  - Geographic sharding: routing workers are assigned to continental regions, reducing graph size per worker and keeping cross-shard stitching rare.

## Summary

Turn-by-turn navigation combines a preprocessed contracted graph for fast shortest-path queries, a traffic overlay for real-time accuracy, HMM map matching for GPS noise reduction, and a low-latency rerouting pipeline. Offline fallback and dead-reckoning ensure the user is never stranded without guidance even under poor connectivity.

See also: [Netflix Interview Guide 2026: Streaming Architecture, Recommendation Systems, and Engineering Excellence](https://www.techinterview.org/post/3233460274/netflix-interview-guide-2026-streaming-architecture-recommendation-systems-and-engineering-excellence/)

See also: [Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering](https://www.techinterview.org/post/3233460273/uber-interview-guide-2026-dispatch-systems-geospatial-algorithms-and-marketplace-engineering/)

See also: [Lyft Interview Guide 2026: Rideshare Engineering, Real-Time Dispatch, and Safety Systems](https://www.techinterview.org/post/3233460306/lyft-interview-guide-2026-rideshare-engineering-real-time-dispatch-and-safety-systems/)