Design Underground System
Design a class to simulate an underground system. The class should have methods to check-in and check-out a customer, and to get the average travel time of a customer.
Constraints:
- The number of customers will not exceed 100.
- The number of check-in/check-out operations will not exceed 1000.
Examples:
Input: UndergroundSystem underground = new UndergroundSystem(); underground.checkIn(45, "Leyton", 3); underground.checkIn(32, "Paradise", 8); underground.checkIn(27, "Leyton", 10); underground.checkOut(45, "Waterloo", 15); underground.checkOut(27, "Waterloo", 20); underground.getAverageTime("Paradise", "Cambridge")
Output: 14.00000
Explanation: Customer 45 checks in at Leyton at time 3 and checks out at Waterloo at time 15. Customer 27 checks in at Leyton at time 10 and checks out at Waterloo at time 20. Customer 32 checks in at Paradise at time 8 but does not check out. The average travel time from Paradise to Cambridge is 0.00000 because there are no customers who have traveled from Paradise to Cambridge.
Solutions
Hash Map
We use two hash maps to store the check-in information and the route information. The checkInMap stores the check-in time and station for each customer, and the routeMap stores the total travel time and the number of customers for each route.
class UndergroundSystem {
private Map<Integer, int[]> checkInMap;
private Map<String, long[]> routeMap;
public UndergroundSystem() {
checkInMap = new HashMap<>();
routeMap = new HashMap<>();
}
public void checkIn(int customer, String stationName, int t) {
checkInMap.put(customer, new int[] {
stationName.hashCode(), t}
);
}
public void checkOut(int customer, String stationName, int t) {
int[] checkIn = checkInMap.get(customer);
String route = checkIn[0] + "->" + stationName;
long travelTime = t - checkIn[1];
routeMap.putIfAbsent(route, new long[] {
0, 0}
);
long[] routeData = routeMap.get(route);
routeData[0] += travelTime;
routeData[1]++;
checkInMap.remove(customer);
}
public double getAverageTime(String startStation, String endStation) {
String route = startStation + "->" + endStation;
if (!routeMap.containsKey(route)) {
return 0.0;
}
long[] routeData = routeMap.get(route);
return (double) routeData[0] / routeData[1];
}
}Follow-up:
How would you optimize the solution if the number of customers and check-in/check-out operations are very large?
