Start learning free

LESSON 332 OF 573 · HASH TABLE

Design Underground System in Go: O(1) Average Trip Time

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

    GO · HASH TABLE

    Design Underground System in Go, explained

    Problem overview

    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. The system records these trips and tells, for any two stations, the average time of the finished trips from the first to the second.

    The lesson asks for an UndergroundSystem struct with these parts: Constructor creates an empty system. CheckIn(id, stationName, t) starts a trip for the card id, and a card can be checked in at only one place at a time. CheckOut(id, stationName, t) ends that trip, which took t minus the check-in time. GetAverageTime(startStation, endStation) returns the average, as a float64, of all finished trips from the start station to the end station. Only finished trips count, and direction matters: a trip from B to A belongs to a different route than a trip from A to B.

    In the first example, cards 45 and 27 both go from Leyton to Waterloo in 12 and 10 minutes, and card 32 goes from Paradise to Cambridge in 14. The average for Paradise to Cambridge is 14.00, and for Leyton to Waterloo it is (12 + 10) / 2 = 11.00. Card 10 then checks in at Leyton, but its trip is not finished, so the average stays 11.00.

    Approach: keep a running total and count per route

    One way is to keep a list of all finished trips and, at each GetAverageTime, walk through the list and average the ones on the route. That costs O(n) per call, where n is the number of trips so far.

    An average only needs two numbers: the total time of the trips and their count. If those are updated at every check-out, nothing else about a finished trip needs to be remembered, and an answer is one lookup and one division.

    So the system keeps two maps:

    • Trips in progress: for each card id, the station and the time of its check-in. A card has at most one trip in progress, so the id is a good key. The entry is removed at check-out, which lets the same card check in again later.
    • Routes: for each route, the pair (total time, number of trips). The route is the string "start,end", so a trip from A to B goes under "A,B" and one from B to A under "B,A".

    The comma in the route name keeps station names apart: without it, the pairs "A" and "BC" and "AB" and "C" would both produce "ABC".

    Step by step

    1. Declare the trip struct for a check-in: station as a string and time as an int.
    2. Declare checkIns in the main struct as a map[int]trip, from card id to check-in.
    3. Declare routes as a map[string][2]int. The array [2]int has exactly two ints: the total at index 0 and the count at index 1.
    4. Create both maps in Constructor. A map must be made before anything is stored in it.
    5. In CheckIn, store trip{stationName, t} under the key id. The trip's time isn't known until check-out, so nothing else is needed.
    6. In CheckOut, read the check-in into start. It is a copy, so it stays usable after the entry is deleted.
    7. Delete the card's entry with delete(this.checkIns, id), which ends the trip in progress.
    8. Build the route's name: the start station, a comma, then the station where the trip ended.
    9. Read the route's pair. For a route not in the map yet, Go returns the zero value, [2]int{0, 0}, so a new route starts at total 0 and count 0.
    10. Store a new pair: the total plus this trip's time, t - start.time, and the count plus 1. Only two numbers change, so a check-out is O(1).
    11. In GetAverageTime, read the pair for the route built exactly the same way, with the comma.
    12. Return the total divided by the count, both converted to float64 first.

    The solution in Go

    type trip struct {
    station string
    time int
}

type UndergroundSystem struct {
    checkIns map[int]trip
    routes map[string][2]int
}

func Constructor() UndergroundSystem {
    return UndergroundSystem{checkIns: map[int]trip{}, routes: map[string][2]int{}}
}

func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) {
    this.checkIns[id] = trip{stationName, t}
}

func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) {
    start := this.checkIns[id]
    delete(this.checkIns, id)
    route := start.station + "," + stationName
    stats := this.routes[route]
    this.routes[route] = [2]int{stats[0] + t - start.time, stats[1] + 1}
}

func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
    stats := this.routes[startStation+","+endStation]
    return float64(stats[0]) / float64(stats[1])
}

    The Go details worth a closer look:

    • Arrays are values. [2]int is an array of exactly two ints, and map values can't be changed in place (this.routes[route][0] += 1 does not compile). That is why CheckOut reads the pair into stats and stores a new array under the key.
    • Missing keys give zero values. Reading a route that has no trips gives [2]int{0, 0}, which is exactly the starting state needed. No existence check is required.
    • Integer division truncates. 11 / 2 with ints is 5. Converting both operands first with float64(x) gives 5.5.
    • Struct fields named time. A field called time is fine; it would only clash with a package of that name if the file imported one.

    Complexity

    Time: O(1) per call. Each operation is a few map lookups, writes or deletes and some arithmetic. Building the route's name costs time proportional to the length of the two station names, at most 10 characters each. GetAverageTime never looks at the individual trips.

    Space. One entry for each trip in progress, plus one entry for each route that has finished trips. Finished trips are not stored one by one.

    Edge cases and common mistakes

    • Direction. Trips from A to B take 3 and 2 minutes and one trip from B to A takes 7. GetAverageTime("A", "B") is 2.50 and GetAverageTime("B", "A") is 7.00.
    • Unfinished trips. A check-in alone changes no route. The average stays the same until the card checks out.
    • Cards that travel again. Card 10 can travel twice on the same route, and each trip counts. With trips of 5, 6, 9 and 5 minutes on one route, the average after the first trip is 5.00, after two it is 5.50 and after all four it is 6.25.
    • Integer division. Without the float64 conversion the average of 11 and 2 would be 5, not 5.5.
    • Forgetting to delete the check-in. The entry would stay forever, and a stale entry could be used by mistake.
    • Different keys at check-out and lookup. If one place used "A,B" and the other "A-B", the lookup would find an empty pair, and the division would give NaN for 0 / 0.

    Testing

    Printing the results with two decimals (%.2f), the first example's three averages are 14.00, 11.00, 11.00, and the second example's are 5.00, 5.50, 6.25. In the third example, the route map holds A,B with total 5 over 2 trips and B,A with total 7 over 1 trip, and the averages are 2.50 and 7.00.

    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free