On this page

Design an Elevator System

The elevator problem tests your ability to model concurrent state machines and implement scheduling algorithms. The core challenge is not the elevator itself — it is how multiple elevators coordinate to minimize wait time.

There are two separate scheduling decisions, and most weak answers blur them:

  1. Movement: when a car keeps going and when it turns around. SCAN and LOOK are answers to this, and each car makes the decision on its own.
  2. Dispatch: which car answers a hall call. "Nearest car" is an answer to this, and the controller makes the decision for all cars.

1. Clarifying questions and requirements

QuestionAssumption if the interviewer says "you decide"What it changes
Floors and cars?10 floors (0 to 9), 1 to 3 carsConstructor parameters
Hall buttons have a direction?Yes. A DOWN call must be answered by a car that will leave going down.Separate up and down call sets per car
Who picks the car?A central controller, nearest car firstDispatcher strategy
SCAN or LOOK?LOOK, but make it switchableMovementPolicy strategy
How is time modelled?Discrete ticks: one floor per tick, doors open for two ticksA tick() method that tests can call
Buttons pressed concurrently?Yes, from many threadsA thread-safe command inbox
Out of service?A car can enter maintenance, and its calls go to other carsA MAINTENANCE state

Requirements & Use Cases

Functional Requirements

  1. Building has N floors and M elevators
  2. Each floor has Up and Down request buttons (hall calls)
  3. Inside each elevator, passengers select destination floors (cabin calls)
  4. Elevators move up and down, opening doors at requested floors
  5. Scheduling algorithm determines which elevator services which request
  6. Display current floor and direction for each elevator
  7. Support capacity limits per elevator

Non-Functional Requirements

  • Minimize average wait time across all passengers
  • Elevators should not "starve" requests (no indefinite waiting)
  • Thread-safe request handling (multiple buttons pressed concurrently)
  • Extensible to add new scheduling algorithms

Use Cases

ActorUse Case
PassengerPress hall button (up/down) on a floor
PassengerSelect destination floor inside elevator
SystemDispatch optimal elevator to a hall call
SystemMove elevator and open doors at stops
AdminConfigure number of elevators and floors
AdminTake an elevator out of service

2. Entities and relationships

EntityOwnsInvariant
ElevatorControllerCars, the command inbox, unassigned calls, the dispatcherEvery accepted hall call is held by exactly one car, or waits in unassigned
CarFloor, direction, state, cabin stops, up calls, down callsNever leaves the shaft. A hall call is cleared only when the doors open for its direction.
MovementPolicyThe keep-going-or-turn rulePure. Looks at the car and answers.
DispatcherThe rule for choosing a carPure. Never mutates a car.
CommandHallCall, CabinCall, MaintenanceImmutable messages, applied in arrival order

3. Class diagram

classDiagram
    class ElevatorController {
        -cars: List~Car~
        -inbox: Queue~Command~
        -unassigned: Deque~HallCall~
        -dispatcher: Dispatcher
        +pressHall(floor, dir)
        +pressCabin(carId, floor)
        +setMaintenance(carId, on)
        +tick()
        +quiet() boolean
    }
    class Car {
        +id: int
        +floor: int
        +dir: Direction
        +state: CarState
        +cabin: SortedSet~Integer~
        +up: SortedSet~Integer~
        +down: SortedSet~Integer~
        +tick() int
        +hasStopsBeyond(dir) boolean
        +farthestStop(dir) int
    }
    class MovementPolicy {
        <<interface>>
        +keepGoing(car, dir) boolean
    }
    class Look
    class Scan
    class Dispatcher {
        <<interface>>
        +choose(call, cars) Car
    }
    class NearestCarDispatcher
    class Command {
        <<sealed interface>>
    }
    class HallCall {
        +floor: int
        +dir: Direction
    }
    class CabinCall {
        +carId: int
        +floor: int
    }
    class Maintenance {
        +carId: int
        +on: boolean
    }
    class CarState {
        <<enumeration>>
        IDLE
        MOVING
        DOORS_OPEN
        MAINTENANCE
    }
    ElevatorController "1" *-- "many" Car
    ElevatorController --> Dispatcher
    ElevatorController ..> Command : drains
    Car --> MovementPolicy
    Car --> CarState
    MovementPolicy <|.. Look
    MovementPolicy <|.. Scan
    Dispatcher <|.. NearestCarDispatcher
    Command <|.. HallCall
    Command <|.. CabinCall
    Command <|.. Maintenance

The first-pass diagram below is kept. It folds the movement rule into Elevator and has no inbox.

Class Diagram

classDiagram
    class ElevatorSystem {
        -elevators: Elevator[]
        -dispatcher: Dispatcher
        -floors: int
        +requestElevator(floor: int, dir: Direction): void
        +selectFloor(elevatorId: int, floor: int): void
        +step(): void
    }

    class Elevator {
        -id: int
        -currentFloor: int
        -direction: Direction
        -state: ElevatorState
        -stops: SortedSet~int~
        -capacity: int
        -currentLoad: int
        +addStop(floor: int): void
        +move(): void
        +openDoors(): void
        +closeDoors(): void
        +shouldStop(): boolean
    }

    class Dispatcher {
        <<interface>>
        +dispatch(request: Request, elevators: Elevator[]): Elevator
    }

    class LOOKDispatcher {
        +dispatch(request: Request, elevators: Elevator[]): Elevator
    }

    class SCANDispatcher {
        +dispatch(request: Request, elevators: Elevator[]): Elevator
    }

    class DestinationDispatcher {
        +dispatch(request: Request, elevators: Elevator[]): Elevator
    }

    class Request {
        -floor: int
        -direction: Direction
        -timestamp: Date
    }

    class ElevatorState {
        <<enumeration>>
        IDLE
        MOVING_UP
        MOVING_DOWN
        DOORS_OPEN
        OUT_OF_SERVICE
    }

    class Direction {
        <<enumeration>>
        UP
        DOWN
        NONE
    }

    ElevatorSystem *-- Elevator
    ElevatorSystem --> Dispatcher
    Dispatcher <|.. LOOKDispatcher
    Dispatcher <|.. SCANDispatcher
    Dispatcher <|.. DestinationDispatcher
    Elevator --> ElevatorState
    Elevator --> Direction
    ElevatorSystem --> Request

4. Key flows

A hall call, from button to doors

sequenceDiagram
    participant B as Floor 5 DOWN button
    participant Q as Command inbox
    participant T as Tick loop
    participant D as Dispatcher
    participant C as Car 1
    B->>Q: HallCall 5 DOWN, from any thread
    T->>Q: poll all commands
    T->>D: choose(5 DOWN, cars)
    D-->>T: car 1, lowest cost
    T->>C: add 5 to down calls
    loop every tick
        T->>C: tick()
        C->>C: move one floor, check servesHere
    end
    C-->>T: doors opened at 5, leaving DOWN

The car state machine

stateDiagram-v2
    [*] --> IDLE
    IDLE --> DOORS_OPEN: request at this floor
    IDLE --> MOVING: stops elsewhere
    MOVING --> MOVING: next floor, nothing to serve
    MOVING --> DOORS_OPEN: cabin stop or a call in the leaving direction
    MOVING --> IDLE: turnaround floor with no work left
    DOORS_OPEN --> DOORS_OPEN: door timer running
    DOORS_OPEN --> MOVING: timer done, more stops
    DOORS_OPEN --> IDLE: timer done, no stops
    IDLE --> MAINTENANCE: maintenance on
    MOVING --> MAINTENANCE: maintenance on
    DOORS_OPEN --> MAINTENANCE: maintenance on
    MAINTENANCE --> IDLE: maintenance off

At each floor a car asks: do I serve this floor (a cabin stop, or a hall call in my leaving direction), and do I keep going (the MovementPolicy)? If not, it reverses and may serve the opposite call here.

5. Patterns used, and the alternatives rejected

PatternWhereWhy
StrategyMovementPolicy (LOOK, SCAN) and Dispatcher (nearest car)Two independent decisions, each switchable
CommandHallCall, CabinCall, Maintenance in the inboxButton presses become data, applied in order on one thread
State, as an enumCarState with a switch in tickFour states with short transitions. State classes would scatter one small machine across five files.
DecoratorZonedDispatcher (extension 1)Restrict the cars, then reuse any dispatcher

The movement policies

PolicyRuleBehaviour
LOOKReverse when nothing is left aheadFewer wasted floors. The usual default.
SCANWhile any work exists, run to the end of the shaft before reversingPredictable, but slower. The demo shows a call at floor 1 served later under SCAN.
FCFSServe requests in arrival orderEasy, and terrible: the car zig-zags

Nearest-car cost is the plain distance for an idle car or one already heading there in the caller's direction, else the trip to its turnaround floor and back, a one-turn estimate marked in the code.

