Start learning free

LESSON 328 OF 569 · HASH TABLE

Design Underground System in Java: Route Totals in a HashMap

Practice O(1) Read the full explanation

An underground railway wants to know how long its passengers travel between stations. Each passenger has a card with an id: they check in with it at the station where they start, and check out at the station where they leave. Design a system that records these trips and tells, for any two stations, the average time of the trips made so far from the first to the second.

Implement the class UndergroundSystem:

  • UndergroundSystem() creates an empty system.
  • checkIn(id, stationName, t): the passenger with the card id checks in at the station stationName at the time t. A passenger can be checked in at only one place at a time.
  • checkOut(id, stationName, t): the passenger with the card id checks out at the station stationName at the time t. This ends their trip: it went from the station where they checked in to stationName, and took t minus their check-in time.
  • getAverageTime(startStation, endStation) returns the average time of all the trips so far that went from startStation to endStation. Only finished trips count, and the direction matters: a trip from endStation to startStation belongs to a different route.

The input is a list of operations, applied in order to one new UndergroundSystem. The output lists what the getAverageTime calls return, in order, each with exactly two decimals. The starter code spells these names the way your language does.

 

Example 1:

Input:
    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")
Output: 14.00 11.00 11.00
Explanation:
Card 45 travels from Leyton to Waterloo in 15 - 3 = 12, card 27 on the same route in 20 - 10 = 10,
and card 32 from Paradise to Cambridge in 22 - 8 = 14.
The only trip from Paradise to Cambridge took 14. The two trips from Leyton to Waterloo average (12 + 10) / 2 = 11.
Card 10 has checked in at Leyton but not checked out yet: its trip doesn't count, and the average stays 11.

Example 2:

Input:
    checkIn(10, "Leyton", 3)
    checkOut(10, "Paradise", 8)
    getAverageTime("Leyton", "Paradise")
    checkIn(5, "Leyton", 10)
    checkOut(5, "Paradise", 16)
    getAverageTime("Leyton", "Paradise")
    checkIn(2, "Leyton", 21)
    checkOut(2, "Paradise", 30)
    checkIn(10, "Leyton", 32)
    checkOut(10, "Paradise", 37)
    getAverageTime("Leyton", "Paradise")
Output: 5.00 5.50 6.25
Explanation:
The trips from Leyton to Paradise take 5, 6, 9 and 5. After the first trip the average is 5, after two trips
(5 + 6) / 2 = 5.5, and after all four (5 + 6 + 9 + 5) / 4 = 6.25. Card 10 travels twice: each trip counts.

Example 3:

Input:
    checkIn(1, "A", 1)
    checkOut(1, "B", 4)
    checkIn(2, "B", 5)
    checkOut(2, "A", 12)
    checkIn(3, "A", 13)
    checkOut(3, "B", 15)
    getAverageTime("A", "B")
    getAverageTime("B", "A")
Output: 2.50 7.00
Explanation: The trips from A to B take 3 and 2, so their average is 2.5. The trip from B to A goes the other way: it belongs to its own route, with an average of 7.

 

Constraints:

  • 1 <= id, t <= 106
  • 1 <= stationName.length, startStation.length, endStation.length <= 10
  • Station names consist of uppercase and lowercase English letters and digits.
  • The calls come in time order: t never goes down from one call to the next, and every trip checks out later than it checked in, at a different station.
  • A passenger checks in only when they are not checked in already, and checks out only after checking in.
  • getAverageTime is only called for two stations with at least one finished trip between them.
  • All the trips together take at most 109, so every total fits in a 32-bit integer.
  • Every average in the tests has at most two decimals, so printing it with two decimals needs no rounding.
  • At most 105 calls in total are made to checkIn, checkOut and getAverageTime.

Note:

Each operation should run in O(1) time, apart from building the route's name from the two station names. Going through all the finished trips in getAverageTime would take O(n) time per call, where n is the number of trips so far.

