Episode 9 — System Design / 9.6 — LLD Problem Solving

9.6.f — Elevator System

Problem: Design an elevator control system for a building with multiple elevators and floors. The system processes requests (both external hall calls and internal cabin buttons), assigns the optimal elevator, and moves elevators using scheduling algorithms.

Table of Contents

  1. Requirements
  2. Entities and Enums
  3. Class Diagram
  4. Scheduling Algorithms
  5. State Machine
  6. Sequence Flow
  7. Complete Implementation
  8. Usage Walkthrough
  9. Edge Cases
  10. Key Takeaways

Requirements

Functional Requirements

  1. A building has N floors and M elevators.
  2. Each floor has hall buttons (UP and DOWN) for external requests.
  3. Each elevator has internal buttons (one per floor) for destination requests.
  4. The controller assigns the optimal elevator to each external request.
  5. Elevators move UP or DOWN, stopping at requested floors.
  6. Three scheduling algorithms: FCFS, SCAN (elevator algorithm), and LOOK.
  7. Display the current floor and direction of each elevator.

Non-Functional Requirements

  • The system should minimize average wait time.
  • Easy to swap scheduling algorithms.
  • Support adding/removing elevators (maintenance mode).

Out of Scope

  • Weight/capacity limits.
  • Emergency mode / fire alarm.
  • VIP or express elevators.

Entities and Enums

┌────────────────────┐    ┌────────────────────┐    ┌────────────────────┐
│    Direction        │    │  ElevatorStatus     │    │   RequestType       │
│────────────────────│    │────────────────────│    │────────────────────│
│  UP                 │    │  IDLE               │    │  EXTERNAL           │
│  DOWN               │    │  MOVING_UP          │    │  INTERNAL           │
│  IDLE               │    │  MOVING_DOWN        │    └────────────────────┘
└────────────────────┘    │  MAINTENANCE         │
                           └────────────────────┘

Class Diagram

┌──────────────────────────────────────────────────────────────────────┐
│                      ElevatorController                               │
│──────────────────────────────────────────────────────────────────────│
│ - elevators: Elevator[]                                               │
│ - totalFloors: number                                                 │
│ - scheduler: SchedulingStrategy                                       │
│ - pendingRequests: Request[]                                          │
│──────────────────────────────────────────────────────────────────────│
│ + requestElevator(floor, direction): void      (external hall call)   │
│ + selectFloor(elevatorId, floor): void         (internal button)      │
│ + step(): void                                 (advance simulation)   │
│ + setScheduler(strategy): void                                        │
│ + getStatus(): object[]                                               │
└───────────────────┬──────────────────────────┬───────────────────────┘
                    │ has-many                  │ has-a
                    ▼                           ▼
┌────────────────────────────────┐  ┌───────────────────────────────────┐
│          Elevator               │  │  SchedulingStrategy (interface)    │
│────────────────────────────────│  │───────────────────────────────────│
│ - id: string                    │  │ + assignElevator(request,          │
│ - currentFloor: number          │  │     elevators): Elevator           │
│ - direction: Direction          │  └──────────┬───────────────────────┘
│ - status: ElevatorStatus        │             │ implemented by
│ - destinations: SortedSet       │    ┌────────┼────────┬──────────┐
│ - doorsOpen: boolean            │    ▼        ▼        ▼          ▼
│────────────────────────────────│  FCFS    SCANScheduler  LOOKScheduler
│ + addDestination(floor): void   │  Scheduler
│ + move(): void                  │
│ + openDoors(): void             │
│ + closeDoors(): void            │
│ + hasStops(): boolean           │
│ + getNextStop(): number | null  │
└────────────────────────────────┘

┌────────────────────────────────┐
│          Request                │
│────────────────────────────────│
│ - floor: number                 │
│ - direction: Direction          │
│ - type: RequestType             │
│ - elevatorId: string | null     │
│ - timestamp: Date               │
└────────────────────────────────┘

Scheduling Algorithms

1. FCFS (First Come, First Served)

Requests arrive: Floor 5 UP, Floor 2 DOWN, Floor 8 UP

Assign the FIRST idle (or nearest idle) elevator to each request
in the order they arrive.

Simple but not optimal — elevator might pass request floors
without stopping.

2. SCAN (Elevator Algorithm)

Elevator at Floor 3, going UP.
Pending: 1, 5, 8, 2, 6

1. Go UP, stopping at all floors in upward direction: 5, 6, 8
2. Reverse to DOWN at top
3. Go DOWN, stopping at: 2, 1
4. Reverse again

Like a disk head scanning in one direction then reversing.

   Floor 8  ───●──────────┐
   Floor 6  ───●           │
   Floor 5  ───●           │
   Floor 3  ─● start       │
   Floor 2  ──────────────●│
   Floor 1  ──────────────●┘

Movement: 3 -> 5 -> 6 -> 8 -> 2 -> 1

3. LOOK (Improved SCAN)

Same as SCAN, but does NOT go to the extreme floor.
Only goes as far as the farthest request in each direction.

Elevator at Floor 3, going UP.
Pending UP: 5, 8     Pending DOWN: 2

SCAN:  3 -> 5 -> 8 -> (goes to top) -> ... -> 2
LOOK:  3 -> 5 -> 8 -> (reverses here) -> 2

LOOK saves unnecessary travel to unneeded floors.

Comparison

AlgorithmStrategyProsCons
FCFSAssign in arrival orderSimple to implementHigh average wait time
SCANSweep up then downFair, no starvationMay travel to empty extremes
LOOKSweep up then down, only to farthest requestMost efficientSlightly more complex

State Machine

                    ┌────────────┐
     ┌─────────────│    IDLE     │◄──────────────────┐
     │             └─────┬──────┘                    │
     │                   │ request received           │
     │                   │ (assign direction)          │
     │      ┌────────────┴───────────┐                │
     │      ▼                        ▼                │
┌──────────────┐            ┌──────────────┐          │
│  MOVING_UP   │            │ MOVING_DOWN  │          │
└──────┬───────┘            └──────┬───────┘          │
       │                           │                  │
       │ arrived at                │ arrived at       │
       │ requested floor           │ requested floor  │
       │                           │                  │
       ▼                           ▼                  │
   [Open doors, wait, close doors]                    │
       │                                              │
       │── more stops in same direction? ──► continue │
       │                                              │
       │── stops in other direction? ──► reverse ─────┘
       │                                              │
       └── no more stops? ──► IDLE ───────────────────┘


  ┌──────────────┐
  │ MAINTENANCE  │  (separate state, no requests accepted)
  └──────────────┘

Sequence Flow

External Request (Hall Call)

  User         Controller        Scheduler         Elevator
    │               │                │                 │
    │── press UP    │                │                 │
    │   at Floor 5 ─►│                │                 │
    │               │── assign() ───►│                 │
    │               │                │── evaluate all ─►│
    │               │                │◄── scores ──────│
    │               │◄── best elev ──│                 │
    │               │                │                 │
    │               │── addDest(5) ───────────────────►│
    │               │                │                 │── moving...
    │               │                │                 │── arrived at 5
    │               │                │                 │── open doors
    │◄── elevator   │                │                 │
    │   arrives     │                │                 │

Complete Implementation

Enums

// ─── Enums ──────────────────────────────────────────────

const Direction = Object.freeze({
  UP: 'UP',
  DOWN: 'DOWN',
  IDLE: 'IDLE',
});

const ElevatorStatus = Object.freeze({
  IDLE: 'IDLE',
  MOVING_UP: 'MOVING_UP',
  MOVING_DOWN: 'MOVING_DOWN',
  MAINTENANCE: 'MAINTENANCE',
});

const RequestType = Object.freeze({
  EXTERNAL: 'EXTERNAL',
  INTERNAL: 'INTERNAL',
});

Request

// ─── Request ────────────────────────────────────────────

class Request {
  constructor(floor, direction, type, elevatorId = null) {
    this.floor = floor;
    this.direction = direction;   // Direction desired (UP/DOWN)
    this.type = type;             // EXTERNAL (hall) or INTERNAL (cabin)
    this.elevatorId = elevatorId; // Only set for internal requests
    this.timestamp = new Date();
  }
}

Elevator

// ─── Elevator ───────────────────────────────────────────

class Elevator {
  constructor(id, totalFloors) {
    this.id = id;
    this.totalFloors = totalFloors;
    this.currentFloor = 1;           // Starts at ground floor
    this.direction = Direction.IDLE;
    this.status = ElevatorStatus.IDLE;
    this.upStops = new Set();        // Floors to stop at going UP
    this.downStops = new Set();      // Floors to stop at going DOWN
    this.doorsOpen = false;
  }

  addDestination(floor) {
    if (floor < 1 || floor > this.totalFloors) {
      throw new Error(`Floor ${floor} is out of range (1-${this.totalFloors}).`);
    }

    if (floor > this.currentFloor) {
      this.upStops.add(floor);
    } else if (floor < this.currentFloor) {
      this.downStops.add(floor);
    }
    // If floor === currentFloor, open doors immediately (handled in step)
  }

  hasStops() {
    return this.upStops.size > 0 || this.downStops.size > 0;
  }

  // Get sorted stops for current direction
  _getSortedUpStops() {
    return [...this.upStops].sort((a, b) => a - b);
  }

  _getSortedDownStops() {
    return [...this.downStops].sort((a, b) => b - a); // descending
  }

  // Move one floor in the current direction
  move() {
    if (this.status === ElevatorStatus.MAINTENANCE) return;

    // Determine direction if idle
    if (this.status === ElevatorStatus.IDLE) {
      if (this.upStops.size > 0) {
        this.status = ElevatorStatus.MOVING_UP;
        this.direction = Direction.UP;
      } else if (this.downStops.size > 0) {
        this.status = ElevatorStatus.MOVING_DOWN;
        this.direction = Direction.DOWN;
      } else {
        return; // Nothing to do
      }
    }

    // Move one step
    if (this.status === ElevatorStatus.MOVING_UP) {
      this.currentFloor++;

      // Check if this is a stop
      if (this.upStops.has(this.currentFloor)) {
        this.upStops.delete(this.currentFloor);
        this._stopAtFloor();
      }

      // Check if we should reverse
      if (this.upStops.size === 0) {
        if (this.downStops.size > 0) {
          this.status = ElevatorStatus.MOVING_DOWN;
          this.direction = Direction.DOWN;
        } else {
          this.status = ElevatorStatus.IDLE;
          this.direction = Direction.IDLE;
        }
      }
    } else if (this.status === ElevatorStatus.MOVING_DOWN) {
      this.currentFloor--;

      // Check if this is a stop
      if (this.downStops.has(this.currentFloor)) {
        this.downStops.delete(this.currentFloor);
        this._stopAtFloor();
      }

      // Check if we should reverse
      if (this.downStops.size === 0) {
        if (this.upStops.size > 0) {
          this.status = ElevatorStatus.MOVING_UP;
          this.direction = Direction.UP;
        } else {
          this.status = ElevatorStatus.IDLE;
          this.direction = Direction.IDLE;
        }
      }
    }
  }

  _stopAtFloor() {
    this.doorsOpen = true;
    console.log(`  [Elevator ${this.id}] Stopped at Floor ${this.currentFloor}. Doors open.`);
    this.doorsOpen = false;
  }

  getStatus() {
    return {
      id: this.id,
      floor: this.currentFloor,
      direction: this.direction,
      status: this.status,
      upStops: [...this.upStops].sort((a, b) => a - b),
      downStops: [...this.downStops].sort((a, b) => a - b),
    };
  }
}

Scheduling Strategies

// ─── Scheduling Strategies ──────────────────────────────

// Base interface
class SchedulingStrategy {
  assignElevator(request, elevators) {
    throw new Error('Not implemented');
  }
}

// ─── FCFS: Assign to the nearest idle elevator ──────────

class FCFSScheduler extends SchedulingStrategy {
  assignElevator(request, elevators) {
    const available = elevators.filter(e => e.status !== ElevatorStatus.MAINTENANCE);
    if (available.length === 0) return null;

    // Prefer idle elevators, then by distance
    let best = null;
    let bestScore = Infinity;

    for (const elevator of available) {
      const distance = Math.abs(elevator.currentFloor - request.floor);
      const idleBonus = elevator.status === ElevatorStatus.IDLE ? 0 : 1000;
      const score = distance + idleBonus;

      if (score < bestScore) {
        bestScore = score;
        best = elevator;
      }
    }

    return best;
  }
}

// ─── SCAN: Prefer elevator moving toward the request ────

class SCANScheduler extends SchedulingStrategy {
  assignElevator(request, elevators) {
    const available = elevators.filter(e => e.status !== ElevatorStatus.MAINTENANCE);
    if (available.length === 0) return null;

    let best = null;
    let bestScore = Infinity;

    for (const elevator of available) {
      const distance = Math.abs(elevator.currentFloor - request.floor);
      let score;

      if (elevator.status === ElevatorStatus.IDLE) {
        // Idle elevators get distance score directly
        score = distance;
      } else if (
        // Moving toward the request in the same direction
        (elevator.status === ElevatorStatus.MOVING_UP &&
          request.direction === Direction.UP &&
          elevator.currentFloor <= request.floor) ||
        (elevator.status === ElevatorStatus.MOVING_DOWN &&
          request.direction === Direction.DOWN &&
          elevator.currentFloor >= request.floor)
      ) {
        // Best case: moving toward request in same direction
        score = distance;
      } else {
        // Moving away or different direction — penalize
        score = distance + 1000;
      }

      if (score < bestScore) {
        bestScore = score;
        best = elevator;
      }
    }

    return best;
  }
}

