Problem 2: Design an Elevator System

The setup

"Design an elevator system for a 50-floor building. Multiple elevators serve the building. Users press call buttons on each floor (up/down) and floor buttons inside the elevator. The system must minimize wait times and travel times."

This problem tests state machines, scheduling algorithms, and concurrency. The interviewer is looking for: a clear state model for each elevator, a scheduling strategy that handles multiple concurrent requests, and an understanding of how dispatching decisions are made.

Clarifying questions

Core entities

Design Decision 1: Elevator state machine

stateDiagram-v2
    [*] --> Idle
    Idle --> MovingUp: request above
    Idle --> MovingDown: request below
    MovingUp --> AtFloor: arrived at next stop
    MovingDown --> AtFloor: arrived at next stop
    AtFloor --> DoorsOpen: stop requested
    AtFloor --> MovingUp: more stops above
    AtFloor --> MovingDown: more stops below
    AtFloor --> Idle: no more requests
    DoorsOpen --> DoorsClosed: close button / timeout
    DoorsClosed --> AtFloor: ready
    MovingUp --> Halted: emergency
    MovingDown --> Halted: emergency
    Halted --> Idle: reset

An elevator is a textbook state machine. States and transitions:

States:
  IDLE     — at a floor, no destinations
  MOVING_UP   — ascending toward destination
  MOVING_DOWN — descending
  STOPPING    — decelerating to a floor
  DOORS_OPENING
  DOORS_OPEN  — boarding/exiting
  DOORS_CLOSING
  
Transitions:
  IDLE + new_destination_above → MOVING_UP
  IDLE + new_destination_below → MOVING_DOWN
  MOVING_UP + reached_destination → STOPPING
  STOPPING → DOORS_OPENING → DOORS_OPEN → DOORS_CLOSING → next state
  DOORS_CLOSING + no_destinations → IDLE
  DOORS_CLOSING + more_destinations → MOVING_UP/DOWN

Implement via the State pattern for cleanliness:

interface ElevatorState {
  void onTick(Elevator elevator);
  void onDestinationAdded(Elevator elevator, int floor);
}

class IdleState implements ElevatorState { ... }
class MovingUpState implements ElevatorState { ... }
class MovingDownState implements ElevatorState { ... }
class DoorsOpenState implements ElevatorState { ... }
// etc.

class Elevator {
  private ElevatorState state;
  private int currentFloor;
  private TreeSet destinations;
  
  void tick() {
    state.onTick(this);
  }
  
  void addDestination(int floor) {
    destinations.add(floor);
    state.onDestinationAdded(this, floor);
  }
  
  void transitionTo(ElevatorState newState) {
    this.state = newState;
  }
}

State pattern makes each state's behavior local to its class. Adding a new state (e.g., MAINTENANCE_MODE) is a new class — no big switch statement to update.

Design Decision 2: Scheduling algorithm — SCAN / elevator algorithm

How does a single elevator handle multiple destinations? The naive "service in order of request" is inefficient. The classic approach is the SCAN algorithm (also called elevator algorithm — yes, named after this exact problem):

1. Elevator picks a direction (up or down).
2. It services all requests in that direction in floor order.
3. When no more requests in current direction, reverse.

This minimises travel: passengers in the same direction are served on a single sweep.

// Within an Elevator
class Elevator {
  Direction currentDirection;  // UP, DOWN, NONE
  TreeSet destinations;
  
  int nextDestination() {
    if (currentDirection == UP) {
      Integer next = destinations.ceiling(currentFloor);
      if (next != null) return next;
      // No more above; switch direction
      currentDirection = DOWN;
    }
    if (currentDirection == DOWN) {
      Integer next = destinations.floor(currentFloor);
      if (next != null) return next;
      currentDirection = NONE;
    }
    return -1; // No destinations
  }
}

Design Decision 3: Multi-elevator dispatching

With 4 elevators, when a user presses an up-call on floor 23, which elevator goes? The dispatcher's job.

Simple heuristics:

• Nearest idle elevator: easy but ignores busy elevators that might be passing by anyway
• Nearest moving in the right direction: smarter — if an elevator is going up and will pass floor 23, send it
• Lowest expected arrival time: compute for each elevator: "how long would it take to reach floor 23 going up?" Pick minimum.

The third is what production systems do. Implementation via Strategy pattern:

interface DispatchStrategy {
  Elevator selectElevator(Request request, List elevators);
}

class ShortestExpectedArrivalStrategy implements DispatchStrategy {
  public Elevator selectElevator(Request req, List elevators) {
    Elevator best = null;
    long bestETA = Long.MAX_VALUE;
    for (Elevator e : elevators) {
      long eta = computeETA(e, req);
      if (eta < bestETA) {
        bestETA = eta;
        best = e;
      }
    }
    return best;
  }
  
  private long computeETA(Elevator e, Request req) {
    // Simulate: if I send this request to elevator e, how long until it
    // reaches req.floor in the right direction?
    // Considers current floor, current direction, current destinations.
  }
}

Design Decision 4: Internal vs external requests

Two types of requests:

• External (floor call): someone on floor 15 presses "up". The dispatcher decides which elevator to send.
• Internal (car button): someone inside elevator 2 presses "23". Goes directly to that elevator's destination queue.

class Dispatcher {
  private final List elevators;
  private final DispatchStrategy strategy;
  
  void requestExternal(int fromFloor, Direction direction) {
    Request req = new ExternalRequest(fromFloor, direction);
    Elevator assigned = strategy.selectElevator(req, elevators);
    assigned.addDestination(fromFloor);
  }
  
  void requestInternal(Elevator elevator, int toFloor) {
    elevator.addDestination(toFloor);
  }
}

Cross-examination round 1: concurrency

Cross-examination round 2: starvation

Cross-examination round 3: emergency mode

Takeaway

Elevator design demonstrates the State pattern in its natural habitat: a system with explicit, finite states that drive behavior. The SCAN algorithm is a textbook scheduling problem with clean implementation. Multi-elevator dispatching introduces the Strategy pattern for swappable scheduling policies. Together: a clean, extensible, defensible design.

The deeper lesson: recognise when a problem is fundamentally a state machine. The states might be obvious (elevator) or hidden (network connection has states: connecting, connected, disconnecting; an order has states: created, paid, shipped, delivered). Naming the states explicitly — and using the State pattern — makes complex transition logic manageable.