Design Underground System

Med

#1293Time: `checkIn`: O(1) - Hash map insertion is on average constant time. `checkOut`: O(1) - Hash map lookup and list append are on average constant time. `getAverageTime`: O(N), where N is the total number of completed trips. In the worst case, we have to scan the entire list of trips.Space: O(P + N), where P is the number of passengers currently checked in, and N is the total number of completed trips. We need space to store ongoing check-ins and all historical trip data.

Patterns

Design

Data structures

Hash Table String

Prompt

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

void checkIn(int id, string stationName, int t)
- A customer with a card ID equal to id, checks in at the station stationName at time t.
- A customer can only be checked into one place at a time.
void checkOut(int id, string stationName, int t)
- A customer with a card ID equal to id, checks out from the station stationName at time t.
double getAverageTime(string startStation, string endStation)
- Returns the average time it takes to travel from startStation to endStation.
- The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
- The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
- There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.

You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t₁ then checks out at time t₂, then t₁ < t₂. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);  // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12

Example 2:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

Constraints:

1 <= id, t <= 10⁶
1 <= stationName.length, startStation.length, endStation.length <= 10
All strings consist of uppercase and lowercase English letters and digits.
There will be at most 2 * 10⁴ calls in total to checkIn, checkOut, and getAverageTime.
Answers within 10^-5 of the actual value will be accepted.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves storing the details of every single trip that is completed. When a customer checks out, we calculate the travel time for their journey and add a record of this trip (start station, end station, and travel time) to a list. To find the average time for a specific route, we iterate through this entire list of trips, find all the matching ones, sum up their travel times, and divide by the count of matching trips.

Algorithm

checkIn(id, stationName, t):
1. Store the stationName and t associated with the customer id in a hash map checkIns.
checkOut(id, stationName, t):
1. Retrieve the check-in data (startStation, startTime) for id from checkIns.
2. Calculate travelTime = t - startTime.
3. Create a new Trip object with startStation, endStation (stationName), and travelTime.
4. Add this Trip object to a list completedTrips.
5. Remove the entry for id from checkIns.
getAverageTime(startStation, endStation):
1. Initialize totalTime = 0 and count = 0.
2. Iterate through each trip in the completedTrips list.
3. If trip.startStation equals startStation and trip.endStation equals endStation, increment count and add trip.travelTime to totalTime.
4. Return totalTime / count.

Walkthrough

We use two main data structures:

A hash map, checkIns, to keep track of customers who are currently on a journey. The key is the customer's id, and the value is an object or pair containing their startStation and checkInTime.
A list, completedTrips, to store information about every trip that has been completed. Each element in the list would be an object containing startStation, endStation, and travelTime.

checkIn(id, stationName, t): We simply record the check-in information by adding an entry to the checkIns map.
checkOut(id, stationName, t): We look up the customer's check-in data from the checkIns map using their id. With the start station and start time, we can calculate the travel time. We then create a new trip record and add it to our completedTrips list. Finally, we remove the customer's data from the checkIns map as their journey is complete.
getAverageTime(startStation, endStation): This is the most intensive operation. We must traverse the entire completedTrips list. For each trip, we check if its start and end stations match the requested route. If they do, we add its travel time to a running total and increment a counter. After checking all trips, we calculate the average by dividing the total time by the count.

1// Helper class to store check-in data2class CheckInData {3    String stationName;4    int time;5 6    public CheckInData(String stationName, int time) {7        this.stationName = stationName;8        this.time = time;9    }10}11 12// Helper class to store completed trip data13class Trip {14    String startStation;15    String endStation;16    int travelTime;17 18    public Trip(String startStation, String endStation, int travelTime) {19        this.startStation = startStation;20        this.endStation = endStation;21        this.travelTime = travelTime;22    }23}24 25class UndergroundSystem {26    private Map<Integer, CheckInData> checkIns;27    private List<Trip> completedTrips;28 29    public UndergroundSystem() {30        checkIns = new HashMap<>();31        completedTrips = new ArrayList<>();32    }33 34    public void checkIn(int id, String stationName, int t) {35        checkIns.put(id, new CheckInData(stationName, t));36    }37 38    public void checkOut(int id, String stationName, int t) {39        CheckInData checkInData = checkIns.get(id);40        int travelTime = t - checkInData.time;41        completedTrips.add(new Trip(checkInData.stationName, stationName, travelTime));42        checkIns.remove(id);43    }44 45    public double getAverageTime(String startStation, String endStation) {46        double totalTime = 0;47        int count = 0;48        for (Trip trip : completedTrips) {49            if (trip.startStation.equals(startStation) && trip.endStation.equals(endStation)) {50                totalTime += trip.travelTime;51                count++;52            }53        }54        return totalTime / count;55    }56}

