Design Underground System

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 t1 then checks out at time t2, then t1 < t2. All events happen in chronological order.

Example 1

Input: Operations in this order "checkIn" : [45,"Leyton",3] "checkIn" : [32,"Paradise",8] "checkIn" : [27,"Leyton",10] "checkOut" : [45,"Waterloo",15] "checkOut" : [27,"Waterloo",20] "checkOut" : [32,"Cambridge",22] "getAverageTime" : ["Paradise","Cambridge"] "getAverageTime" : ["Leyton","Waterloo"] "checkIn" : [10,"Leyton",24] "getAverageTime" : ["Leyton","Waterloo"] "checkOut" : [10,"Waterloo",38] "getAverageTime" : ["Leyton","Waterloo"] Output: Operation 1 "checkIn" : void Operation 2 "checkIn" : void Operation 3 "checkIn" : void Operation 4 "checkOut" : void Operation 5 "checkOut" : void Operation 6 "checkOut" : void Operation 7 "getAverageTime" : 14.00000 Operation 8 "getAverageTime" : 11.00000 Operation 9 "checkIn" : void Operation 10 "getAverageTime" : 11.00000 Operation 11 "checkOut" : void Operation 12 "getAverageTime" : 12.00000 Explanation: 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

Constraints:

1 <= id, t <= 10⁶
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⁴ calls in total to checkIn, checkOut, and getAverageTime.
Answers within 10^-5 of the actual value will be accepted.

Solution 1 - Store checkin and checkout time information into a HashMaps

Solution 1 - Store checkin and checkout time information into a HashMaps

In this approach, we will use two HashMap's to store checkin and checkout time information for calculating the average.

Implementation steps:

We will create two HashMap's, checkInMap to store checkin information, and totalTimeToCountMap to track total time took between stations, and the number of travels made between those stations, that reason we track this is to compute the average, average = total time / count .
Implementation steps for checkIn (id, stationName, t):
- In checkIn method, add this information into checkInMap, with id as key and (stationName, t) pair as value.
Implementation steps for checkOut (id, stationName, t):
- When a person is checked out, we will get their checkin information from checkInMap using the their id, and then get the total time it took from starting station to end station by taking the diff between t passed to checkOut method and the t stored in checkinMap. We then store information into totalTimeToCountMap with (startStation, endStation) pair as key and (total time it took to travel, number of travels made between these stations) pair as value.
Implementation steps for getAverageTime(String startStation, String endStation):
- We will get total time and count information from totalTimeToCountMap by passing (startStation, endStation) as key and simply compute total time it took to travel / number of travels made between these stations that is already stored as value in the map.

Java

import java.util.AbstractMap.SimpleEntry;
import java.util.HashMap;

public class UndergroundSystem {

    HashMap<Integer, SimpleEntry<String, Integer>> checkInMap = new HashMap<>(); // Id -> (stationName, t)
    HashMap<SimpleEntry<String, String>, int[]> totalTimeToCountMap = new HashMap<>(); //(startStation, endStation)
                                                                            // -> (totalTime, count)

    public UndergroundSystem() {}

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

    public void checkOut(int id, String stationName, int t) {
        SimpleEntry<String, Integer> checkInTime = checkInMap.get(id);
        SimpleEntry<String, String> startEndStationsKey = new SimpleEntry<>(checkInTime.getKey(), stationName);
        int[] timesCount = new int[]{t - checkInTime.getValue(), 1};
        totalTimeToCountMap.merge(startEndStationsKey, timesCount, (oldVal, newVal) -> {
            oldVal[0]+= newVal[0];
            oldVal[1]+= newVal[1];
            return oldVal;
        });
    }

    public double getAverageTime(String startStation, String endStation) {
        SimpleEntry<String, String> key = new SimpleEntry<>(startStation, endStation);
        int[] countTimes = totalTimeToCountMap.get(key);
        return (double)countTimes[0]/countTimes[1];
    }

    public static void main(String[] args) {

        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);
        System.out.println(undergroundSystem.getAverageTime("Paradise", "Cambridge"));
        System.out.println(undergroundSystem.getAverageTime("Leyton", "Waterloo"));
        undergroundSystem.checkIn(10, "Leyton", 24);
        System.out.println(undergroundSystem.getAverageTime("Leyton", "Waterloo"));
        undergroundSystem.checkOut(10, "Waterloo", 38);
        System.out.println(undergroundSystem.getAverageTime("Leyton", "Waterloo"));
    }
}

Complexity Analysis:

Time complexity: Above code runs in O(1) since we are using HashMaps and that returns in constant time.
Space complexity: O(n), since we are storing information into HashMap, where n is total number of unique travels made, that is between a (startStation, endStation).

Above implementations source code can be found at GitHub link for Java code

Example 1

Constraints:

Contents

Solution 1 - Store checkin and checkout time information into a HashMaps

Implementation steps:

Complexity Analysis: