Design Underground System
Asked at Rippling
Problem
Design an underground system that tracks passenger check-in and check-out times at stations and computes average travel time between station pairs.
Asked At
| Company | Difficulty | |
|---|---|---|
| Rippling | Medium | View all Rippling questions → |
How to Think About It
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.
Use two HashMaps: one mapping checkInID to (stationName, time) for active trips, and another mapping (startStation, endStation) to a list of travel times.
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.
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.
The route key can be a tuple or a concatenated string like startStation + "->" + endStation for HashMap use.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 / countFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.