Designing a Multi-Elevator System

Why the elevator problem is a trap

The elevator system is the most-asked machine-coding problem after parking-lot, and it is where strong candidates over-build. Most people start drawing a Building, a Floor, a Door, a Button panel, and 40 minutes later they have a UML diagram and zero scheduling logic. The interviewer does not care about your Door class. They care about one thing: when a hall button is pressed on floor 14 going up, which of your N elevators answers it, and in what order does a moving elevator service the requests it has accumulated — including the subtle case where a call’s travel direction differs from whether the floor is above or below the car.

So this lesson is organized around that core. We will still build clean entities, but the center of gravity is the scheduler (SCAN/LOOK) and the hall-call dispatch (which car). Get those two right and the rest is plumbing.

In an interview, say this out loud early: “There are two scheduling decisions here — (1) which elevator should answer a hall call, and (2) once a car has a set of target floors, what order does it visit them. And the trap inside (2) is that a hall call carries a requested direction, so a ‘floor 2 going DOWN’ call must be served on a down-sweep even if the car is below floor 2.” That single sentence signals seniority.

Step 1 — Clarify requirements (don’t skip)

Spend 2-3 minutes here. Ask, then state your assumptions. The functional set is large; only a few requirements actually change the design.

Functional (the obvious ones):

• Multiple floors, multiple elevator cars in one building.
• Two kinds of requests: hall calls (a person on a floor presses up/down) and car calls (a person inside presses a destination floor).
• Cars move up/down, open/close doors, stop at floors.

The requirements that actually matter (ask these):

Out of scope (say so explicitly): door mechanics hardware, maintenance-mode UI, fire-service override protocol (mention it as an extensibility hook), emergency-stop wiring. Naming them and deferring them is better than ignoring them.

Step 2 — Core entities and responsibilities

Keep the class count small. Each class earns its place by owning one decision.

• Direction — enum: UP, DOWN, IDLE. Central to the whole problem; it is the state that makes SCAN/LOOK work, and it is carried by every hall call.
• Request — a single demand. A hall call has floor + a real travel direction (the button pressed). A car call has floor and no meaningful direction (you’re already moving with the car). Modeling both as Request with a source keeps dispatch and routing uniform.
• Elevator (the car) — owns its currentFloor, direction, state, capacity, load, and its own sorted sets of target floors. It knows how to compute its next stop (a pure peek), to advance() its direction/state, and to step() one floor. It does NOT decide which hall calls belong to it — that’s the controller’s job — but it does answer canAccept and costFor so the controller can score it.
• ElevatorController (the dispatcher) — owns the list of cars. Receives hall calls, runs the dispatch cost function (delegating per-car scoring to costFor) to pick a car, and drives the simulation tick. This is the brain.
• Building (optional) — just holds floor count and the controller. Often unnecessary; mention it, don’t over-invest.

The key design move: car calls go straight onto the target car (you’re already inside it, so the call inherits the car’s travel direction), while hall calls go to the controller, which assigns them to exactly one car and forwards the call’s requested direction so the car routes it onto the correct sweep. This split — and the propagation of direction — is the single most important modeling decision in the problem.