AlternativeWhy it was rejected
A thread per car with locks on its stop setsMany locks and real interleavings to reason about, for a system that changes state a few times a second
Calls in one SortedSet per carLoses the hall-call direction, which is the bug in the first-pass code
Car classes per stateFine for a richer machine. Here it's ceremony.

Scheduling Algorithms

AlgorithmHow It WorksProsCons
FCFSServe requests in arrival orderSimpleTerrible performance — elevator bounces randomly
SCANMove in one direction serving all requests, then reverseFairGoes to extremes even without requests
LOOKLike SCAN but reverses when no more requests in current directionEfficientSlightly more complex
Destination DispatchPassengers enter destination before entering elevator; group by destinationBest throughputRequires lobby kiosks
flowchart LR
    subgraph "SCAN (Elevator Algorithm)"
        A["Floor 1"] --- B["Floor 2"] --- C["Floor 3"] --- D["Floor 4"] --- E["Floor 5"]
    end

    F["Go UP: serve all UP requests<br/>Hit top → reverse<br/>Go DOWN: serve all DOWN requests<br/>Hit bottom → reverse"]

    style F fill:#e8f5e9,color:#000

Correction (2026-11-10): what the first-pass dispatchers really do

The first-pass SCANDispatcher doesn't implement SCAN. It picks the nearest car moving in the same direction, ignoring whether that car has already passed the floor, which is a nearest-car heuristic. DestinationDispatcher doesn't use destinations either: it prefers idle cars, then the closest. Destination dispatch needs the destination at the hall panel, which a plain up/down Request doesn't carry. The names in the code and tables below are kept, but read them as heuristics. SCAN and LOOK are movement rules, implemented as MovementPolicy in the complete code.

Design Patterns Used

PatternWhereWhy
StrategyDispatcher interface with LOOK, SCAN, Destination variantsSwap scheduling algorithms at runtime without changing the system
StateElevatorState enum driving Elevator.move() behaviorElevator behavior changes based on current state (idle, moving, doors open)
FacadeElevatorSystemHides dispatch logic, elevator management, pending queue from callers
Observer (extension)Floor displays watching elevator positionsDecouple display updates from elevator movement logic

6. Complete code

Each version runs on its own and prints elevator: all checks passed. All three ran before publishing:

  • Java 24: javac -d out ElevatorDemo.java && java -cp out ElevatorDemo
  • Python 3.12: python elevator.py
  • TypeScript (strict): tsc --strict --noEmit --target es2022 --types node elevator.ts && npx tsx elevator.ts
import java.util.*;
import java.util.concurrent.*;
import java.util.stream.Stream;

enum Direction {
    UP, DOWN, IDLE;
    Direction opposite() { return this == UP ? DOWN : this == DOWN ? UP : IDLE; }
    int step() { return this == UP ? 1 : this == DOWN ? -1 : 0; }
}

enum CarState { IDLE, MOVING, DOORS_OPEN, MAINTENANCE }

/** Everything a button press can mean. The controller applies them on its own thread. */
sealed interface Command permits HallCall, CabinCall, Maintenance {}
record HallCall(int floor, Direction dir) implements Command {}
record CabinCall(int carId, int floor) implements Command {}
record Maintenance(int carId, boolean on) implements Command {}

/** When does a car stop sweeping in its current direction? */
interface MovementPolicy { boolean keepGoing(Car car, Direction dir); }

/** LOOK: reverse as soon as nothing is left ahead. */
final class Look implements MovementPolicy {
    public boolean keepGoing(Car c, Direction d) { return c.hasStopsBeyond(d); }
}

/** SCAN: while there is any work, run to the end of the shaft before reversing. */
final class Scan implements MovementPolicy {
    public boolean keepGoing(Car c, Direction d) {
        return c.hasStopsBeyond(d) || (c.hasStops() && c.floor != (d == Direction.UP ? c.top : 0));
    }
}

final class Car {
    static final int DOOR_TICKS = 2;
    final int id, top;
    final MovementPolicy policy;
    int floor, doorTimer;
    Direction dir = Direction.IDLE;
    CarState state = CarState.IDLE;
    final SortedSet<Integer> cabin = new TreeSet<>(), up = new TreeSet<>(), down = new TreeSet<>();

    Car(int id, int top, MovementPolicy policy) { this.id = id; this.top = top; this.policy = policy; }

    boolean inService() { return state != CarState.MAINTENANCE; }
    boolean hasStops() { return !cabin.isEmpty() || !up.isEmpty() || !down.isEmpty(); }
    private Stream<Integer> allStops() { return Stream.of(cabin, up, down).flatMap(Set::stream); }
    boolean hasStopsBeyond(Direction d) {
        return allStops().anyMatch(f -> d == Direction.UP ? f > floor : d == Direction.DOWN && f < floor);
    }
    int farthestStop(Direction d) {
        return allStops().reduce(floor, d == Direction.UP ? Math::max : Math::min);
    }
    void addHall(HallCall c) { (c.dir() == Direction.UP ? up : down).add(c.floor()); }
    boolean hasHall(HallCall c) { return (c.dir() == Direction.UP ? up : down).contains(c.floor()); }

    /** One time unit of the state machine. Returns the floor where the doors opened, or -1. */
    int tick() {
        switch (state) {
            case MAINTENANCE: return -1;
            case DOORS_OPEN:
                if (--doorTimer > 0) return -1;
                state = CarState.IDLE;
                return decide();
            case IDLE: return decide();
            default:                                          // MOVING
                floor += dir.step();
                if (floor < 0 || floor > top) throw new IllegalStateException("car " + id + " left the shaft");
                return arrive();
        }
    }

    private int decide() {
        if (!hasStops()) { dir = Direction.IDLE; state = CarState.IDLE; return -1; }
        if (dir == Direction.IDLE) dir = towardNearestStop();
        if (servesHere(dir)) return openDoors();
        if (!policy.keepGoing(this, dir)) {
            dir = dir.opposite();
            if (servesHere(dir)) return openDoors();
        }
        state = CarState.MOVING;
        return -1;
    }

    private int arrive() {
        if (servesHere(dir)) return openDoors();
        if (!policy.keepGoing(this, dir)) {                   // turnaround floor
            dir = dir.opposite();
            if (servesHere(dir)) return openDoors();
            if (!hasStops()) { dir = Direction.IDLE; state = CarState.IDLE; }
        }
        return -1;
    }

    /** A hall call is served only by a car leaving in the caller's direction. */
    private boolean servesHere(Direction d) {
        return cabin.contains(floor) || (d != Direction.DOWN && up.contains(floor))
            || (d != Direction.UP && down.contains(floor));
    }

    private int openDoors() {
        cabin.remove(floor);
        if (dir == Direction.IDLE) dir = up.contains(floor) ? Direction.UP : down.contains(floor) ? Direction.DOWN : Direction.IDLE;
        if (dir == Direction.UP) up.remove(floor);
        if (dir == Direction.DOWN) down.remove(floor);
        state = CarState.DOORS_OPEN;
        doorTimer = DOOR_TICKS;
        return floor;
    }

    private Direction towardNearestStop() {
        int target = allStops().min(Comparator.comparingInt((Integer f) -> Math.abs(f - floor)).thenComparing(f -> f)).orElse(floor);
        return target > floor ? Direction.UP : target < floor ? Direction.DOWN : Direction.IDLE;
    }
}

/** Which car answers a hall call. */
interface Dispatcher { Optional<Car> choose(HallCall call, List<Car> cars); }

/** Nearest car by travel distance, counting the detour of a car that must turn around first. */
final class NearestCarDispatcher implements Dispatcher {
    public Optional<Car> choose(HallCall call, List<Car> cars) {
        return cars.stream().filter(Car::inService)
            .min(Comparator.comparingInt((Car c) -> cost(c, call)).thenComparingInt(c -> c.id));
    }
    static int cost(Car c, HallCall call) {
        int f = call.floor();
        if (c.dir == Direction.IDLE) return Math.abs(c.floor - f);
        boolean ahead = c.dir == Direction.UP ? f >= c.floor : f <= c.floor;
        if (ahead && c.dir == call.dir()) return Math.abs(c.floor - f);
        // Simplification: one-turn estimate; a call behind and in the car's direction really needs two turns
        int turn = c.dir == Direction.UP ? Math.max(c.farthestStop(Direction.UP), f) : Math.min(c.farthestStop(Direction.DOWN), f);
        return Math.abs(turn - c.floor) + Math.abs(turn - f);
    }
}

interface DoorListener { void doorsOpened(int carId, int floor, Direction leaving); }

final class ElevatorController {
    private final List<Car> cars;
    private final Dispatcher dispatcher;
    private final DoorListener listener;
    private final int top;
    private final Queue<Command> inbox = new ConcurrentLinkedQueue<>();   // the only shared state
    private final Deque<HallCall> unassigned = new ArrayDeque<>();        // confined to the tick thread
    private long time;

