Start learning free

LESSON 333 OF 574 · HASH TABLE

Design Underground System in Swift: O(1) Averages with Two Dictionaries

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

    SWIFT · HASH TABLE

    Design Underground System in Swift, explained

    Problem overview

    Passengers check in at a station with a card id and check out at another. The class UndergroundSystem records these trips and answers one question: what is the average time of all finished trips from station A to station B? Its methods are checkIn(id, stationName, t), checkOut(id, stationName, t) and getAverageTime(startStation, endStation).

    Only finished trips count, and direction matters: a trip from B to A belongs to a different route. A card can travel many times, but is checked in at one place at a time. The statement asks for O(1) per operation, apart from building the route's name.

    Take card 45 checking in at "Alder" at time 3 and out at "Cedar" at time 15, and card 27 doing the same route from time 10 to time 20. The trips take 12 and 10 minutes, so getAverageTime("Alder", "Cedar") is 11. A card 10 that checks in at "Alder" at time 24 has not finished, so the average stays 11. The method returns a Double, and the lesson's tests show it with two decimals, such as 11.00.

    Approach: store a total and a count per route

    The simple design keeps a list of every finished trip: start, end and duration. getAverageTime then goes through the list, picks the trips of the route and averages them. That works, but each call costs O(n) for n trips so far, and it needs to store every trip.

    An average only needs two numbers: the total time and the number of trips. Updating them when a trip finishes is cheap, and reading them is cheap too. So the class keeps two dictionaries:

    • checkIns: for each card id, the station and time of the trip in progress;
    • routes: for each route, the pair (total time, number of trips).

    checkIn saves the pair. checkOut takes it out, which ends the trip and frees the card for its next one, builds the route's name from the two stations, and adds the duration t - startTime to the route's total and 1 to its count. getAverageTime reads the route and divides.

    The route is a string of the form "start,end". The comma matters. Without it, a trip from "A" to "BC" and one from "AB" to "C" would both be the route "ABC", and their times would be mixed.

    Step by step

    1. Declare checkIns as a var of type [Int: (String, Int)], set to [:]. The tuple holds a station and a time.
    2. Declare routes as a var of type [String: (Int, Int)], set to [:]. The tuple holds the total time and the number of trips.
    3. In checkIn, set checkIns[id] to (stationName, t). The duration is not known yet.
    4. In checkOut, remove the check-in with removeValue(forKey: id)! and unpack the tuple with let (startStation, startTime) = ....
    5. Build route as startStation + "," + stationName.
    6. Read the route's pair with routes[route, default: (0, 0)], unpacked into total and count. A new route starts at 0 and 0.
    7. Store the updated pair: total + t - startTime and count + 1.
    8. In getAverageTime, read the pair for startStation + "," + endStation, with ! after the lookup. The lesson promises the route has at least one finished trip.
    9. Return Double(total) / Double(count).

    The solution in Swift

    class UndergroundSystem {
    var checkIns: [Int: (String, Int)] = [:]
    var routes: [String: (Int, Int)] = [:]

    func checkIn(_ id: Int, _ stationName: String, _ t: Int) {
        checkIns[id] = (stationName, t)
    }

    func checkOut(_ id: Int, _ stationName: String, _ t: Int) {
        let (startStation, startTime) = checkIns.removeValue(forKey: id)!
        let route = startStation + "," + stationName
        let (total, count) = routes[route, default: (0, 0)]
        routes[route] = (total + t - startTime, count + 1)
    }

    func getAverageTime(_ startStation: String, _ endStation: String) -> Double {
        let (total, count) = routes[startStation + "," + endStation]!
        return Double(total) / Double(count)
    }
}

    The Swift details worth a closer look:

    • Tuple destructuring. let (startStation, startTime) = ... splits a tuple into two constants in one line. It works the same way for the pair read from routes.
    • removeValue(forKey:). It deletes the entry and returns its old value as an optional, nil if the key was missing. The ! unwraps it, which is safe because the lesson says a card checks out only after checking in. After it, checkIns no longer holds the card, so it can check in again.
    • default: with a tuple. routes[route, default: (0, 0)] gives (0, 0) for a route that isn't there yet. Reading with default doesn't add anything to the dictionary. The line that follows stores the updated pair.
    • Integer division. total and count are Int. Dividing them directly drops the fraction: 11 / 2 is 5. Converting each to Double first gives Double(11) / Double(2), which is 5.5. Converting after the division, Double(11 / 2), gives 5.0, the wrong answer.
    • The type of the result. Swift prints a Double without trailing zeros: 14.0 and 5.5 appear as 14.0 and 5.5. The lesson's tests format the value to two decimals.
    • Arithmetic order. total + t - startTime adds first, then subtracts. The lesson guarantees totals fit in 32 bits, so there is no overflow on a 64-bit Int.
    • Class properties. The dictionaries are var properties of a class, so methods change them without being marked mutating.

    Complexity

    Time. Every method is a few dictionary operations, O(1) on average, plus building the route's name, which takes time proportional to the two names (at most 10 characters each). getAverageTime does one lookup and one division, whatever the number of trips.

    Space. O(P + R), where P is the number of passengers currently checked in and R the number of different routes. Finished trips are not stored one by one: each adds to a total and a count and is forgotten.

    Edge cases and common mistakes

    • Unfinished trips. A card that has checked in but not out is in checkIns only, so it doesn't affect any average. After the extra check-in in the first example, checkIns holds just card 10 and the average of "Alder" to "Cedar" is still 11.
    • The direction. With two trips from A to B taking 3 and 2, and one from B to A taking 7, getAverageTime("A", "B") is 2.5 and getAverageTime("B", "A") is 7. Using the same key for both directions would mix them.
    • The same card travelling twice. In the second example, card 10 makes two trips from "Leyton" to "Paradise". The averages after the trips are 5.0, 5.5 and 6.25, since each finished trip counts. Because checkOut removes the check-in, the second check-in starts clean.
    • No separator in the route. Joining the names without the comma makes "A" + "BC" equal "AB" + "C". Station names are letters and digits only, so a comma can never be part of a name.
    • Integer division. total / count on two Int values returns 5 for 11 and 2. Convert both to Double before dividing.
    • Keeping a list of all trips. It is correct but makes getAverageTime O(n) and the memory grow with every trip.
    • Checking out without a check-in. The ! would crash the program. The lesson never does this.

    Testing

    • Cards 45, 32 and 27 check in at "Alder" (time 3), "Birch" (8) and "Alder" (10), and check out at "Cedar" (15), "Dune" (22) and "Cedar" (20). The average from "Birch" to "Dune" is 14.0 and from "Alder" to "Cedar" is 11.0. After card 10 checks in at "Alder" at 24, the average from "Alder" to "Cedar" is still 11.0.
    • Four trips from "Leyton" to "Paradise" taking 5, 6, 9 and 5 give 5.0, 5.5 and 6.25 after the first, the second and the fourth.
    • Trips A to B taking 3 and 2, and B to A taking 7: the averages are 2.5 and 7.0.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free