Start learning free

LESSON 327 OF 568 · HASH TABLE

Design Underground System in C++: O(1) Averages with Two Hash Maps

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

    C++ · HASH TABLE

    Design Underground System in C++, explained

    Problem overview

    Passengers check in with a card at the station where they start and check out at the station where they leave. The class UndergroundSystem records these trips and answers one question: what is the average time of the finished trips from one station to another?

    It has three methods. checkIn(id, stationName, t) starts a trip for the card id. checkOut(id, stationName, t) ends that card's trip, which took t minus the check-in time. getAverageTime(startStation, endStation) returns the average time of all finished trips from the first station to the second. Direction matters: a trip from B to A belongs to a different route than one from A to B. A trip that has not been checked out does not count. The tests print each average with two decimals.

    In the first example, cards 45 and 27 both go from Leyton to Waterloo, taking 12 and 10 minutes, and card 32 goes from Paradise to Cambridge in 14. The averages are 14.00 for Paradise to Cambridge and 11.00 for Leyton to Waterloo. Then card 10 checks in at Leyton but does not check out, so the Leyton to Waterloo average stays 11.00.

    The statement asks for O(1) time per operation, apart from building the route's name from the two station names.

    Approach: keep a total and a count per route

    The simple solution stores every finished trip in a list and, in getAverageTime, walks the whole list, adds up the matching trips and divides. That is O(n) per call for n trips so far.

    An average is a total divided by a count, and both can be updated one trip at a time. So the class keeps, for each route, only two numbers: the total time of its finished trips and how many there are. A check-out adds the trip's time to the total and adds one to the count. getAverageTime reads the two numbers and divides.

    The class needs two maps:

    • checkIns: for each card id, where and when its owner checked in. It holds the trips in progress, and an entry is removed when its trip ends.
    • routes: for each route, written as one string "start,end", the pair (total time, number of trips).

    After the first example's check-outs and the extra check-in by card 10, the state is:

    routes:
  Leyton,Waterloo -> total 22, count 2
  Paradise,Cambridge -> total 14, count 1
trips in progress: 1

    The average for Leyton to Waterloo is 22 / 2 = 11.00. The one trip in progress belongs to card 10 and is not in routes.

    The comma in the route's name keeps stations apart. Without it, the stations A and BC and the stations AB and C would both give the route ABC. With the comma they give A,BC and AB,C, which differ. The station names contain only letters and digits, so a comma never occurs inside a name.

    Step by step

    1. Declare checkIns as an unordered_map from int to pair<string, int>: the station and the time of each check-in in progress.
    2. Declare routes as an unordered_map from string to pair<int, int>: the total time and the number of trips of each route.
    3. In checkIn, set checkIns[id] to {stationName, t}. The trip's time is only known at check-out.
    4. In checkOut, unpack checkIns[id] into startStation and startTime with auto [startStation, startTime].
    5. Erase id from checkIns. The trip is over, and the card may check in again later.
    6. Build the route's name: startStation, a comma, then stationName. The order gives the direction.
    7. Unpack routes[route] into total and count. A route not in the map yet gets a pair of two zeros.
    8. Store the new pair: total + t - startTime and count + 1.
    9. In getAverageTime, unpack the pair of the route startStation + "," + endStation, built exactly as in checkOut.
    10. Return (double) total / count. The cast turns the division into a division of doubles and keeps the fraction.

    The solution in C++

    class UndergroundSystem {
public:
    unordered_map<int, pair<string, int>> checkIns;
    unordered_map<string, pair<int, int>> routes;

    void checkIn(int id, string stationName, int t) {
        checkIns[id] = {stationName, t};
    }

    void checkOut(int id, string stationName, int t) {
        auto [startStation, startTime] = checkIns[id];
        checkIns.erase(id);
        string route = startStation + "," + stationName;
        auto [total, count] = routes[route];
        routes[route] = {total + t - startTime, count + 1};
    }

    double getAverageTime(string startStation, string endStation) {
        auto [total, count] = routes[startStation + "," + endStation];
        return (double) total / count;
    }
};

    The C++ details worth a closer look:

    • Structured bindings. auto [a, b] = pair; copies the two parts of a pair into two new variables. It needs C++17. Here the copy is taken before checkIns.erase(id), so erasing the entry is safe. The names startStation and startTime are copies, not references into the map.
    • Braces assign a pair. checkIns[id] = {stationName, t}; builds a pair<string, int> from the two values. Assigning to checkIns[id] overwrites an existing entry or creates a new one.
    • operator[] creates missing entries. In checkOut, routes[route] for a new route inserts a pair of two zeros, which is exactly the starting state. In getAverageTime the same call would insert an empty route if it were asked about one with no trips; the statement promises there is always at least one.
    • Integer division. total / count with two ints drops the fraction: 11 / 2 is 5. With (double) total it is 5.5. The cast applies to total before the division.
    • Overflow. The constraints keep the sum of all trips within one billion, so the totals fit in an int. Signed overflow in C++ is undefined behaviour, so it matters that they do.

    Running the second example (four trips from Leyton to Paradise taking 5, 6, 9 and 5 minutes, with card 10 travelling twice) prints 5.00 5.50 6.25 for the three calls to getAverageTime. Running the third example prints 2.50 7.00: the trips from A to B take 3 and 2, and the one trip from B to A takes 7.

    Complexity

    Time: O(1) per operation on average. Each method does a few hash-map lookups, one addition and at most one division. The route's name is built by joining two strings of at most 10 characters each, so the cost is proportional to the length of the names, a small constant here.

    Space: O(p + r), where p is the number of passengers currently in a trip and r is the number of distinct routes. The map of finished trips does not grow with the number of trips, only with the number of routes.

    Edge cases and common mistakes

    • Direction. The route "A,B" and the route "B,A" are different entries. With trips A to B of 3 and 2 minutes and one B to A trip of 7, the averages are 2.50 and 7.00.
    • Unfinished trips. A card that checked in but did not check out is only in checkIns, so it does not change any average.
    • The same card travelling twice. The check-out erases the entry, and the next check-in creates a new one, so checkIns holds only the trips in progress.
    • Integer division. Without the (double) cast, the average of 5 and 6 would be 5.00 instead of 5.50.
    • Forgetting the comma. It makes different routes collide, as ABC shows. Building the name differently in checkOut and in getAverageTime makes every lookup miss.
    • Averaging averages. Storing a running average and averaging it with each new trip gives wrong results. Keep the total and the count, and divide at the end.
    • Using the check-out time as the trip time. The trip took t - startTime.

    Testing

    • Cards 45, 27 and 32 as in the first example, then getAverageTime("Paradise", "Cambridge") and getAverageTime("Leyton", "Waterloo") give 14.00 11.00; after checkIn(10, "Leyton", 24) the second average is still 11.00.
    • Four Leyton to Paradise trips taking 5, 6, 9 and 5, with an average read after the first, second and fourth, give 5.00 5.50 6.25.
    • Trips A to B (3 and 2 minutes) and B to A (7 minutes), then getAverageTime("A", "B") and getAverageTime("B", "A") give 2.50 7.00.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free