Design Underground System

Medium

Asked by:

56 views

Topics:

ArraysStringsDynamic Programming

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of concurrent passengers the system needs to support, and what are the potential scale limitations for storing station names and travel times?
Are station names guaranteed to be unique across all trips, or is there a possibility of having the same station name for different stations?
What data types should I use for representing time and average time? Should I consider potential overflow issues if the time values or the number of trips become very large?
If a passenger starts and ends their journey at the same station, what should the average travel time be? Should the journey be recorded at all?
Can I assume that the start and end stations are always valid and exist within the system, or do I need to handle cases where a passenger attempts to check in or out at a non-existent station?

Brute Force Solution

Approach

The brute force method for the underground system problem means we record every single trip detail as it happens. When asked for the average time between two stations, we go through all recorded trips to find the ones that match those stations.

Here's how the algorithm would work step-by-step:

When a person enters a station, record their ID, the station name, and the time.
When that same person exits a station, record their ID, the station name, and the time.
To find the average travel time between any two stations, look through all the recorded entry and exit events.
Identify all trips that started at the first station and ended at the second station.
For each trip, calculate the travel time by subtracting the entry time from the exit time.
Finally, calculate the average travel time by adding up all the individual travel times and dividing by the total number of trips between those two stations.

Code Implementation

class UndergroundSystem:

    def __init__(self):
        self.trip_history = []

    def checkIn(self, passenger_id: int, station_name: str, travel_time: int) -> None:
        self.trip_history.append({
            'passenger_id': passenger_id,
            'start_station': station_name,
            'start_time': travel_time,
            'end_station': None,
            'end_time': None
        })

    def checkOut(self, passenger_id: int, station_name: str, travel_time: int) -> None:
        for trip in self.trip_history:
            if trip['passenger_id'] == passenger_id and trip['end_station'] is None:
                trip['end_station'] = station_name
                trip['end_time'] = travel_time
                break

    def getAverageTime(self, start_station: str, end_station: str) -> float:
        total_travel_time = 0
        number_of_trips = 0

        # Iterate over all trips to find the relevant ones
        for trip in self.trip_history:
            if trip['start_station'] == start_station and trip['end_station'] == end_station:

                #Calculate time for each trip and increment totals
                total_travel_time += trip['end_time'] - trip['start_time']
                number_of_trips += 1

        # Prevent division by zero
        if number_of_trips == 0:
            return 0.0

        # Average time calculation
        average_time = total_travel_time / number_of_trips
        return average_time

Big(O) Analysis

Time Complexity

O(n) – The enter and exit methods take O(1) since they involve hashmap lookups/insertions which are constant time operations on average. The getAverageTime method iterates through all the recorded trips (entry and exit events) to find trips between startStation and endStation. Assuming there are n recorded trips, the getAverageTime method iterates through all n trips once. Therefore, the time complexity of getAverageTime is O(n).

Space Complexity

O(N) – The brute force approach stores every single trip detail. This means we need to record each person's entry and exit information, creating auxiliary data structures to hold this information. The space required grows linearly with the number of trips, which we can represent as N, where N is the total number of entry and exit events. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The underground system problem is best solved by remembering key information as people travel. We want to efficiently store and retrieve average travel times between stations. To do this, we'll use memory to track who is travelling and calculations to determine average journey times.

Here's how the algorithm would work step-by-step:

When someone starts a journey, record their ID, the station they started at, and the time.
When the same person finishes their journey, find their starting station and time using their ID.
Calculate the travel time for that journey (end time minus start time).
Store the travel time and journey route (start station to end station).
To calculate the average travel time between two stations, add up all the travel times for that route and divide by the number of journeys on that route.
This avoids recomputing the times for each request by using cached values, and only do calculations when new travel data is added

Code Implementation

