Start learning free

LESSON 332 OF 573 · HASH TABLE

Design Underground System in Kotlin: O(1) Averages with Two HashMaps

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

    KOTLIN · HASH TABLE

    Design Underground System in Kotlin, explained

    Problem overview

    You write a class UndergroundSystem that records passenger trips. checkIn(id, stationName, t) says that the card id entered a station at time t. checkOut(id, stationName, t) ends that card's trip at another station. getAverageTime(startStation, endStation) returns, as a Double, the average duration of all finished trips that went from the first station to the second.

    Direction matters: A to B and B to A are different routes. Only finished trips count, and a card can travel again after it checks out, so a card may have many trips. The lesson's tests print each average with two decimals, such as 11.00; the method itself returns a Double.

    For example, if card 45 goes from Leyton to Waterloo from time 3 to 15 (12 minutes) and card 27 from time 10 to 20 (10 minutes), the average for Leyton to Waterloo is (12 + 10) / 2 = 11. A third card that has checked in at Leyton but not out yet doesn't change it.

    Approach

    The straightforward design stores every finished trip as a record (start, end, duration) in a list. getAverageTime then goes through the list, picks the trips of the route and averages them. That is O(n) per call, where n is how many trips have happened.

    An average needs only two numbers: the total time and the number of trips. Both can be kept up to date at each check-out, so a trip never needs to be stored at all. The class therefore keeps two hash maps:

    • checkIns for trips in progress: card id to (station, time). A check-in adds an entry and a check-out removes it.
    • routes for finished trips, per route: route name to (total time, trip count).

    The route name is the two station names joined with a comma, for example "Leyton,Waterloo". The comma matters: station names can be any letters and digits, and without a separator "A" + "BC" and "AB" + "C" would both produce "ABC". Every operation is then a couple of hash lookups, and the average is one lookup and one division.

    Step by step

    1. Trips in progress. Declare checkIns as a HashMap<Int, Pair<String, Int>>. A Pair holds two values in one item, here the station and the time.
    2. Finished trips per route. Declare routes as a HashMap<String, Pair<Int, Int>>: the route name maps to (total time, count).
    3. checkIn. Set checkIns[id] to Pair(stationName, t). The duration is unknown until the passenger leaves.
    4. Close the trip in checkOut. checkIns.remove(id)!! deletes the entry and returns what was stored. The !! says it isn't null, which the rules guarantee because a card checks out only after checking in. Destructuring val (startStation, startTime) = … unpacks the pair.
    5. Name the route: startStation + "," + stationName, in that order.
    6. Read the old totals. routes.getOrDefault(route, Pair(0, 0)) returns the route's pair, or (0, 0) for a route with no finished trips yet. Destructure it into total and count.
    7. Update them. Store Pair(total + t - startTime, count + 1): this trip's duration is added and the count grows by one.
    8. getAverageTime. Look up startStation + "," + endStation with routes[...]!! and destructure it. The tests only ask for routes with at least one finished trip.
    9. Divide as a Double. total.toDouble() / count.

    The solution in Kotlin

    class UndergroundSystem {
    val checkIns = HashMap<Int, Pair<String, Int>>()
    val routes = HashMap<String, Pair<Int, Int>>()

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

    fun checkOut(id: Int, stationName: String, t: Int) {
        val (startStation, startTime) = checkIns.remove(id)!!
        val route = startStation + "," + stationName
        val (total, count) = routes.getOrDefault(route, Pair(0, 0))
        routes[route] = Pair(total + t - startTime, count + 1)
    }

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

    Kotlin details worth knowing:

    • Integer versus floating division. 11 / 2 is 5 in Kotlin, because dividing two Int values drops the fraction. 11.toDouble() / 2 is 5.5. That's why the code converts the total before dividing.
    • Destructuring a Pair. val (a, b) = pair takes pair.first and pair.second. Both names must be new.
    • map[key] is nullable. A missing key gives null, so a plain lookup has type Pair<Int, Int>?. The !! turns it into Pair<Int, Int> and throws if it was null.
    • remove returns the removed value. One call both reads and deletes, which is exactly what a check-out needs. The card can then check in again later.
    • Default for a missing key. getOrDefault avoids writing an if and a separate insertion for the first trip of a route.
    • Int totals. They are 32-bit, and wrap on overflow without an error. The statement says all trips together fit, so Int is enough here; with unbounded input a Long would be the safer choice.

    Seeing it run

    This code builds a small system and prints the internal maps and the averages. Kotlin prints a Double such as 11.0 with one decimal; String.format("%.2f", …) gives the two-decimal form that the lesson's tests print.

    fun main() {
    val metro = UndergroundSystem()
    metro.checkIn(45, "Leyton", 3)
    metro.checkIn(27, "Leyton", 10)
    println(metro.checkIns.size)
    metro.checkOut(45, "Waterloo", 15)
    println(metro.routes)
    metro.checkOut(27, "Waterloo", 20)
    println(metro.routes)
    println(metro.checkIns.size)
    println(metro.getAverageTime("Leyton", "Waterloo"))
    println(String.format("%.2f", metro.getAverageTime("Leyton", "Waterloo")))
    metro.checkIn(10, "Leyton", 24)
    println(metro.getAverageTime("Leyton", "Waterloo"))

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

    val ab = UndergroundSystem()
    ab.checkIn(1, "A", 1)
    ab.checkOut(1, "B", 4)
    ab.checkIn(2, "B", 5)
    ab.checkOut(2, "A", 12)
    println(ab.getAverageTime("A", "B"))
    println(ab.getAverageTime("B", "A"))
    println(11 / 2)
    println(11.toDouble() / 2)
}

    It prints:

    2
{Leyton,Waterloo=(12, 1)}
{Leyton,Waterloo=(22, 2)}
0
11.0
11.00
11.0
6.25
3.0
7.0
5
5.5

    The first number is the count of trips in progress (two cards checked in). After the first check-out, the route holds total 12 and count 1. After the second, the total is 22 and the count 2. Then no trips are in progress and the average is 11.0. Card 10's later check-in, with no check-out, changes nothing. The next value, 6.25, is the average of four trips on the same route, 5, 6, 9 and 5, where card 10 made two trips. The last two averages are for A to B and B to A, which are separate routes, followed by the two divisions from the Kotlin notes.

    Complexity

    • Time: each of the three methods does a fixed number of hash operations, O(1), apart from building the route name, which takes time proportional to the length of the station names (at most 10 characters each here).
    • Space: O(p + r), for p passengers in progress and r distinct routes. Finished trips are not stored, only their totals.

    Edge cases and common mistakes

    • Integer division. Dividing the two Int values truncates the average, so 11 / 2 would give 5 instead of 5.5.
    • Route name without a separator. Different pairs of stations can collide.
    • Wrong direction. Using the check-out station first mixes up A to B with B to A.
    • Forgetting to remove the check-in. A card that travels twice would then keep a stale entry. Here the second checkIn overwrites it anyway, but the map would keep growing for cards that never return.
    • Counting unfinished trips. Only checkOut updates routes, so a trip in progress never affects an average.
    • Storing the average itself. An average can't be updated from an older average alone without the count. Keep total and count, and divide at the end.
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free