System requirements

Functional:

• Users can specify a starting point and a destination by typing addresses and ask for the shortest route and estimated time of arrival.
• The system provides both a textual and graphical representation of the shortest route in terms of time.
• The system provides the estimated amount of time required to take that path.

Non-Functional:

• Low latency.
• Scalability.
• Availability.

Capacity estimation

Estimate the scale of the system you are going to design...

API design

GET /route {

start_point

end_point

} - returns list os roads and estimates time to arrival.

Database design

We can represent map as graph , where nodes - road intersections and edges - roads with metrics (distance, speed limits, traffic data). Lets split graph on grid with layers, where layers represent : 1) local, small roads, 2 larger streets typically within a city, and 3 highways.

nodes table {

node_id,

lon,

lat

}

edges_table {

edge_id,

source_node_id,

target_node_id,

length_m,

speed_limit_kph,

road_class,

is_one_way,

traffic_factor,

last_updated_at

)

edge_profiles_table {

edge_id

car_cost

truck_cost

bike_cost

pedestrian_cost

}

High-level design

1. User

• Mobile App / Web Client
• Requests map data, directions, etc.

2. Load Balancer (Global)

• Geo-aware routing to nearest data center
• Uses DNS + edge routing ( Cloud CDN)

3. API Gateway

• Rate limiting, auth (OAuth2), request logging
• Parses endpoints like

4. Internal Load Balancer

• Routes requests to appropriate microservices

5. Routing Service

• Handles core logic for:
  • Pathfinding (A*, Dijkstra’s, Graph optimizations)
  • Real-time traffic adjustments
  • Toll roads, public transit, time windows

6. Cache Layer (e.g., Redis, Memcached)

• Stores frequently accessed paths, popular routes, and tiles
• Reduces latency and DB hits

7. Database Layer

• Road Network Graph DB: Used for route computation

Request flows

Client (e.g. using a map app on a mobile phone) sends route() request to API Gateway.

API Gateway forwards the request to Routing Service.

Routing Service uses the grid data from Database to find the shortest paths and return.

Routing Service uses cache to store some already computed paths.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

Trade offs between Dijkstra and A* algorithms.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?