Welcome to Subscribe On Youtube

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; // each customer’s trip
    Map<String, List<Integer>> tripsMap; // each trip’s list of time

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

############

class UndergroundSystem {
    private Map<Integer, String> checkInStation;
    private Map<Integer, Integer> checkInTime;
    private Map<String, int[]> totalTime;

    public UndergroundSystem() {
        checkInStation = new HashMap<>();
        checkInTime = new HashMap<>();
        totalTime = new HashMap<>();
    }

    public void checkIn(int id, String stationName, int t) {
        checkInStation.put(id, stationName);
        checkInTime.put(id, t);
    }

    public void checkOut(int id, String stationName, int t) {
        int cost = t - checkInTime.remove(id);
        String startStation = checkInStation.remove(id);
        String stations = startStation + "." + stationName;
        int[] times = totalTime.getOrDefault(stations, new int[2]);
        times[0] += cost;
        ++times[1];
        totalTime.put(stations, times);
    }

    public double getAverageTime(String startStation, String endStation) {
        String stations = startStation + "." + endStation;
        int[] times = totalTime.get(stations);
        return times[0] * 1.0 / times[1];
    }
}

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

  • // OJ: https://leetcode.com/problems/design-underground-system/
// Time: O(1) for all
// Space: O(N)
class UndergroundSystem {
    unordered_map<string, unordered_map<string, pair<int, int>>> m; // fromStation -> { toStation -> { sum of time used, count } }
    unordered_map<int, pair<string, int>> checkInMap; // id -> { fromStation, checkInTime }
public:
    UndergroundSystem() {
    }
    void checkIn(int id, string stationName, int t) {
        checkInMap[id] = {stationName, t};
    }
    void checkOut(int id, string stationName, int t) {
        auto [from, startTime] = checkInMap[id];
        checkInMap.erase(id);
        auto &item = m[from][stationName];
        item.first += t - startTime;
        item.second++;
    }
    double getAverageTime(string startStation, string endStation) {
        auto &item = m[startStation][endStation];
        return (double)item.first / item.second;
    }
};

  • class UndergroundSystem:
    def __init__(self):
        self.check_in_station = {}
        self.check_in_time = {}
        self.total_time = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_in_station[id] = stationName
        self.check_in_time[id] = t

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        cost = t - self.check_in_time.pop(id)
        start_station = self.check_in_station.pop(id)
        stations = start_station + '.' + stationName
        times = self.total_time.get(stations, [0, 0])
        times[0] += cost
        times[1] += 1
        self.total_time[stations] = times

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        stations = startStation + '.' + endStation
        times = self.total_time[stations]
        return times[0] / times[1]


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



  • type UndergroundSystem struct {
	ts map[int]pair
	d  map[station][2]int
}

func Constructor() UndergroundSystem {
	return UndergroundSystem{
		ts: make(map[int]pair),
		d:  make(map[station][2]int),
	}
}

func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) {
	this.ts[id] = pair{t, stationName}
}

func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) {
	p := this.ts[id]
	s := station{p.a, stationName}
	if _, ok := this.d[s]; !ok {
		this.d[s] = [2]int{t - p.t, 1}
	} else {
		this.d[s] = [2]int{this.d[s][0] + t - p.t, this.d[s][1] + 1}
	}

}

func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
	s := station{startStation, endStation}
	return float64(this.d[s][0]) / float64(this.d[s][1])
}

type station struct {
	a string
	b string
}

type pair struct {
	t int
	a string
}

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * obj := Constructor();
 * obj.CheckIn(id,stationName,t);
 * obj.CheckOut(id,stationName,t);
 * param_3 := obj.GetAverageTime(startStation,endStation);
 */

All Problems

All Solutions