22. Design Underground System

mediumAsked at LINE

Design a system that records check-ins and check-outs and reports average travel time between stations — LINE uses this to test event-pairing and rolling-average design, the same shape as their delivery-receipt latency tracker.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Implement the UndergroundSystem class with checkIn(id, stationName, t), checkOut(id, stationName, t), and getAverageTime(startStation, endStation). getAverageTime returns the average travel time between the two stations over all completed trips. Each id checks in and out alternately, and the answer is guaranteed to have at most one valid average.

Constraints

1 <= id, t <= 10^6
Station names are strings of <= 10 characters
All checkOut calls correspond to a prior checkIn.

Examples

Example 1

Input

checkIn(45,"Leyton",3); checkOut(45,"Waterloo",15); getAverageTime("Leyton","Waterloo")

Output

12.0

Example 2

Input

checkIn(10,"A",0); checkOut(10,"B",10); checkIn(20,"A",2); checkOut(20,"B",6); getAverageTime("A","B")

Output

7.0

Approaches

1. Trip log scan

Store every completed trip in a list and scan to compute averages on each query.

Time: O(trips) per query
Space: O(trips)

// trips.push({a,b,delta}); getAverageTime filters + averages -> too slow at scale.

Tradeoff:

2. Two hash maps

checkIns maps id to (station, t). totals maps 'a->b' to (sum, count). On checkout, look up the start, increment totals, drop the checkIn. getAverageTime divides sum by count in O(1).

Time: O(1) per op
Space: O(active + pairs)

class UndergroundSystem {
  constructor() { this.in = new Map(); this.totals = new Map(); }
  checkIn(id, s, t) { this.in.set(id, { s, t }); }
  checkOut(id, e, t) {
    const { s, t: t0 } = this.in.get(id);
    this.in.delete(id);
    const key = s + '->' + e;
    const cur = this.totals.get(key) || { sum: 0, count: 0 };
    cur.sum += t - t0; cur.count++;
    this.totals.set(key, cur);
  }
  getAverageTime(s, e) {
    const cur = this.totals.get(s + '->' + e);
    return cur.sum / cur.count;
  }
}

Tradeoff:

LINE-specific tips

At LINE, frame this as a delivery-receipt latency tracker that pairs send and ack events per chat room — chat fan-out framing wins.

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 LINE interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →