Start learning free

LESSON 332 OF 573 · HASH TABLE

Design Underground System in TypeScript: Maps of Trips and Routes

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

    TYPESCRIPT · HASH TABLE

    Design Underground System in TypeScript, explained

    Problem overview

    An underground railway records trips. A passenger checks in with a card id at the station where they start and checks out at the station where they leave. The class UndergroundSystem must answer: for two stations, what is the average time of all finished trips from the first to the second? It has three methods:

    • checkIn(id, stationName, t): the card id checks in at stationName at time t. A card is checked in at only one place at a time.
    • checkOut(id, stationName, t): the card checks out, which ends its trip. The trip went from the check-in station to stationName and took t minus the check-in time.
    • getAverageTime(startStation, endStation): the average time of the finished trips from startStation to endStation. Unfinished trips don't count, and direction matters: a trip from B to A is a different route from A to B.

    Example: cards 45 and 27 travel from Leyton to Waterloo (check-ins at times 3 and 10, check-outs at 15 and 20), and card 32 travels from Paradise to Cambridge (8 to 22). The calls getAverageTime("Paradise", "Cambridge") and getAverageTime("Leyton", "Waterloo") return 14 and 11. After card 10 checks in at Leyton at time 24 without checking out, getAverageTime("Leyton", "Waterloo") still returns 11, because that trip isn't finished.

    Approach: keep a total and a count per route

    The simple approach stores every finished trip and, on each getAverageTime, walks through all of them, keeping those on the route and averaging their times. That costs O(n) per call for n trips so far.

    An average needs only two numbers: the sum of the times and the number of trips. Both can be updated at each check-out, so there is no need to remember the individual trips. The class keeps two maps:

    • checkIns: for each card id, the pair [station, time] of its trip in progress.
    • routes: for each route, written as the string "start,end", the pair [total time, number of trips].

    The route key joins the two station names with a comma. Without a separator, different pairs of stations could give the same key: "A" + "BC" and "AB" + "C" are both "ABC", whereas with the comma they are "A,BC" and "AB,C". Station names consist of letters and digits only, so a comma never appears in a name.

    With these maps, checkIn is one set, checkOut is a few lookups and one set, and getAverageTime is one lookup and one division. All are O(1) apart from building the route string, which depends on the length of the station names.

    Step by step

    1. Declare checkIns as a Map<number, [string, number]>, set to a new empty Map. The tuple type [string, number] is an array of exactly two items, a station and a time.
    2. Declare routes as a Map<string, [number, number]>, also empty: the total time and the trip count per route.
    3. checkIn: set the key id to [stationName, t]. The trip's duration is unknown until check-out.
    4. checkOut, read the check-in: unpack this.checkIns.get(id) into startStation and startTime with let [startStation, startTime] = ....
    5. Delete the entry for id from checkIns. The trip is over, and the card can check in again later.
    6. Build the route name: startStation + "," + stationName.
    7. Read the route's totals: this.routes.get(route) || [0, 0], unpacked into total and count. get returns undefined for a route that has no finished trip yet, and || then takes [0, 0].
    8. The key line: set the route to [total + t - startTime, count + 1].
    9. getAverageTime: unpack the pair stored for startStation + "," + endStation, built exactly as in checkOut, into total and count.
    10. Return total / count. In TypeScript, / on numbers keeps the fraction, so (5 + 6) / 2 is 5.5.

    The solution in TypeScript

    class UndergroundSystem {
    checkIns: Map<number, [string, number]> = new Map();
    routes: Map<string, [number, number]> = new Map();

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

    checkOut(id: number, stationName: string, t: number): void {
        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: string, endStation: string): number {
        let [total, count] = this.routes.get(startStation + "," + endStation);
        return total / count;
    }
}

    Details:

    • After the example above, routes holds "Leyton,Waterloo" with [22, 2] and "Paradise,Cambridge" with [14, 1], and checkIns holds only card 10: [10, ["Leyton", 24]].
    • Number division gives a double, never an integer: getAverageTime returns 5, 5.5 or 6.25 as plain numbers. The lesson's tests print two decimals; in your own code, (5.5).toFixed(2) gives the string "5.50".
    • The destructuring let [a, b] = pair unpacks an array by position. Because Map.get can return undefined, unpacking it for an unknown route would throw a TypeError; the lesson promises that getAverageTime is only called for routes with a finished trip.

    Complexity

    Every method does a fixed number of map operations, so each runs in O(1) time apart from building the route string from the station names. Space is O(P + R) for P trips in progress and R different routes. It does not grow with the number of finished trips.

    Edge cases and common mistakes

    • Direction matters. With trips A to B taking 3 and 2, and B to A taking 7, getAverageTime("A", "B") is 2.5 and getAverageTime("B", "A") is 7. Keys "A,B" and "B,A" are different.
    • The same card travels twice. Card 10 rides Leyton to Paradise twice in the lesson's second example. Each trip counts, which is why checkOut deletes the entry from checkIns. Averages after the trips in that example: 5, 5.5, 6.25.
    • Unfinished trips. They live only in checkIns and never touch routes.
    • Missing separator in the route name. Without the comma, different station pairs can collide on one key.
    • Building the route differently in two places. If getAverageTime doesn't build the name exactly as checkOut does, the lookup finds nothing.
    • Integer division. Unlike some languages, TypeScript doesn't truncate /. Don't wrap the result in Math.floor.
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free