Sponsored
Sponsored
In this approach, we use two dictionaries to store the data: one for storing check-in information and another to store route information.
Time Complexity: O(1) for each operation (check-in, check-out, and get average time) because dictionary operations are constant time.
Space Complexity: O(P + R) where P is the number of passengers and R is the number of route pairs.
1#include <unordered_map>
2#include <string>
3#include <utility>
4using namespace std;
5
6class UndergroundSystem {
7private:
8 unordered_map<int, pair<string, int>> checkInData;
9 unordered_map<string, pair<int, int>> routeData;
10
11public:
12 UndergroundSystem() {}
13
14 void checkIn(int id, const string &stationName, int t) {
15 checkInData[id] = {stationName, t};
16 }
17
18 void checkOut(int id, const string &stationName, int t) {
19 auto &checkInInfo = checkInData[id];
20 string routeKey = checkInInfo.first + "->" + stationName;
21 int travelTime = t - checkInInfo.second;
22 checkInData.erase(id);
23
24 if (routeData.find(routeKey) == routeData.end()) {
25 routeData[routeKey] = {0, 0};
26 }
27 routeData[routeKey].first += travelTime;
28 routeData[routeKey].second += 1;
29 }
30
31 double getAverageTime(const string &startStation, const string &endStation) {
32 string routeKey = startStation + "->" + endStation;
33 auto &routeInfo = routeData[routeKey];
34 return (double) routeInfo.first / routeInfo.second;
35 }
36};This C++ solution handles the check-in process using an unordered_map to associate customer IDs with their respective check-in stations and times. During check-out, travel time is computed using the stored entry, then the entry is removed. Another unordered_map keeps track of total times and counts for each route as described by a start and end station. Finally, the getAverageTime method calculates the average time by accessing the correct route data and computing the result.
This method uses a list and constructs a unique key using the combination of start and end stations for storing travel information.
Time Complexity: O(1) for all operations due to constant time performance of the HashMap.
Space Complexity: O(P + R), where P represents the checked-in passengers, and R is the number of unique routes.
1#include <stdio.h>
2
The C implementation manually manages data using hash tables with array-based chaining to handle hash collisions. The checkIn and checkOut functions update situational data accordingly, while getAverageTime calculates the average directly from stored totals and counts.