Step 3 — Class diagram (ASCII UML)

                    +----------------------------+
                    |     ElevatorController     |
                    +----------------------------+
                    | - elevators: List<Elevator>|
                    | - pending: Queue<Request>  |   (hall calls awaiting assignment)
                    +----------------------------+
                    | + requestHallCall(req)     |
                    | + requestCarCall(id,floor) |
                    | + dispatch(req): Elevator?  |  <-- the "which car" decision
                    | + step()                   |   <-- advance simulation one tick
                    +----------------------------+
                               | 1
                               | *  manages / scores via costFor
                               v
        +-------------------------------------------------+
        |                   Elevator                      |
        +-------------------------------------------------+
        | - id: int                                       |
        | - currentFloor: int                             |
        | - direction: Direction                          |
        | - state: ElevatorState                          |
        | - capacity: int                                 |
        | - load: int                                     |
        | - upStops: SortedSet<int>   (served ascending)  |
        | - downStops: SortedSet<int> (served descending) |
        | - dwell: int                (door-open ticks)   |
        +-------------------------------------------------+
        | + addStop(floor, callDir)                       |  <-- callDir routes the sweep
        | + peekNextStop(): Optional<int>   (pure query)  |  <-- NO mutation (SCAN/LOOK)
        | + advance()                       (flip dir/st) |  <-- the ONLY state transition
        | + step()                          (move 1 floor)|
        | + canAccept(req): bool            (capacity/svc)|
        | + costFor(req): int               (dispatch bid)|
        +-------------------------------------------------+

   enum Direction { UP, DOWN, IDLE }
   enum ElevatorState { MOVING, DOORS_OPEN, IDLE, OUT_OF_SERVICE }

        +--------------------------+
        |        Request           |
        +--------------------------+
        | + floor: int             |
        | + direction: Direction   | (IDLE for a car call)
        | + source: Source         | { HALL_CALL, CAR_CALL }
        +--------------------------+

   enum Source { HALL_CALL, CAR_CALL }

The two sorted collections (upStops, downStops) per car are the heart of the LOOK algorithm: while heading up, you keep visiting the smallest remaining up-stop at-or-above you; when none remain above, you flip direction and drain downStops from the top. A stop’s set membership is decided by the call’s service direction, not merely by floor-vs-current — that is the crux fixed in Step 4.

Step 4 — The direction-aware SCAN / LOOK scheduler

SCAN (“elevator algorithm”) sweeps in one direction servicing every request in its path, then reverses. LOOK is the practical variant: instead of running to the physical end of the shaft, you reverse as soon as there are no further requests in the current direction. Real elevators use LOOK. Say “LOOK” in the interview and explain it’s SCAN-without-the-wasteful-overscan.

The bug everyone writes — and the fix

The naive routing rule is “if floor > currentFloor → upStops, else downStops.” This is wrong, and it is precisely the defect this problem is designed to expose. Counterexample: a car at floor 3 moving UP gets a hall call “floor 8, going DOWN.” Floor 8 is above 3, so naive routing drops it into upStops and the car stops at 8 during its up-sweep — picking up someone who wants to go down, then carrying them further up. Wrong.

The fix: route by the call’s service direction, falling back to floor-vs-current only for car calls (which have no independent direction):

• A hall call with UP → upStops (served on an up-sweep), regardless of whether the floor is above or below the car.
• A hall call with DOWN → downStops, served on a down-sweep — so “floor 8 going down” from a car at floor 3 lands in downStops and is served on the return sweep after the car tops out.
• A car call (no direction) → routed by floor-vs-current, because you board moving with the car.

Per car, the pure peek rule for peekNextStop() (no mutation):

1. If direction == UP: next stop is the smallest floor in upStops that is >= currentFloor. If none, the peek reports what a down-sweep would yield (largest in downStops); the actual flip happens only in advance().
2. If direction == DOWN: symmetric — largest floor in downStops <= currentFloor, else fall through to an up-sweep.
3. If both sets empty: no next stop.

enum Direction { UP, DOWN, IDLE }
enum ElevatorState { MOVING, DOORS_OPEN, IDLE, OUT_OF_SERVICE }
enum Source { HALL_CALL, CAR_CALL }
interface Request { floor: number; direction: Direction; source: Source; }

const DWELL_TICKS = 1; // ticks the door stays open per stop (explicit, not an accident)

