1396. Design Underground System

At a Glance

Topic: system-design-coding
Pattern: Hash maps (trip state + rolling aggregates)
Difficulty: Medium
Companies: DoorDash, Uber, Lyft, Amazon, Bloomberg
Frequency: Medium
LeetCode: 1396

Problem (one-liner)

Simulate turnstiles: customers check in at a station and time, later check out at another station and time; answer rolling average travel duration between station pairs.

Recognition Cues

Open trips keyed by id
Aggregate statistics keyed by (startStation -> endStation)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Optimal — map customerId → active {entryStation, entryTime}; map routeKey → {totalMinutes, tripCount} — O(1) per event amortized.

Optimal Solution

Go

package main

import "fmt"

// UndergroundSystem API:
// - Constructor()
// - void checkIn(id int, stationName string, timestamp int)
// - void checkOut(id int, stationName string, timestamp int)
// - float64 getAverageTime(startStation string, endStation string)

type activeTrip struct {
	entryStation  string
	entryTimestamp int
}

type routeStats struct {
	totalMinutes int
	tripCount    int
}

type UndergroundSystem struct {
	openTrips map[int]activeTrip
	stats     map[string]routeStats
}

func Constructor() UndergroundSystem {
	return UndergroundSystem{
		openTrips: map[int]activeTrip{},
		stats:     map[string]routeStats{},
	}
}

func (system *UndergroundSystem) CheckIn(customerId int, stationName string, timestamp int) {
	system.openTrips[customerId] = activeTrip{
		entryStation:   stationName,
		entryTimestamp: timestamp,
	}
}

func (system *UndergroundSystem) CheckOut(customerId int, stationName string, timestamp int) {
	trip := system.openTrips[customerId]
	delete(system.openTrips, customerId)
	routeKey := fmt.Sprintf("%s>%s", trip.entryStation, stationName)
	aggregate := system.stats[routeKey]
	duration := timestamp - trip.entryTimestamp
	aggregate.totalMinutes += duration
	aggregate.tripCount++
	system.stats[routeKey] = aggregate
}

func (system *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
	routeKey := fmt.Sprintf("%s>%s", startStation, endStation)
	aggregate := system.stats[routeKey]
	return float64(aggregate.totalMinutes) / float64(aggregate.tripCount)
}

JavaScript

class UndergroundSystem {
	constructor() {
		this.openTrips = new Map();
		this.stats = new Map();
	}

	checkIn(customerId, stationName, timestamp) {
		this.openTrips.set(customerId, {
			entryStation: stationName,
			entryTimestamp: timestamp,
		});
	}

	checkOut(customerId, stationName, timestamp) {
		const trip = this.openTrips.get(customerId);
		this.openTrips.delete(customerId);
		const routeKey = `${trip.entryStation}>${stationName}`;
		const duration = timestamp - trip.entryTimestamp;
		const prior = this.stats.get(routeKey) || { totalMinutes: 0, tripCount: 0 };
		prior.totalMinutes += duration;
		prior.tripCount += 1;
		this.stats.set(routeKey, prior);
	}

	getAverageTime(startStation, endStation) {
		const routeKey = `${startStation}>${endStation}`;
		const aggregate = this.stats.get(routeKey);
		return aggregate.totalMinutes / aggregate.tripCount;
	}
}