Design Underground System

Problem Statement

The purpose here is to design an UndergroundSystem class for an underground railway system that effectively tracks the travel times between different stations. This system captures data related to customer check-ins and check-outs at various stations and computes the average travel times between these stations based on historical data. The key functionalities included are:

• Check-in functionality: Upon arrival at any station, a customer can check in with their unique identifier at a specific time.
• Check-out functionality: When departing from a station, the customer checks out, thereby logging the end of their trip.
• Average computation: For any two given stations, this system can compute the average time taken for journeys that have occurred directly from the first station to the second.

The logic requires that a user can only be checked into one station at a time, and check-outs must correspond to previous check-ins in a chronological manner. There is assurance of at least one complete trip between requested stations for a valid average time calculation.

Examples

Example 1

Input

["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output

[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation

UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15); // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20); // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38); // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12

Example 2

Input

["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

Output

[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation

UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

Constraints

• 1 <= id, t <= 106
• 1 <= stationName.length, startStation.length, endStation.length <= 10
• All strings consist of uppercase and lowercase English letters and digits.
• There will be at most 2 * 104 calls in total to checkIn, checkOut, and getAverageTime.
• Answers within 10-5 of the actual value will be accepted.

Approach and Intuition

Using the examples provided gives a clearer insight into how the system operates:

Example 1 Details:

• Here, the process flow includes multiple customers checking in and out from various stations at different times. The operations illustrate how journeys are tracked individually for each customer based on their unique IDs.
• The getAverageTime function computes an average based on all completed trips between two specific stations.
• For instance, tracking two trips between "Leyton" to "Waterloo", and deriving average trip time illustrates the direct relationship and required historical aggregation.

Example 2 Details:

• This example emphasizes situations with sequentially processed check-ins and check-outs and how each trip affects the overall average time between two specified stations.
• It shows the system handling a series of transactions, adjusting the average as each new trip data becomes available.

From these examples and following the constraints given including the limits on IDs, timings, string lengths, total operational calls, and accuracy requirements, the system needs an efficiently managed data logging and retrieval mechanism. Handling data using hashing (like dictionaries in Python) offers a quick and efficient way of keeping track and calculating averages:

1. Mapping of customer ID to (check-in station, check-in time) ensures quick look-up during check-out to calculate travel time.
2. Using a composite key (startStation, endStation) to map to (total travel time, trip count) allows for immediate access and update when calculating averages, providing efficient average calculations for getAverageTime.

This approach not only ensures data consistency but also facilitates quick computations necessary for a responsive transit system backend, supporting both real-time user interactions and data integrity for trip analytics.

Solutions

class TransitSystem {
    private Map<String, Pair<Double, Double>> travelDetails = new HashMap<>();
    private Map<Integer, Pair<String, Integer>> entryDetails = new HashMap<>();
    
    public TransitSystem() {
    }
    
    public void enterStation(int id, String stationName, int t) {
        entryDetails.put(id, new Pair<>(stationName, t));
    }
    
    public void exitStation(int id, String stationName, int t) {
        Pair<String, Integer> entryData = entryDetails.get(id);
        String entryStation = entryData.getKey();
        Integer entryTime = entryData.getValue();
        
        String route = createRouteKey(entryStation, stationName);
        Pair<Double, Double> routeInfo = travelDetails.getOrDefault(route, new Pair<>(0.0, 0.0));
        Double totalDuration = routeInfo.getKey();
        Double totalJourneys = routeInfo.getValue();
        
        double travelDuration = t - entryTime;
        travelDetails.put(route, new Pair<>(totalDuration + travelDuration, totalJourneys + 1));
        
        entryDetails.remove(id);
    }
    
    public double computeAverageTime(String startStation, String finishStation) {
        String route = createRouteKey(startStation, finishStation);
        Double totalTravelTime = travelDetails.get(route).getKey();
        Double countJourneys = travelDetails.get(route).getValue();
        return totalTravelTime / countJourneys;
    }
    
    private String createRouteKey(String startStation, String finishStation) {
        return startStation + "->" + finishStation;
    }
}