915. Metro Trip Averages

Medium3.5 points estimatedDesignHash TableString4 hints
RPby Rohit Parihar

A metro company analyses journey times with the class MetroTrips.

  • checkIn(id, station, t): the card id enters station at time t.
  • checkOut(id, station, t): the same card leaves the system at station at time t, finishing its trip. A trip lasts t minus its check-in time.
  • getAverageTime(origin, dest): returns the average duration, as a double, of all finished trips that started at origin and ended at dest. Trips are directional, so origin to dest differs from dest to origin, and both may name the same station.

Each card has at most one open trip at a time and every checkout matches an earlier check-in of that card. Queries are only made when at least one such finished trip exists. Answers within 1e-6 are accepted.

Example 1

Input:
operations = ["MetroTrips","checkIn","checkOut","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]arguments = [[],[7,"Alder",10],[7,"Birch",25],[8,"Alder",30],[8,"Birch",40],["Alder","Birch"],[9,"Birch",41],[9,"Alder",44],["Birch","Alder"]]
Output:
[null,null,null,null,null,12.5,null,null,3]
Explanation:

The two Alder-to-Birch trips lasted 15 and 10, so the average is 12.5. The only Birch-to-Alder trip lasted 3, so its average is 3.0.

Example 2

Input:
operations = ["MetroTrips","checkIn","checkIn","checkOut","checkOut","getAverageTime"]arguments = [[],[1,"Mill",5],[2,"Mill",6],[2,"Mill",9],[1,"Mill",12],["Mill","Mill"]]
Output:
[null,null,null,null,null,5]
Explanation:

Both trips start and end at Mill and last 3 and 7, giving an average of 5.0. Several travellers can be inside the system at once.

Constraints

1 ≤ id ≤ 106

1 ≤ station.length ≤ 12, lowercase and uppercase letters

0 ≤ t ≤ 106, and a trip ends strictly later than it starts

At most 20000 calls in total

How this problem is judged

Answers
Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
Tolerance
0.000001
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(1) per call
Space
O(open trips + station pairs)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.