    ElevatorController(int floors, int carCount, MovementPolicy policy, Dispatcher dispatcher, DoorListener listener) {
        this.top = floors - 1; this.dispatcher = dispatcher; this.listener = listener;
        List<Car> list = new ArrayList<>();
        for (int i = 0; i < carCount; i++) list.add(new Car(i, top, policy));
        this.cars = List.copyOf(list);
    }

    // Called from any thread: buttons only enqueue.
    void pressHall(int floor, Direction dir) {
        if (floor < 0 || floor > top || dir == Direction.IDLE || (floor == top && dir == Direction.UP) || (floor == 0 && dir == Direction.DOWN))
            throw new IllegalArgumentException("no such button");
        inbox.add(new HallCall(floor, dir));
    }
    void pressCabin(int carId, int floor) {
        if (floor < 0 || floor > top || carId < 0 || carId >= cars.size()) throw new IllegalArgumentException("no such button");
        inbox.add(new CabinCall(carId, floor));
    }
    void setMaintenance(int carId, boolean on) { inbox.add(new Maintenance(carId, on)); }

    /** One deterministic step: apply commands in arrival order, dispatch, then move every car. */
    void tick() {
        for (Command c; (c = inbox.poll()) != null; ) apply(c);
        for (int n = unassigned.size(); n > 0; n--) assign(unassigned.poll());
        for (Car car : cars) {
            int opened = car.tick();
            if (opened >= 0) listener.doorsOpened(car.id, opened, car.dir);
        }
        time++;
    }

    private void apply(Command c) {
        switch (c) {
            case HallCall h -> assign(h);
            case CabinCall cc -> { Car car = cars.get(cc.carId()); if (car.inService()) car.cabin.add(cc.floor()); }
            case Maintenance m -> {
                Car car = cars.get(m.carId());
                if (m.on()) {
                    car.up.forEach(f -> unassigned.add(new HallCall(f, Direction.UP)));
                    car.down.forEach(f -> unassigned.add(new HallCall(f, Direction.DOWN)));
                    car.up.clear(); car.down.clear(); car.cabin.clear();
                    car.state = CarState.MAINTENANCE; car.dir = Direction.IDLE;
                } else if (!car.inService()) car.state = CarState.IDLE;
            }
        }
    }

    private void assign(HallCall h) {
        if (cars.stream().anyMatch(car -> car.hasHall(h))) return;          // already on its way
        dispatcher.choose(h, cars).ifPresentOrElse(car -> car.addHall(h), () -> unassigned.add(h));
    }

    boolean quiet() { return inbox.isEmpty() && unassigned.isEmpty() && cars.stream().noneMatch(Car::hasStops); }
    Car car(int id) { return cars.get(id); }
    long time() { return time; }
}

public class ElevatorDemo {
    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    record Run(List<String> log, long ticks) {}
    interface Step { void apply(ElevatorController c); }
    static Step ticks(int n) { return c -> { for (int i = 0; i < n; i++) c.tick(); }; }
    static Step cabin(int car, int floor) { return c -> c.pressCabin(car, floor); }
    static Step hall(int floor, Direction d) { return c -> c.pressHall(floor, d); }

    /** Runs a script on a fresh 10-floor building, then ticks until every request is served. */
    static Run run(MovementPolicy policy, int cars, Step... script) {
        List<String> log = new ArrayList<>();
        ElevatorController ctl = new ElevatorController(10, cars, policy, new NearestCarDispatcher(),
            (id, f, d) -> log.add(id + "@" + f));
        for (Step step : script) step.apply(ctl);
        while (!ctl.quiet()) ctl.tick();
        return new Run(log, ctl.time());
    }

    public static void main(String[] args) throws Exception {
        // 1. A DOWN call is not picked up on the way up. The car serves 8, then comes back to 5.
        check(run(new Look(), 1, cabin(0, 8), ticks(2), hall(5, Direction.DOWN)).log().equals(List.of("0@8", "0@5")),
              "direction-aware stops");

        // 2. LOOK turns at the last request. SCAN runs to the top floor first. Same script, same result.
        Step[] script = { cabin(0, 3), ticks(1), hall(1, Direction.DOWN) };
        Run look = run(new Look(), 1, script), scan = run(new Scan(), 1, script);
        check(look.ticks() < scan.ticks(), "LOOK is faster here");
        check(look.equals(run(new Look(), 1, script)), "deterministic");

        // 3. Nearest car: car 1 parked at 6 is nearer to floor 5 than car 0 at 0.
        check(run(new Look(), 2, cabin(1, 6), ticks(12), hall(5, Direction.UP)).log().equals(List.of("1@6", "1@5")),
              "car 1 answers");

        // 4. Concurrency: 8 threads press buttons while this thread ticks. Everything is served.
        ElevatorController busy = new ElevatorController(20, 3, new Look(), new NearestCarDispatcher(), (i, f, d) -> {});
        ExecutorService pressers = Executors.newFixedThreadPool(8);
        for (int t = 0; t < 8; t++) {
            Random r = new Random(t);
            pressers.submit(() -> {
                for (int i = 0; i < 200; i++) {
                    int f = 1 + r.nextInt(18);
                    if (r.nextBoolean()) busy.pressHall(f, r.nextBoolean() ? Direction.UP : Direction.DOWN);
                    else busy.pressCabin(r.nextInt(3), f);
                }
            });
        }
        pressers.shutdown();
        while (!pressers.isTerminated()) busy.tick();
        for (int i = 0; i < 2_000 && !busy.quiet(); i++) busy.tick();
        check(busy.quiet(), "every request served");
        System.out.println("elevator: all checks passed");
    }
}
from __future__ import annotations

import queue
from collections import deque
from dataclasses import dataclass
from enum import Enum
from typing import Callable, Optional, Protocol, Union


class Direction(Enum):
    UP = 1
    DOWN = -1
    IDLE = 0

    def opposite(self) -> Direction:
        return {Direction.UP: Direction.DOWN, Direction.DOWN: Direction.UP}.get(self, Direction.IDLE)


class CarState(Enum):
    IDLE = "IDLE"
    MOVING = "MOVING"
    DOORS_OPEN = "DOORS_OPEN"
    MAINTENANCE = "MAINTENANCE"


@dataclass(frozen=True)
class HallCall:
    floor: int
    dir: Direction


@dataclass(frozen=True)
class CabinCall:
    car_id: int
    floor: int


@dataclass(frozen=True)
class Maintenance:
    car_id: int
    on: bool


Command = Union[HallCall, CabinCall, Maintenance]


class MovementPolicy(Protocol):
    def keep_going(self, car: Car, d: Direction) -> bool: ...


class Look:
    def keep_going(self, car: Car, d: Direction) -> bool:
        return car.has_stops_beyond(d)


class Scan:
    def keep_going(self, car: Car, d: Direction) -> bool:
        end = car.top if d is Direction.UP else 0
        return car.has_stops_beyond(d) or (car.has_stops() and car.floor != end)


class Car:
    DOOR_TICKS = 2

    def __init__(self, car_id: int, top: int, policy: MovementPolicy):
        self.id, self.top, self.policy = car_id, top, policy
        self.floor, self.door_timer = 0, 0
        self.dir, self.state = Direction.IDLE, CarState.IDLE
        self.cabin: set[int] = set()
        self.up: set[int] = set()
        self.down: set[int] = set()

    def in_service(self) -> bool:
        return self.state is not CarState.MAINTENANCE

    def has_stops(self) -> bool:
        return bool(self.cabin or self.up or self.down)

    def _all(self) -> set[int]:
        return self.cabin | self.up | self.down

    def has_stops_beyond(self, d: Direction) -> bool:
        return any((f - self.floor) * d.value > 0 for f in self._all())

    def farthest_stop(self, d: Direction) -> int:
        return (max if d is Direction.UP else min)(self._all() | {self.floor})

    def calls(self, d: Direction) -> set[int]:
        return self.up if d is Direction.UP else self.down

    def tick(self) -> Optional[int]:
        """One time unit of the state machine. Returns the floor where doors opened."""
        if self.state is CarState.MAINTENANCE:
            return None
        if self.state is CarState.DOORS_OPEN:
            self.door_timer -= 1
            if self.door_timer > 0:
                return None
            self.state = CarState.IDLE
        if self.state is CarState.IDLE:
            return self._decide()
        self.floor += self.dir.value
        if not 0 <= self.floor <= self.top:
            raise RuntimeError(f"car {self.id} left the shaft")
        return self._arrive()

    def _decide(self) -> Optional[int]:
        if not self.has_stops():
            self.dir, self.state = Direction.IDLE, CarState.IDLE
            return None
        if self.dir is Direction.IDLE:
            target = min(self._all(), key=lambda f: (abs(f - self.floor), f))
            self.dir = Direction.UP if target > self.floor else Direction.DOWN if target < self.floor else Direction.IDLE
        if self._serves_here(self.dir):
            return self._open()
        if not self.policy.keep_going(self, self.dir):
            self.dir = self.dir.opposite()
            if self._serves_here(self.dir):
                return self._open()
        self.state = CarState.MOVING
        return None

    def _arrive(self) -> Optional[int]:
        if self._serves_here(self.dir):
            return self._open()
        if not self.policy.keep_going(self, self.dir):
            self.dir = self.dir.opposite()
            if self._serves_here(self.dir):
                return self._open()
            if not self.has_stops():
                self.dir, self.state = Direction.IDLE, CarState.IDLE
        return None

    def _serves_here(self, d: Direction) -> bool:
        f = self.floor
        return f in self.cabin or (d is not Direction.DOWN and f in self.up) or (d is not Direction.UP and f in self.down)

    def _open(self) -> int:
        self.cabin.discard(self.floor)
        if self.dir is Direction.IDLE:
            self.dir = Direction.UP if self.floor in self.up else Direction.DOWN if self.floor in self.down else Direction.IDLE
        if self.dir is not Direction.IDLE:
            self.calls(self.dir).discard(self.floor)
        self.state, self.door_timer = CarState.DOORS_OPEN, self.DOOR_TICKS
        return self.floor