STEP 1 OF 9
    Ctrl + Enter to check

    JAVA · HASH TABLE

    Design Underground System in Java, explained

    Problem overview

    An underground railway records how long passengers travel and wants the average time between any two stations. The class UndergroundSystem has three methods. checkIn(int id, String stationName, int t) records that the card id entered a station at time t. checkOut(int id, String stationName, int t) ends that passenger's trip at another station. getAverageTime(String startStation, String endStation) returns, as a double, the average time of all finished trips from the first station to the second.

    Two rules shape the design. Only finished trips count, so a passenger who has checked in but not out yet does not change any average. And direction matters: a trip from B to A is a different route from A to B. The tests print each average with exactly two decimals.

    Take three passengers. Card 45 goes from Leyton to Waterloo in 15 - 3 = 12, card 27 on the same route in 20 - 10 = 10, and card 32 from Paradise to Cambridge in 22 - 8 = 14.

    UndergroundSystem us = new UndergroundSystem();
us.checkIn(45, "Leyton", 3);
us.checkIn(32, "Paradise", 8);
us.checkIn(27, "Leyton", 10);
us.checkOut(45, "Waterloo", 15);
us.checkOut(27, "Waterloo", 20);
us.checkOut(32, "Cambridge", 22);
System.out.println(String.format("%.2f", us.getAverageTime("Paradise", "Cambridge")));
System.out.println(String.format("%.2f", us.getAverageTime("Leyton", "Waterloo")));
us.checkIn(10, "Leyton", 24);
System.out.println(String.format("%.2f", us.getAverageTime("Leyton", "Waterloo")));

    14.00
11.00
11.00

    The last average stays 11.00, because card 10 has checked in at Leyton but has not checked out.

    Approach: keep a total and a count per route

    The simple approach stores every finished trip in a list as (start, end, duration). Then getAverageTime walks the whole list, picks the trips on the route, adds their times and divides. That costs O(n) per question, where n is the number of trips so far, and the tests may ask many questions after many trips.

    An average needs only two numbers: the total time and the number of trips. A new trip changes both by a known amount, so there is no need to remember the individual trips. For each route the system keeps a pair (total time, number of trips). A check-out adds the trip's time to the total and one to the count, which is O(1). A question reads the pair and divides, which is also O(1).

    The second thing to store is the trips in progress. When a passenger checks out, the system needs to know where and when that card checked in, so a second map goes from the card id to the pair (station, time). Checking out removes that entry, which means the same card can check in again later. This matters: in the tests a card may travel more than once, and each trip counts.

    The route needs a key for the map. The lesson joins the two station names with a comma, as in "Leyton,Waterloo". The order is part of the key, so the opposite direction gets its own entry. The comma keeps names apart: without it, the stations "A" and "BC" would give the same key as "AB" and "C".

    Step by step

    1. Declare checkIns, a Map<Integer, Map.Entry<String, Integer>>: the trips in progress, from card id to (station, time). Map.Entry is Java's ready-made pair, made with Map.entry(a, b) and read with getKey() and getValue().
    2. Declare routes, a Map<String, int[]>: for each route, an array of two ints, the total at index 0 and the count at index 1.
    3. checkIn: put Map.entry(stationName, t) in checkIns under id. The duration is unknown until check-out, so nothing more is needed.
    4. checkOut: call checkIns.remove(id). It deletes the entry and returns what was stored, which goes in start.
    5. Build the route name: the start station start.getKey(), a comma, and stationName.
    6. Read the route's pair with getOrDefault(route, new int[] {0, 0}). A route with no finished trip starts from a total of 0 and a count of 0.
    7. Put a new pair under the route: the old total plus this trip's time t - start.getValue(), and the old count plus 1.
    8. getAverageTime: read the pair stored under startStation + "," + endStation, built exactly as in checkOut.
    9. Return the total divided by the count, with (double) before stats[0].

    The solution in Java

    class UndergroundSystem {
    Map<Integer, Map.Entry<String, Integer>> checkIns = new HashMap<>();
    Map<String, int[]> routes = new HashMap<>();

    public void checkIn(int id, String stationName, int t) {
        checkIns.put(id, Map.entry(stationName, t));
    }

    public void checkOut(int id, String stationName, int t) {
        Map.Entry<String, Integer> start = checkIns.remove(id);
        String route = start.getKey() + "," + stationName;
        int[] stats = routes.getOrDefault(route, new int[] {0, 0});
        routes.put(route, new int[] {stats[0] + t - start.getValue(), stats[1] + 1});
    }

    public double getAverageTime(String startStation, String endStation) {
        int[] stats = routes.get(startStation + "," + endStation);
        return (double) stats[0] / stats[1];
    }
}

    A few details about the Java code:

    • The cast. Dividing two int values in Java drops the fraction: 11 / 2 is 5. Writing (double) stats[0] / stats[1] converts the total first, so the division is a double division and gives 5.5. The cast applies to stats[0] only, which is enough.
    • The printed form. The method returns a double, and printing one directly shows 14.0, not 14.00. The tests format the result with two decimals, which you can do yourself with String.format("%.2f", value).
    • remove returns the value. Map.remove(key) returns the removed value, or null if the key was absent. The constraints say a passenger checks out only after checking in, so start is never null.
    • Replacing the array. The code creates a new int[] for each check-out and puts it back. Changing stats in place would also work for an existing route, but the default array from getOrDefault is not in the map, so creating a new pair covers both cases with one line.
    • Unboxing. start.getValue() is an Integer, and t - start.getValue() unboxes it to an int.

    Seeing it work

    The state after the first run above shows what is kept. The map routes holds two routes, Paradise,Cambridge and Leyton,Waterloo, and the pair stored for Leyton,Waterloo is [22, 2]: the total of 12 and 10, over two trips. The map checkIns holds one entry, card 10, still in progress. The average is 22 divided by 2.

    The division itself:

    int total = 11, count = 2;
