#1396

Medium

LeetCode Problem Workspace

Design Underground System

Design an underground system to calculate travel times between stations using hash tables for efficient lookups and average time calculations.

hash table string design

Problem Statement

You are tasked with designing an underground railway system that tracks travel times between stations. Customers check in at one station and check out at another, and you need to calculate the average travel time between two stations.

You are required to implement the UndergroundSystem class. The class has the following methods: checkIn(id, stationName, t), checkOut(id, stationName, t), and getAverageTime(startStation, endStation). The class should handle all events in chronological order, and you may assume that customer data is consistent.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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: See original problem statement.

Output: See original problem statement.

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 Approach

Using Two Hash Tables

To solve this problem efficiently, use two hash tables: one for storing check-in times for customers and another for tracking total travel times between stations. This design allows for quick lookups when calculating average travel times.

Handling Multiple Customer Events

Ensure that each customer's check-in and check-out data are correctly paired. Store the check-in times in the first hash table and update the total travel time and count for each station pair in the second hash table. This ensures that multiple customers' data can be processed efficiently.

Calculating Average Time

For each query requesting the average time between two stations, retrieve the total travel time and the count of trips between the stations from the second hash table, then calculate the average. The result must be accurate up to 5 decimal places.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is primarily driven by the hash table lookups, making each method call (checkIn, checkOut, and getAverageTime) efficient, typically O(1). Space complexity depends on the number of unique customers and station pairs, with a space complexity of O(n), where n is the number of customers and station pairs.

What Interviewers Usually Probe

Look for understanding of hash table usage in managing time and space complexities.
Assess the ability to handle multiple events and efficient data retrieval.
Check for clarity in implementing the getAverageTime method and ensuring precision.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly pair check-ins and check-outs for each customer, leading to incorrect calculations.
Inadequate handling of edge cases, such as the first check-in for a station pair.
Incorrect average time calculation, especially in handling precision up to 5 decimal places.

Follow-up variants

Handle different station names or a higher number of station pairs.
Optimize for scenarios where the system is under high traffic, with a large number of events.
Consider adding features such as a real-time station occupancy tracker alongside travel time tracking.

FAQ

What is the primary pattern used in the "Design Underground System" problem?

The primary pattern is a combination of hash tables and string manipulation, used to track check-in times and calculate average travel times between stations.

How does the check-in and check-out system work in this problem?

Customers check in at a station with a timestamp, and when they check out at another station, the system calculates the total time between the two stations to compute the average travel time.

How do you calculate the average travel time between two stations?

The average travel time is calculated by dividing the total travel time between the stations by the number of trips between them.

What is the time complexity of this problem?

The time complexity for each method is O(1), as hash table lookups are constant time operations.

What should be the precision of the average time calculation?

The average time should be calculated with a precision of 5 decimal places.

terminal

Solution

Solution 1: Hash Table

We use two hash tables to store data:

class 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))
        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)

Continue Practicing

#981 time based key value store #745 prefix and suffix search #677 map sum pairs