class Dispatcher(Protocol):
    def choose(self, call: HallCall, cars: list[Car]) -> Optional[Car]: ...


class NearestCarDispatcher:
    def choose(self, call: HallCall, cars: list[Car]) -> Optional[Car]:
        candidates = [c for c in cars if c.in_service()]
        return min(candidates, key=lambda c: (self.cost(c, call), c.id), default=None)

    @staticmethod
    def cost(c: Car, call: HallCall) -> int:
        f = call.floor
        if c.dir is Direction.IDLE:
            return abs(c.floor - f)
        ahead = (f - c.floor) * c.dir.value >= 0
        if ahead and c.dir is call.dir:
            return abs(c.floor - f)
        far = c.farthest_stop(c.dir)
        turn = max(far, f) if c.dir is Direction.UP else min(far, f)
        return abs(turn - c.floor) + abs(turn - f)


class ElevatorController:
    def __init__(self, floors: int, car_count: int, policy: MovementPolicy, dispatcher: Dispatcher,
                 on_open: Callable[[int, int], None] = lambda car_id, floor: None):
        self.top = floors - 1
        self.cars = [Car(i, self.top, policy) for i in range(car_count)]
        self._dispatcher, self._on_open = dispatcher, on_open
        self._inbox: queue.SimpleQueue[Command] = queue.SimpleQueue()   # the only shared state
        self._unassigned: deque[HallCall] = deque()                     # tick thread only
        self.time = 0

    # Any thread: buttons only enqueue.
    def press_hall(self, floor: int, d: Direction) -> None:
        if not 0 <= floor <= self.top or d is Direction.IDLE or (floor, d) in ((self.top, Direction.UP), (0, Direction.DOWN)):
            raise ValueError("no such button")
        self._inbox.put(HallCall(floor, d))

    def press_cabin(self, car_id: int, floor: int) -> None:
        if not 0 <= floor <= self.top or not 0 <= car_id < len(self.cars):
            raise ValueError("no such button")
        self._inbox.put(CabinCall(car_id, floor))

    def set_maintenance(self, car_id: int, on: bool) -> None:
        self._inbox.put(Maintenance(car_id, on))

    def tick(self) -> None:
        while not self._inbox.empty():
            self._apply(self._inbox.get())
        for _ in range(len(self._unassigned)):
            self._assign(self._unassigned.popleft())
        for car in self.cars:
            opened = car.tick()
            if opened is not None:
                self._on_open(car.id, opened)
        self.time += 1

    def _apply(self, c: Command) -> None:
        if isinstance(c, HallCall):
            self._assign(c)
        elif isinstance(c, CabinCall):
            if self.cars[c.car_id].in_service():
                self.cars[c.car_id].cabin.add(c.floor)
        else:
            car = self.cars[c.car_id]
            if c.on:
                self._unassigned.extend([HallCall(f, Direction.UP) for f in sorted(car.up)] +
                                        [HallCall(f, Direction.DOWN) for f in sorted(car.down)])
                car.up.clear(); car.down.clear(); car.cabin.clear()
                car.state, car.dir = CarState.MAINTENANCE, Direction.IDLE
            elif not car.in_service():
                car.state = CarState.IDLE

    def _assign(self, h: HallCall) -> None:
        if any(h.floor in car.calls(h.dir) for car in self.cars):
            return
        car = self._dispatcher.choose(h, self.cars)
        if car:
            car.calls(h.dir).add(h.floor)
        else:
            self._unassigned.append(h)

    def quiet(self) -> bool:
        return self._inbox.empty() and not self._unassigned and not any(c.has_stops() for c in self.cars)


def run(policy: MovementPolicy, cars: int, *script: Callable[[ElevatorController], None]) -> tuple[list[str], int]:
    log: list[str] = []
    ctl = ElevatorController(10, cars, policy, NearestCarDispatcher(), lambda i, f: log.append(f"{i}@{f}"))
    for step in script:
        step(ctl)
    while not ctl.quiet():
        ctl.tick()
    return log, ctl.time


def ticks(n: int) -> Callable[[ElevatorController], None]:
    return lambda c: [c.tick() for _ in range(n)]


def demo() -> None:
    log, _ = run(Look(), 1, lambda c: c.press_cabin(0, 8), ticks(2), lambda c: c.press_hall(5, Direction.DOWN))
    assert log == ["0@8", "0@5"], log

    script = (lambda c: c.press_cabin(0, 3), ticks(1), lambda c: c.press_hall(1, Direction.DOWN))
    look, scan = run(Look(), 1, *script), run(Scan(), 1, *script)
    assert look[1] < scan[1] and look == run(Look(), 1, *script)

    log, _ = run(Look(), 2, lambda c: c.press_cabin(1, 6), ticks(12), lambda c: c.press_hall(5, Direction.UP))
    assert log == ["1@6", "1@5"], log

    print("elevator: all checks passed")


if __name__ == "__main__":
    demo()
type Direction = 1 | -1 | 0;                          // UP, DOWN, IDLE
const UP = 1, DOWN = -1, IDLE = 0;
type CarState = "IDLE" | "MOVING" | "DOORS_OPEN" | "MAINTENANCE";

type Command =
  | { kind: "hall"; floor: number; dir: Direction }
  | { kind: "cabin"; carId: number; floor: number }
  | { kind: "maintenance"; carId: number; on: boolean };

interface MovementPolicy { keepGoing(car: Car, dir: Direction): boolean }

class Look implements MovementPolicy {
  keepGoing(car: Car, dir: Direction): boolean { return car.hasStopsBeyond(dir); }
}

class Scan implements MovementPolicy {
  keepGoing(car: Car, dir: Direction): boolean {
    return car.hasStopsBeyond(dir) || (car.hasStops() && car.floor !== (dir === UP ? car.top : 0));
  }
}

class Car {
  static readonly DOOR_TICKS = 2;
  floor = 0;
  dir: Direction = IDLE;
  state: CarState = "IDLE";
  private doorTimer = 0;
  readonly cabin = new Set<number>();
  readonly up = new Set<number>();
  readonly down = new Set<number>();

  constructor(readonly id: number, readonly top: number, private readonly policy: MovementPolicy) {}

  inService(): boolean { return this.state !== "MAINTENANCE"; }
  hasStops(): boolean { return this.cabin.size + this.up.size + this.down.size > 0; }
  private all(): number[] { return [...this.cabin, ...this.up, ...this.down]; }
  hasStopsBeyond(dir: Direction): boolean { return this.all().some((f) => (f - this.floor) * dir > 0); }
  farthestStop(dir: Direction): number {
    return (dir === UP ? Math.max : Math.min)(this.floor, ...this.all());
  }
  calls(dir: Direction): Set<number> { return dir === UP ? this.up : this.down; }

  /** One time unit. Returns the floor where the doors opened, or null. */
  tick(): number | null {
    if (this.state === "MAINTENANCE") return null;
    if (this.state === "DOORS_OPEN") {
      if (--this.doorTimer > 0) return null;
      this.state = "IDLE";
    }
    if (this.state === "IDLE") return this.decide();
    this.floor += this.dir;
    if (this.floor < 0 || this.floor > this.top) throw new Error(`car ${this.id} left the shaft`);
    return this.arrive();
  }

