# Design Underground System Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg
Design HashMap StringViews 63

System design interview questions can be so open-ended, that it's too hard to know the right way to prepare. Now I am able to crack the design rounds of Amazon, Microsoft, and Adobe after buying this book. Daily revise one design question and I promise you can crack the design round.

## Problem Statement

The Design Underground System LeetCode Solution – “Design Underground System” asks you to design a railway system to keep track of customer travel times between two stations. It is needed to calculate the average time it takes to travel from one station to another.

We need to implement the UndergroundSystem class:

• Checkin: A customer with a card ID equal to `id`, checks in at the station `stationName` at time `t`.
• Checkout: A customer with a card ID equal to `id`, checks out from the station `stationName` at time `t`.
• GetAverageTime: Returns the average time it takes to travel from `startStation` to `endStation`. The average time is calculated from all the previous traveling times from start station to end station that had happened directly.

## Example:

```Input:  ["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
`Output: [null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]`

Explanation:

• Checkin at (45, Leyton, 3). Checkin at (32, Paradise, 8), Checkin at (32, Paradise, 8).
• Checkout at (45, Waterloo, 15).
• Checkout at (27, Waterloo, 20).
• Checkout(32, Cambridge, 22).
• Average Time(Paradise, Cambridge) = 14/1 = 14.
• Average Time(Leyton, Waterloo) = (10+12)/2 = 11.
• Average Time(Leyton, Waterloo) = 11.
• Checkout(10, Waterloo, 38).
• Average Time(Leyton, Waterloo) = (10+12+14)/3 = 12.

## Approach

### Idea:

1. The main idea to solve this problem is to use a hashmap.
2. Maintain two different hashmaps, one for check-ins and the other for routes.
3. Now, for each check-in, insert the id with the station name and current time.
4. Also, for each check-out, erase the entry for the check-in hashmap. Also, insert the route formed from the check-in station to the check-out station in the route hashmap.
5. Calculate the average time with the help of count and sum entries of the route hashmap.

## Code

### Design Underground System Leetcode C++ Solution:

```class UndergroundSystem {
public:
unordered_map<int, pair<string, int>> checkins;
unordered_map<string, pair<int, int>> routes;
void checkIn(int id, string stationName, int t) {
checkins[id] = {stationName, t};
}
void checkOut(int id, string stationName, int t) {
auto [stn, start] = checkins[id];
checkins.erase(id);
string route = stn + "," + stationName;
routes[route].first++, routes[route].second += t - start;
}
double getAverageTime(string startStation, string endStation) {
auto& [count, sum] = routes[startStation + "," + endStation];
return (double)sum / count;
}
};```

### Design Underground System Leetcode Java Solution:

```class UndergroundSystem {
Map<Integer, Pair<String, Integer>> checkins = new HashMap<>();
Map<Pair<String, String>, int[]> routes = new HashMap<>();
public void checkIn(int id, String stationName, int t) {
checkins.put(id, new Pair(stationName, t));
}
public void checkOut(int id, String stationName, int t) {
Pair<String, Integer> cIn = checkins.get(id);
checkins.remove(id);
Pair<String, String> route = new Pair(cIn.getKey(), stationName);
int[] trip = routes.getOrDefault(route, new int[2]);
trip[0]++;
trip[1] += t - cIn.getValue();
routes.put(route, trip);
}
public double getAverageTime(String startStation, String endStation) {
int[] trip = routes.get(new Pair(startStation, endStation));
return (double)trip[1] / trip[0];
}
}```

## Complexity Analysis for Design Underground System Leetcode Solution

### Time Complexity

The time complexity of the above code is O(logN) for each function call where N = a maximum number of check-in/check out done.

### Space Complexity

The space complexity of the above code is O(N).

Translate »