The "Design Underground System" problem involves tracking the travel times of passengers in an underground transit system. You are required to design a class UndergroundSystem that supports the following operations:
checkIn(id, stationName, t): A customer with a unique id checks in at stationName at time t.
checkOut(id, stationName, t): The same customer checks out from stationName at time t.
getAverageTime(startStation, endStation): Returns the average time taken by all customers who traveled from startStation to endStation.
Each customer can only be checked into one station at a time. The system should efficiently support multiple queries and updates. The solution must ensure that each trip is only counted once, and the average is calculated only for valid completed trips between the specified stations.
At first glance, a brute-force approach might involve storing each trip individually and iterating through all trips to compute averages. However, this would be inefficient, especially as the number of trips grows.
Instead, we should focus on using data structures that allow us to:
This leads us to use hash maps (dictionaries) to associate customer IDs with their current journey, and another hash map to track total times and trip counts for each station pair.
To design the UndergroundSystem efficiently, we use two main hash maps:
id of the customerstationName, checkInTime)startStation, endStation)totalTravelTime, tripCount)checkIn(id, stationName, t):
stationName and t in the check-in map for this id.checkOut(id, stationName, t):
id.t - checkInTime.startStation, endStation) by adding the duration to the total and incrementing the count.id from the check-in map (since the trip is completed).getAverageTime(startStation, endStation):
totalTime / tripCount.This approach ensures all operations are efficient and the data is always consistent.
Let's step through a sample sequence of operations:
checkIn(45, "Leyton", 3)checkIn(32, "Paradise", 8)checkIn(27, "Leyton", 10)checkOut(45, "Waterloo", 15) checkOut(27, "Waterloo", 20) checkOut(32, "Cambridge", 22) getAverageTime("Paradise", "Cambridge") getAverageTime("Leyton", "Waterloo") At each step, the check-in and check-out maps are updated efficiently, and the average is computed instantly.
Brute-force Approach:
getAverageTime O(N), where N is the number of trips.checkIn, checkOut, getAverageTime) is O(1) due to hash map lookups/updates.This makes the system scalable and efficient even as the number of customers and trips increases.
The key to solving the "Design Underground System" problem efficiently is to use two hash maps: one for tracking ongoing journeys and one for aggregating travel data by station pair. This allows all operations to be performed in constant time, ensuring the system remains fast and scalable. The solution is elegant because it leverages simple data structures to provide robust and efficient functionality for a real-world scenario.
class UndergroundSystem:
def __init__(self):
self.check_in = {} # id -> (stationName, time)
self.travel_data = {} # (startStation, endStation) -> [totalTime, tripCount]
def checkIn(self, id: int, stationName: str, t: int) -> None:
self.check_in[id] = (stationName, t)
def checkOut(self, id: int, stationName: str, t: int) -> None:
startStation, startTime = self.check_in.pop(id)
key = (startStation, stationName)
if key not in self.travel_data:
self.travel_data[key] = [0, 0]
self.travel_data[key][0] += t - startTime
self.travel_data[key][1] += 1
def getAverageTime(self, startStation: str, endStation: str) -> float:
totalTime, tripCount = self.travel_data[(startStation, endStation)]
return totalTime / tripCount
class UndergroundSystem {
unordered_map<int, pair<string, int>> check_in;
unordered_map<string, pair<double, int>> travel_data;
public:
UndergroundSystem() {}
void checkIn(int id, string stationName, int t) {
check_in[id] = {stationName, t};
}
void checkOut(int id, string stationName, int t) {
auto [startStation, startTime] = check_in[id];
check_in.erase(id);
string key = startStation + "-" + stationName;
auto &data = travel_data[key];
data.first += (t - startTime);
data.second += 1;
}
double getAverageTime(string startStation, string endStation) {
string key = startStation + "-" + endStation;
auto &data = travel_data[key];
return data.first / data.second;
}
};
class UndergroundSystem {
private Map<Integer, Pair<String, Integer>> checkIn;
private Map<String, double[]> travelData;
public UndergroundSystem() {
checkIn = new HashMap<>();
travelData = new HashMap<>();
}
public void checkIn(int id, String stationName, int t) {
checkIn.put(id, new Pair<>(stationName, t));
}
public void checkOut(int id, String stationName, int t) {
Pair<String, Integer> entry = checkIn.remove(id);
String key = entry.getKey() + "-" + stationName;
double[] data = travelData.getOrDefault(key, new double[2]);
data[0] += t - entry.getValue();
data[1] += 1;
travelData.put(key, data);
}
public double getAverageTime(String startStation, String endStation) {
String key = startStation + "-" + endStation;
double[] data = travelData.get(key);
return data[0] / data[1];
}
// Helper Pair class (since Java doesn't have one by default)
private static class Pair<K, V> {
private K key;
private V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() { return key; }
public V getValue() { return value; }
}
}
var UndergroundSystem = function() {
this.checkIn = new Map(); // id -> [stationName, time]
this.travelData = new Map(); // "start-end" -> [totalTime, tripCount]
};
UndergroundSystem.prototype.checkIn = function(id, stationName, t) {
this.checkIn.set(id, [stationName, t]);
};
UndergroundSystem.prototype.checkOut = function(id, stationName, t) {
const [startStation, startTime] = this.checkIn.get(id);
this.checkIn.delete(id);
const key = startStation + '-' + stationName;
if (!this.travelData.has(key)) {
this.travelData.set(key, [0, 0]);
}
const data = this.travelData.get(key);
data[0] += t - startTime;
data[1] += 1;
};
UndergroundSystem.prototype.getAverageTime = function(startStation, endStation) {
const key = startStation + '-' + endStation;
const data = this.travelData.get(key);
return data[0] / data[1];
};