1396. Design Underground System

Description

Implement the UndergroundSystem class:

• void checkIn(int id, string stationName, int t)

  • A customer with a card id equal to id, gets in the station stationName at time t.

  • A customer can only be checked into one place at a time.

• void checkOut(int id, string stationName, int t)

  • A customer with a card id equal to id, gets out from the station stationName at time t.

• double getAverageTime(string startStation, string endStation)

  • Returns the average time to travel between the startStation and the endStation.

  • The average time is computed from all the previous traveling from startStation to endStation that happened directly.

  • Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. If a customer gets in at time t1 at some station, they get out at time t2 with t2 > t1. All events happen in chronological order.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

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);

undergroundSystem.checkOut(27, "Waterloo", 20);

undergroundSystem.checkOut(32, "Cambridge", 22);

undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)

undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.00000

undergroundSystem.checkIn(10, "Leyton", 24);

undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000

undergroundSystem.checkOut(10, "Waterloo", 38);

undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 12.00000

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);

undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000

undergroundSystem.checkIn(5, "Leyton", 10);

undergroundSystem.checkOut(5, "Paradise", 16);

undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000

undergroundSystem.checkIn(2, "Leyton", 21);

undergroundSystem.checkOut(2, "Paradise", 30);

undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class UndergroundSystem {
    private Map<String, Pair<Double, Double>> journeyData = new HashMap<>();
    private Map<Integer, Pair<String, Integer>> checkInData = new HashMap<>();
    
    public UndergroundSystem() {
    }
    
    public void checkIn(int id, String stationName, int t) {
        checkInData.put(id, new Pair<>(stationName, t));
    }
    
    public void checkOut(int id, String stationName, int t) {
        // Look up the check in station and check in time for this id.
        // You could combine this "unpacking" into the other lines of code
        // to have less lines of code overall, but we've chosen to be verbose
        // here to make it easy for all learners to follow.
        Pair<String, Integer> checkInDataForId = checkInData.get(id);
        String startStation = checkInDataForId.getKey();
        Integer checkInTime = checkInDataForId.getValue();
        
        // Lookup the current travel time data for this route.
        String routeKey = stationsKey(startStation, stationName);
        Pair<Double, Double> routeStats  = journeyData.getOrDefault(routeKey, new Pair<>(0.0, 0.0));
        Double totalTripTime = routeStats.getKey();
        Double totalTrips = routeStats.getValue();
        
        // Update the travel time data with this trip.
        double tripTime = t - checkInTime;
        journeyData.put(routeKey, new Pair<>(totalTripTime + tripTime, totalTrips + 1));
        
        // Remove check in data for this id.
        // Note that this is optional, we'll talk about it in the space complexity analysis.
        checkInData.remove(id);
    }
    
    public double getAverageTime(String startStation, String endStation) {
        // Lookup how many times this journey has been made, and the total time.
        String routeKey = stationsKey(startStation, endStation);
        Double totalTime = journeyData.get(routeKey).getKey();
        Double totalTrips = journeyData.get(routeKey).getValue();
        // The average is simply the total divided by the number of trips.
        return totalTime / totalTrips;
    }
    
    private String stationsKey(String startStation, String endStation) {
        return startStation + "->" + endStation;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class UndergroundSystem {
    
    private class Trip {
        int checkinTime;
        int checkoutTime;
        String checkinStation;
        String checkoutStation;
        
        Trip(int checkinTime, String checkinStation) {
            this.checkinTime = checkinTime;
            this.checkinStation = checkinStation;
        }
        
        void checkout(int time, String station) {
            this.checkoutTime = time;
            this.checkoutStation = station;
        }
    }
    
    private class Route {
        String checkinStation;
        String checkoutStation;
        int totalNoOfTrips;
        int totalTimeSpentInTrips;
        
        Route(String checkinStation, String checkoutStation) {
            this.checkinStation = checkinStation;
            this.checkoutStation = checkoutStation;
            totalNoOfTrips = 0;
            totalTimeSpentInTrips = 0;
        }
        
        void addTripTime(int checkinTime, int checkoutTime) {
            totalTimeSpentInTrips += (checkoutTime-checkinTime);
            totalNoOfTrips++;
        }
        
        double getAverageTime() {
            return (double) totalTimeSpentInTrips/totalNoOfTrips;
        }
    }
    
    private Map<Integer, Trip> tripMap;
    private Map<String, Route> routeMap;

    public UndergroundSystem() {
        this.tripMap = new HashMap();
        this.routeMap = new HashMap();
    }
    
    public void checkIn(int id, String stationName, int t) {
        if(!tripMap.containsKey(id)) {
            Trip trip = new Trip(t, stationName);
            tripMap.put(id, trip);
        }
    }
    
    public void checkOut(int id, String stationName, int t) {
        if(tripMap.containsKey(id)) {
            Trip trip = tripMap.get(id);
            trip.checkout(t, stationName);
            String routeKey = trip.checkinStation + "-" + trip.checkoutStation;
            Route route = routeMap.getOrDefault(routeKey, new Route(trip.checkinStation, trip.checkoutStation));
            route.addTripTime(trip.checkinTime, trip.checkoutTime);
            routeMap.put(routeKey, route);
            tripMap.remove(id);
        }
    }
    
    public double getAverageTime(String startStation, String endStation) {
        return routeMap.get(startStation + "-" +  endStation).getAverageTime();
    }
}

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem obj = new UndergroundSystem();
 * obj.checkIn(id,stationName,t);
 * obj.checkOut(id,stationName,t);
 * double param_3 = obj.getAverageTime(startStation,endStation);
 */

Follow up