Design Underground System - Leetcode Solution

Problem description:

Design an underground system to track the traveling of the subway riders. Implement the following two methods:

1. void checkIn(int id, string stationName, int t)

• A customer with id card 'id' checked in at station 'stationName' at time 't'.
• A customer can only be checked into one place at a time.

2. void checkOut(int id, string stationName, int t)

• A customer with id card 'id' checked out from station 'stationName' at time 't'.

Implement the following function:

3. double getAverageTime(string startStation, string endStation)

• Returns the average time taken to travel between the startStation and the endStation.

Solution:

To solve this problem, we need to implement a class which handles the check-in and check-out of passengers, and also calculates the average time taken between two stations. We can use two hash tables to store the information of check-in and check-out.

• checkIn hash table: This hash table will store the information of passenger's check-in time and station name, with the passenger's ID as key.
• checkOut hash table: This hash table will store the information of passenger's check-out time and station name, with the passenger's ID as key.

We can also use a nested hash table to calculate the average time taken between two stations, where the outer hash table stores the information of start station and the inner hash table stores the information of end station with the average travel time as value.

Algorithm:

1. Create a class called UndergroundSystem. In the constructor, initialize the checkIn hash table, checkOut hash table, and travelTime hash table.

2. Define a checkIn() method which takes the ID, stationName, and time as input. Retrieve the current station name and time from the checkIn hash table using the ID and store the information in the hash table.

3. Define a checkOut() method which takes the ID, stationName, and time as input. Retrieve the check-in station name and time from the checkIn hash table using the ID, and store the check-out station name and time in the checkOut hash table. Calculate the travel time and store the information in the travelTime hash table.

4. Define a getAverageTime() method which takes startStation and endStation as input. Retrieve the average travel time from the travelTime hash table using the startStation and endStation.

5. Return the average travel time.

Code:

C++ code to solve this problem is given below:

class UndergroundSystem { private: unordered_map<int, pair<string, int>> checkIn; unordered_map<pair<string, string>, pair<int, int>> travelTime; public: UndergroundSystem() { checkIn.clear(); travelTime.clear(); }

void checkIn(int id, string stationName, int t) {
    checkIn[id] = {stationName, t};
}

void checkOut(int id, string stationName, int t) {
    auto& checkInData = checkIn[id];
    string& startStation = checkInData.first;
    int& startTime = checkInData.second;
    int travelDuration = t - startTime;
    auto& travelTimeData = travelTime[{startStation, stationName}];
    travelTimeData.first += travelDuration;
    travelTimeData.second++;
}

double getAverageTime(string startStation, string endStation) {
    auto& travelTimeData = travelTime[{startStation, endStation}];
    return static_cast<double>(travelTimeData.first) / travelTimeData.second;
}

};

Time Complexity:

• The checkIn() method takes O(1) time complexity to check in a passenger.
• The checkOut() method takes O(1) time complexity to check out a passenger and calculates the travel duration.
• The getAverageTime() method takes O(1) time complexity to retrieve the average travel time from the nested hash table.

Therefore, the overall time complexity of this solution is O(1).

1