Design Underground System

Explanation & Solution

Practice Problem

Description

Design a system to track transit times between stations and compute average travel times.

Implement a function that processes an array of operations and an array of arguments:

"UndergroundSystem" — Initializes the system.
"checkIn" — A customer with customerId checks in at stationName at time t.
"checkOut" — A customer with customerId checks out at stationName at time t.
"getAverageTime" — Returns the average travel time from startStation to endStation (rounded to 5 decimal places).

Customers are guaranteed to check in before checking out, and each customer checks in only once at a time.

Input:operations = ["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"], args = [[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],[10,"Leyton",24],[10,"Waterloo",38],["Leyton","Waterloo"]]

UndergroundSystem

checkIn

checkOut

getAverageTime

checkIn

checkOut

getAverageTime

Output:[null,null,null,null,null,null,null,14.0,null,null,12.0]

null

Explanation: Paradise→Cambridge: one trip of 14 mins → avg 14.0. Leyton→Waterloo: trips of 12 and 14 mins (avg=13)... wait — trips: 45: 15-3=12, 27: 20-10=10, 10: 38-24=14. Leyton→Waterloo: (12+10+14)/3=12.0.

Constraints

1 <= id, t <= 10^6
1 <= stationName.length <= 10
At most 2 * 10^4 calls to checkIn, checkOut, and getAverageTime
All getAverageTime calls use valid startStation/endStation routes that have been traveled

Approach

Custom Data Structures pattern

1. Two Hash Maps

checkIns: maps customerId → [stationName, timestamp] for in-progress journeys
trips: maps "startStation,endStation" → [totalTime, count] for completed journeys

2. Implement CheckIn

Record the customer's starting station and time in the checkIns map
At most one open check-in per customer at any time

3. Implement CheckOut

Retrieve the check-in info from checkIns, then remove it
Compute trip duration: t - startTime
Accumulate the duration and count into the trips map using a composite key "start,end"

4. Implement GetAverageTime

Look up the total time and count for the route
Return total / count

5. Composite Key for Routes

Using "startStation,endStation" as a string key uniquely identifies each route
Avoid using a nested map for simplicity

Key Insight

Separate the problem into two concerns: tracking in-progress journeys and accumulating completed trip statistics
Clean up checkIns on checkout to save memory

Time

O(1) for all operations

Space

O(customers + routes)

Solution Code

Snapshot Array

Design Twitter