Formatted question description: https://leetcode.ca/all/1396.html

1396. Design Underground System

Level

Medium

Description

Implement the class UndergroundSystem that supports three methods:

  1. checkIn(int id, string stationName, int t)
    • A customer with id card equal to id, gets in the station stationName at time t.
    • A customer can only be checked into one place at a time.
  2. checkOut(int id, string stationName, int t)
    • A customer with id card equal to id, gets out from the station stationName at time t.
  3. 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. That is, if a customer gets in at time t1 at some station, then it gets out at time t2 with t2 > t1. All events happen in chronological order.

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.0,11.0,null,11.0,null,12.0]

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.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0. 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.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.0

Constraints:

  • There will be at most 20000 operations.
  • 1 <= id, t <= 10^6
  • All strings consist of uppercase, lowercase English letters and digits.
  • 1 <= stationName.length <= 10
  • Answers within 10^-5 of the actual value will be accepted as correct.

Solution

Use two maps to store each customer’s trip and each trip’s list of time.

For the constructor, initialize the two maps.

For method checkIn, represent the trip as stationName, t and store the entry into the first map using id and the trip.

For method checkOut, first obtain the trip from the first map and obtain the start station and the start time, and then represent the complete trip as startStation, endStation where endStation is stationName in the method, and calculate the duration as the difference between the end time t and the start time. Then add the duration into the complete trip’s time list, store the complete trip and the duration list into the second map, and remove the id from the first map.

For method getAverageTime, use the start station and the end station to obtain the list of time, and calculate the average of all elements in the list.

class UndergroundSystem {
    Map<Integer, String> customerTripMap;
    Map<String, List<Integer>> tripsMap;

    public UndergroundSystem() {
        customerTripMap = new HashMap<Integer, String>();
        tripsMap = new HashMap<String, List<Integer>>();
    }
    
    public void checkIn(int id, String stationName, int t) {
        String value = stationName + ", " + t;
        customerTripMap.put(id, value);
    }
    
    public void checkOut(int id, String stationName, int t) {
        String prevValue = customerTripMap.get(id);
        String[] array = prevValue.split(", ");
        String startStation = array[0];
        int startTime = Integer.parseInt(array[1]);
        String trip = startStation + ", " + stationName;
        int duration = t - startTime;
        List<Integer> list = tripsMap.getOrDefault(trip, new ArrayList<Integer>());
        list.add(duration);
        tripsMap.put(trip, list);
        customerTripMap.remove(id);
    }
    
    public double getAverageTime(String startStation, String endStation) {
        String trip = startStation + ", " + endStation;
        List<Integer> list = tripsMap.getOrDefault(trip, new ArrayList<Integer>());
        if (list.size() == 0)
            return 0;
        int size = list.size();
        double sum = 0;
        for (int time : list)
            sum += time;
        return sum / size;
    }
}

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

All Problems

All Solutions