Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.
Implement the UndergroundSystem class:
void checkIn(int id, string stationName, int t)
id, checks in at the station stationName at time t.void checkOut(int id, string stationName, int t)
id, checks out from the station stationName at time t.double getAverageTime(string startStation, string endStation)
startStation to endStation.startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.startStation to endStation may be different from the time it takes to travel from endStation to startStation.startStation to endStation before getAverageTime is called.You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t1 then checks out at time t2, then t1 < t2. All events happen in chronological order.
Example 1:
Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[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]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15); // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20); // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38); // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12
Example 2:
Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667
Constraints:
1 <= id, t <= 1061 <= stationName.length, startStation.length, endStation.length <= 102 * 104 calls in total to checkIn, checkOut, and getAverageTime.10-5 of the actual value will be accepted.Problem summary: An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another. Implement the UndergroundSystem class: void checkIn(int id, string stationName, int t) A customer with a card ID equal to id, checks in at the station stationName at time t. A customer can only be checked into one place at a time. void checkOut(int id, string stationName, int t) A customer with a card ID equal to id, checks out from the station stationName at time t. double getAverageTime(string startStation, string endStation) Returns the average time it takes to travel from startStation to endStation. The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Design
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"] [[],[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"]]
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"] [[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
design-bitset)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1396: Design Underground System
class UndergroundSystem {
private Map<Integer, Integer> ts = new HashMap<>();
private Map<Integer, String> names = new HashMap<>();
private Map<String, int[]> d = new HashMap<>();
public UndergroundSystem() {
}
public void checkIn(int id, String stationName, int t) {
ts.put(id, t);
names.put(id, stationName);
}
public void checkOut(int id, String stationName, int t) {
String key = names.get(id) + "-" + stationName;
int[] v = d.getOrDefault(key, new int[2]);
v[0] += t - ts.get(id);
v[1]++;
d.put(key, v);
}
public double getAverageTime(String startStation, String endStation) {
String key = startStation + "-" + endStation;
int[] v = d.get(key);
return (double) v[0] / v[1];
}
}
/**
* Your UndergroundSystem object will be instantiated and called as such:
* UndergroundSystem obj = new UndergroundSystem();
* obj.checkIn(id,stationName,t);
* obj.checkOut(id,stationName,t);
* double param_3 = obj.getAverageTime(startStation,endStation);
*/
// Accepted solution for LeetCode #1396: Design Underground System
type UndergroundSystem struct {
ts map[int]pair
d map[station][2]int
}
func Constructor() UndergroundSystem {
return UndergroundSystem{
ts: make(map[int]pair),
d: make(map[station][2]int),
}
}
func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) {
this.ts[id] = pair{t, stationName}
}
func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) {
p := this.ts[id]
s := station{p.a, stationName}
if _, ok := this.d[s]; !ok {
this.d[s] = [2]int{t - p.t, 1}
} else {
this.d[s] = [2]int{this.d[s][0] + t - p.t, this.d[s][1] + 1}
}
}
func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
s := station{startStation, endStation}
return float64(this.d[s][0]) / float64(this.d[s][1])
}
type station struct {
a string
b string
}
type pair struct {
t int
a string
}
/**
* Your UndergroundSystem object will be instantiated and called as such:
* obj := Constructor();
* obj.CheckIn(id,stationName,t);
* obj.CheckOut(id,stationName,t);
* param_3 := obj.GetAverageTime(startStation,endStation);
*/
# Accepted solution for LeetCode #1396: Design Underground System
class UndergroundSystem:
def __init__(self):
self.ts = {}
self.d = {}
def checkIn(self, id: int, stationName: str, t: int) -> None:
self.ts[id] = (t, stationName)
def checkOut(self, id: int, stationName: str, t: int) -> None:
t0, station = self.ts[id]
x = self.d.get((station, stationName), (0, 0))
self.d[(station, stationName)] = (x[0] + t - t0, x[1] + 1)
def getAverageTime(self, startStation: str, endStation: str) -> float:
x = self.d[(startStation, endStation)]
return x[0] / x[1]
# Your UndergroundSystem object will be instantiated and called as such:
# obj = UndergroundSystem()
# obj.checkIn(id,stationName,t)
# obj.checkOut(id,stationName,t)
# param_3 = obj.getAverageTime(startStation,endStation)
// Accepted solution for LeetCode #1396: Design Underground System
use std::collections::HashMap;
#[derive(Default)]
struct UndergroundSystem {
time: HashMap<String, HashMap<String, (i32, i32)>>,
customer: HashMap<i32, (String, i32)>,
}
impl UndergroundSystem {
fn new() -> Self {
UndergroundSystem::default()
}
fn check_in(&mut self, id: i32, start_station: String, start_t: i32) {
self.customer.insert(id, (start_station, start_t));
}
fn check_out(&mut self, id: i32, end_station: String, end_t: i32) {
let (start_station, start_t) = self.customer.remove(&id).expect("in");
let (sum, count) = self
.time
.entry(start_station)
.or_default()
.entry(end_station)
.or_default();
*sum += end_t - start_t;
*count += 1;
}
fn get_average_time(&mut self, start_station: String, end_station: String) -> f64 {
let (sum, count) = self
.time
.entry(start_station)
.or_default()
.entry(end_station)
.or_default();
*sum as f64 / *count as f64
}
}
#[test]
fn test() {
use assert_approx_eq::assert_approx_eq;
let mut obj = UndergroundSystem::new();
obj.check_in(45, "Leyton".to_string(), 3);
obj.check_in(32, "Paradise".to_string(), 8);
obj.check_in(27, "Leyton".to_string(), 10);
obj.check_out(45, "Waterloo".to_string(), 15);
obj.check_out(27, "Waterloo".to_string(), 20);
obj.check_out(32, "Cambridge".to_string(), 22);
let t = obj.get_average_time("Paradise".to_string(), "Cambridge".to_string());
assert_approx_eq!(t, 14.0);
let t = obj.get_average_time("Leyton".to_string(), "Waterloo".to_string());
assert_approx_eq!(t, 11.0);
obj.check_in(10, "Leyton".to_string(), 24);
let t = obj.get_average_time("Leyton".to_string(), "Waterloo".to_string());
assert_approx_eq!(t, 11.0);
obj.check_out(10, "Waterloo".to_string(), 38);
let t = obj.get_average_time("Leyton".to_string(), "Waterloo".to_string());
assert_approx_eq!(t, 12.0);
}
// Accepted solution for LeetCode #1396: Design Underground System
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1396: Design Underground System
// class UndergroundSystem {
// private Map<Integer, Integer> ts = new HashMap<>();
// private Map<Integer, String> names = new HashMap<>();
// private Map<String, int[]> d = new HashMap<>();
//
// public UndergroundSystem() {
// }
//
// public void checkIn(int id, String stationName, int t) {
// ts.put(id, t);
// names.put(id, stationName);
// }
//
// public void checkOut(int id, String stationName, int t) {
// String key = names.get(id) + "-" + stationName;
// int[] v = d.getOrDefault(key, new int[2]);
// v[0] += t - ts.get(id);
// v[1]++;
// d.put(key, v);
// }
//
// public double getAverageTime(String startStation, String endStation) {
// String key = startStation + "-" + endStation;
// int[] v = d.get(key);
// return (double) v[0] / v[1];
// }
// }
//
// /**
// * Your UndergroundSystem object will be instantiated and called as such:
// * UndergroundSystem obj = new UndergroundSystem();
// * obj.checkIn(id,stationName,t);
// * obj.checkOut(id,stationName,t);
// * double param_3 = obj.getAverageTime(startStation,endStation);
// */
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.