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:
- 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.
- 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
| Question | Assumption if the interviewer says "you decide" | What it changes |
|---|---|---|
| Floors and cars? | 10 floors (0 to 9), 1 to 3 cars | Constructor 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 first | Dispatcher strategy |
| SCAN or LOOK? | LOOK, but make it switchable | MovementPolicy strategy |
| How is time modelled? | Discrete ticks: one floor per tick, doors open for two ticks | A tick() method that tests can call |
| Buttons pressed concurrently? | Yes, from many threads | A thread-safe command inbox |
| Out of service? | A car can enter maintenance, and its calls go to other cars | A MAINTENANCE state |
Requirements & Use Cases
Functional Requirements
- Building has N floors and M elevators
- Each floor has Up and Down request buttons (hall calls)
- Inside each elevator, passengers select destination floors (cabin calls)
- Elevators move up and down, opening doors at requested floors
- Scheduling algorithm determines which elevator services which request
- Display current floor and direction for each elevator
- 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
| Actor | Use Case |
|---|---|
| Passenger | Press hall button (up/down) on a floor |
| Passenger | Select destination floor inside elevator |
| System | Dispatch optimal elevator to a hall call |
| System | Move elevator and open doors at stops |
| Admin | Configure number of elevators and floors |
| Admin | Take an elevator out of service |
2. Entities and relationships
| Entity | Owns | Invariant |
|---|---|---|
ElevatorController | Cars, the command inbox, unassigned calls, the dispatcher | Every accepted hall call is held by exactly one car, or waits in unassigned |
Car | Floor, direction, state, cabin stops, up calls, down calls | Never leaves the shaft. A hall call is cleared only when the doors open for its direction. |
MovementPolicy | The keep-going-or-turn rule | Pure. Looks at the car and answers. |
Dispatcher | The rule for choosing a car | Pure. Never mutates a car. |
Command | HallCall, CabinCall, Maintenance | Immutable 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
| Pattern | Where | Why |
|---|---|---|
| Strategy | MovementPolicy (LOOK, SCAN) and Dispatcher (nearest car) | Two independent decisions, each switchable |
| Command | HallCall, CabinCall, Maintenance in the inbox | Button presses become data, applied in order on one thread |
| State, as an enum | CarState with a switch in tick | Four states with short transitions. State classes would scatter one small machine across five files. |
| Decorator | ZonedDispatcher (extension 1) | Restrict the cars, then reuse any dispatcher |
The movement policies
| Policy | Rule | Behaviour |
|---|---|---|
| LOOK | Reverse when nothing is left ahead | Fewer wasted floors. The usual default. |
| SCAN | While any work exists, run to the end of the shaft before reversing | Predictable, but slower. The demo shows a call at floor 1 served later under SCAN. |
| FCFS | Serve requests in arrival order | Easy, 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.
| Alternative | Why it was rejected |
|---|---|
| A thread per car with locks on its stop sets | Many locks and real interleavings to reason about, for a system that changes state a few times a second |
Calls in one SortedSet per car | Loses the hall-call direction, which is the bug in the first-pass code |
| Car classes per state | Fine for a richer machine. Here it's ceremony. |
Scheduling Algorithms
| Algorithm | How It Works | Pros | Cons |
|---|---|---|---|
| FCFS | Serve requests in arrival order | Simple | Terrible performance — elevator bounces randomly |
| SCAN | Move in one direction serving all requests, then reverse | Fair | Goes to extremes even without requests |
| LOOK | Like SCAN but reverses when no more requests in current direction | Efficient | Slightly more complex |
| Destination Dispatch | Passengers enter destination before entering elevator; group by destination | Best throughput | Requires 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
| Pattern | Where | Why |
|---|---|---|
| Strategy | Dispatcher interface with LOOK, SCAN, Destination variants | Swap scheduling algorithms at runtime without changing the system |
| State | ElevatorState enum driving Elevator.move() behavior | Elevator behavior changes based on current state (idle, moving, doors open) |
| Facade | ElevatorSystem | Hides dispatch logic, elevator management, pending queue from callers |
| Observer (extension) | Floor displays watching elevator positions | Decouple 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:
-
Request queue with single consumer — All hall calls go into a thread-safe queue. A single dispatcher thread processes them sequentially.
-
Lock per elevator — When the dispatcher assigns a request, it locks the elevator's stop list. Other dispatches see the updated state.
-
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
| Extension | Design Impact |
|---|---|
| Express elevator | Subclass Elevator with restricted floor list; dispatcher filters candidates |
| Weight sensor | Add currentWeight to Elevator; skip dispatch if near capacity |
| Fire mode | New state: all elevators go to ground floor, doors open, disable hall calls |
| VIP priority | Request gets priority field; dispatcher processes high-priority first |
| Energy optimization | Dispatcher factors in elevator proximity to reduce total movement |
| Real-time display | Observer pattern: FloorDisplay subscribes to Elevator position changes |
| Group scheduling | Assign 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 Type | What to Test |
|---|---|
| Unit | Elevator.addStop() — adds to correct direction set |
| Unit | Elevator.move() — increments/decrements floor, changes state |
| Unit | LOOKDispatcher — picks closest elevator going in right direction |
| Unit | distanceTo() — correct cost when same direction, opposite, idle |
| Integration | Full scenario: request on floor 5, elevator moves from 1, stops, opens doors |
| Edge case | All elevators out of service — request goes to pending queue |
| Edge case | Elevator at top floor reverses direction |
| Performance | 100-floor building, 8 elevators, 1000 random requests — measure average wait time |
10. Common mistakes
- One stop set per car. The hall-call direction is lost.
- Mixing dispatch and movement in one class, so neither can change alone.
- A thread per car with locks, when a single tick loop is simpler and testable.
Thread.sleepin tests. Drive the tick instead.- No turnaround rule. The car runs past the top floor, or idles with work left.
- 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.