class Elevator {
private upStops = new Set<number>();   // served ascending
private downStops = new Set<number>(); // served descending
private dwell = 0;

constructor(
  readonly id: number,
  public currentFloor = 0,
  public direction: Direction = Direction.IDLE,
  public state: ElevatorState = ElevatorState.IDLE,
  public load = 0,
  readonly capacity = 10,
) {}

// callDir is the SERVICE direction: UP/DOWN for a hall call, IDLE for a car call.
addStop(floor: number, callDir: Direction = Direction.IDLE): void {
  // Same-floor request: if we're parked here (IDLE or already at a stop with
  // doors open), open the doors now instead of dropping the floor into a stop set.
  // Gate on the elevator STATE directly — never compare it to a Direction value.
  if (floor === this.currentFloor &&
      (this.state === ElevatorState.IDLE || this.state === ElevatorState.DOORS_OPEN)) {
    this.state = ElevatorState.DOORS_OPEN;
    this.dwell = DWELL_TICKS;
    return;
  }
  const target =
    callDir === Direction.UP   ? this.upStops :
    callDir === Direction.DOWN ? this.downStops :
    (floor > this.currentFloor ? this.upStops : this.downStops); // car call fallback
  target.add(floor);
  if (this.direction === Direction.IDLE)
    this.direction = (target === this.upStops) ? Direction.UP : Direction.DOWN;
}

// PURE query: no field is mutated. Safe for the dispatcher to probe.
peekNextStop(): number | null {
  if (this.direction === Direction.UP || this.direction === Direction.IDLE) {
    const above = [...this.upStops].filter(f => f >= this.currentFloor);
    if (above.length) return Math.min(...above);
    if (this.downStops.size) return Math.max(...this.downStops); // reverse target
    if (this.upStops.size) return Math.min(...this.upStops);
  } else { // DOWN
    const below = [...this.downStops].filter(f => f <= this.currentFloor);
    if (below.length) return Math.max(...below);
    if (this.upStops.size) return Math.min(...this.upStops);     // reverse target
    if (this.downStops.size) return Math.max(...this.downStops);
  }
  return null;
}

// The ONLY method that mutates direction/state during scheduling.
private advance(): void {
  if (this.direction === Direction.UP) {
    if (![...this.upStops].some(f => f >= this.currentFloor) && this.downStops.size)
      this.direction = Direction.DOWN;
  } else if (this.direction === Direction.DOWN) {
    if (![...this.downStops].some(f => f <= this.currentFloor) && this.upStops.size)
      this.direction = Direction.UP;
  }
  if (this.upStops.size === 0 && this.downStops.size === 0) {
    this.direction = Direction.IDLE;
    this.state = ElevatorState.IDLE;
  }
}

step(): void {
  if (this.state === ElevatorState.DOORS_OPEN) {       // serving a stop
    if (--this.dwell > 0) return;                      // still dwelling
    this.advance();                                    // doors closed; recompute heading
    return;
  }
  this.advance();
  const target = this.peekNextStop();
  if (target === null) { this.state = ElevatorState.IDLE; return; }
  if (target === this.currentFloor) {                  // arrived: open doors, dwell
    this.upStops.delete(target);
    this.downStops.delete(target);
    this.state = ElevatorState.DOORS_OPEN;
    this.dwell = DWELL_TICKS;
    return;
  }
  this.state = ElevatorState.MOVING;
  this.currentFloor += target > this.currentFloor ? 1 : -1;
}

canAccept(req: Request): boolean {
  if (this.state === ElevatorState.OUT_OF_SERVICE) return false;
  if (this.load >= this.capacity) return false;        // full car is skippable
  return true; // extend here for express/restricted-floor eligibility
}

// Lower is better. INF means ineligible. Probes via the PURE peek; never mutates.
costFor(req: Request): number {
  if (!this.canAccept(req)) return Number.POSITIVE_INFINITY;
  const d = Math.abs(this.currentFloor - req.floor);
  if (this.direction === Direction.IDLE) return d + 1;             // ready, tiny penalty
  const onTheWay =
    (this.direction === Direction.UP   && req.floor >= this.currentFloor && req.direction === Direction.UP) ||
    (this.direction === Direction.DOWN && req.floor <= this.currentFloor && req.direction === Direction.DOWN);
  return onTheWay ? d : d + 1000; // must finish sweep + return → expensive
}
}

The C++ version uses std::set::lower_bound/upper_bound/rbegin for O(log n) neighbor lookup — call that out in the interview as the reason a sorted structure beats re-scanning a list each tick. The TS/Python versions filter for brevity; in production you’d use a balanced tree or two heaps.

Why peek/advance are split (command-query separation)

peekNextStop() mutates nothing, so the dispatcher (costFor) can probe a car’s next target without corrupting its heading. All direction/state transitions live in advance(), called exactly once per step(). A method named nextStop() that silently flipped direction would be a maintainability landmine: any logging or cost-estimation caller would change the car’s behavior just by looking at it. Splitting them is the idiomatic fix an SSE reviewer expects.

Door dwell is modeled, not accidental

On arrival, step() deletes the stop, opens the doors (DOORS_OPEN), and sets dwell = DWELL_TICKS. Subsequent ticks decrement the dwell; when it hits zero we close doors and advance(). This makes the “one tick per stop” cost intentional (door-open dwell) rather than an artifact of recomputation, and it uses all four states of the ElevatorState machine. Bump DWELL_TICKS to model slower doors.

Worked trace: the return-sweep behavior

Two cars, 0–9 floors. Car A at floor 3, IDLE. Hall call “floor 8, going DOWN.” Dispatch picks A (idle, cost = |3−8|+1 = 6). We call A.addStop(8, DOWN).

• Naive (buggy) routing would put 8 in upStops → A heads up, stops at 8 on the up-sweep, serving a down-traveler mid-ascent. Wrong.
• Correct routing puts 8 in downStops. With only down-stops, addStop sets direction = DOWN… but 8 > current floor 3, so on a down-sweep there’s nothing at-or-below. advance() sees no down-stop ≤ 3 and an up-stop is absent, so it stays consistent: the car must first ascend to 8, then 8 becomes serviceable on the return (down) sweep.

In an interview, walk this exact trace — a multi-car, mixed-direction trace is what surfaces the routing bug and proves your model honors request.direction.

Step 5 — Dispatch: which car answers a hall call

This is the question the interviewer is really asking. The controller scores every car via costFor and assigns the lowest-cost one. The scoring rules (implemented on Elevator.costFor above, so the diagram, prose, and code agree):

• Same direction, car is “ahead” of the call and call direction matches: cost = distance. Cheapest — it’s a free pickup on the current sweep.
• Idle car: cost = distance + small penalty.
• Opposite direction, already passed, or mismatched call direction: cost = distance + big penalty (must finish the sweep and come back).
• Ineligible (full → load >= capacity, out of service, restricted): cost = ∞ (skip). This is how “a full car must be skippable” is realized.

If no car is eligible (all full), the hall call stays in pending and is retried next tick.

class ElevatorController {
private pending: Request[] = [];
constructor(private elevators: Elevator[], private floors: number) {}

requestHallCall(floor: number, dir: Direction): void {
  this.pending.push({ floor, direction: dir, source: Source.HALL_CALL });
}

// car call: routed directly to the car you're standing in (no service direction)
requestCarCall(carId: number, floor: number): void {
  this.elevators.find(e => e.id === carId)?.addStop(floor, Direction.IDLE);
}

dispatch(req: Request): Elevator | null {
  let best: Elevator | null = null;
  let bestCost = Number.POSITIVE_INFINITY;
  for (const e of this.elevators) {
    const c = e.costFor(req);               // pure: does not mutate e
    if (c < bestCost) { bestCost = c; best = e; }
  }
  return best;
}

step(): void {
  // 1) try to assign everything pending (skip if all cars ineligible)
  const stillPending: Request[] = [];
  for (const req of this.pending) {
    const car = this.dispatch(req);
    if (car) car.addStop(req.floor, req.direction); // forwards the CALL direction
    else stillPending.push(req);
  }
  this.pending = stillPending;
  // 2) advance every car one tick
  for (const e of this.elevators) e.step();
}
}

