Code an elevator scheduler

In one minute

• An elevator system is a scheduler with motors attached. Two decisions dominate: which car answers a hall call (dispatch) and in what order a car visits its stops (the per-car algorithm).
• The per-car algorithm should be LOOK: keep going in the current direction while there are stops ahead, then reverse. It never starves a request, unlike "go to the nearest stop", and it is the same idea as the disk-scheduling algorithm of the same name.
• Drive the whole simulation from a deterministic step() tick. Real controllers run a fixed scan cycle; a tick-driven model is testable, replayable, and free of sleeps and threads in the core logic.
• Model each car as a state machine (idle, moving up, moving down, doors open, out of service) and the dispatcher as a strategy. Requirements change in those two places.
• The shape is ordering under contention: many requests, one shared resource that moves. It reappears as disk head scheduling, a delivery driver's route, and a database vacuum sweeping pages in order.

Requirements

Functional:

• A building has F floors and N cars. Each floor has up and down hall buttons (the bottom and top floors have one each). Each car has a panel of floor buttons.
• A hall call is assigned to exactly one car. A car call (pressed inside) is served by that car.
• Cars move one floor at a time, stop at requested floors, open and close doors, and report position and direction to displays.
• Cars can be taken out of service for maintenance.

Non-functional:

• Every accepted request is eventually served (no starvation).
• Safety invariants hold always: never move with doors open, never open doors between floors.
• Reasonable average wait time; in an interview, say "minimise wait, bound the worst case" rather than promise optimality.

Out of scope: weight sensors, fire service modes, destination dispatch keypads and energy optimisation. Name them and put them in Extensibility.

Entities and relationships

• ElevatorSystem is the controller and mediator. Buttons talk to it, never to cars directly. It owns the cars, the dispatcher and the tick loop.
• ElevatorCar holds its current floor, direction, door state and its set of pending stops. It runs LOOK on its own stops and does not know other cars exist.
• Door is a small state machine (closed, opening, open, closing). Keeping it separate lets you add a door-obstruction sensor without touching movement logic.
• Request is a value: either a hall call (floor plus direction) or a car call (car id plus floor). Making requests objects is the Command pattern in miniature: they can be queued, logged and replayed.
• Dispatcher is an interface with one method: given the cars and a hall call, return a car. Nearest-car, zoning and destination dispatch are implementations.
• Display and hall lanterns observe car position and direction.

Relationships: the system is composed of cars; each car owns one door and its stop set. Requests are transient and get folded into a car's stop set once assigned. The dispatcher reads car state but never mutates it.

Class diagram

classDiagram
    class ElevatorSystem {
      -cars: ElevatorCar[]
      -dispatcher: Dispatcher
      +hallCall(floor, direction) CarId
      +requestFloor(carId, floor)
      +step() Stop[]
    }
    class ElevatorCar {
      +floor: int
      +direction: Direction
      -stops: Set~int~
      -state: CarState
      +addStop(floor)
      +step() int
    }
    class Door {
      +state: DoorState
      +open()
      +close()
    }
    class CarState {
      <<interface>>
      +onTick(car)
      +onRequest(car, floor)
    }
    class Dispatcher {
      <<interface>>
      +pick(cars, floor, direction) CarId
    }
    class Request {
      +floor: int
      +direction: Direction
      +carId: int
    }
    ElevatorSystem "1" *-- "many" ElevatorCar
    ElevatorCar "1" *-- "1" Door
    ElevatorCar --> CarState
    ElevatorSystem --> Dispatcher
    ElevatorSystem ..> Request
    NearestCarDispatcher ..|> Dispatcher
    Idle ..|> CarState
    Moving ..|> CarState
    DoorsOpen ..|> CarState
    OutOfService ..|> CarState

Key flows

A hall call is assigned at once; movement happens only on ticks. Separating "decide" from "move" is what makes the system deterministic.

sequenceDiagram
    participant P as Passenger
    participant B as HallButton
    participant S as ElevatorSystem
    participant D as Dispatcher
    participant C as Car 2
    participant L as HallLantern
    P->>B: press UP at floor 7
    B->>S: hallCall(7, UP)
    S->>D: pick(cars, 7, UP)
    D-->>S: car 2 (cost 3)
    S->>C: addStop(7)
    S-->>L: light UP lantern, car 2
    loop every tick
        S->>C: step()
        C-->>S: moved to next floor or stopped
    end
    C-->>S: stopped at 7
    S-->>L: chime, clear UP light
    P->>C: press 12
    S->>C: addStop(12)

Design patterns used and why

• State for the car. Unlike a parking ticket, car states really behave differently. A floor request while out of service is rejected; a tick while doors are open counts down the dwell timer instead of moving; a tick while idle checks for new stops. One class per state keeps each onTick short and makes illegal transitions (move while doors open) impossible to write by accident.
• Strategy for dispatch. The first version picks the nearest suitable car. A busy office tower wants zoning in the morning rush (cars 1 to 3 serve floors 1 to 20 only); a hotel wants something else. Each is a Dispatcher implementation selected by configuration or time of day.
• Mediator: ElevatorSystem sits between buttons, cars and displays. Without it, every button would need references to every car.
• Command: requests are objects. You can queue them while the controller is mid-tick, log them for analysis and replay a day's traffic against a new dispatcher before shipping it.
• Observer for lanterns and floor displays: they subscribe to car events and do not poll.