class UndergroundSystem:

    def __init__(self):
        self.passenger_check_in = {}
        self.station_travel_times = {}

    def checkIn(self, passenger_id: int, start_station: str, travel_time: int) -> None:
        self.passenger_check_in[passenger_id] = (start_station, travel_time)

    def checkOut(self, passenger_id: int, end_station: str, travel_time: int) -> None:
        start_station, check_in_time = self.passenger_check_in[passenger_id]
        del self.passenger_check_in[passenger_id]

        journey_route = (start_station, end_station)
        travel_duration = travel_time - check_in_time

        # Store total time and count for calculating average
        if journey_route in self.station_travel_times:
            total_time, journey_count = self.station_travel_times[journey_route]
            self.station_travel_times[journey_route] = (total_time + travel_duration, journey_count + 1)
        else:
            self.station_travel_times[journey_route] = (travel_duration, 1)

    def getAverageTime(self, start_station: str, end_station: str) -> float:
        journey_route = (start_station, end_station)

        # Retrieve the precalculated values
        total_travel_time, journey_count = self.station_travel_times[journey_route]

        # Return average
        return total_travel_time / journey_count

Big(O) Analysis

Time Complexity

O(1) – The start station and end station functions involve constant-time operations such as hash table lookups to store and retrieve data based on ID. The getAverageTime function involves constant time operations: retrieving stored sums and counts (hash table lookups), performing division, and returning the result. No iteration or recursion depends on the size of the input, thus the time complexity for each operation is O(1).

Space Complexity

O(P + S^2) – The primary auxiliary space is used by two data structures. First, we store information about each passenger in transit, requiring O(P) space, where P is the number of passengers currently checked in but not yet checked out. Second, we store average travel times between each pair of stations, needing to store potentially all combinations of start and end stations, which takes O(S^2) space where S is the number of stations. Therefore, the total auxiliary space is O(P + S^2).

Edge Cases

Case	How to Handle
Multiple people at the same station and time	The enterStation method should handle multiple concurrent check-ins at the same station and time by using customer ID as the unique identifier.
Same person checking in at the same station multiple times without checking out	Overwrite previous check-in data for the customer ID to only consider the latest check-in.
getAverageTime called before any customers complete a journey between two stations	Return 0 or throw an exception indicating no journeys have been completed yet.
Integer overflow in calculating total time or count	Use long data type for storing total time and count to avoid integer overflow.
Station names are the same for start and end stations	The average time should still be calculated and stored separately for journeys from station A to station A if such journeys exist.
Large number of concurrent customers using the system	Use efficient data structures like HashMaps for fast lookups and consider memory usage for a large number of customers.
Extremely large time values	Using long type should mitigate most cases, but be aware of the limits of long and consider alternative representations if needed for extremely large time values.
Customer forgets to check out	There is no graceful recovery, this incomplete data pollutes the average and should be discarded or handled offline, as online recovery might be inconsistent.

Multiple people at the same station and time

How to Handle:

The enterStation method should handle multiple concurrent check-ins at the same station and time by using customer ID as the unique identifier.

Same person checking in at the same station multiple times without checking out

How to Handle:

Overwrite previous check-in data for the customer ID to only consider the latest check-in.

getAverageTime called before any customers complete a journey between two stations

How to Handle:

Return 0 or throw an exception indicating no journeys have been completed yet.

Integer overflow in calculating total time or count

How to Handle:

Use long data type for storing total time and count to avoid integer overflow.

Station names are the same for start and end stations

How to Handle:

The average time should still be calculated and stored separately for journeys from station A to station A if such journeys exist.

Large number of concurrent customers using the system

How to Handle:

Use efficient data structures like HashMaps for fast lookups and consider memory usage for a large number of customers.

Extremely large time values

How to Handle:

Using long type should mitigate most cases, but be aware of the limits of long and consider alternative representations if needed for extremely large time values.

Customer forgets to check out

How to Handle:

There is no graceful recovery, this incomplete data pollutes the average and should be discarded or handled offline, as online recovery might be inconsistent.