Start learning free

LESSON 335 OF 576 · HASH TABLE

Design Underground System in Rust: Per-Route Totals and Counts

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

    RUST · HASH TABLE

    Design Underground System in Rust, explained

    Problem overview

    Passengers check in at a station with a card id and check out at another. The struct UndergroundSystem records these trips and reports, for two stations, the average time of all finished trips from the first to the second. It has four methods: new(), check_in(id, station_name, t), check_out(id, station_name, t) and get_average_time(start_station, end_station), which returns an f64.

    Direction matters: a trip from B to A belongs to a different route than a trip from A to B. Only finished trips count, and a card can travel again after it checks out.

    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 average from Leyton to Waterloo is (12 + 10) / 2 = 11. A card that has checked in but not out yet changes nothing.

    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 design stores every finished trip in a list with its two stations and its duration. get_average_time then walks the list, picks the trips on the route, and averages them. That costs O(n) per call for n trips so far.

    An average needs only two numbers: the total time and the number of trips. So the system stores those two numbers for each route and updates them at every check-out. After that, get_average_time is one lookup and one division, whatever the number of trips.

    The system needs two maps. The first, check_ins, holds trips in progress: for each card id, the station and time of its check-in. A trip's duration is known only at check-out, so check_in just stores this pair. The second, routes, holds the finished trips by route: the key is the string "start,end", and the value is the pair (total time, number of trips).

    The comma in the key keeps the two names apart. Without it, "A" followed by "BC" and "AB" followed by "C" would both give "ABC". Station names contain only letters and digits, so a comma can never be part of a name.

    Running the first example up to the first averages gives these stored values and results:

    average Paradise to Cambridge: 14.00
average Leyton to Waterloo: 11.00
route Leyton,Waterloo: (total, count) = (22, 2)
route Paradise,Cambridge: (total, count) = (14, 1)
trips in progress: 0

    After check_in(10, "Leyton", 24) there is one trip in progress, and the average from Leyton to Waterloo stays 11.00.

    Step by step

    1. Declare check_ins as a HashMap<i32, (String, i32)>: card id to the station and time of the check-in.
    2. Declare routes as a HashMap<String, (i32, i32)>: route name to total time and trip count.
    3. In new, return the struct with two empty maps.
    4. In check_in, insert (station_name, t) under the key id.
    5. In check_out, remove the passenger's check-in with remove(&id).unwrap() and unpack it into start_station and start_time. Removing it ends the trip in progress, so the card can check in again later.
    6. Build the route name: the start station, a comma, then the end station, in that order.
    7. Read the route's current pair, using (0, 0) when the route has no finished trip yet.
    8. Store the updated pair: the total plus t - start_time, and the count plus 1.
    9. In get_average_time, look up the pair for the route built the same way, with the comma.
    10. Divide the total by the count as f64 values.

    The solution in Rust

    struct UndergroundSystem {
    check_ins: HashMap<i32, (String, i32)>,
    routes: HashMap<String, (i32, i32)>,
}

impl UndergroundSystem {
    fn new() -> UndergroundSystem {
        UndergroundSystem { check_ins: HashMap::new(), routes: HashMap::new() }
    }

    fn check_in(&mut self, id: i32, station_name: String, t: i32) {
        self.check_ins.insert(id, (station_name, t));
    }

    fn check_out(&mut self, id: i32, station_name: String, t: i32) {
        let (start_station, start_time) = self.check_ins.remove(&id).unwrap();
        let route = start_station + "," + &station_name;
        let (total, count) = *self.routes.get(&route).unwrap_or(&(0, 0));
        self.routes.insert(route, (total + t - start_time, count + 1));
    }

    fn get_average_time(&self, start_station: String, end_station: String) -> f64 {
        let (total, count) = self.routes[&(start_station + "," + &end_station)];
        total as f64 / count as f64
    }
}

    In a file of your own, add use std::collections::HashMap; at the top. Using the system with the second example, the three calls to get_average_time after one, two and four trips print:

    5.00
5.50
6.25

    The trips from Leyton to Paradise take 5, 6, 9 and 5, and card 10 makes two of them. Because the totals and counts are kept per route, the card's second trip needs no special handling: the check-out removed its first check-in.

    The Rust details worth a closer look:

    • remove(&id).unwrap(). remove deletes the entry and returns an Option with the old value. unwrap() would panic on None, but a card can only check out after checking in. The tuple then moves out of the map, so start_station is an owned String.
    • Building the route with +. start_station + "," + &station_name takes ownership of start_station and appends to it. The right side of + must be a &str; a &String is accepted because it converts to &str automatically. The same expression in get_average_time works because that method owns its start_station parameter.
    • *self.routes.get(&route).unwrap_or(&(0, 0)). get returns an Option holding a reference to the pair, unwrap_or supplies a reference to (0, 0) when the route is missing, and the leading * copies the pair out. A tuple of two i32s is Copy, so nothing is moved, and the borrow of self.routes ends there. That is what allows the insert on the next line.
    • insert(route, ...) moves route. It is the last use of the string, so the map takes ownership. Inserting under an existing key replaces the old pair.
    • Integer versus float division. With i32 operands, 11 / 2 is 5. 11 as f64 / 2 as f64 is 5.5. The method converts both numbers with as f64 before dividing.
    • Indexing a map. self.routes[&(...)] panics when the key is missing. The statement promises that get_average_time is called only for routes with a finished trip.
    • Two decimals. The method returns the number itself. The lesson's tests print it with two decimals, which in Rust is the format {:.2}.

    Complexity

    Time. Each method does a constant number of hash-map operations plus a division, so it runs in O(1) on average, apart from building the route name, which is linear in the length of the two names (at most 10 characters each).

    Space. O(P + R), where P is the number of passengers checked in right now and R is the number of distinct routes with a finished trip. The system does not store individual finished trips, only one pair per route.

    Edge cases and common mistakes

    • Direction. In the third example, the trips from A to B take 3 and 2, and the trip from B to A takes 7. The averages are 2.50 for A to B and 7.00 for B to A. The route names "A,B" and "B,A" are different keys.
    • A trip in progress. It lives only in check_ins, so it doesn't affect any average.
    • A card travelling again. Check-out must remove the card's entry, so that the next check-in can start fresh.
    • Integer division. Dividing the two i32 values gives 5 instead of 5.5 for a total of 11 over 2 trips. Convert to f64 first.
    • Forgetting the separator. Without the comma in the route key, different pairs of stations can collide.
    • Storing every trip. It works but makes get_average_time O(n).
    • Averaging the averages. Keeping a running average and averaging it with each new trip gives the wrong answer. Keep the total and the count.

    Testing

    • The first example gives 14.00, 11.00 and 11.00.
    • The second example gives 5.00, 5.50 and 6.25.
    • The third example gives 2.50 for A to B and 7.00 for B to A.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free