{x}
blog image

Design Underground System

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 t1 then checks out at time t2, then t1 < t2. 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 <= 106
  • 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 * 104 calls in total to checkIn, checkOut, and getAverageTime.
  • Answers within 10-5 of the actual value will be accepted.

Solution Explanation: Design Underground System

This problem requires designing a system to track customer travel times on an underground railway. The system needs to handle check-ins, check-outs, and calculating average travel times between stations. The optimal solution uses hash tables (or dictionaries) for efficient data storage and retrieval.

Data Structures:

The core of the solution lies in using two hash tables:

  1. checkin_data (or ts in the code): This hash table stores information about currently checked-in passengers. The key is the passenger's ID (id), and the value is a tuple (or similar structure) containing the check-in time (t) and the check-in station (stationName).

  2. travel_times (or d in the code): This hash table stores the accumulated travel times between station pairs. The key is a tuple representing the start and end stations ((startStation, endStation)), and the value is another tuple containing the total travel time for that pair and the number of trips made between those stations.

Methods:

  • checkIn(id, stationName, t): This method simply adds the passenger's ID, check-in station, and time to the checkin_data hash table. The lookup and insertion in a hash table takes O(1) on average.

  • checkOut(id, stationName, t): This method does the following:

    • Retrieves the check-in time and station from checkin_data using the passenger ID. O(1) lookup.
    • Calculates the travel time (t - t_checkin).
    • Updates the travel_times hash table. If the (startStation, endStation) pair already exists, it adds the travel time to the total and increments the trip count; otherwise, it creates a new entry. This is an O(1) operation on average.

  • getAverageTime(startStation, endStation): This method retrieves the total travel time and trip count from travel_times for the given station pair. It then calculates and returns the average travel time. The lookup in the hash table takes O(1) on average.

Time and Space Complexity:

  • Time Complexity: All three methods (checkIn, checkOut, getAverageTime) have an average time complexity of O(1) because they primarily involve hash table lookups and updates, which are typically constant-time operations. In the worst case (hash collisions), it could become O(n), where n is the number of entries in the hash table, but this is unlikely with a good hash function.

  • Space Complexity: The space complexity is O(n+m), where 'n' is the number of unique passenger IDs and 'm' is the number of unique station pairs. This is because the size of the hash tables grows linearly with the number of passengers and the number of distinct station pairs.

Code Examples (Python):

class UndergroundSystem:
    def __init__(self):
        self.checkin_data = {}
        self.travel_times = {}
 
    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.checkin_data[id] = (t, stationName)
 
    def checkOut(self, id: int, stationName: str, t: int) -> None:
        t_checkin, start_station = self.checkin_data[id]
        travel_time = t - t_checkin
        key = (start_station, stationName)
        if key in self.travel_times:
            total_time, count = self.travel_times[key]
            self.travel_times[key] = (total_time + travel_time, count + 1)
        else:
            self.travel_times[key] = (travel_time, 1)
 
    def getAverageTime(self, startStation: str, endStation: str) -> float:
        total_time, count = self.travel_times[(startStation, endStation)]
        return total_time / count

The provided Java, C++, and Go code examples follow the same logic and data structures, achieving the same time and space complexity. They differ only in syntax and specific data structure implementations.