Skip to main content

18. Design Underground System

mediumAsked at Redis

Track passenger check-in/check-out and compute average travel times; Redis uses it to test hash and counter aggregation patterns close to Streams + HINCRBYFLOAT.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement checkIn(id, station, t), checkOut(id, station, t), and getAverageTime(start, end). All operations should run in amortized O(1).

Constraints

  • 1 <= id <= 10^6
  • 1 <= t <= 10^9
  • Up to 2 * 10^4 ops

Examples

Example 1

Input
checkIn(45,'Leyton',3); checkOut(45,'Waterloo',15); getAverageTime('Leyton','Waterloo')
Output
12.0

Approaches

1. Store every trip and average on query

Append trips to a list keyed by (start,end); average on demand.

Time
O(trips) per query
Space
O(trips)
// Map<string, number[]>; getAverage sums and divides on each call.

Tradeoff:

2. Running sum + count per route

Maintain a Map keyed by 'start|end' with {sum, count}. On checkOut add (t - startTime) to its entry. getAverageTime returns sum/count. Mirrors HINCRBYFLOAT + HINCRBY counter hashes in real Redis dashboards.

Time
O(1) per op
Space
O(routes + active passengers)
class UndergroundSystem {
  constructor() {
    this.active = new Map(); // id -> {station, t}
    this.totals = new Map(); // 'a|b' -> {sum, count}
  }
  checkIn(id, station, t) { this.active.set(id, { station, t }); }
  checkOut(id, station, t) {
    const ci = this.active.get(id);
    this.active.delete(id);
    const key = `${ci.station}|${station}`;
    const cur = this.totals.get(key) || { sum: 0, count: 0 };
    cur.sum += t - ci.t;
    cur.count += 1;
    this.totals.set(key, cur);
  }
  getAverageTime(s, e) {
    const cur = this.totals.get(`${s}|${e}`);
    return cur.sum / cur.count;
  }
}

Tradeoff:

Redis-specific tips

Redis interviewers grade for the running-sum-per-route framing because HINCRBYFLOAT is the natural production primitive; mention you'd shard the totals hash by route prefix for very high cardinality.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Design Underground System and other Redis interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →