Design an Elevator System

The state-machine classic: elevator states, the SCAN scheduling insight, Strategy for dispatch, and the multi-elevator follow-ups.

The analogy: a scanning sweep

Think of an elevator scheduler like a giant street sweeper. If the sweeper answered calls in the order they arrived (FIFO) — driving to block 2, then block 9, then back to block 3 — it would burn fuel and waste everyone's time.

Instead, the sweeper moves in a continuous direction, sweeping block by block, picking up all debris in its path. Only when there is no debris left in that direction does it reverse and sweep the other way.

This is the SCAN algorithm (also called the elevator algorithm). To make this work in software, we don't use a simple queue of jobs. We use two sorted sets per elevator: one for stops above (sorted ascending), and one for stops below (sorted descending). Our job is to design a system that dispatches the best elevator for a call, manages cabin states (moving, stopped, open doors), and synchronizes concurrency so two users never call the same elevator to different floors at the same millisecond.

Scope it first

"Design an elevator" is two problems wearing one prompt: object model (states, requests, doors) and scheduling (which elevator answers, in what order). Clarify both: "N elevators, M floors, hall calls (up/down button on a floor) + cabin calls (floor button inside), optimize average wait — ignore weight sensors and maintenance mode, OK?"

The two request types are the first real modeling decision — they carry different information: a hall call is (floor, direction); a cabin call is just (floor). Conflating them breaks scheduling later.

Entities & relationships

