Loading page…
Practice problem · medium
A transit feature in a maps app shows how long a trip between two stations usually takes. Riders tap a card in at a station and tap it out at another. The app keeps a running average for each route.
New taps arrive all day, and riders ask for averages at any moment. Each tap and each question must take constant time.
Write run_trips(commands, args).
commands[i] is "in", "out" or "avg", and args[i] holds its numbers."in" has args[i] = [card, station, time]. The card starts a trip at that station and time. A card has at most one open trip at a time."out" has args[i] = [card, station, time]. It always matches the card's open trip. It closes the trip, which took time minus the start time, on the route from the start station to this station."avg" has args[i] = [from, to]. It asks for the average time of the closed trips on the route from from to to, rounded down. When no trip on that route has closed, the answer is -1."avg", in order.Input: commands = ["in", "in", "out", "avg", "out", "avg", "avg"], args = [[1, 10, 0], [2, 10, 3], [1, 20, 8], [10, 20], [2, 20, 13], [10, 20], [20, 10]]
Output: [8, 9, -1]The trace shows the open trips and the route totals.
| Step | Command | Open trips after | Route 10 to 20 (total, trips) | Answer |
|---|---|---|---|---|
| 1 | card 1 in at station 10, time 0 | card 1 | none | |
| 2 | card 2 in at station 10, time 3 | cards 1, 2 | none | |
| 3 | card 1 out at station 20, time 8 | card 2 | 8, 1 | |
| 4 | avg 10 to 20 | card 2 | 8, 1 | 8 |
| 5 | card 2 out at station 20, time 13 | none | 18, 2 | |
| 6 | avg 10 to 20 | none | 18, 2 | 9 |
| 7 | avg 20 to 10 | none | -1 |
Input: commands = ["in", "out", "in", "out", "avg"], args = [[1, 1, 0], [1, 2, 5], [2, 1, 10], [2, 2, 16], [1, 2]]
Output: [5]The two trips took 5 and 6 minutes. The average is 5.5, which rounds down to 5.
Input: commands = ["avg"], args = [[3, 4]]
Output: [-1]No trip has closed on the route 3 to 4.
1 ≤ commands.length = args.length ≤ 100,000"out" matches an open trip of that card.Keeping every closed trip in a list and scanning it for each question costs up to one step for each closed trip. With tens of thousands of trips and tens of thousands of questions, that is billions of steps.
A table of route totals answers a question in one step, and a table of open trips closes a trip in one step.
run_trips · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.