Leetcode: Design Underground System

This question is asked extremely commonly at Bloomberg, in fact, among Leetcode Coders, it was asked 98 times in the last 6 months. That's crazy. Which is why this question is so important.

We want to implement an UndergroundSystem class with different methods, such as check in, check out, get the average time, and return the array with the chronological order. Here are the  methods:

1.

Check in: 

void checkIn(int id, string stationName, int t) A customer with card id gets the stationname at t, and a customer can only be checked in at one place at a time.

2.

Check out:

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. 

3.

double getAverageTime(string startStation, string endStation) 

This returns the average time to travel between the start station and the end station. This time is computed from all the previous travelling that happened directly, and the call should be always balid. Assume that all the events are in chronological order. And now, here are some 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

 

Constraints:

There will be at most 20000 operations.

1 <= id, t <= 106

All strings consist of uppercase and lowercase English letters, and digits.

1 <= stationName.length <= 10

Answers within 10-5 of the actual value will be accepted as correct.

Now, let's code the solution to this problem.

So first, we need to consider some issues to this problem.

1. You can't really store the data in volatile data memory. Use a database instead so that the data is readily available when queried. 

2. We need to use more than 1 computer especially if we are dealing with several thousand to several million trips a day. Then, dealing with concurrency issues would be more important than ever. 

I will describe a HashMap approach below. 

checkin() and checkout() take inputs but don't return anything. GetAverageTime() take input returns a value. 

GetAverageTime() returns the start station and the end station and returns the average trip time between these 2 stations, basically, we need to get all of the trip times, and I believe a Hashmap is an effective way to achieve this. 

We get trip times through checkin() and checkout() methods. We should use a hashmap to map the id of the checkin station and times. We can store the total distance and the total number of trips and average these 2 numbers out subsequently. 

class UndergroundSystem {

    //first for data to store the number of trips and total trips for each person id. 

    //second for data to store the id and the time 

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

        //put the starting time to the data associated with the person 

        checkInData.put(id, new Pair<>(stationName, t));

    }

    public void checkOut(int id, String stationName, int t) {

        //get the data for the check-in data

        Pair<String, Integer> checkInDataForId = checkInData.get(id);

        String startStation = checkInDataForId.getKey();

        Integer checkInTime = checkInDataForId.getValue();

        String routeKey = stationsKey(startStation, stationName);

        //find the statistics of the route from input to output

        Pair<Double, Double> routeStats = journeyData.getOrDefault(routeKey, new Pair<>(0.0, 0.0));

        //get the key of the trip time, and get the amount of time, and place this into the final map.

        Double totalTripTime = routeStats.getKey();

        Double totalTrips = routeStats.getValue();

        double tripTime = t - checkInTime;

        journeyData.put(routeKey, new Pair<>(totalTripTime + tripTime, totalTrips + 1));

        checkInData.remove(id);

    }

    public double getAverageTime(String startStation, String endStation) {

        //get the total time and number of trips, and then get the routemap data, divide total time by total laps. 

        String routeKey = stationsKey(startStation, endStation);

        Double totalTime = journeyData.get(routeKey).getKey();

        Double totalTrips = journeyData.get(routeKey).getValue();

        return totalTime / totalTrips;

    }

  private String stationsKey(String startStation, String endStation) {

//string up the station in a from-one-station to-another-station format

        return startStation + "->" + endStation;

   }

}

Hashmaps are useful for many classes.