Skip to main content

19. Design Underground System

mediumAsked at Rappi

Track passengers checking in and out of stations and report average travel time between any two stations — Rappi frames this as tracking courier check-in/check-out at pickup and drop-off zones to compute average leg-time for ETA models.

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

Problem

Implement UndergroundSystem with checkIn(id, station, t), checkOut(id, station, t), and getAverageTime(startStation, endStation) returning the average travel time between the two stations.

Constraints

  • 1 <= id <= 10^6
  • 1 <= t <= 10^9
  • All check-in/out pairs are valid

Examples

Example 1

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

Example 2

Input
checkIn(27, 'Leyton', 20); checkOut(27, 'Waterloo', 36); getAverageTime('Leyton','Waterloo')
Output
14.0

Approaches

1. Store every trip then sum

Keep a list of all (start,end,duration); compute average by filtering on each query.

Time
O(trips) per query
Space
O(trips)
class UndergroundSystem {
  constructor() { this.trips = []; this.inflight = new Map(); }
  checkIn(id, s, t) { this.inflight.set(id, [s,t]); }
  checkOut(id, e, t) { const [s, st] = this.inflight.get(id); this.trips.push([s,e,t-st]); }
  getAverageTime(a,b) { const ts = this.trips.filter(x=>x[0]===a&&x[1]===b); return ts.reduce((s,x)=>s+x[2],0)/ts.length; }
}

Tradeoff:

2. Aggregate (sum,count) per route

Keep a map keyed by 'start>end' holding running [sum, count]; updates are O(1) and queries are O(1).

Time
O(1) per op
Space
O(routes + active)
class UndergroundSystem {
  constructor() { this.in = new Map(); this.agg = new Map(); }
  checkIn(id, s, t) { this.in.set(id, [s,t]); }
  checkOut(id, e, t) {
    const [s, st] = this.in.get(id); this.in.delete(id);
    const k = `${s}>${e}`;
    const cur = this.agg.get(k) || [0,0];
    cur[0] += t - st; cur[1]++;
    this.agg.set(k, cur);
  }
  getAverageTime(a, b) {
    const [sum, cnt] = this.agg.get(`${a}>${b}`);
    return sum / cnt;
  }
}

Tradeoff:

Rappi-specific tips

Rappi grades for the O(1)-per-query aggregate — their leg-time service runs millions of getAverage calls and cannot scan per query.

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

Practice these live with InterviewChamp.AI →