Complexity

Time

`checkIn`: O(1) - Hash map insertion is on average constant time. `checkOut`: O(1) - Hash map lookup and list append are on average constant time. `getAverageTime`: O(N), where N is the total number of completed trips. In the worst case, we have to scan the entire list of trips.

Space

O(P + N), where P is the number of passengers currently checked in, and N is the total number of completed trips. We need space to store ongoing check-ins and all historical trip data.

Trade-offs

Pros

Simple to conceptualize and implement.
Fast checkIn and checkOut operations.

Cons

getAverageTime is slow, its performance degrades as more trips are completed.
High memory usage as it stores data for every single trip, which can be redundant if many trips occur on the same routes.

This approach optimizes the getAverageTime operation by pre-calculating and storing the aggregated travel data for each route. Instead of storing every single trip, we maintain the total travel time and the number of trips for each unique route (startStation to endStation). When a customer checks out, we update these aggregates. This way, calculating the average time becomes a simple lookup and a division, making it extremely fast.

Algorithm

Data Structures:
- checkIns: A hash map mapping customer id to their check-in data (stationName, time).
- routeStats: A hash map mapping a route identifier string (e.g., "start:end") to an object containing totalTime and tripCount.
checkIn(id, stationName, t):
1. Store the stationName and t for the customer id in the checkIns map.
checkOut(id, stationName, t):
1. Retrieve the check-in data (startStation, startTime) for id from checkIns.
2. Calculate travelTime = t - startTime.
3. Construct a route key, e.g., startStation + ":" + stationName.
4. Fetch the current statistics for this route from routeStats. If none exist, create a new statistics object with zero values.
5. Update the statistics: add travelTime to totalTime and increment tripCount.
6. Store the updated statistics back into routeStats.
7. Remove the entry for id from checkIns.
getAverageTime(startStation, endStation):
1. Construct the route key from startStation and endStation.
2. Retrieve the statistics object for this route from routeStats.
3. Return totalTime / tripCount from the statistics object.

Walkthrough

We use two hash maps:

A hash map checkIns to track active journeys. It maps a customer id to their check-in information (startStation and checkInTime).
A second hash map routeStats to store the aggregated data for each route. The key for this map is a string representation of the route (e.g., "startStation:endStation"), and the value is an object containing the totalTravelTime and tripCount for that route.

checkIn(id, stationName, t): We store the check-in details in the checkIns map.
checkOut(id, stationName, t): When a customer checks out, we retrieve their check-in data. We calculate the travel time. Then, we form a unique key for the route. We use this key to find the existing statistics in routeStats. We update the total time and trip count with the new trip's data. If no entry exists for this route, we create a new one. Finally, we remove the check-in data for the customer from checkIns.
getAverageTime(startStation, endStation): We form the route key from the given stations. We look up the aggregated data in routeStats using this key. The average is simply totalTravelTime / tripCount.

1// Helper class for check-in data2class CheckInData {3    String stationName;4    int time;5    public CheckInData(String stationName, int time) {6        this.stationName = stationName;7        this.time = time;8    }9}10 11// Helper class for route statistics12class RouteStats {13    double totalTime;14    int tripCount;15    public RouteStats(double totalTime, int tripCount) {16        this.totalTime = totalTime;17        this.tripCount = tripCount;18    }19}20 21class UndergroundSystem {22    private Map<Integer, CheckInData> checkIns;23    private Map<String, RouteStats> routeStats;24 25    public UndergroundSystem() {26        checkIns = new HashMap<>();27        routeStats = new HashMap<>();28    }29 30    public void checkIn(int id, String stationName, int t) {31        checkIns.put(id, new CheckInData(stationName, t));32    }33 34    public void checkOut(int id, String stationName, int t) {35        CheckInData checkInData = checkIns.get(id);36        int travelTime = t - checkInData.time;37        String routeKey = checkInData.stationName + ":" + stationName;38 39        RouteStats stats = routeStats.getOrDefault(routeKey, new RouteStats(0.0, 0));40        stats.totalTime += travelTime;41        stats.tripCount++;42        routeStats.put(routeKey, stats);43 44        checkIns.remove(id);45    }46 47    public double getAverageTime(String startStation, String endStation) {48        String routeKey = startStation + ":" + endStation;49        RouteStats stats = routeStats.get(routeKey);50        return stats.totalTime / stats.tripCount;51    }52}

