1396.design-underground-system.md

1396. Design Underground System

Hash Table

When a passenger checkin, we record the start station and start time in the hash table.

// Card ID -> (Start Station, Time)
Map<Int, Pair<String, Int>>

When a passenger checkout, we:

1. Retrieve the start station and start time from the hash table.
2. Calculate the travel time.
3. Update the route hash table.

// From-To -> (Total Time, Count)
Map<Pair<String, String>, Pair<Int, Int>>

When query the average time, we just look up the route hash table.

A customer can only be checked into one place at a time. The following scenario will not happen:

Stations: A, B, C, D
Users  a: 1     6
       a:    2  3

Before a check out from station A, he can't check in at station B.

class UndergroundSystem() {

    // <Card ID, (Station, Time)>
    private val checkIn = HashMap<Int, Pair<String, Int>>()
    // <From-To, (Total Time, Count)>
    private val route = HashMap<Pair<String, String>, Pair<Int, Int>>()

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

    fun checkOut(id: Int, stationName: String, t: Int) {
        // Find the check in record of the same id from `checkIn` hash table
        // update route: <from-to>, <total time, count>
        if (id in checkIn) {
            val (startStation, startTime) = checkIn[id]!!
            val stationPair = startStation to stationName
            if (stationPair !in route) {
                route[stationPair] = (t - startTime) to 1
            } else {
                val (previousTime, previousCount) = route[stationPair]!!
                route[stationPair] = (previousTime + t - startTime) to (previousCount + 1)
            }
        }
    }

    // The problem statement is that there will be at least one customer that
    // has traveled from `startStation` to `endStation` before `getAverageTime` is called.
    // So we don't need to check if the `route` hash table is empty.
    fun getAverageTime(startStation: String, endStation: String): Double {
        val (totalTime, count) = route[startStation to endStation]!!
        return totalTime.toDouble() / count
    }
}

• Time Complexity:

  • checkIn: O(1)
  • checkOut: O(1)
  • getAverageTime: O(1)

• Space Complexity:

  • O(P) for checkIn hash table, where P is the number of passengers
  • O(S^2) for route hash table, where S is the number of stations

WA

For each check-in and check-out, we need to record the time in the nested hash table: <Station, HashMap<Id, Time>>.

Stations: A, B, C, D
Users  a: 1     6
       c: 0     8
       e: 0        9
       b:    2     3
       d:    3     8
       f:    1  4

Then when we calculate the average time between A and C, we need to find the time at A and C for each user, and then calculate the average time:

checkIn[A] = [
    (a, 1)
    (c, 0)
    (e, 0)
]

checkOut[C] = [
    (a, 6)
    (c, 9)
    (f, 4)
]

a: 6 - 1 = 5
c: 9 - 0 = 9
e: Can't find in checkOut
f: Can't find in checkIn

But this implementation fails at the case: Same user checkins from the same station, but checkouts at different stations. (5, 7) will override (1, 3) at station A in our hash table.

// Failed case:
Stations: A, B, C, D
Users  a: 1  3
       a: 5     7

class UndergroundSystem() {

    // Station -> (User ID, Time)
    private val checkIn = HashMap<String, HashMap<Int, Int>>()
    private val checkOut = HashMap<String, HashMap<Int, Int>>()

    fun checkIn(id: Int, stationName: String, t: Int) {
        if (stationName !in checkIn) {
            checkIn[stationName] = HashMap<Int, Int>()
        }
        checkIn[stationName]!![id] = t
    }

    fun checkOut(id: Int, stationName: String, t: Int) {
        if (stationName !in checkOut) {
            checkOut[stationName] = HashMap<Int, Int>()
        }
        checkOut[stationName]!![id] = t
    }

    fun getAverageTime(startStation: String, endStation: String): Double {
        val startRecords = checkIn[startStation]!!
        val endRecords = checkOut[endStation]!!
        var time = 0L
        var count = 0L
        for ((startId, startTime) in startRecords) {
            if (startId in endRecords) {
                val endTime = endRecords[startId]!!
                time += (endTime - startTime).toLong()
                count++
            }
        }
        return time.toDouble() / count
    }
}