System.out.println(total / count);
System.out.println((double) total / count);

    5
5.5

    The average also moves as trips arrive. Four trips on one route that take 2, 6, 9 and 5 give, after each trip, the averages below, each formatted with two decimals.

    UndergroundSystem u2 = new UndergroundSystem();
int[][] trips = {{3, 5}, {10, 16}, {21, 30}, {32, 37}};
for (int i = 0; i < trips.length; i++) {
    u2.checkIn(i, "Leyton", trips[i][0]);
    u2.checkOut(i, "Paradise", trips[i][1]);
    System.out.print(String.format("%.2f ", u2.getAverageTime("Leyton", "Paradise")));
}

    2.00 4.00 5.67 5.50

    The third value is 17 divided by 3, which is not a two-decimal number: %.2f rounds it to 5.67. The lesson's tests only ask for averages with at most two decimals.

    Direction is its own route. With two trips from A to B that take 3 and 2, and one trip from B to A that takes 7:

    UndergroundSystem u3 = new UndergroundSystem();
u3.checkIn(1, "A", 1);  u3.checkOut(1, "B", 4);
u3.checkIn(2, "B", 5);  u3.checkOut(2, "A", 12);
u3.checkIn(3, "A", 13); u3.checkOut(3, "B", 15);
System.out.println(String.format("%.2f %.2f", u3.getAverageTime("A", "B"), u3.getAverageTime("B", "A")));

    2.50 7.00

    The first value is the average on A to B, (3 + 2) / 2, and the second is the single trip from B to A. In the first loop above, the trips take 2, 6, 9 and 5 time units.

    Complexity

    Time: O(1) for each operation, apart from building the route string, which takes time proportional to the length of the two station names (at most 10 characters each). The hash-map lookups and updates take O(1) on average. Looking through all finished trips in getAverageTime would take O(n).

    Space: O(P + R), where P is the number of passengers currently checked in and R is the number of distinct routes used. Finished trips are not stored, only their total and count per route.

    Edge cases and common mistakes

    • Integer division. Without the cast, 11 / 2 gives 5. Always convert one operand to double before dividing.
    • Mixing up the direction. A trip from B to A must not change the A to B average. The route key keeps the order of the two stations.
    • Counting unfinished trips. A check-in alone adds nothing to routes. Only checkOut updates the totals.
    • Not removing the check-in. If checkOut read the entry with get instead of remove, the stale entry would linger. A later check-in by the same card would overwrite it, but memory would grow for cards that never return.
    • Building the key differently in two places. If checkOut and getAverageTime join the names differently, the lookup misses. Both use "first,second".
    • Overflow. The totals are ints, which wrap silently on overflow in Java. The constraints keep all the trips together below a billion, so they fit. A larger system would use long.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free