Design Underground System

Problem Statement:-

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

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

  • A customer with a card ID equal to id, checks in at 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, checks out from the station stationName at time t.

• double getAverageTime(string startStation, string endStation)

  • Returns the average time it takes to travel from startStation to endStation.

  • The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.

  • The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.

  • There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.

You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t<sub>1</sub> then checks out at time t<sub>2</sub>, then t<sub>1</sub> < t<sub>2</sub>. All events happen in chronological order.

Link: https://leetcode.com/problems/design-underground-system/description/

Problem Explanation with 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 <= 10<sup>6</sup>

• 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 * 10<sup>4</sup> calls in total to checkIn, checkOut, and getAverageTime.

• Answers within 10<sup>-5</sup> of the actual value will be accepted.

Intuition:-

• Have a passenger and route encapsulation with the required data.

• For route, we also need methods to update the average and get the average.

• Keep a dictionary of passengers and routes and update the passengers dictionary when they check in and check out.

• When they check out, get the difference between the check in time and check out time and update the route average.

• Return the average when asked for it.

Solution:-

• Create a passenger class with id, stationName and time and a constructor to initialize them.

• Create a route class with total(total time) and count(number of passengers) and a constructor to initialize them. Also, create a method to update the total and count and a method to get the average.

• Create a dictionary of passengers and routes and initialize it in the constructor.

• When a passenger checks in, add the passenger to the dictionary with the id as the key and the passenger object as the value.

• When a passenger checks out, get the passenger object from the dictionary using the id and delete the entry from the dictionary. Get the difference between the check in time and check out time and update the route average. If the route is not in the dictionary, create a new route object and add it to the dictionary. If the route is already in the dictionary, update the route average.

• When asked for the average, get the route object from the dictionary and return the average.

Code:-

JAVA Solution

class UndergroundSystem {

    class passenger{
        public int id;
        public String stationName;
        public int time;

        public passenger(int id, String stationName, int time){
            this.id = id;
            this.stationName = stationName;
            this.time = time;
        }
    }

    class route{
        public double total = 0;
        public int count = 0;

        public void update(int difference){
            count++;
            total += difference;
        }
        public double getAvg(){
            return total / count;
        }
    }

    public Map<Integer, passenger> passengersArrivals;
    public Map<String, route> routeAverage;

    public UndergroundSystem() {
        passengersArrivals = new HashMap<>();
        routeAverage = new HashMap<>();
    }

    public void checkIn(int id, String stationName, int t) {
        passengersArrivals.put(id, new passenger(id, stationName, t));
    }

    public final String DELIMETER = ",";

    public void checkOut(int id, String stationName, int t) {
        passenger arrivePassenger = passengersArrivals.get(id);
        passengersArrivals.remove(id);

        int difference = t - arrivePassenger.time;
        String key = arrivePassenger.stationName + DELIMETER + stationName;

        route average = routeAverage.containsKey(key) ? routeAverage.get(key) : new route();
        average.update(difference);

        routeAverage.put(key, average);
    }

    public double getAverageTime(String startStation, String endStation) {
        String key = startStation + DELIMETER + endStation;
        return routeAverage.get(key).getAvg();
    }
}

Python Solution

class UndergroundSystem:
    class Passenger:
        def __init__(self, id, stationName, time):
            self.id = id
            self.stationName = stationName
            self.time = time

    class Route:
        def __init__(self):
            self.total = 0
            self.count = 0

        def update(self, difference):
            self.count += 1
            self.total += difference

        def getAvg(self):
            return self.total / self.count

    def __init__(self):
        self.passengersArrivals = {}
        self.routeAverage = {}        

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

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        arrivePassenger = self.passengersArrivals[id]
        del self.passengersArrivals[id]

        difference = t - arrivePassenger.time
        key = arrivePassenger.stationName + ',' + stationName

        average = self.routeAverage.get(key, self.Route())
        average.update(difference)

        self.routeAverage[key] = average       

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        key = startStation + ',' + endStation
        return self.routeAverage[key].getAvg()

Complexity Analysis:-

TIME:-

1. check-in: O(1) as we are just adding the passenger to the dictionary.

2. checkOut: O(1) as we are just getting the passenger from the dictionary and updating the route average.

3. getAverageTime: O(1) as we are just getting the route object from the dictionary and returning the average.

SPACE:-

The space complexity is O(P + R) where P is the number of passengers and R is the number of routes. We are storing the passengers and routes in the dictionary.

References:-

• Dictionary

Connect with me:-

• Twitter

• Github

• LinkedIn