Design Underground System

medium hash map string design

Problem

Implement checkIn(id, station, t), checkOut(id, station, t), and getAverageTime(start, end) that returns the average time of trips that started at start and ended at end.

Input

checkIn(45,'Leyton',3); checkOut(45,'Waterloo',15); checkIn(27,'Leyton',10); checkOut(27,'Waterloo',20); getAverageTime('Leyton','Waterloo')

Output11.0

Trips: 12 and 10 minutes — average 11.

ops (JSON list)

class UndergroundSystem:
    def __init__(self):
        self.start = {}        # id -> (station, t)
        self.totals = {}       # (s, e) -> (sum, count)
    def checkIn(self, id, station, t):
        self.start[id] = (station, t)
    def checkOut(self, id, station, t):
        s, t0 = self.start.pop(id)
        key = (s, station)
        ssum, cnt = self.totals.get(key, (0, 0))
        self.totals[key] = (ssum + t - t0, cnt + 1)
    def getAverageTime(self, s, e):
        ssum, cnt = self.totals[(s, e)]
        return ssum / cnt

class UndergroundSystem {
  constructor() { this.start = new Map(); this.tot = new Map(); }
  checkIn(id, station, t) { this.start.set(id, [station, t]); }
  checkOut(id, station, t) {
    const [s, t0] = this.start.get(id); this.start.delete(id);
    const k = s + ',' + station;
    const cur = this.tot.get(k) || [0, 0];
    this.tot.set(k, [cur[0] + t - t0, cur[1] + 1]);
  }
  getAverageTime(s, e) {
    const [sum, cnt] = this.tot.get(s + ',' + e);
    return sum / cnt;
  }
}

class UndergroundSystem {
    Map start = new HashMap<>();   // id -> {station, t}
    Map tot = new HashMap<>();         // "s->e" -> {sum, count}
    public void checkIn(int id, String station, int t) { start.put(id, new Object[]{station, t}); }
    public void checkOut(int id, String station, int t) {
        Object[] in = start.remove(id);
        String key = in[0] + "->" + station;
        long[] cur = tot.computeIfAbsent(key, k -> new long[2]);
        cur[0] += t - (int) in[1]; cur[1]++;
    }
    public double getAverageTime(String s, String e) { long[] v = tot.get(s + "->" + e); return (double) v[0] / v[1]; }
}

class UndergroundSystem {
    unordered_map> start;
    unordered_map> tot;
public:
    void checkIn(int id, string station, int t) { start[id] = {station, t}; }
    void checkOut(int id, string station, int t) {
        auto [s, t0] = start[id]; start.erase(id);
        auto& p = tot[s + "->" + station];
        p.first += t - t0; p.second++;
    }
    double getAverageTime(string s, string e) {
        auto& p = tot[s + "->" + e]; return (double) p.first / p.second;
    }
};

Explanation

We need the average travel time between two stations, but we never want to store every trip and re-add them on each query. The trick is to keep a running sum and count for each route, so getAverageTime is just one division.

We use two hash maps. start maps a customer id to where and when they checked in. totals maps a route key (startStation, endStation) to a pair: the total time spent on that route and how many trips it covers.

checkIn(id, station, t) simply records (station, t) under that id. checkOut(id, station, t) pops the matching check-in, forms the route key, and adds the trip duration t - t0 into that route's sum while incrementing its count by one.

getAverageTime(s, e) looks up the route's stored (sum, count) and returns sum / count. Because everything is precomputed, all three operations are O(1) on average.

Example: customer 45 rides Leyton→Waterloo in 15 - 3 = 12 minutes; customer 27 rides the same route in 20 - 10 = 10. The route's totals become (22, 2), so the average is 22 / 2 = 11.0.

Time: O(1) per op Space: O(U + T)