  private decide(): number | null {
    if (!this.hasStops()) { this.dir = IDLE; this.state = "IDLE"; return null; }
    if (this.dir === IDLE) {
      const target = this.all().sort((a, b) => Math.abs(a - this.floor) - Math.abs(b - this.floor) || a - b)[0];
      this.dir = Math.sign(target - this.floor) as Direction;
    }
    if (this.servesHere(this.dir)) return this.open();
    if (!this.policy.keepGoing(this, this.dir)) {
      this.dir = -this.dir as Direction;
      if (this.servesHere(this.dir)) return this.open();
    }
    this.state = "MOVING";
    return null;
  }

  private arrive(): number | null {
    if (this.servesHere(this.dir)) return this.open();
    if (!this.policy.keepGoing(this, this.dir)) {
      this.dir = -this.dir as Direction;
      if (this.servesHere(this.dir)) return this.open();
      if (!this.hasStops()) { this.dir = IDLE; this.state = "IDLE"; }
    }
    return null;
  }

  private servesHere(dir: Direction): boolean {
    const f = this.floor;
    return this.cabin.has(f) || (dir !== DOWN && this.up.has(f)) || (dir !== UP && this.down.has(f));
  }

  private open(): number {
    this.cabin.delete(this.floor);
    if (this.dir === IDLE) this.dir = this.up.has(this.floor) ? UP : this.down.has(this.floor) ? DOWN : IDLE;
    if (this.dir !== IDLE) this.calls(this.dir).delete(this.floor);
    this.state = "DOORS_OPEN";
    this.doorTimer = Car.DOOR_TICKS;
    return this.floor;
  }
}

interface Dispatcher { choose(floor: number, dir: Direction, cars: readonly Car[]): Car | null }

class NearestCarDispatcher implements Dispatcher {
  choose(floor: number, dir: Direction, cars: readonly Car[]): Car | null {
    let best: Car | null = null, bestCost = Infinity;
    for (const c of cars) {
      if (!c.inService()) continue;
      const cost = NearestCarDispatcher.cost(c, floor, dir);
      if (cost < bestCost) { best = c; bestCost = cost; }   // ties keep the lower id
    }
    return best;
  }
  static cost(c: Car, f: number, dir: Direction): number {
    if (c.dir === IDLE) return Math.abs(c.floor - f);
    const ahead = (f - c.floor) * c.dir >= 0;
    if (ahead && c.dir === dir) return Math.abs(c.floor - f);
    const far = c.farthestStop(c.dir);
    const turn = c.dir === UP ? Math.max(far, f) : Math.min(far, f);
    return Math.abs(turn - c.floor) + Math.abs(turn - f);
  }
}

class ElevatorController {
  readonly cars: Car[];
  private readonly inbox: Command[] = [];
  private unassigned: { floor: number; dir: Direction }[] = [];
  time = 0;

  constructor(floors: number, carCount: number, policy: MovementPolicy, private readonly dispatcher: Dispatcher,
              private readonly onOpen: (carId: number, floor: number) => void = () => {}) {
    this.cars = Array.from({ length: carCount }, (_, i) => new Car(i, floors - 1, policy));
  }

  private get top(): number { return this.cars[0].top; }

  pressHall(floor: number, dir: Direction): void {
    if (floor < 0 || floor > this.top || dir === IDLE || (floor === this.top && dir === UP) || (floor === 0 && dir === DOWN))
      throw new Error("no such button");
    this.inbox.push({ kind: "hall", floor, dir });
  }
  pressCabin(carId: number, floor: number): void {
    if (floor < 0 || floor > this.top || !this.cars[carId]) throw new Error("no such button");
    this.inbox.push({ kind: "cabin", carId, floor });
  }
  setMaintenance(carId: number, on: boolean): void { this.inbox.push({ kind: "maintenance", carId, on }); }

  tick(): void {
    for (const c of this.inbox.splice(0)) this.apply(c);
    const retry = this.unassigned;
    this.unassigned = [];
    for (const h of retry) this.assign(h.floor, h.dir);
    for (const car of this.cars) {
      const opened = car.tick();
      if (opened !== null) this.onOpen(car.id, opened);
    }
    this.time++;
  }

  private apply(c: Command): void {
    if (c.kind === "hall") return this.assign(c.floor, c.dir);
    const car = this.cars[c.carId];
    if (c.kind === "cabin") { if (car.inService()) car.cabin.add(c.floor); return; }
    if (c.on) {
      for (const f of car.up) this.unassigned.push({ floor: f, dir: UP });
      for (const f of car.down) this.unassigned.push({ floor: f, dir: DOWN });
      car.up.clear(); car.down.clear(); car.cabin.clear();
      car.state = "MAINTENANCE"; car.dir = IDLE;
    } else if (!car.inService()) car.state = "IDLE";
  }

  private assign(floor: number, dir: Direction): void {
    if (this.cars.some((c) => c.calls(dir).has(floor))) return;
    const car = this.dispatcher.choose(floor, dir, this.cars);
    if (car) car.calls(dir).add(floor);
    else this.unassigned.push({ floor, dir });
  }

  quiet(): boolean { return this.inbox.length === 0 && this.unassigned.length === 0 && !this.cars.some((c) => c.hasStops()); }
}

// ─── Demo and self-checks ─────────────────────────────────

function check(ok: boolean, msg: string): void { if (!ok) throw new Error(`check failed: ${msg}`); }
type Step = (c: ElevatorController) => void;
const ticks = (n: number): Step => (c) => { for (let i = 0; i < n; i++) c.tick(); };

function run(policy: MovementPolicy, cars: number, ...script: Step[]): { log: string; time: number } {
  const log: string[] = [];
  const ctl = new ElevatorController(10, cars, policy, new NearestCarDispatcher(), (i, f) => log.push(`${i}@${f}`));
  for (const step of script) step(ctl);
  while (!ctl.quiet()) ctl.tick();
  return { log: log.join(), time: ctl.time };
}

async function main(): Promise<void> {
  check(run(new Look(), 1, (c) => c.pressCabin(0, 8), ticks(2), (c) => c.pressHall(5, DOWN)).log === "0@8,0@5", "direction-aware");

  const script: Step[] = [(c) => c.pressCabin(0, 3), ticks(1), (c) => c.pressHall(1, DOWN)];
  const look = run(new Look(), 1, ...script), scan = run(new Scan(), 1, ...script);
  check(look.time < scan.time && JSON.stringify(look) === JSON.stringify(run(new Look(), 1, ...script)), "LOOK, deterministic");

  check(run(new Look(), 2, (c) => c.pressCabin(1, 6), ticks(12), (c) => c.pressHall(5, UP)).log === "1@6,1@5", "nearest car");

  // Async "button panels" press while a tick loop runs on the same event loop.
  const busy = new ElevatorController(20, 3, new Look(), new NearestCarDispatcher());
  let pressing = true;
  const panel = async (seed: number) => {
    for (let i = 0; i < 100; i++) {
      await new Promise((r) => setTimeout(r, 0));
      const f = 1 + ((seed * 7 + i * 13) % 18);
      if (i % 2) busy.pressHall(f, i % 4 === 1 ? UP : DOWN);
      else busy.pressCabin((seed + i) % 3, f);
    }
  };
  const ticker = (async () => {
    while (pressing || !busy.quiet()) { busy.tick(); await new Promise((r) => setTimeout(r, 0)); }
  })();
  await Promise.all(Array.from({ length: 8 }, (_, s) => panel(s)));
  pressing = false;
  await ticker;
  check(busy.quiet(), "every request served");
  console.log("elevator: all checks passed");
}

main().catch((e) => { console.error(e); process.exit(1); });

The demos check that a DOWN call isn't picked up on the way up, that LOOK beats SCAN on one script and repeats it exactly, and that nearest car picks the closer car. Java and TypeScript also run the button-press race. Maintenance is in the section 9 tests.

Earlier reference implementation

The first version of this page is kept below, with corrections after it.

Core Classes & Interfaces

TypeScript Implementation

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

enum Direction {
  UP = 'UP',
  DOWN = 'DOWN',
  NONE = 'NONE',
}

enum ElevatorState {
  IDLE = 'IDLE',
  MOVING_UP = 'MOVING_UP',
  MOVING_DOWN = 'MOVING_DOWN',
  DOORS_OPEN = 'DOORS_OPEN',
  OUT_OF_SERVICE = 'OUT_OF_SERVICE',
}

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

interface Request {
  floor: number;
  direction: Direction;
  timestamp: Date;
}

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

class Elevator {
  private currentFloor: number = 1;
  private direction: Direction = Direction.NONE;
  private state: ElevatorState = ElevatorState.IDLE;
  private upStops: Set<number> = new Set();
  private downStops: Set<number> = new Set();
  private capacity: number;
  private currentLoad: number = 0;

  constructor(
    public readonly id: number,
    capacity: number = 10
  ) {
    this.capacity = capacity;
  }

  getCurrentFloor(): number {
    return this.currentFloor;
  }

  getDirection(): Direction {
    return this.direction;
  }

  getState(): ElevatorState {
    return this.state;
  }

  isIdle(): boolean {
    return this.state === ElevatorState.IDLE;
  }

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

  addStop(floor: number): void {
    if (floor > this.currentFloor) {
      this.upStops.add(floor);
    } else if (floor < this.currentFloor) {
      this.downStops.add(floor);
    }
    // If floor === currentFloor, open doors immediately
    if (floor === this.currentFloor) {
      this.openDoors();
    }
  }

  /** Compute distance to a floor considering current direction */
  distanceTo(floor: number, requestDir: Direction): number {
    const diff = Math.abs(this.currentFloor - floor);

    if (this.isIdle()) return diff;

    // Elevator going in same direction as request and hasn't passed the floor
    if (
      this.direction === Direction.UP &&
      requestDir === Direction.UP &&
      floor >= this.currentFloor
    ) {
      return floor - this.currentFloor;
    }

    if (
      this.direction === Direction.DOWN &&
      requestDir === Direction.DOWN &&
      floor <= this.currentFloor
    ) {
      return this.currentFloor - floor;
    }

    // Elevator must reverse — penalize
    return diff + 2 * this.getRemainingDistance();
  }

  private getRemainingDistance(): number {
    if (this.direction === Direction.UP && this.upStops.size > 0) {
      return Math.max(...this.upStops) - this.currentFloor;
    }
    if (this.direction === Direction.DOWN && this.downStops.size > 0) {
      return this.currentFloor - Math.min(...this.downStops);
    }
    return 0;
  }

  /** Move one floor in current direction */
  move(): void {
    if (this.state === ElevatorState.OUT_OF_SERVICE) return;

    if (!this.hasStops()) {
      this.state = ElevatorState.IDLE;
      this.direction = Direction.NONE;
      return;
    }

    this.decideDirection();

    if (this.direction === Direction.UP) {
      this.currentFloor++;
      this.state = ElevatorState.MOVING_UP;
    } else if (this.direction === Direction.DOWN) {
      this.currentFloor--;
      this.state = ElevatorState.MOVING_DOWN;
    }

    if (this.shouldStop()) {
      this.openDoors();
    }
  }

  private decideDirection(): void {
    if (this.direction === Direction.UP || this.direction === Direction.NONE) {
      if (this.upStops.size > 0) {
        this.direction = Direction.UP;
      } else if (this.downStops.size > 0) {
        this.direction = Direction.DOWN;
      }
    } else {
      if (this.downStops.size > 0) {
        this.direction = Direction.DOWN;
      } else if (this.upStops.size > 0) {
        this.direction = Direction.UP;
      }
    }
  }

  private shouldStop(): boolean {
    if (this.direction === Direction.UP) {
      return this.upStops.has(this.currentFloor);
    }
    if (this.direction === Direction.DOWN) {
      return this.downStops.has(this.currentFloor);
    }
    return false;
  }

  openDoors(): void {
    this.state = ElevatorState.DOORS_OPEN;
    this.upStops.delete(this.currentFloor);
    this.downStops.delete(this.currentFloor);
    // In production: emit event for passengers to enter/exit
  }

  closeDoors(): void {
    if (!this.hasStops()) {
      this.state = ElevatorState.IDLE;
      this.direction = Direction.NONE;
    } else {
      this.state =
        this.direction === Direction.UP
          ? ElevatorState.MOVING_UP
          : ElevatorState.MOVING_DOWN;
    }
  }

  setOutOfService(): void {
    this.state = ElevatorState.OUT_OF_SERVICE;
  }

  setInService(): void {
    this.state = ElevatorState.IDLE;
    this.direction = Direction.NONE;
  }
}

// ─── Dispatcher (Strategy Pattern) ───────────────────────

interface Dispatcher {
  dispatch(request: Request, elevators: Elevator[]): Elevator | null;
}

/**
 * LOOK Algorithm:
 * Picks the elevator with the minimum "cost" to serve the request.
 * Cost = distance considering direction and remaining stops.
 */
class LOOKDispatcher implements Dispatcher {
  dispatch(request: Request, elevators: Elevator[]): Elevator | null {
    const available = elevators.filter(
      (e) => e.getState() !== ElevatorState.OUT_OF_SERVICE
    );

    if (available.length === 0) return null;

    let best: Elevator | null = null;
    let bestCost = Infinity;

    for (const elevator of available) {
      const cost = elevator.distanceTo(request.floor, request.direction);
      if (cost < bestCost) {
        bestCost = cost;
        best = elevator;
      }
    }

    return best;
  }
}

/**
 * SCAN Dispatcher:
 * Always assigns to the nearest elevator moving in
 * the same direction. If none, assigns the nearest idle.
 */
class SCANDispatcher implements Dispatcher {
  dispatch(request: Request, elevators: Elevator[]): Elevator | null {
    const available = elevators.filter(
      (e) => e.getState() !== ElevatorState.OUT_OF_SERVICE
    );

    // Prefer elevator going in same direction
    const sameDir = available.filter(
      (e) => e.getDirection() === request.direction
    );

    const candidates = sameDir.length > 0 ? sameDir : available;

    let best: Elevator | null = null;
    let bestDist = Infinity;

    for (const e of candidates) {
      const dist = Math.abs(e.getCurrentFloor() - request.floor);
      if (dist < bestDist) {
        bestDist = dist;
        best = e;
      }
    }

    return best;
  }
}

/**
 * Destination Dispatch:
 * Groups passengers going to similar destinations into the same elevator.
 * Minimizes total stops per trip.
 */
class DestinationDispatcher implements Dispatcher {
  dispatch(request: Request, elevators: Elevator[]): Elevator | null {
    const available = elevators.filter(
      (e) => e.getState() !== ElevatorState.OUT_OF_SERVICE
    );

    if (available.length === 0) return null;

    // Prefer idle elevators first, then closest
    const idle = available.filter((e) => e.isIdle());
    const candidates = idle.length > 0 ? idle : available;

    let best: Elevator | null = null;
    let bestDist = Infinity;

    for (const e of candidates) {
      const dist = Math.abs(e.getCurrentFloor() - request.floor);
      if (dist < bestDist) {
        bestDist = dist;
        best = e;
      }
    }

    return best;
  }
}

// ─── Elevator System (Facade) ────────────────────────────

class ElevatorSystem {
  private elevators: Elevator[] = [];
  private pendingRequests: Request[] = [];

  constructor(
    private numFloors: number,
    numElevators: number,
    private dispatcher: Dispatcher = new LOOKDispatcher()
  ) {
    for (let i = 1; i <= numElevators; i++) {
      this.elevators.push(new Elevator(i));
    }
  }

  setDispatcher(dispatcher: Dispatcher): void {
    this.dispatcher = dispatcher;
  }

  /** Hall call — passenger presses UP or DOWN on a floor */
  requestElevator(floor: number, direction: Direction): void {
    if (floor < 1 || floor > this.numFloors) {
      throw new Error(`Invalid floor: ${floor}`);
    }

    const request: Request = { floor, direction, timestamp: new Date() };
    const elevator = this.dispatcher.dispatch(request, this.elevators);

    if (elevator) {
      elevator.addStop(floor);
    } else {
      this.pendingRequests.push(request); // all elevators out of service
    }
  }

  /** Cabin call — passenger selects a destination inside the elevator */
  selectFloor(elevatorId: number, floor: number): void {
    if (floor < 1 || floor > this.numFloors) {
      throw new Error(`Invalid floor: ${floor}`);
    }

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

    elevator.addStop(floor);
  }

  /** Advance simulation by one time step */
  step(): void {
    for (const elevator of this.elevators) {
      if (elevator.getState() === ElevatorState.DOORS_OPEN) {
        elevator.closeDoors();
      } else {
        elevator.move();
      }
    }
    this.processPendingRequests();
  }

  private processPendingRequests(): void {
    const remaining: Request[] = [];
    for (const req of this.pendingRequests) {
      const elevator = this.dispatcher.dispatch(req, this.elevators);
      if (elevator) {
        elevator.addStop(req.floor);
      } else {
        remaining.push(req);
      }
    }
    this.pendingRequests = remaining;
  }

  getStatus(): Array<{
    id: number;
    floor: number;
    direction: Direction;
    state: ElevatorState;
  }> {
    return this.elevators.map((e) => ({
      id: e.id,
      floor: e.getCurrentFloor(),
      direction: e.getDirection(),
      state: e.getState(),
    }));
  }
}

Python Implementation

from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from datetime import datetime
from enum import Enum
from typing import Optional