Complexity

Time

`checkIn`: O(1) - Average time for hash map insertion. `checkOut`: O(1) - Average time for hash map lookups and updates. String concatenation is fast for short strings. `getAverageTime`: O(1) - Average time for hash map lookup.

Space

O(P + R), where P is the number of passengers currently checked in, and R is the number of unique routes that have been traveled. This is more memory-efficient than the brute-force approach because R is typically much smaller than the total number of trips N, especially with many repeated journeys on the same routes.

Trade-offs

Pros

Extremely fast getAverageTime operation, with constant time complexity.
Efficient memory usage by storing aggregated data instead of individual trip records.
All operations (checkIn, checkOut, getAverageTime) are very fast, making the system scalable.

Cons

Slightly more complex to implement due to managing two separate data structures and the logic for aggregating data.
The choice of the route key (e.g., string concatenation) might have minor performance implications, though negligible in this case.

Solutions

Solution

1class UndergroundSystem { private Map < Integer , Integer > ts = new HashMap <>(); private Map < Integer , String > names = new HashMap <>(); private Map < String , int []> d = new HashMap <>(); public UndergroundSystem () { } public void checkIn ( int id , String stationName , int t ) { ts . put ( id , t ); names . put ( id , stationName ); } public void checkOut ( int id , String stationName , int t ) { String key = names . get ( id ) + "-" + stationName ; int [] v = d . getOrDefault ( key , new int [ 2 ]); v [ 0 ] += t - ts . get ( id ); v [ 1 ]++; d . put ( key , v ); } public double getAverageTime ( String startStation , String endStation ) { String key = startStation + "-" + endStation ; int [] v = d . get ( key ); return ( double ) v [ 0 ] / v [ 1 ]; } } /** * Your UndergroundSystem object will be instantiated and called as such: * UndergroundSystem obj = new UndergroundSystem(); * obj.checkIn(id,stationName,t); * obj.checkOut(id,stationName,t); * double param_3 = obj.getAverageTime(startStation,endStation); */

1class UndergroundSystem { public: UndergroundSystem () { } void checkIn ( int id , string stationName , int t ) { ts [ id ] = { stationName , t }; } void checkOut ( int id , string stationName , int t ) { auto [ station , t0 ] = ts [ id ]; auto key = station + "-" + stationName ; auto [ tot , cnt ] = d [ key ]; d [ key ] = { tot + t - t0 , cnt + 1 }; } double getAverageTime ( string startStation , string endStation ) { auto [ tot , cnt ] = d [ startStation + "-" + endStation ]; return ( double ) tot / cnt ; } private: unordered_map < int , pair < string , int >> ts ; unordered_map < string , pair < int , int >> d ; }; /** * Your UndergroundSystem object will be instantiated and called as such: * UndergroundSystem* obj = new UndergroundSystem(); * obj->checkIn(id,stationName,t); * obj->checkOut(id,stationName,t); * double param_3 = obj->getAverageTime(startStation,endStation); */

1class UndergroundSystem : def __init__ ( self ): self . ts = {} self . d = {} def checkIn ( self , id : int , stationName : str , t : int ) -> None : self . ts [ id ] = ( t , stationName ) def checkOut ( self , id : int , stationName : str , t : int ) -> None : t0 , station = self . ts [ id ] x = self . d . get (( station , stationName ), ( 0 , 0 )) # (startStation, endStation) => (totalTime, count) # add up on all history data for start/end station self . d [( station , stationName )] = ( x [ 0 ] + t - t0 , x [ 1 ] + 1 ) def getAverageTime ( self , startStation : str , endStation : str ) -> float : x = self . d [( startStation , endStation )] return x [ 0 ] / x [ 1 ] # Your UndergroundSystem object will be instantiated and called as such: # obj = UndergroundSystem() # obj.checkIn(id,stationName,t) # obj.checkOut(id,stationName,t) # param_3 = obj.getAverageTime(startStation,endStation)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem