MediumHash TableStringDesignUpdated Sep 2026

1396. Design Underground System

Asked at Rippling

Difficulty

Medium

Time

O(1) per operation

Space

O(n)

Pattern

Hash Table

Companies

1

Problem

Design a class that tracks passengers moving through an underground train system, and answers questions about average travel times.

You must support three operations. checkIn(id, stationName, t) records that the passenger with card id entered at stationName at time t. checkOut(id, stationName, t) records that the same passenger left at stationName at time t. A passenger is inside the system between these two calls, and each passenger can only be checked in at one station at a time.

getAverageTime(startStation, endStation) returns the average travel time over all completed trips that started at startStation and ended at endStation. Only direct trips count: a check-in at the start station followed later by a check-out at the end station for the same passenger. The reverse direction is a separate route with its own average. You may assume at least one such trip already happened before the query.

All calls are consistent: check-out times are always later than the matching check-in time, and events arrive in time order.

Two records, one route

checkIn(45, Leyton, 3)checkOut(45, Waterloo, 15)duration = 15 - 3 = 12route Leyton->Waterloo gets 12The passenger id links the two events, and the timedifference becomes one trip.
A trip is created by matching a check-in with the later check-out of the same passenger, and it is filed under the station pair.

Constraints

  • ●1 <= id, t <= 10^6
  • ●1 <= stationName.length, startStation.length, endStation.length <= 10
  • ●Station names contain only uppercase and lowercase English letters and digits.
  • ●At most 2 * 10^4 total calls to checkIn, checkOut, and getAverageTime.
  • ●Answers within 10^-5 of the exact value are accepted.
  • ●getAverageTime is only called for a route that already has at least one completed trip.

Examples

Example 1
Input["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"] [[],[45,"Leyton",3],[32,"P
Output[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]
WhyPassenger 45 rides Leyton→Waterloo in 15-3=12, passenger 27 rides the same route in 20-10=10, so that route averages (12+10)/2=11. Passenger 32 rides Paradise→Cambridge in 22-8=14, and that route has only one trip, so the average is 14. Later passenger 10 adds a 38-24=14 ride on Leyton→Waterloo, mak
Example 2
Input["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"] [[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"
Output[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
WhyThree passengers all travel Leyton→Paradise, taking 5, 6 and 9 minutes. The running averages are 5/1=5, (5+6)/2=5.5, and (5+6+9)/3=6.66667.

Asked At

1 companies
CompanyDifficulty
RipplingMediumView all Rippling questions →

How to Think About It

1

Brute force: store all check-in and check-out records in lists, then filter and average on each getAverageTime call. Each query is O(m) where m is total records.

2

Use two HashMaps: one mapping checkInID to (stationName, time) for active trips, and another mapping (startStation, endStation) to a list of travel times.

3

On checkIn, store the passenger ID, station, and time in the active-trips map. On checkOut, look up the start info, compute duration, and add to the route map.

4

To get the average in O(1), store a running sum and count per route instead of a list of times. Update sum and count on each checkOut.

5

The route key can be a tuple or a concatenated string like startStation + "->" + endStation for HashMap use.

6

Example: checkIn(45, "Leyton", 3), checkIn(32, "Paradise", 8), checkIn(27, "Leyton", 10). checkOut(45, "Waterloo", 15) -> route "Leyton->Waterloo" gets time 12. checkOut(27, "Waterloo", 20) -> route gets another entry with time 10. getAverageTime("Leyton","Waterloo") = (12+10)/2 = 11.0.

Optimal Approach

Step 1: Maintain checkIns HashMap mapping passenger ID to (stationName, time) for currently checked-in passengers.

Step 2: Maintain routeData HashMap mapping a route string (start->end) to a pair (totalTime, tripCount).

Step 3: checkIn(id, station, t) stores (station, t) in checkIns for the given id.

Step 4: checkOut(id, station, t) retrieves the check-in record, computes duration = t - checkInTime, then updates the route entry: totalTime += duration, tripCount += 1.

Step 5: getAverageTime(start, end) looks up the route key and returns totalTime / tripCount.

Step 6: Example walkthrough: checkIn(10, "A", 3) -> checkIns={10:(A,3)}. checkIn(10, "B", 6) is invalid if 10 is already checked in (clarify with interviewer). checkIn(20, "A", 5) -> checkIns={10:(A,3), 20:(A,5)}. checkOut(10, "B", 9) -> route "A->B" gets totalTime=4, count=1. checkOut(20, "B", 12) -> route "A->B" gets totalTime=11, count=2. getAverageTime("A","B") = 11/2 = 5.5.

Time: O(1) per operation. Space: O(n) where n is the number of active trips plus route entries.

Two hash maps

checkIns (id -> station, time)station, time45Leyton, 327Leyton, 1032Paradise, 8Before any check-out, three passengers are waiting inside thesystem.routes (start->end -> sum, count)sumcountLeyton->Waterloo222Paradise->Cambridge141After the check-outs, each route stores the total time and how manytrips produced it.checkOut: sum += t - startTime, count += 1getAverageTime: return sum / count
One map holds passengers who are still inside; the other holds a running sum and count for every route.
ComplexityTime O(1) per operationSpace O(n)Each call does a constant number of hash map lookups and updates; n is the number of passengers currently inside plus the number of distinct routes seen.

What Trips People Up in Real Interviews

1

Storing travel times as a plain list and recomputing the average on every query. Store sum and count instead for O(1) average.

2

Forgetting to remove the passenger from the active check-in map after checkOut. This causes stale data and incorrect future lookups.

3

Using the passenger ID as part of the route key for the average. The average should be across all passengers on the same route.

4

Not handling the case where checkOut is called without a matching checkIn. Decide with the interviewer whether to throw or ignore.

5

Confusing the timestamp units. Make sure to compute duration as checkOut time minus checkIn time, not the other way around.

Solution Code

O(1) per operation time
class UndergroundSystem:

    def __init__(self):
        self.check_ins = {}
        self.routes = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_ins[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start_station, start_time = self.check_ins.pop(id)
        route = (start_station, stationName)
        duration = t - start_time
        if route not in self.routes:
            self.routes[route] = [0.0, 0]
        self.routes[route][0] += duration
        self.routes[route][1] += 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        total, count = self.routes[(startStation, endStation)]
        return total / count

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Design Underground System problem?

Design an underground system that tracks passenger check-in and check-out times at stations and computes average travel time between station pairs.

How do you solve Design Underground System?

The optimal approach runs in O(1) per operation time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Design Underground System?

Design Underground System is asked at Rippling. It is a medium difficulty problem.

What are common mistakes on Design Underground System?
  • Storing travel times as a plain list and recomputing the average on every query. Store sum and count instead for `O(1)` average.
  • Forgetting to remove the passenger from the active check-in map after checkOut. This causes stale data and incorrect future lookups.
  • Using the passenger ID as part of the route key for the average. The average should be across all passengers on the same route.
  • Not handling the case where checkOut is called without a matching checkIn. Decide with the interviewer whether to throw or ignore.
  • Confusing the timestamp units. Make sure to compute duration as checkOut time minus checkIn time, not the other way around.