Concurrency and edge cases

• Asynchronous input, synchronous core. Buttons are pressed at any moment from many places; the scheduler must see a consistent snapshot. Put requests on a queue (or take a mutex), drain the queue at the start of each tick, then step every car. The core logic never runs on two threads at once, which removes a whole class of bugs.
• Request for the floor you are passing. A car moving at 2 m/s cannot stop at a floor it is half a metre from. Real controllers compute the next floor where stopping is still possible and only accept stops at or beyond it. In the tick model, the car commits to the next floor as soon as it starts moving.
• Request for the current floor. If the car is idle there, reopen the doors instead of moving. The practice code serves it on the next tick without moving.
• Duplicate presses. People press the button five times. Stops are a set, so repeats are free and idempotent.
• Starvation. Shortest-seek-first (always go to the nearest stop) can leave someone on floor 30 waiting forever while floors 2 to 6 keep calling. LOOK bounds the wait: a request is reached within at most two sweeps.
• Direction of hall calls. An up call at floor 7 should not be answered by a car passing 7 on its way down; the passenger would ride the wrong way. Production cars keep separate up and down stop sets. The practice keeps one set and handles direction only in dispatch, which is a reasonable interview simplification if you say so.
• Car taken out of service with stops pending. Its hall calls must be reassigned to other cars, or those passengers wait forever. The car calls die with it; passengers inside are taken to the nearest floor.

Down the stack

Extensibility

• Separate up and down stops: replace the single stop set with two, and let a car pick up only calls in its current direction. LOOK still works; the reversal point now also checks the other set.
• Destination dispatch: passengers enter their destination in the lobby and are told which car to take. The request becomes (origin, destination) and the dispatcher groups people going to nearby floors. Only the Request type and a new dispatcher change.
• Zoning and peak modes: a dispatcher that consults a schedule. In the morning up-peak, idle cars return to the lobby.
• Capacity: add load to the car state; a full car skips hall calls but still serves car calls.
• Fire service and maintenance: new car states. Fire recall sends every car to a designated floor and ignores all calls; the State pattern makes this an added class, not an edited switch statement.
• Express cars and sky lobbies: cars carry the set of floors they can serve, and the dispatcher filters on it.

Leadership lens

• Build first: the single-car LOOK state machine with a deterministic tick and a replay test harness. Every later dispatcher is judged by replaying recorded traffic through it, so the harness is the most valuable asset.
• Ask in review: what is the worst-case wait and how do you know; what happens to assigned calls when a car goes out of service; which invariants live in hardware and which in software.
• Measure what passengers feel: average and 95th-percentile wait and journey time, from logs, per hour of day. Tune dispatch against those, not against intuition.
• Ownership: safety-critical control and scheduling should be separate components with separate review bars. A dispatcher bug costs seconds; a door-interlock bug costs lives.
• In an interview, say which simplifications you make (one stop set, no capacity) before coding. It shows you know the real problem is bigger.

Check yourself

1. Why does LOOK not starve requests while shortest-seek-first can?

   Show answer

   LOOK only reverses when no stops remain ahead, so any waiting floor is reached within at most two sweeps. Shortest-seek-first always picks the nearest stop, so a steady stream of nearby requests can keep a far floor waiting forever.

2. Why should the dispatcher penalise a car that is moving away from the call?

   Show answer

   That car must finish its sweep and come back, so its true arrival time is much longer than its distance suggests. Using raw distance would assign calls to cars that cannot serve them soon.

3. What does a tick-driven step() model buy you over a thread per car with sleeps?

   Show answer

   Determinism: the same inputs at the same ticks produce the same outputs, so tests are exact and recorded traffic can be replayed against a new algorithm. It also matches the scan cycle real controllers use.

4. Where would you put "never move with the doors open" so that a scheduler bug cannot violate it?

   Show answer

   In the car's state machine, so the moving transition is impossible from the doors-open state, and ultimately in the hardware safety chain, which cuts power regardless of what software asks for.

Watch

• Low-Level Design Interview: Design an Elevator w/ a Ex-Meta Staff Engineer (Hello Interview): a mock interview that shows how to scope the problem and structure the classes.
• Elevator System | Google SWE Teaches Low Level Design Episode 3 (Jordan has no life): a code-first walkthrough including the scheduling logic.
• State Pattern, Design Patterns ep 17 (Christopher Okhravi): the pattern behind the car's lifecycle, explained carefully.

Free resources

• Elevator algorithm (Wikipedia): SCAN and LOOK as disk-scheduling algorithms, the same ideas used per car here.
• Destination dispatch (Wikipedia): how modern high-rise systems group passengers by destination.
• State pattern (Refactoring.Guru): the car state machine as classes, with examples in several languages.
• Strategy pattern (Refactoring.Guru): the shape of a pluggable dispatcher.
• Programmable logic controller (Wikipedia): the scan-cycle controllers that a step() model imitates.