Design a Travel Map App's Places and Routes
Model places, nearby search, and walking or driving routes for a city map app, then choose the data structures behind them.
For this exercise, assume a phone map app helps travelers find places and get directions in one city. A place has an ID, a name, a category (hotel, restaurant, or attraction), and a location given as latitude and longitude. The city's roads are stored as intersections joined by road segments.
Each segment joins two intersections, has a length in meters, can be used in both directions, and is open to walking, to driving, or to both. Each place has one entrance intersection, where routes to and from that place start and end.
A traveler can: (1) look up a place by its ID; (2) find the places of one category within a given straight-line distance of a location, nearest first; and (3) get a route between two places for walking or for driving.
A route is the list of segments with the smallest total length among the segments that the chosen mode may use, together with that total length and an estimated time (walking at 5 km/h, driving at 40 km/h).
An unknown place ID, a search distance of zero or less, and two places that no route connects for the chosen mode each return a clear result. A search with no matches returns an empty list, not an error. The map data is loaded once when the app starts and does not change while the app runs.
Design the objects, their responsibilities, the interfaces, and the interactions. No code is needed. A follow-up asks which data structures make search and routing fast.
Live traffic, turn-by-turn navigation and GPS tracking, drawing the map, public transit, trips with several stops, bookings and reviews, offline downloads, and servers and scaling are out of scope.