Start learning free

LESSON 328 OF 569 · HASH TABLE

Design Underground System in JavaScript: Maps with O(1) Averages

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 10
    Ctrl + Enter to check

    JAVASCRIPT · HASH TABLE

    Design Underground System in JavaScript, explained

    Problem overview

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

    Only finished trips count, and the direction matters: a trip from B to A belongs to a different route from A to B. The tests print each average with exactly two decimals, so a value of 2.5 appears as 2.50.

    Take the first example. Card 45 goes from Leyton to Waterloo from time 3 to 15 (12), card 27 on the same route from 10 to 20 (10), and card 32 from Paradise to Cambridge from 8 to 22 (14). Then getAverageTime("Paradise", "Cambridge") is 14 and getAverageTime("Leyton", "Waterloo") is (12 + 10) / 2 = 11. Card 10 then checks in at Leyton but has not checked out, so its trip is not counted and the average stays 11. The three answers, printed to two decimals:

    14.00 11.00
11.00

    Approach: two maps and a running total per route

    The obvious design stores every finished trip in a list and, on each getAverageTime, walks through the list, picks the trips on that route and averages them. That is O(n) per question, where n is the number of trips so far.

    An average is a total divided by a count, so it is enough to keep those two numbers for each route and update them whenever a trip ends. The class keeps two maps:

    • this.checkIns: the trips in progress. For each card id, the pair [stationName, t] where its passenger checked in. An entry is needed only until the same card checks out.
    • this.routes: the finished trips, per route. The key is the route as one string, "start,end", and the value is the pair [total time, number of trips].

    Now checkIn is one map write. checkOut reads and deletes the card's check-in, builds the route key, and adds the trip's time to the route's total and one to its count. getAverageTime is one lookup and one division. The only work that depends on anything but the number of operations is building the route string from the two station names, which is short.

    After the first example, the maps hold:

    routes:   Leyton,Waterloo => [22, 2]    Paradise,Cambridge => [14, 1]
checkIns: 10 => ["Leyton", 24]

    The route "Leyton,Waterloo" has total 22 over 2 trips, so its average is 11. Card 10's open trip sits in checkIns and has not touched routes.

    Step by step

    1. Constructor, first map: set this.checkIns to a new empty Map for the trips in progress.
    2. Constructor, second map: set this.routes to a new empty Map for the finished trips. The pair stored per route lets getAverageTime avoid walking through every trip.
    3. checkIn: store [stationName, t] under the key id in this.checkIns. The trip's time is not known until check-out, so that is all it does.
    4. checkOut: read the passenger's check-in and unpack it with let [startStation, startTime] = this.checkIns.get(id).
    5. Delete id from this.checkIns. The trip is over, and the same card can check in again later.
    6. Build the route's name: startStation + "," + stationName. The order matters, since A to B and B to A are different routes. The comma keeps names apart: without it, "A" and "BC" would give the same route as "AB" and "C".
    7. Unpack the route's current pair into total and count, with this.routes.get(route) || [0, 0]. For a route with no finished trip yet, get returns undefined and || picks [0, 0].
    8. Set the route to a new pair: [total + t - startTime, count + 1]. Only these two numbers change, so a check-out is O(1) however many trips came before.
    9. getAverageTime: unpack the pair stored for startStation + "," + endStation, building the name exactly as checkOut does.
    10. Return total / count. The statement promises the route has at least one finished trip.

    The solution in JavaScript

    class UndergroundSystem {
    constructor() {
        this.checkIns = new Map();
        this.routes = new Map();
    }

    checkIn(id, stationName, t) {
        this.checkIns.set(id, [stationName, t]);
    }

    checkOut(id, stationName, t) {
        let [startStation, startTime] = this.checkIns.get(id);
        this.checkIns.delete(id);
        let route = startStation + "," + stationName;
        let [total, count] = this.routes.get(route) || [0, 0];
        this.routes.set(route, [total + t - startTime, count + 1]);
    }

    getAverageTime(startStation, endStation) {
        let [total, count] = this.routes.get(startStation + "," + endStation);
        return total / count;
    }
}

    JavaScript details:

    • Division keeps the fraction. (5 + 6) / 2 is 5.5, with no integer truncation. The method returns a number such as 2.5; the two decimals (2.50) come from the way the result is printed, for example with toFixed(2).
    • Destructuring. let [a, b] = pair unpacks an array into variables, in order. It throws a TypeError if the right side is undefined. That is why checkOut uses || [0, 0], and why getAverageTime relies on the promise that the route exists: for a route with no finished trip, it would throw.
    • String keys. A route is a string such as "A,B", because a Map compares array keys by identity: a new array ["A", "B"] would never find an earlier one.

    Complexity

    Time: checkIn, checkOut and getAverageTime are each O(1), apart from building the route string, which depends only on the length of the two station names (at most 10 characters each). They are map reads and writes and a little arithmetic.

    Space: O(C + R), where C is the number of cards currently checked in and R the number of different routes. Finished trips are not stored one by one, only their total and count, so space does not grow with the number of trips.

    Edge cases and common mistakes

    • Direction. After the third example's trips, route "A,B" holds [5, 2] (trips of 3 and 2) and route "B,A" holds [7, 1]. getAverageTime("A", "B") returns 2.5 and getAverageTime("B", "A") returns 7, printed as 2.50 7.00.
    • Unfinished trips. A card that checked in but not out is only in checkIns, so it does not affect any average.
    • One card, many trips. In the second example card 10 travels twice, and the deletion in checkOut frees it to check in again. The four trips from Leyton to Paradise take 5, 6, 9 and 5, and the averages after one, two and four trips are 5.00, 5.50 and 6.25.
    • Forgetting the delete. Without it the map keeps stale check-ins forever. A later check-in overwrites it, so the answers stay right, but the map grows with the number of cards.
    • Averaging averages. Do not store the current average and update it with the new time: keep the total and the count and divide only when asked.
    • A route key without a separator. With plain "A" + "BC" and "AB" + "C" both producing "ABC" (true in JavaScript), two different routes would share one entry. With the comma, "A,BC" and "AB,C" differ.

    Testing

    Outputs of the solution above, printed with toFixed(2):

    • Example 1 prints 14.00 11.00 and then 11.00.
    • Example 2 prints 5.00, 5.50 and 6.25.
    • Example 3 prints 2.50 7.00.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free