Start learning free

LESSON 331 OF 572 · HASH TABLE

Design Underground System in C#: O(1) Averages per Route

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

    You write the class UndergroundSystem. Passengers have a card id. CheckIn(id, stationName, t) starts a trip and CheckOut(id, stationName, t) ends it. GetAverageTime(startStation, endStation) returns, as a double, the average time of all finished trips from the first station to the second. Direction matters: a trip from B to A is a different route from A to B. A trip that has checked in but not out yet does not count.

    In the first example, 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. The averages come out as:

    Paradise to Cambridge: 14.00
Leyton to Waterloo: 11.00
Leyton to Waterloo, after card 10 checks in but not out: 11.00

    The second example has one card, 10, travelling twice; each trip counts. The trips from Leyton to Paradise take 5, 6, 9 and 5, and the average after one, two and four trips is:

    5.00
5.50
6.25

    Approach: keep a total and a count per route

    The simple design stores every finished trip and, in GetAverageTime, walks through all of them to add up the matching ones. That costs 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 never stores finished trips at all. It keeps two maps:

    • checkIns: the trips in progress. For each card id, the station and the time it checked in.
    • routes: for each route, written as the string "start,end", the pair (total time of its finished trips, number of trips).

    CheckIn only records the start. CheckOut looks up the start, computes the trip time t - startTime, and adds it to the route's total and 1 to its count. GetAverageTime is one lookup and one division. Each operation is O(1), apart from building the route string from the two station names.

    The comma in the route name matters. Without it, the stations "A" and "BC" would give the same route string as "AB" and "C". With it, the two routes are A,BC and AB,C.

    Step by step

    1. Declare checkIns, a Dictionary<int, (string, int)>, set to new(). The value is a tuple holding a station and a time.
    2. Declare routes, a Dictionary<string, (int, int)>, set to new(): the pair is (total time, number of trips).
    3. CheckIn sets checkIns[id] to (stationName, t). Nothing else is known until the passenger leaves.
    4. CheckOut unpacks the stored pair with var (startStation, startTime) = checkIns[id];, which copies the tuple's two values into two new variables.
    5. Remove id from checkIns. The trip is over, and the same card can check in again later, as card 10 does in the second example.
    6. Build route as startStation + "," + stationName.
    7. Unpack the route's current pair with GetValueOrDefault(route, (0, 0)), so a route with no finished trip yet starts from (0, 0).
    8. Store the new pair: the total plus t - startTime, and the count plus 1. Only these two numbers change, so the cost does not depend on how many trips came before.
    9. GetAverageTime unpacks the pair stored for startStation + "," + endStation, built exactly as in CheckOut, and returns (double) total / count.

    The solution in C#

    class UndergroundSystem {
    Dictionary<int, (string, int)> checkIns = new();
    Dictionary<string, (int, int)> routes = new();

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

    public void CheckOut(int id, string stationName, int t) {
        var (startStation, startTime) = checkIns[id];
        checkIns.Remove(id);
        string route = startStation + "," + stationName;
        var (total, count) = routes.GetValueOrDefault(route, (0, 0));
        routes[route] = (total + t - startTime, count + 1);
    }

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

    Details in C#. Dividing two int values drops the fraction: 11 / 2 is 5, while (double) total / count with total 11 and count 2 gives 5.5. The cast applies to total before the division, so the division is done in double. Reading checkIns[id] or routes[...] for a missing key throws a KeyNotFoundException; that is safe here because the problem promises that a card checks out only after checking in, and that averages are asked only for routes with at least one finished trip. GetValueOrDefault is used in CheckOut exactly because a route's first trip has no pair yet.

    Complexity

    • CheckIn, CheckOut, GetAverageTime: O(1) each, plus the cost of building the route string from two short station names.
    • Space: O(P + R) for P passengers currently travelling and R distinct routes, instead of one entry per finished trip.

    Testing

    The third example checks that direction matters. Trips: card 1 goes A to B in 3, card 2 goes B to A in 7, card 3 goes A to B in 2. The averages:

    A to B: 2.50
B to A: 7.00

    Edge cases and common mistakes

    • Integer division. Without the cast, 5 + 6 = 11 over 2 trips gives 5 instead of 5.5.
    • Mixing up directions. Build the route as start then end in both methods, so A to B and B to A stay apart.
    • No separator in the route name. Two different pairs of stations can then collide.
    • Forgetting to remove the check-in. It would leave stale data behind, and a card that checks in again would rely on overwriting it.
    • Counting unfinished trips. Only CheckOut changes routes, so a passenger who has only checked in never affects an average.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free