ElevatorSystem is the facade: receives calls, delegates "who goes?" to a DispatchStrategy, ticks the world via step().
Elevator owns its position, direction, door and stop set — and is a textbook state machine: IDLE → MOVING_UP / MOVING_DOWN → STOPPED(doors) → …. Transitions live in one place; "can't move with doors open" becomes an invariant, not a scattered if.
DispatchStrategy (Strategy pattern, like the parking lot's spot assignment): nearest-available, least-loaded, same-direction-first — swappable without touching the elevator.

Here's that state machine drawn out — note what's missing: there is no arrow from MOVING to DOORS_OPEN's neighbor states that skips STOPPED, and no arrow out of DOORS_OPEN while moving. Illegal transitions simply don't exist in the diagram, which is the whole point of the State pattern:

Now drive that machine yourself. Step through a call → arrive → doors → idle cycle, then add an illegal event (an arrive while still Idle) and watch it get refused — the invariant "can't arrive when you never moved" is enforced by the absence of a transition, not a scattered if.

Elevator controllertime O(1) per eventspace O(states)

events:callUparriveclosecallDownarriveclose

1/7Start in Idle. Each event is handled by the current state — the State pattern moves this branching out of one giant switch and into the state objects themselves.

state = Idle

events (try an illegal one)

The scheduling insight: SCAN, not FIFO

Serving requests in arrival order (FIFO) makes the cabin ping-pong: 2 → 9 → 3 → 8 wastes everyone's time. Real elevators run SCAN (the "elevator algorithm" — disk drives borrowed it from elevators): keep moving in the current direction, servicing every stop in that direction; reverse only when none remain.

The data structure follows from the algorithm: not a queue but two sorted sets per elevator — stops above (served ascending while going up) and stops below (descending while going down). In code:

Python

from enum import Enum
import threading
from typing import Set

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

class Elevator:
    def __init__(self, elevator_id: int):
        self.id = elevator_id
        self.current_floor = 0
        self.direction = Direction.IDLE
        self.up_stops: Set[int] = set()
        self.down_stops: Set[int] = set()
        self._lock = threading.Lock()

    def add_stop(self, floor: int):
        with self._lock:
            if floor > self.current_floor:
                self.up_stops.add(floor)
                if self.direction == Direction.IDLE:
                    self.direction = Direction.UP
            elif floor < self.current_floor:
                self.down_stops.add(floor)
                if self.direction == Direction.IDLE:
                    self.direction = Direction.DOWN

    def step(self):
        with self._lock:
            if self.direction == Direction.UP:
                self.current_floor += 1
                if self.current_floor in self.up_stops:
                    self.up_stops.remove(self.current_floor)
                    self._open_doors()
                if not self.up_stops:
                    self.direction = Direction.DOWN if self.down_stops else Direction.IDLE
            elif self.direction == Direction.DOWN:
                self.current_floor -= 1
                if self.current_floor in self.down_stops:
                    self.down_stops.remove(self.current_floor)
                    self._open_doors()
                if not self.down_stops:
                    self.direction = Direction.UP if self.up_stops else Direction.IDLE

    def _open_doors(self):
        print(f"Elevator {self.id} stopped at {self.current_floor}. Doors open.")

1. Java

Java

import java.util.TreeSet;
import java.util.concurrent.locks.ReentrantLock;

enum Direction { IDLE, UP, DOWN }

class Elevator {
    private final int id;
    private int currentFloor = 0;
    private Direction direction = Direction.IDLE;
    private final TreeSet<Integer> upStops = new TreeSet<>();
    private final TreeSet<Integer> downStops = new TreeSet<>();
    private final ReentrantLock lock = new ReentrantLock();

    public Elevator(int id) { this.id = id; }

    public void addStop(int floor) {
        lock.lock();
        try {
            if (floor > currentFloor) {
                upStops.add(floor);
                if (direction == Direction.IDLE) direction = Direction.UP;
            } else if (floor < currentFloor) {
                downStops.add(floor);
                if (direction == Direction.IDLE) direction = Direction.DOWN;
            }
        } finally {
            lock.unlock();
        }
    }

    public void step() {
        lock.lock();
        try {
            if (direction == Direction.UP) {
                currentFloor++;
                if (upStops.contains(currentFloor)) {
                    upStops.remove(currentFloor);
                    openDoors();
                }
                if (upStops.isEmpty()) {
                    direction = downStops.isEmpty() ? Direction.IDLE : Direction.DOWN;
                }
            } else if (direction == Direction.DOWN) {
                currentFloor--;
                if (downStops.contains(currentFloor)) {
                    downStops.remove(currentFloor);
                    openDoors();
                }
                if (downStops.isEmpty()) {
                    direction = upStops.isEmpty() ? Direction.IDLE : Direction.UP;
                }
            }
        } finally {
            lock.unlock();
        }
    }

    private void openDoors() {
        System.out.println("Elevator " + id + " opened doors at floor " + currentFloor);
    }
}

2. C++

C++

#include <iostream>
#include <set>
#include <mutex>

enum class Direction { IDLE, UP, DOWN };

class Elevator {
private:
    int id;
    int current_floor = 0;
    Direction direction = Direction::IDLE;
    std::set<int> up_stops;
    std::set<int> down_stops;
    std::mutex mtx;

    void openDoors() {
        std::cout << "Elevator " << id << " opened doors at floor " << current_floor << "\n";
    }
public:
    Elevator(int elevator_id) : id(elevator_id) {}

    void addStop(int floor) {
        std::lock_guard<std::mutex> lock(mtx);
        if (floor > current_floor) {
            up_stops.insert(floor);
            if (direction == Direction::IDLE) direction = Direction::UP;
        } else if (floor < current_floor) {
            down_stops.insert(floor);
            if (direction == Direction::IDLE) direction = Direction::DOWN;
        }
    }

    void step() {
        std::lock_guard<std::mutex> lock(mtx);
        if (direction == Direction::UP) {
            current_floor++;
            if (up_stops.count(current_floor)) {
                up_stops.erase(current_floor);
                openDoors();
            }
            if (up_stops.empty()) {
                direction = down_stops.empty() ? Direction::IDLE : Direction::DOWN;
            }
        } else if (direction == Direction::DOWN) {
            current_floor--;
            if (down_stops.count(current_floor)) {
                down_stops.erase(current_floor);
                openDoors();
            }
            if (down_stops.empty()) {
                direction = up_stops.empty() ? Direction::IDLE : Direction::UP;
            }
        }
    }
};

A simple, defensible DispatchStrategy: prefer elevators already moving toward the call in the same direction (cost = distance), then idle ones (distance), then opposite-direction ones (distance to their reversal point

back). Naming that cost function out loud is the senior move; the exact formula matters less.

Check yourself

Check yourself0/3 answered

1. Why is the SCAN algorithm (keeping direction until no stops remain) preferred over a FIFO queue in elevator design?

2. In modeling the system requests, why is it critical to distinguish between a HallCall and a CabinCall?

3. What does the step() method pattern (explicit time ticking) buy you in an LLD interview?

Where the patterns live

State — the elevator's lifecycle. Guards illegal transitions (MOVING → doors open) structurally.
Strategy — dispatch policy, and door-dwell policy if pressed.
Observer — floor displays and hall-button lamps subscribe to elevator events rather than being polled.
Singleton (resist it) — one ElevatorSystem, but inject it; tests will thank you.

Drive the design with `step()`

Making time explicit — a step()/tick method — turns the whole system into something you can unit-test deterministically ("after 3 ticks, elevator 2 is at floor 5 with doors open") and demo in the interview without threads. Real-time is then just a loop calling step() on a timer.

Think it through like the interview

Think it through: Design an Elevator SystemLLD Classic0/5 stages

PROBLEMDesign the classes and scheduling for N elevators serving M floors. Hall calls (up/down on a floor) and cabin calls (floor button inside) arrive continuously; minimize average wait.

1
Split the problem
“This prompt hides two different problems. Can I name them before designing?”
2
Find the state machine
“An elevator can't move with doors open. Where should that rule LIVE?”
unlocks after the stage above
3
Model the two request types
“Hall call vs cabin call — same class or different? What data does each carry?”
unlocks after the stage above
4
Derive the algorithm, then the data structure
“Requests at floors 2, 9, 3, 8 from floor 1 — what order do I serve them, and what structure holds them?”
unlocks after the stage above
5
Walk a scenario + break it
“Floor 6 presses DOWN; A is at 3 going up with stops {7,9}; B idle at 8. Who goes — and what's the race?”
unlocks after the stage above

Walk a scenario + the concurrency question

"User on floor 6 presses DOWN; elevator A is at 3 going up with stops 9; B is idle at 8." Dispatch: A is moving away-then-toward (cost ≈ (9−3) + (9−6) = 9), B is idle at distance 2 → B. B: IDLE → MOVING_DOWN, stops 6; arrives, doors open; user presses 1 → cabin call adds 1 to down-stops; continues down. SCAN means if someone on 4 presses DOWN meanwhile, B collects them en route — no extra trip.

Concurrency follow-up: hall calls arrive from many floors while elevators tick. Same answer family as the parking lot's last spot: serialize mutations — a lock (or single-threaded event loop) around assign-and-add-stop so a call is assigned exactly once, and make step() atomic per elevator. One elevator's state is touched by one thread at a time.

Practice — level up

An elevator controller is a scheduler: given the pending requests and the car's position, pick the next stop — then serve a sweep efficiently. These drills are that same "choose the next job" decision.

Practice ladder: Scheduling & dispatch0/4 solved

Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.

Warm-up — pick the next job

Single-Threaded CPUMedium
When free, take the best pending task by a policy — exactly 'which floor next'.

Core — assign over time

Many requests, limited movers, a clock.

Process Tasks Using ServersMedium
Route each request to a free resource as resources free up — multi-car dispatch.
Task SchedulerMedium
Order work under a cooldown constraint — sequencing a sweep of stops, not just choosing one.

Stretch — concurrent demand on a shared resource

Meeting Rooms IIMedium
Peak simultaneous demand over a timeline — how many cars a request pattern actually needs.