// ─── LOOK: Same as SCAN but considers current destination set ──

class LOOKScheduler extends SchedulingStrategy {
  assignElevator(request, elevators) {
    const available = elevators.filter(e => e.status !== ElevatorStatus.MAINTENANCE);
    if (available.length === 0) return null;

    let best = null;
    let bestScore = Infinity;

    for (const elevator of available) {
      const distance = Math.abs(elevator.currentFloor - request.floor);
      let score;

      if (elevator.status === ElevatorStatus.IDLE) {
        score = distance;
      } else if (
        (elevator.status === ElevatorStatus.MOVING_UP &&
          request.direction === Direction.UP &&
          elevator.currentFloor <= request.floor)
      ) {
        // Moving up and request is above — great, just add to upStops
        score = distance;
      } else if (
        (elevator.status === ElevatorStatus.MOVING_DOWN &&
          request.direction === Direction.DOWN &&
          elevator.currentFloor >= request.floor)
      ) {
        // Moving down and request is below
        score = distance;
      } else {
        // Calculate how far elevator must travel before it can serve this request
        // (go to farthest stop, reverse, then reach request)
        let detour;
        if (elevator.status === ElevatorStatus.MOVING_UP) {
          const maxUp = elevator.upStops.size > 0
            ? Math.max(...elevator.upStops)
            : elevator.currentFloor;
          detour = (maxUp - elevator.currentFloor) + Math.abs(maxUp - request.floor);
        } else {
          const minDown = elevator.downStops.size > 0
            ? Math.min(...elevator.downStops)
            : elevator.currentFloor;
          detour = (elevator.currentFloor - minDown) + Math.abs(minDown - request.floor);
        }
        score = detour;
      }

      if (score < bestScore) {
        bestScore = score;
        best = elevator;
      }
    }

    return best;
  }
}

ElevatorController

// ─── ElevatorController ─────────────────────────────────

class ElevatorController {
  constructor(totalFloors, numElevators) {
    this.totalFloors = totalFloors;
    this.elevators = [];
    this.scheduler = new LOOKScheduler(); // Default: LOOK
    this.pendingRequests = [];

    for (let i = 1; i <= numElevators; i++) {
      this.elevators.push(new Elevator(`E${i}`, totalFloors));
    }
  }

  setScheduler(strategy) {
    this.scheduler = strategy;
    console.log(`[CONTROLLER] Scheduler set to: ${strategy.constructor.name}`);
  }

  // ── External request (hall button) ────────────────────

  requestElevator(floor, direction) {
    if (floor < 1 || floor > this.totalFloors) {
      throw new Error(`Floor ${floor} out of range.`);
    }

    const request = new Request(floor, direction, RequestType.EXTERNAL);
    const elevator = this.scheduler.assignElevator(request, this.elevators);

    if (!elevator) {
      this.pendingRequests.push(request);
      console.log(`[HALL] Floor ${floor} ${direction} — no elevator available. Queued.`);
      return null;
    }

    elevator.addDestination(floor);
    console.log(
      `[HALL] Floor ${floor} ${direction} -> assigned to Elevator ${elevator.id} ` +
      `(currently at Floor ${elevator.currentFloor})`
    );
    return elevator.id;
  }

  // ── Internal request (cabin button) ───────────────────

  selectFloor(elevatorId, floor) {
    const elevator = this.elevators.find(e => e.id === elevatorId);
    if (!elevator) throw new Error(`Elevator ${elevatorId} not found.`);

    elevator.addDestination(floor);
    console.log(`[CABIN] Elevator ${elevatorId}: passenger selected Floor ${floor}`);
  }

  // ── Simulation: advance one time step ─────────────────
  // Each call moves each elevator one floor (if it has destinations)

  step() {
    for (const elevator of this.elevators) {
      elevator.move();
    }

    // Try to assign pending requests
    const stillPending = [];
    for (const req of this.pendingRequests) {
      const elevator = this.scheduler.assignElevator(req, this.elevators);
      if (elevator) {
        elevator.addDestination(req.floor);
        console.log(`[QUEUE] Assigned pending request Floor ${req.floor} -> ${elevator.id}`);
      } else {
        stillPending.push(req);
      }
    }
    this.pendingRequests = stillPending;
  }

  // ── Run multiple steps ────────────────────────────────

