Problem 422172 · medium · Phase 04 Non-Linear Data Structures

Average Ride Times Between Stops

design · hash map · tuples as keys · classes

A tram network records card taps. Design a class RideLog:

  • RideLog() starts empty.
  • tap_in(card, stop, t): card card boards at stop at time t. A card never taps in twice without tapping out in between.
  • tap_out(card, stop, t): the card leaves at stop at time t, completing a trip that started at its last tap-in. A card only taps out after tapping in.
  • average(start, end) returns the mean duration of all completed trips that began at start and ended at end, rounded to 2 decimals with round(x, 2). Direction matters: trips from end to start do not count. If there are no such trips return -1.

Examples

ops:  ["RideLog", "tap_in", "tap_in", "tap_out", "tap_out", "average", "tap_in", "tap_out", "average", "average", "tap_in", "tap_out", "average"]
args: [[], [1, "Elm", 3], [2, "Elm", 8], [1, "Pier", 15], [2, "Pier", 18], ["Elm", "Pier"], [1, "Pier", 20], [1, "Elm", 27], ["Pier", "Elm"], ["Elm", "Oak"], [3, "Elm", 30], [3, "Pier", 43], ["Elm", "Pier"]]
Output: [None, None, None, None, None, 11.0, None, None, 7.0, -1, None, None, 11.67]
Explanation: Elm -> Pier trips took 12 and 10 minutes (mean 11.0); later a 13-minute trip makes it 35 / 3.

Constraints

  • 0 <= t <= 10**6, times of one card are increasing; stop names are short strings
  • Up to 2 * 10**4 calls in total
  • Target: every method in O(1) average time; do not keep a list of all trips

Goals

  • Keep in-progress trips and finished-trip statistics in two separate maps
  • Aggregate with a running (sum, count) pair instead of storing every trip
Starting Python…