620/670

620. Design Underground System

Medium

A metro network tracks riders through its fare gates and wants live travel-time statistics. Implement a class UndergroundSystem with three operations:

check_in(id, station_name, t) — rider id passes through the entry gate at station_name at time t.
check_out(id, station_name, t) — the same rider exits through the gate at station_name at time t, completing one journey of duration t − t_in.
get_average_time(start_station, end_station) — returns the mean duration over all journeys completed so far that began at start_station and ended at end_station.

Direction matters: trips a → b and b → a are separate statistics. A rider is inside the system at most once at any moment, checkout always follows the matching check-in, and every average query concerns a route with at least one finished journey.

Each queried average must be printed with exactly two digits after the decimal point (e.g. 11.50).

Example 1:

Input: checkIn(45, "alpha", 3), checkIn(32, "alpha", 8), checkIn(27, "delta", 10), checkOut(45, "omega", 15), checkOut(27, "gamma", 20), checkOut(32, "omega", 22), getAverageTime("alpha", "omega"), getAverageTime("delta", "gamma"), checkIn(10, "alpha", 24), checkOut(10, "omega", 34), getAverageTime("alpha", "omega")

Output: [13.00, 10.00, 12.00]

Explanation: Riders 45 and 32 both travel alpha → omega, taking 12 and 14: average 13.00. Rider 27's delta → gamma trip takes 10. After rider 10 adds a third alpha → omega trip of 10, the average becomes (12 + 14 + 10) / 3 = 12.00.

Example 2:

Input: checkIn(5, "north", 1), checkOut(5, "south", 5), getAverageTime("north", "south"), checkIn(5, "south", 6), checkOut(5, "north", 12), getAverageTime("south", "north"), getAverageTime("north", "south")

Output: [4.00, 6.00, 4.00]

Explanation: Rider 5 rides north → south in 4, then back south → north in 6. The two directions are tracked separately, so the last query still answers 4.00.

Constraints:

1 ≤ q ≤ 2 * 10⁴ operations
1 ≤ id, t ≤ 10⁶
Station names are single lowercase words of length ≤ 10
Checkout always happens after the matching check-in, and a rider has at most one open journey at a time
Every avg query targets a directed route with at least one completed journey
In this judge every queried average is an exact multiple of 0.25, so two decimals always represent it exactly

Hints:

Two different questions need remembering: "where and when did this rider enter?" (keyed by rider id) and "what happened on this route historically?" (keyed by the station pair). That suggests two hash maps.

An average needs only two aggregates — the sum of durations and their count. You never need to keep the individual journeys.

On checkout, pop the rider's open entry, compute the duration, and fold it into the (total, count) pair stored under the **ordered** key (start, end). Every operation becomes O(1).

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: checkIn(45, "alpha", 3) … getAverageTime("alpha", "omega") after journeys of 12, 14, then 10

Expected output: [13.00, 10.00, 12.00]