  run(steps) {
    console.log(`\n--- Running ${steps} steps ---`);
    for (let i = 0; i < steps; i++) {
      console.log(`\nStep ${i + 1}:`);
      this.step();
      this._printStatus();
    }
  }

  // ── Status display ────────────────────────────────────

  getStatus() {
    return this.elevators.map(e => e.getStatus());
  }

  _printStatus() {
    for (const e of this.elevators) {
      const s = e.getStatus();
      const stops = [...s.upStops, ...s.downStops];
      console.log(
        `  ${s.id}: Floor ${s.floor} | ${s.status} | ` +
        `Stops: [${stops.length > 0 ? stops.join(', ') : 'none'}]`
      );
    }
  }

  // ── Maintenance ───────────────────────────────────────

  setMaintenance(elevatorId, enabled) {
    const elevator = this.elevators.find(e => e.id === elevatorId);
    if (!elevator) throw new Error(`Elevator ${elevatorId} not found.`);

    if (enabled) {
      elevator.status = ElevatorStatus.MAINTENANCE;
      elevator.direction = Direction.IDLE;
      console.log(`[MAINTENANCE] Elevator ${elevatorId} taken out of service.`);
    } else {
      elevator.status = ElevatorStatus.IDLE;
      console.log(`[MAINTENANCE] Elevator ${elevatorId} back in service.`);
    }
  }
}

Usage Walkthrough

// ─── Demo ───────────────────────────────────────────────

const controller = new ElevatorController(10, 3);
// Building: 10 floors, 3 elevators (E1, E2, E3), all start at Floor 1

// Set LOOK scheduler (default)
controller.setScheduler(new LOOKScheduler());

// ── External requests (hall buttons) ────────────────────

controller.requestElevator(5, Direction.UP);
// Floor 5 UP -> assigned to E1 (nearest idle)

controller.requestElevator(3, Direction.DOWN);
// Floor 3 DOWN -> assigned to E2

controller.requestElevator(8, Direction.UP);
// Floor 8 UP -> assigned to E3

// ── Run simulation ──────────────────────────────────────

controller.run(5);
// Step 1: E1 -> Floor 2, E2 -> Floor 2, E3 -> Floor 2
// Step 2: E1 -> Floor 3, E2 -> Floor 3 (stops, doors open), E3 -> Floor 3
// ...
// Step 4: E1 -> Floor 5 (stops, doors open)

// ── Internal request (passenger in E1 presses Floor 8) ──

controller.selectFloor('E1', 8);

// ── More external requests during movement ──────────────

controller.requestElevator(6, Direction.UP);
// LOOK scheduler assigns to E1 (already moving up and will pass Floor 6)

controller.run(5);

// ── Put E3 in maintenance ───────────────────────────────

controller.setMaintenance('E3', true);

controller.requestElevator(7, Direction.DOWN);
// Only E1 and E2 considered for assignment

// ── Switch to FCFS scheduler ────────────────────────────

controller.setScheduler(new FCFSScheduler());
controller.requestElevator(2, Direction.UP);

controller.run(3);

// ── View final status ───────────────────────────────────

console.log('\nFinal Status:');
console.log(controller.getStatus());

Edge Cases

Edge CaseHow It Is Handled
All elevators in maintenanceRequest is queued in pendingRequests
Request for current flooraddDestination does nothing (floor === currentFloor)
Request while elevator passing that floorAdded to stop set; caught on next step
Floor out of rangeaddDestination and requestElevator throw errors
Multiple requests for same floorSet-based stops naturally deduplicate
Elevator at top floor, request for UPElevator is there already; opens doors
No stops remainingElevator transitions to IDLE
Pending requests after elevator frees upstep() retries pending assignments

Key Takeaways

  1. Separate UP and DOWN stop sets make the SCAN/LOOK algorithm natural — serve all stops in one direction before reversing.
  2. Strategy Pattern for scheduling allows hot-swapping algorithms (FCFS for testing, LOOK for production) without modifying the controller.
  3. Step-based simulation is the standard approach in interviews — each step() moves elevators one floor, making the logic easy to trace and debug.
  4. The LOOK algorithm is the most practical: it reduces unnecessary travel compared to SCAN by only going as far as the farthest actual request.
  5. Maintenance mode is a simple state that excludes an elevator from assignment — interviewers often ask about this as a follow-up.
  6. The controller is the orchestrator: it receives all requests, delegates to the scheduler, and manages the simulation loop. Individual elevators only know how to move and stop.

Next -> 9.6-Exercise-Questions