# ─── Enums ──────────────────────────────────────────────

class Direction(Enum):
    UP = "UP"
    DOWN = "DOWN"
    NONE = "NONE"


class ElevatorState(Enum):
    IDLE = "IDLE"
    MOVING_UP = "MOVING_UP"
    MOVING_DOWN = "MOVING_DOWN"
    DOORS_OPEN = "DOORS_OPEN"
    OUT_OF_SERVICE = "OUT_OF_SERVICE"


# ─── Request ────────────────────────────────────────────

@dataclass
class Request:
    floor: int
    direction: Direction
    timestamp: datetime = field(default_factory=datetime.now)


# ─── Elevator ───────────────────────────────────────────

class Elevator:
    def __init__(self, elevator_id: int, capacity: int = 10):
        self.id = elevator_id
        self._current_floor = 1
        self._direction = Direction.NONE
        self._state = ElevatorState.IDLE
        self._up_stops: set[int] = set()
        self._down_stops: set[int] = set()
        self._capacity = capacity
        self._current_load = 0

    @property
    def current_floor(self) -> int:
        return self._current_floor

    @property
    def direction(self) -> Direction:
        return self._direction

    @property
    def state(self) -> ElevatorState:
        return self._state

    @property
    def is_idle(self) -> bool:
        return self._state == ElevatorState.IDLE

    @property
    def has_stops(self) -> bool:
        return len(self._up_stops) > 0 or len(self._down_stops) > 0

    def add_stop(self, floor: int) -> None:
        if floor > self._current_floor:
            self._up_stops.add(floor)
        elif floor < self._current_floor:
            self._down_stops.add(floor)
        else:
            self.open_doors()

    def distance_to(self, floor: int, request_dir: Direction) -> int:
        diff = abs(self._current_floor - floor)

        if self.is_idle:
            return diff

        if (
            self._direction == Direction.UP
            and request_dir == Direction.UP
            and floor >= self._current_floor
        ):
            return floor - self._current_floor

        if (
            self._direction == Direction.DOWN
            and request_dir == Direction.DOWN
            and floor <= self._current_floor
        ):
            return self._current_floor - floor

        return diff + 2 * self._remaining_distance()

    def _remaining_distance(self) -> int:
        if self._direction == Direction.UP and self._up_stops:
            return max(self._up_stops) - self._current_floor
        if self._direction == Direction.DOWN and self._down_stops:
            return self._current_floor - min(self._down_stops)
        return 0

    def move(self) -> None:
        if self._state == ElevatorState.OUT_OF_SERVICE:
            return

        if not self.has_stops:
            self._state = ElevatorState.IDLE
            self._direction = Direction.NONE
            return

        self._decide_direction()

        if self._direction == Direction.UP:
            self._current_floor += 1
            self._state = ElevatorState.MOVING_UP
        elif self._direction == Direction.DOWN:
            self._current_floor -= 1
            self._state = ElevatorState.MOVING_DOWN

        if self._should_stop():
            self.open_doors()

    def _decide_direction(self) -> None:
        if self._direction in (Direction.UP, Direction.NONE):
            if self._up_stops:
                self._direction = Direction.UP
            elif self._down_stops:
                self._direction = Direction.DOWN
        else:
            if self._down_stops:
                self._direction = Direction.DOWN
            elif self._up_stops:
                self._direction = Direction.UP

    def _should_stop(self) -> bool:
        if self._direction == Direction.UP:
            return self._current_floor in self._up_stops
        if self._direction == Direction.DOWN:
            return self._current_floor in self._down_stops
        return False

    def open_doors(self) -> None:
        self._state = ElevatorState.DOORS_OPEN
        self._up_stops.discard(self._current_floor)
        self._down_stops.discard(self._current_floor)

    def close_doors(self) -> None:
        if not self.has_stops:
            self._state = ElevatorState.IDLE
            self._direction = Direction.NONE
        else:
            self._state = (
                ElevatorState.MOVING_UP
                if self._direction == Direction.UP
                else ElevatorState.MOVING_DOWN
            )

    def set_out_of_service(self) -> None:
        self._state = ElevatorState.OUT_OF_SERVICE

    def set_in_service(self) -> None:
        self._state = ElevatorState.IDLE
        self._direction = Direction.NONE


# ─── Dispatcher (Strategy Pattern) ──────────────────────

class Dispatcher(ABC):
    @abstractmethod
    def dispatch(
        self, request: Request, elevators: list[Elevator]
    ) -> Optional[Elevator]:
        ...


class LOOKDispatcher(Dispatcher):
    def dispatch(
        self, request: Request, elevators: list[Elevator]
    ) -> Optional[Elevator]:
        available = [
            e for e in elevators
            if e.state != ElevatorState.OUT_OF_SERVICE
        ]
        if not available:
            return None

        return min(
            available,
            key=lambda e: e.distance_to(request.floor, request.direction),
        )


class SCANDispatcher(Dispatcher):
    def dispatch(
        self, request: Request, elevators: list[Elevator]
    ) -> Optional[Elevator]:
        available = [
            e for e in elevators
            if e.state != ElevatorState.OUT_OF_SERVICE
        ]
        same_dir = [e for e in available if e.direction == request.direction]
        candidates = same_dir if same_dir else available
        if not candidates:
            return None

        return min(
            candidates,
            key=lambda e: abs(e.current_floor - request.floor),
        )


# ─── Elevator System ───────────────────────────────────

class ElevatorSystem:
    def __init__(
        self,
        num_floors: int,
        num_elevators: int,
        dispatcher: Optional[Dispatcher] = None,
    ):
        self._num_floors = num_floors
        self._dispatcher = dispatcher or LOOKDispatcher()
        self._elevators = [Elevator(i + 1) for i in range(num_elevators)]
        self._pending: list[Request] = []

    def set_dispatcher(self, dispatcher: Dispatcher) -> None:
        self._dispatcher = dispatcher

    def request_elevator(self, floor: int, direction: Direction) -> None:
        if not 1 <= floor <= self._num_floors:
            raise ValueError(f"Invalid floor: {floor}")

        request = Request(floor=floor, direction=direction)
        elevator = self._dispatcher.dispatch(request, self._elevators)

        if elevator:
            elevator.add_stop(floor)
        else:
            self._pending.append(request)

    def select_floor(self, elevator_id: int, floor: int) -> None:
        if not 1 <= floor <= self._num_floors:
            raise ValueError(f"Invalid floor: {floor}")

        elevator = next(
            (e for e in self._elevators if e.id == elevator_id), None
        )
        if not elevator:
            raise ValueError(f"Elevator {elevator_id} not found")
        elevator.add_stop(floor)

    def step(self) -> None:
        for elevator in self._elevators:
            if elevator.state == ElevatorState.DOORS_OPEN:
                elevator.close_doors()
            else:
                elevator.move()
        self._process_pending()

    def _process_pending(self) -> None:
        remaining = []
        for req in self._pending:
            elevator = self._dispatcher.dispatch(req, self._elevators)
            if elevator:
                elevator.add_stop(req.floor)
            else:
                remaining.append(req)
        self._pending = remaining

    def get_status(self) -> list[dict]:
        return [
            {
                "id": e.id,
                "floor": e.current_floor,
                "direction": e.direction.value,
                "state": e.state.value,
            }
            for e in self._elevators
        ]

Correction (2026-11-10): hall-call direction is ignored in the first-pass code

addStop files a stop by whether it's above or below the car, not by the button's direction. A DOWN call at floor 5 while the car travels from 1 to 8 goes into upStops, so the car stops at 5 on the way up, and the passenger who wants to go down boards a car going up. Running the first-pass TypeScript confirms it: with a cabin stop at 8 and a DOWN call at 5, the doors open at [5, 8]. The correct order is [8, 5]. The complete code keeps separate up and down call sets and serves a hall call only when the car leaves in its direction. Also, capacity and currentLoad are declared but never checked, so requirement 7 isn't implemented.

7. Concurrency

What's shared? Only the command inbox. Buttons on any thread call pressHall or pressCabin, which validate and enqueue. Nothing else is touched outside the tick thread.

Who owns the cars? The tick thread alone, so car state needs no locks: thread confinement. It's the first-pass "single consumer" option below, built out.

Why it's safe:

  • ConcurrentLinkedQueue (Java), queue.SimpleQueue (Python) and a plain array (TypeScript, one thread) make enqueueing atomic.
  • Duplicate presses collapse in assign: if any car already holds the call, the press is ignored.
  • Maintenance is also a command, so a car can't be taken out of service halfway through a dispatch decision.

The Java demo runs eight threads pressing 200 random buttons each while the main thread ticks, then asserts the building drains with no car leaving the shaft. The TypeScript demo does the same with async panels.

