Practice/Google/Design a Navigation System

Design a Navigation System

System DesignMust

Problem Statement

Design a directions service that computes optimal routes between two points, similar to the routing engine behind Google Maps or Apple Maps. Given an origin and destination, the system returns one or more route options with estimated travel times, considering real-time traffic conditions, road closures, and the user's chosen transport mode (driving, walking, cycling, public transit).

The core algorithmic challenge is finding shortest paths in a massive road network graph containing hundreds of millions of nodes (intersections) and edges (road segments). Running Dijkstra's algorithm on the full graph for every query is far too slow — you need preprocessing techniques like contraction hierarchies or highway hierarchies that reduce query-time graph traversal by orders of magnitude while still producing optimal or near-optimal routes.

Beyond the algorithmic challenge, the system must integrate real-time traffic data to adjust edge weights dynamically, support multi-modal routing (combining driving to a train station with a transit leg and a walking segment), handle millions of concurrent routing requests, and re-route users mid-trip when conditions change.

Key Requirements

Functional

• Point-to-point routing -- Compute the fastest or shortest route between an origin and destination, returning turn-by-turn directions
• Multi-modal transport -- Support driving, walking, cycling, and public transit modes, including routes that combine multiple modes
• Real-time traffic integration -- Adjust route recommendations based on current traffic speeds, incidents, and road closures
• Live re-routing -- Detect when a user deviates from the planned route or conditions change, and compute an updated route within seconds

Non-Functional

• Scalability -- Handle millions of routing requests per minute during peak hours across all transport modes
• Latency -- Return route results within 500ms for single-mode queries and within 1 second for multi-modal queries
• Accuracy -- Routes should reflect actual road connectivity, turn restrictions, one-way streets, and time-dependent access rules
• Availability -- The routing service must remain available at all times, falling back to routes without real-time traffic if the live data feed is delayed

What Interviewers Focus On

Based on real interview experiences, these are the areas interviewers probe most deeply:

1. Graph Representation and Preprocessing

The road network is too large for brute-force shortest-path queries. Interviewers want to see that you understand how to make routing fast. Hints to consider:

• How do contraction hierarchies reduce the search space by creating shortcut edges that skip over unimportant nodes?
• What is the tradeoff between preprocessing time and query speed, and how often must you re-preprocess?
• How do you represent turn restrictions, U-turn penalties, and time-dependent edge weights in the graph model?
• Can you partition the graph into regions and use a two-level hierarchy (local roads vs. highways) to speed up long-distance queries?

2. Real-time Traffic Integration

Static shortest paths are useless if they route drivers into congestion. Interviewers explore how you incorporate live data. Hints to consider:

• How do you update edge weights in a preprocessed graph (like contraction hierarchies) without re-preprocessing the entire graph?
• What is the tradeoff between using live traffic for all edges versus only adjusting edges that deviate significantly from historical speeds?
• How do you handle the feedback loop where routing drivers away from congestion can create new congestion on alternate routes?
• How do you predict traffic conditions 20-30 minutes into the future for a route that takes that long to drive?

3. Multi-Modal Routing

Combining different transport modes in a single route adds significant complexity to the graph model. Hints to consider:

• How do you model transfer points (parking lots, transit stations) as edges connecting the driving graph to the transit graph?
• How do transit schedules (buses run every 15 minutes, trains have fixed timetables) affect your shortest-path algorithm?
• How do you handle walking segments — do you use the full pedestrian graph, or simplify to straight-line estimates with a walking speed factor?
• What objective function do you optimize for multi-modal routes: total time, number of transfers, walking distance, or a weighted combination?