Step 6 — Edge cases interviewers probe

Step 7 — Patterns that naturally appear

You should name these only where they genuinely fit — don’t pattern-drop.

• Strategy — the dispatch cost function is a DispatchStrategy. Swapping “nearest car” for “minimize total wait” or “zone-based” is a strategy swap. Mention this when asked “what if the scheduling goal changes?”
• State — ElevatorState (MOVING / DOORS_OPEN / IDLE / OUT_OF_SERVICE) is a small state machine; step() is the transition driver. A full State pattern (one class per state) is usually over-engineering here — say so.
• Command — each Request is a reified command queued and dispatched; the pending queue is a command buffer.
• Observer (extensibility) — floor displays / a monitoring dashboard subscribe to car position changes.

Step 8 — Concurrency and thread-safety

The summary promised this; here’s the SSE-level discussion.

In a real system, hall-call requests arrive on arbitrary threads (button-press handlers, an API), while a clock thread drives step(). Two concerns:

1. Pending-queue contention. requestHallCall (producer) and step (consumer) touch pending concurrently. Guard it — a lock around enqueue/drain, or a lock-free/concurrent queue (ConcurrentLinkedQueue / std::mutex-guarded std::deque).
2. Car-state mutation during scoring. dispatch reads each car’s fields while step() may be mutating them on the clock thread. Because scoring is a pure peek, the danger is only a torn read, not corruption. The clean model: single-writer tick loop — all mutation (step, addStop application) happens on the clock thread; external requests only enqueue into the guarded pending queue, and assignment happens inside step(). This collapses the problem to one writer and removes most locking.

Recommended interview answer: “I’d make the tick loop the single writer. External callers only push onto a thread-safe pending queue; the tick thread drains it, dispatches, and advances cars. That gives me one writer per car and a single synchronized boundary — far simpler than locking every car.”

// Single-writer model: external threads ONLY enqueue; tick thread mutates.
class ThreadSafeController {
private pending: Request[] = [];
// In Node a simple array + microtask loop suffices (single-threaded event loop);
// in a worker-thread setup, guard 'pending' with a mutex/Atomics-backed queue.
enqueueHallCall(floor: number, dir: Direction): void {
  this.pending.push({ floor, direction: dir, source: Source.HALL_CALL }); // guard here
}
tick(elevators: Elevator[]): void {           // sole writer
  const drained = this.pending; this.pending = []; // atomic swap under lock
  for (const req of drained) { /* dispatch + addStop */ }
  for (const e of elevators) e.step();
}
}

Step 9 — Extensibility: “what if they ask for X?”

• “Express elevators / restricted floors.” Extend canAccept with an eligibility predicate (servesFloor(floor), isExpress). Dispatch already skips ineligible cars via ∞ cost — no structural change.
• “Change the scheduling goal to minimize total wait.” Swap the cost function (Strategy). costFor becomes one DispatchStrategy implementation; inject another.
• “Fire-service / emergency override.” Add a controller mode that recalls all cars to the lobby and ignores normal dispatch — a global state on the controller, cars transition to a RECALL/OUT_OF_SERVICE-like state.
• “Real weight-based capacity.” Replace integer load/capacity with kilograms; canAccept compares weight. The interface (canAccept) is unchanged — that’s the payoff of having modeled it as a method, not an inline check.
• “Persist / distribute across buildings.” The controller becomes a service; pending becomes a durable queue. The single-writer model maps cleanly onto one partition per building.

Closing interview line: “Every ‘what if’ here is absorbed by one of three seams — canAccept for eligibility, costFor/Strategy for the scheduling goal, and the controller mode for global overrides. I designed those three seams up front precisely so extensions don’t reshape the core.”