Design Underground System - Practice Coding Problems

Design Underground System - Problem

Design an UndergroundSystem class that tracks customer travel times between different stations.

Implement these methods:

void checkIn(int id, string stationName, int t) - Customer with card ID checks in at station at time t
void checkOut(int id, string stationName, int t) - Customer checks out from station at time t
double getAverageTime(string startStation, string endStation) - Returns average travel time from start to end station

The system calculates averages from all previous trips between the same start and end stations. All check-ins will have corresponding check-outs, and times are consistent (check-out time > check-in time).

Input & Output

Example 1 — Basic Operations

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

› Output: [null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

💡 Note: System tracks trips: Paradise→Cambridge (14 min), Leyton→Waterloo (15 min initially, then average with 14 min = 12.0 min)

Example 2 — Multiple Routes

$ Input: operations = ["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"], parameters = [[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[11,"Paradise",10],[11,"Cambridge",20],["Paradise","Cambridge"],[12,"Cambridge",22],[12,"Leyton",30],["Cambridge","Leyton"]]

› Output: [null,null,null,5.00000,null,null,10.00000,null,null,8.00000]

💡 Note: Three different routes: Leyton→Paradise (5 min), Paradise→Cambridge (10 min), Cambridge→Leyton (8 min)

Example 3 — Same Route Multiple Times

$ Input: operations = ["UndergroundSystem","checkIn","checkOut","checkIn","checkOut","getAverageTime"], parameters = [[],[1,"A",0],[1,"B",10],[2,"A",5],[2,"B",13],["A","B"]]

› Output: [null,null,null,null,null,9.00000]

💡 Note: Two trips on same route A→B: first takes 10 min, second takes 8 min, average = (10+8)/2 = 9.0

Constraints

1 ≤ id, t ≤ 10⁶
1 ≤ stationName.length, startStation.length, endStation.length ≤ 10
All strings contain only lowercase English letters and digits
There will be at most 2 × 10⁴ calls in total
All calls to checkIn and checkOut are consistent
getAverageTime is called with stations that have at least one trip

Visualization

Tap to expand

Understanding the Visualization

Check In

Passengers tap in with ID at start station

Check Out

Passengers tap out at destination, system records trip

Query Average

System returns average time for any route instantly

Key Takeaway

🎯 Key Insight: Use hash maps for O(1) operations - track active trips separately from route statistics

Asked in

a Amazon 28 f Facebook 15 G Google 12 🍎 Apple 8

The optimal approach uses two hash maps: one to track active trips (id → station, time) and another for route statistics (route → total_time, count). This enables O(1) operations for all methods. Time: O(1), Space: O(P + R) where P is active trips and R is unique routes.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Route Statistics	O(1)	O(P + R)	Track running totals and counts for each route to calculate averages in O(1)
Brute Force - Store All Trips	O(n)	O(n)	Store every individual trip and recalculate averages on each query

Optimized - Route Statistics — Algorithm Steps

Track active trips: id -> (station, time)
Track route stats: route -> (total_time, trip_count)
Calculate average in O(1): total_time / trip_count

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Out

Calculate trip duration and update route statistics

Update Stats

Add duration to running total, increment count

O(1) Query

Return average = total_time / count instantly

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ROUTES 1000
#define MAX_ACTIVE 1000

typedef struct {
    char route[100];
    int totalTime;
    int count;
} RouteStats;

typedef struct {
    int id;
    char station[50];
    int time;
} ActiveTrip;

typedef struct {
    ActiveTrip activeTrips[MAX_ACTIVE];
    int activeCount;
    RouteStats routeStats[MAX_ROUTES];
    int routeCount;
} UndergroundSystem;

UndergroundSystem* createSystem() {
    UndergroundSystem* system = (UndergroundSystem*)malloc(sizeof(UndergroundSystem));
    system->activeCount = 0;
    system->routeCount = 0;
    return system;
}

void checkIn(UndergroundSystem* system, int id, char* stationName, int t) {
    ActiveTrip* trip = &system->activeTrips[system->activeCount++];
    trip->id = id;
    strcpy(trip->station, stationName);
    trip->time = t;
}

void checkOut(UndergroundSystem* system, int id, char* stationName, int t) {
    // Find active trip
    int activeIndex = -1;
    for (int i = 0; i < system->activeCount; i++) {
        if (system->activeTrips[i].id == id) {
            activeIndex = i;
            break;
        }
    }
    
    if (activeIndex == -1) return;
    
    ActiveTrip* trip = &system->activeTrips[activeIndex];
    int duration = t - trip->time;
    
    // Create route string
    char route[100];
    sprintf(route, "%s-%s", trip->station, stationName);
    
    // Find or create route stats
    int routeIndex = -1;
    for (int i = 0; i < system->routeCount; i++) {
        if (strcmp(system->routeStats[i].route, route) == 0) {
            routeIndex = i;
            break;
        }
    }
    
    if (routeIndex == -1) {
        routeIndex = system->routeCount++;
        strcpy(system->routeStats[routeIndex].route, route);
        system->routeStats[routeIndex].totalTime = 0;
        system->routeStats[routeIndex].count = 0;
    }
    
    system->routeStats[routeIndex].totalTime += duration;
    system->routeStats[routeIndex].count++;
    
    // Remove active trip
    for (int i = activeIndex; i < system->activeCount - 1; i++) {
        system->activeTrips[i] = system->activeTrips[i + 1];
    }
    system->activeCount--;
}

double getAverageTime(UndergroundSystem* system, char* startStation, char* endStation) {
    char route[100];
    sprintf(route, "%s-%s", startStation, endStation);
    
    for (int i = 0; i < system->routeCount; i++) {
        if (strcmp(system->routeStats[i].route, route) == 0) {
            return (double)system->routeStats[i].totalTime / system->routeStats[i].count;
        }
    }
    return 0.0;
}

int main() {
    printf("[null,null,null,null,null,null,10.0,null,null,20.0]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

All operations use hash map lookups and simple arithmetic

✓ Linear Growth

Space Complexity

O(P + R)

P active trips and R unique routes stored

✓ Linear Space

98.5K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Route Statistics — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler