Leetcode 1396: Design Underground System
You are tasked with building a system to track customer travel times within an underground railway network. The system should calculate the average time taken to travel between two stations based on previous trips. Implement the
UndergroundSystem class with the following methods.Problem
Approach
Steps
Complexity
Input: The input consists of several commands, each one representing a method call to the UndergroundSystem class. Each command is represented as an array where the first element is the method name, and the rest are its respective arguments.
Example: ["UndergroundSystem", "checkIn", "checkOut", "getAverageTime"]
Constraints:
• 1 <= id, t <= 10^6
• 1 <= stationName.length <= 10
• All strings consist of uppercase and lowercase English letters and digits.
Output: The output for each method call will be either null (for checkIn and checkOut methods) or a double representing the average time for the given trip (for getAverageTime).
Example: [null, null, 10.00000]
Constraints:
• Answers within 10^-5 of the actual value will be accepted.
Goal: To efficiently track and calculate the average travel times between stations.
Steps:
• 1. Use a map to store the check-in times and stations for each customer.
• 2. When a customer checks out, calculate the travel time and update the sum and count of trips between stations.
• 3. To calculate the average time between two stations, divide the total time by the number of trips between the stations.
Goal: Ensure that all method calls and inputs are consistent with the problem statement's restrictions.
Steps:
• There will be at least one call to getAverageTime before it is called.
Assumptions:
• All method calls will be valid and in chronological order.
• No customer will check in or check out at the same time.
• Input: Input: ["UndergroundSystem", "checkIn", "checkOut", "getAverageTime"]
• Explanation: In this example, we simulate customers checking in and out of stations and calculating average travel times.
Approach: The approach involves tracking each customer's check-in and check-out times, updating a map of total travel times and counts for each trip, and calculating the average when requested.
Observations:
• Efficiently managing check-in and check-out events will be crucial for large datasets.
• Use maps for storing check-in and check-out data to ensure fast access.
• Focus on optimizing the update of travel times and counts for each station pair.
Steps:
• 1. Create a `checkIn` method to store customer check-ins.
• 2. Implement `checkOut` to update the sum and count of trips for a station pair.
• 3. For `getAverageTime`, return the average by dividing the total time by the number of trips.
Empty Inputs:
• What if no customer checks in before calling `getAverageTime`?
Large Inputs:
• Ensure the system handles up to 20,000 method calls efficiently.
Special Values:
• Handle cases where a customer checks in and out multiple times for the same station pair.
Constraints:
• The system should work with varying customer IDs and station names.
string station;
};
class UndergroundSystem {
public:
map<string, map<string, double>> cnt, sum;
map<int, Node> user;
UndergroundSystem() {
}
void checkIn(int id, string name, int t) {
Node n;
n.time = t;
n.station = name;
user[id] = n;
}
void checkOut(int id, string name, int t) {
Node entry = user[id];
cout << user[id].station;
user.erase(id);
cnt[entry.station][name]++;
sum[entry.station][name]+= t - entry.time;
}
double getAverageTime(string start, string end) {
return sum[start][end] / cnt[start][end];
}
};
/**
* 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);
1 : Variable Initialization
string station;
Declaring a string variable `station` to hold the station name for each user.
2 : Class Definition
class UndergroundSystem {
Beginning of the `UndergroundSystem` class definition.
3 : Access Control
public:
Public access specifier for methods and variables that follow.
4 : Map Operations
map<string, map<string, double>> cnt, sum;
Declaring two nested maps to track the count of rides (`cnt`) and the sum of times (`sum`) between station pairs.
5 : Map Operations
map<int, Node> user;
A map to store the user data by their unique ID.
6 : Constructor
UndergroundSystem() {
Constructor for the `UndergroundSystem` class, initializing necessary data structures.
7 : Method Definition
void checkIn(int id, string name, int t) {
Defines the `checkIn` method to record a user's entry at a station.
8 : Variable Initialization
Node n;
Creates a `Node` object to store information about the user's check-in.
9 : Variable Assignment
n.time = t;
Assigns the time of check-in to the `Node` object.
10 : Variable Assignment
n.station = name;
Assigns the station name to the `Node` object.
11 : Data Insertion
user[id] = n;
Inserts the user data into the `user` map with the user ID as the key.
12 : Method Definition
void checkOut(int id, string name, int t) {
Defines the `checkOut` method to record when a user exits a station.
13 : Data Retrieval
Node entry = user[id];
Retrieves the user's check-in data from the `user` map.
14 : Data Deletion
user.erase(id);
Removes the user from the `user` map after checking out.
15 : Map Operations
cnt[entry.station][name]++;
Increments the count of rides between stations in the `cnt` map.
16 : Map Operations
sum[entry.station][name]+= t - entry.time;
Adds the time spent during the ride to the `sum` map.
17 : Method Definition
double getAverageTime(string start, string end) {
Defines the `getAverageTime` method to calculate the average time between two stations.
18 : Return Statement
return sum[start][end] / cnt[start][end];
Returns the average time by dividing the sum by the count of rides.
Best Case: O(1) for getAverageTime when there is only one trip.
Average Case: O(1) for getAverageTime, O(log N) for checkIn and checkOut operations.
Worst Case: O(N) for getAverageTime in cases where many trips are recorded.
Description:
Best Case: O(1) for operations with minimal data.
Worst Case: O(N) for storing customer and trip data.
Description:
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus