Design Underground System

Design Underground System

What is this problem about?

The Design Underground System coding problem involves tracking the travel times of customers in a subway system. You need to implement checkIn(id, stationName, t), checkOut(id, stationName, t), and getAverageTime(startStation, endStation). The average time is calculated for all completed journeys between two specific stations.

Why is this asked in interviews?

Companies like Goldman Sachs and Bloomberg use this to test your ability to maintain multiple types of state. It evaluations your skill in using Hash Tables to store transient data (customers currently checked in) versus aggregated data (total times and counts between station pairs). It’s a practical test of data modeling and clean class design.

Algorithmic pattern used

This problem relies on two Hash Tables.

1. Check-In Map: Maps a customerID to their (startStation, checkInTime). This tracks active journeys.
2. Statistics Map: Maps a (startStation, endStation) pair to a (totalTime, count). This stores the aggregated data needed for averages. When a user checks out, you retrieve their check-in info, calculate the travel duration, and update the statistics map.

Example explanation

1. checkIn(45, "Station A", 3): User 45 starts at A at time 3.
2. checkOut(45, "Station B", 10): User 45 finishes. Trip duration = $10 - 3 = 7$. Update stats for "A-B": total=7, count=1.
3. checkIn(32, "Station A", 8): User 32 starts.
4. checkOut(32, "Station B", 11): Trip duration = 3. Update stats for "A-B": total=10 ($7+3$), count=2.
5. getAverageTime("Station A", "Station B"): Returns $10 / 2 = 5.0$.

Common mistakes candidates make

• Inefficient Averaging: Storing every single trip duration in a list and recalculating the sum every time getAverageTime is called ($O(N)$). A better way is to maintain a running sum and count ($O(1)$).
• ID Collision: Not removing the customer from the check-in map after they check out, which could lead to errors if the same ID checks in again later.
• String Formatting: Using station names as keys without a clear delimiter (e.g., "A" and "B" as "AB" vs "A-B"), which can cause collisions.

Interview preparation tip

When a problem asks for an "average," always maintain two variables: sum and count. This allows you to return the result instantly without re-traversing the history.