Start learning free

LESSON 332 OF 573 · HASH TABLE

Design Underground System in Scala: Two HashMaps and Running Totals

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

    SCALA · HASH TABLE

    Design Underground System in Scala, explained

    Problem overview

    An underground railway wants to know how long trips take between stations. A passenger checks in with a card at the station where the trip starts and checks out at the station where it ends. The class UndergroundSystem records the trips and reports the average time between any two stations:

    • checkIn(id: Int, stationName: String, t: Int): Unit starts a trip for the card id.
    • checkOut(id: Int, stationName: String, t: Int): Unit ends that trip. It took t minus the check-in time.
    • getAverageTime(startStation: String, endStation: String): Double returns the average time of the finished trips from startStation to endStation. Direction matters: a trip from B to A belongs to a different route than a trip from A to B. Trips still in progress do not count.

    The statement guarantees that a passenger checks in only when not checked in already, checks out only after checking in, and that getAverageTime is only asked about routes with at least one finished trip.

    Example: card 45 goes from Leyton to Waterloo between times 3 and 15 (12), card 27 on the same route between 10 and 20 (10), and card 32 from Paradise to Cambridge between 8 and 22 (14). The average for Paradise to Cambridge is 14.0, and for Leyton to Waterloo it is (12 + 10) / 2 = 11.0. A card that has checked in but not out yet changes nothing.

    Approach

    The simple way and its cost

    Store every finished trip as a record (start, end, duration) in a list. To answer getAverageTime, go through the list, pick the trips on the route and average them. That costs O(n) per question, where n is the number of trips so far, and the list keeps growing. The lesson asks for O(1) per operation.

    Keep only what the answer needs

    An average is a total divided by a count. So for each route the class only needs two numbers: the sum of all the trip times and the number of trips. At each check-out both change by a small amount, and getAverageTime becomes one lookup and one division.

    The class keeps two hash maps:

    • checkIns holds the trips in progress: card id to a pair (station, time).
    • routes holds the finished trips, per route: the route written as one string, "start,end", to the pair (total time, number of trips).

    The comma in the route's name keeps stations apart. Without it, the stations "A" and "BC" would give the same text, "ABC", as "AB" and "C". Because the route is built in the order start, then end, the route from A to B and the route from B to A are different keys.

    When a passenger checks out, the class removes their entry from checkIns. That ends the trip and also lets the same card check in again later, as in the case of one card making two trips.

    Step by step

    1. Declare checkIns, a mutable.HashMap[Int, (String, Int)]. (String, Int) is a tuple type: a station and a time.
    2. Declare routes, a mutable.HashMap[String, (Int, Int)]: a route name to its total time and its trip count.
    3. In checkIn, store the pair (stationName, t) under the card: checkIns(id) = (stationName, t). The trip's duration is not known yet.
    4. In checkOut, take the check-in out of the map with checkIns.remove(id).get and unpack it: val (startStation, startTime) = .... remove deletes the entry and returns its old value inside an Option, and .get takes the value out of it.
    5. Build the route's name as startStation + "," + stationName.
    6. Read the route's totals with routes.getOrElse(route, (0, 0)) and unpack them into total and count. A route with no trips yet starts at zero.
    7. Store the new totals: routes(route) = (total + t - startTime, count + 1). Only two numbers change, however many trips came before.
    8. In getAverageTime, read the pair for startStation + "," + endStation from routes, built with the comma exactly as in checkOut.
    9. Return total.toDouble / count. Converting the total to a Double first keeps the fraction.

    The solution in Scala

    class UndergroundSystem {
    val checkIns = mutable.HashMap[Int, (String, Int)]()
    val routes = mutable.HashMap[String, (Int, Int)]()

    def checkIn(id: Int, stationName: String, t: Int): Unit = {
        checkIns(id) = (stationName, t)
    }

    def checkOut(id: Int, stationName: String, t: Int): Unit = {
        val (startStation, startTime) = checkIns.remove(id).get
        val route = startStation + "," + stationName
        val (total, count) = routes.getOrElse(route, (0, 0))
        routes(route) = (total + t - startTime, count + 1)
    }

    def getAverageTime(startStation: String, endStation: String): Double = {
        val (total, count) = routes(startStation + "," + endStation)
        return total.toDouble / count
    }
}

    A short run, with one card making two trips on the same route:

    val u = new UndergroundSystem
