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.
1class UndergroundSystem {
2 constructor() {
3 this.checkInData = new Map();
4 this.routeData = new Map();
5 }
6
7 checkIn(id, stationName, t) {
8 this.checkInData.set(id, { stationName, t });
9 }
10
11 checkOut(id, stationName, t) {
12 const { stationName: startStation, t: startTime } = this.checkInData.get(id);
13 this.checkInData.delete(id);
14 const routeKey = startStation + '->' + stationName;
15 const travelTime = t - startTime;
16 if (!this.routeData.has(routeKey)) {
17 this.routeData.set(routeKey, { totalTime: 0, tripCount: 0 });
18 }
19 const routeInfo = this.routeData.get(routeKey);
20 routeInfo.totalTime += travelTime;
21 routeInfo.tripCount += 1;
22 this.routeData.set(routeKey, routeInfo);
23 }
24
25 getAverageTime(startStation, endStation) {
26 const routeKey = startStation + '->' + endStation;
27 const { totalTime, tripCount } = this.routeData.get(routeKey);
28 return totalTime / tripCount;
29 }
30}In the JavaScript solution, we use Map objects for checkInData and routeData. The checkIn method adds an entry in checkInData mapping the customer's ID to an object containing station name and time. The checkOut method retrieves and removes the check-in information, calculates the travel time, and updates the corresponding route statistics in routeData. The getAverageTime method returns the average travel time by dividing total time by the number of trips for the specified route.
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.
1import java.util.HashMap;
The Java solution utilizes helper classes, CheckInData and RouteData, to encapsulate the requisite data. The main class, UndergroundSystem, manages check-ins using checkInMap, mapping customer IDs to CheckInData. The check-out data is stored in routeMap, where travel information for each route is updated using RouteData. The average time is computed directly when requested.