The trade-off: one thread does all scheduling, which is microseconds per tick even for dozens of cars. An expensive optimiser could run on a worker and send its decisions back through the inbox. See Concurrency Patterns in LLD and Thread-Safe Class Design.

Concurrency Considerations

Race Condition: Simultaneous Hall Calls

Two passengers pressing buttons at the same time could cause the same elevator to be dispatched to both, or a request could be lost.

Solutions:

  1. Request queue with single consumer — All hall calls go into a thread-safe queue. A single dispatcher thread processes them sequentially.

  2. Lock per elevator — When the dispatcher assigns a request, it locks the elevator's stop list. Other dispatches see the updated state.

  3. Event-driven architecture — Use an event bus. HallCallEvent → dispatcher processes → ElevatorAssignedEvent → elevator processes.

// Thread-safe request processing
class ElevatorSystem {
  private requestQueue = new AsyncQueue<Request>();

  async processRequests(): Promise<void> {
    while (true) {
      const request = await this.requestQueue.dequeue();
      // Single-threaded dispatch — no race conditions
      const elevator = this.dispatcher.dispatch(request, this.elevators);
      if (elevator) {
        elevator.addStop(request.floor);
      }
    }
  }
}

8. Extensibility: "the interviewer adds X"

Extension 1: express cars that only serve some floors

"Car 1 is an express: it only stops at 0, 8 and 9." Where: a decorator that filters the cars before any dispatcher chooses. Unchanged: cars, policies and the controller.

/** Decorator: restricts each car to the floors it serves, then lets any dispatcher choose. */
final class ZonedDispatcher implements Dispatcher {
    private final Dispatcher inner;
    private final Map<Integer, Set<Integer>> floorsByCar;      // car id -> floors it stops at
    ZonedDispatcher(Dispatcher inner, Map<Integer, Set<Integer>> floorsByCar) {
        this.inner = inner; this.floorsByCar = floorsByCar;
    }
    public Optional<Car> choose(HallCall call, List<Car> cars) {
        return inner.choose(call, cars.stream()
            .filter(c -> floorsByCar.getOrDefault(c.id, Set.of()).contains(call.floor())).toList());
    }
}

Extension 2: fire recall

"When the fire alarm sounds, every car returns to the lobby and ignores buttons." Where: a new command, applied in order with the button presses. It clears each car's work and sets one cabin stop at 0. The existing state machine does the rest, including turning a car that's heading up. Unchanged: Car, the policies and the dispatcher.

@dataclass(frozen=True)
class FireRecall:
    pass


class FireAwareController(ElevatorController):
    """Fire recall: every in-service car drops its work and returns to the lobby. Buttons stop working."""

    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.recalled = False

    def fire_alarm(self) -> None:
        self._inbox.put(FireRecall())                    # same queue, so it's ordered with button presses

    def _apply(self, c) -> None:
        if isinstance(c, FireRecall):
            self.recalled = True
            self._unassigned.clear()
            for car in self.cars:
                if car.in_service():
                    car.up.clear(); car.down.clear(); car.cabin.clear()
                    car.cabin.add(0)                     # the car's own state machine does the rest
        elif not self.recalled:                          # presses queued after the alarm are ignored
            super()._apply(c)

Extension 3: spread a burst of calls

"In the morning rush, nearest car sends every call to the same car." Where: a new dispatcher that adds a penalty per stop already queued. The check below shows four calls at floors 3 to 6: nearest car gives all four to car 0, busy-aware splits them 2 and 2.

/** Nearest car, plus a penalty per stop the car already has, so a burst of calls spreads across cars. */
class BusyAwareDispatcher implements Dispatcher {
  constructor(private readonly ticksPerStop = 3) {}
  choose(floor: number, dir: Direction, cars: readonly Car[]): Car | null {
    let best: Car | null = null, bestCost = Infinity;
    for (const c of cars) {
      if (!c.inService()) continue;
      const stops = c.cabin.size + c.up.size + c.down.size;
      const cost = NearestCarDispatcher.cost(c, floor, dir) + this.ticksPerStop * stops;
      if (cost < bestCost) { best = c; bestCost = cost; }
    }
    return best;
  }
}

All three extensions ran against the complete code with their own checks.

Extensions & Follow-ups

ExtensionDesign Impact
Express elevatorSubclass Elevator with restricted floor list; dispatcher filters candidates
Weight sensorAdd currentWeight to Elevator; skip dispatch if near capacity
Fire modeNew state: all elevators go to ground floor, doors open, disable hall calls
VIP priorityRequest gets priority field; dispatcher processes high-priority first
Energy optimizationDispatcher factors in elevator proximity to reduce total movement
Real-time displayObserver pattern: FloorDisplay subscribes to Elevator position changes
Group schedulingAssign floors to elevator zones (1-10 = Elevator A, 11-20 = Elevator B)

9. Testing

The tick is the testing seam. Tests press buttons, call tick() a known number of times and assert on positions, states and the door log, with no sleeps, no threads and no flakiness. Save the Python code as elevator.py to run this suite:

import unittest

from elevator import (Car, CarState, Direction, ElevatorController, Look,
                      NearestCarDispatcher, Scan)


class ElevatorTest(unittest.TestCase):
    def controller(self, cars=1, policy=None):
        self.log = []
        return ElevatorController(10, cars, policy or Look(), NearestCarDispatcher(),
                                  lambda i, f: self.log.append((i, f, self.ctl.time)))

    def drain(self):
        for _ in range(500):
            if self.ctl.quiet():
                return
            self.ctl.tick()
        self.fail("did not drain")

    def test_doors_stay_open_for_door_ticks(self):
        self.ctl = self.controller()
        self.ctl.press_cabin(0, 0)                  # a request at the current floor
        self.ctl.tick()
        self.assertIs(self.ctl.cars[0].state, CarState.DOORS_OPEN)
        for _ in range(Car.DOOR_TICKS):
            self.ctl.tick()
        self.assertIs(self.ctl.cars[0].state, CarState.IDLE)

    def test_scan_visits_the_top_floor_before_reversing(self):
        self.ctl = self.controller(policy=Scan())
        self.ctl.press_cabin(0, 3)
        self.ctl.tick()
        self.ctl.press_hall(1, Direction.DOWN)
        self.drain()
        _, _, served_at = self.log[-1]
        # 3 floors up, 6 more to the top, 8 back down to 1, plus two door stops and the first decision
        self.assertGreaterEqual(served_at, 3 + 6 + 8)

    def test_maintenance_hands_assigned_calls_to_another_car(self):
        self.ctl = self.controller(cars=2)
        self.ctl.press_hall(6, Direction.DOWN)
        self.ctl.tick()
        owner = next(c for c in self.ctl.cars if 6 in c.down)
        self.ctl.set_maintenance(owner.id, True)
        self.drain()
        self.assertEqual([(i, f) for i, f, _ in self.log], [(1 - owner.id, 6)])

    def test_duplicate_presses_collapse_to_one_stop(self):
        self.ctl = self.controller(cars=2)
        for _ in range(5):
            self.ctl.press_hall(4, Direction.UP)
        self.drain()
        self.assertEqual(len(self.log), 1)


if __name__ == "__main__":
    unittest.main()

Testing Strategy

Test TypeWhat to Test
UnitElevator.addStop() — adds to correct direction set
UnitElevator.move() — increments/decrements floor, changes state
UnitLOOKDispatcher — picks closest elevator going in right direction
UnitdistanceTo() — correct cost when same direction, opposite, idle
IntegrationFull scenario: request on floor 5, elevator moves from 1, stops, opens doors
Edge caseAll elevators out of service — request goes to pending queue
Edge caseElevator at top floor reverses direction
Performance100-floor building, 8 elevators, 1000 random requests — measure average wait time

10. Common mistakes

  1. One stop set per car. The hall-call direction is lost.
  2. Mixing dispatch and movement in one class, so neither can change alone.
  3. A thread per car with locks, when a single tick loop is simpler and testable.
  4. Thread.sleep in tests. Drive the tick instead.
  5. No turnaround rule. The car runs past the top floor, or idles with work left.
  6. A car in maintenance that keeps its assigned calls. Those passengers wait for ever.

11. Interview follow-ups

How do you prevent starvation?

LOOK can't starve a request: the car sweeps both ways while work exists, so any floor is reached within two sweeps. Dispatch can starve if a cost function keeps preferring new calls, so track each call's age and add it to the cost, or reassign calls older than a threshold.

How does destination dispatch change the design?

HallCall becomes TripRequest(from, to), and the dispatcher groups similar destinations into one car and tells the passenger which. The inbox, tick loop and policies don't change.

How would you measure that a new dispatcher is better?

The tick loop doubles as a simulator. Run both dispatchers on the same seeded day of traffic and compare mean wait, 95th-percentile wait and total travel. The seed makes the comparison repeatable.