u.checkIn(10, "Leyton", 3)
u.checkOut(10, "Paradise", 8)
println(u.getAverageTime("Leyton", "Paradise"))
u.checkIn(5, "Leyton", 10)
u.checkOut(5, "Paradise", 16)
println(u.getAverageTime("Leyton", "Paradise"))
u.checkIn(2, "Leyton", 21)
u.checkOut(2, "Paradise", 30)
u.checkIn(10, "Leyton", 32)
u.checkOut(10, "Paradise", 37)
println(u.getAverageTime("Leyton", "Paradise"))
println(u.routes)

    5.0
5.5
6.25
HashMap(Leyton,Paradise -> (25,4))

    The four trips take 5, 6, 9 and 5, so the route holds a total of 25 and a count of 4. The lesson's tests print averages with two decimals, so the values above show as 5.00, 5.50 and 6.25.

    Scala details:

    • Tuple unpacking. val (total, count) = pair declares two values at once from the two elements of a tuple.
    • remove(id).get. remove on a mutable map returns an Option: Some(value) if the key was there, None otherwise. Calling .get on None throws NoSuchElementException. The statement guarantees that a check-out always has a check-in.
    • getOrElse against routes(route). getOrElse(route, (0, 0)) returns the default when the key is missing. Plain routes(route) throws for a missing key, which is acceptable in getAverageTime only because the statement promises that the route has a trip.
    • checkIns(id) = ... is shorthand for checkIns.update(id, ...). It inserts the card, or replaces the value if the key was present.
    • Integer versus floating-point division. Two Ints divide to an Int: 11 / 2 is 5. With one side a Double, 11.toDouble / 2 is 5.5. That is why total.toDouble comes first.
    • The lesson's code uses mutable without a prefix. In a file of your own, add import scala.collection.mutable.

    Complexity

    Time. Every operation is a few hash-map operations on average, so it is O(1), apart from building the route's name, which takes time proportional to the lengths of the two station names (at most 10 characters each here).

    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 route's two numbers.

    Edge cases and common mistakes

    • Integer division. total / count with both Ints drops the fraction: a total of 11 over 2 trips would give 5 instead of 5.5. The result type is Double, so write total.toDouble / count.
    • The direction of the route. A to B and B to A are different keys. After trips A to B of 3 and 2 minutes, and a trip B to A of 7, getAverageTime("A", "B") is 2.5 and getAverageTime("B", "A") is 7.0.
    • Leaving the check-in in the map. If checkOut used checkIns(id) without removing it, the old entry would stay behind forever. A card that checks in again simply overwrites it, but the map would hold finished trips.
    • Counting unfinished trips. Only checkOut touches routes, so a passenger who has checked in but not out does not change any average.
    • A card travelling twice. Each check-out removes the card's entry, so the card can check in again, and both trips count.
    • Route names without a separator. Joining the stations with no comma can make two different routes collide, such as "A" to "BC" and "AB" to "C".
    • Asking about an unknown route. routes(...) throws NoSuchElementException for a route with no finished trip. The statement rules this case out.

    Testing

    • Cards 45 and 27 travel Leyton to Waterloo (3 to 15, and 10 to 20), and card 32 travels Paradise to Cambridge (8 to 22). getAverageTime("Paradise", "Cambridge") is 14.00, and getAverageTime("Leyton", "Waterloo") is 11.00. After checkIn(10, "Leyton", 24) with no check-out, it is still 11.00.
    • Four trips from Leyton to Paradise of 5, 6, 9 and 5 minutes give 5.00, 5.50 and then 6.25 after the fourth.
    • Trips A to B of 3 and 2 minutes and one trip B to A of 7 minutes give 2.50 and 7.00.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free