Design an Elevator System
Multi-car scheduling, direction/state machines, and pluggable dispatch strategies under concurrent requests.
Problem Statement
Design the object model for a multi-car elevator system in a building. The system receives external hall calls from floors and internal car calls from passengers inside an elevator. A controller assigns hall calls to cars, each car maintains stop queues, moves one floor at a time, opens doors at served stops, and keeps its direction and lifecycle state consistent.
This is an intermediate LLD problem because the interesting part is not just classes. You must reason about scheduling, request queues, state transitions, display updates, and concurrent requests arriving while cars are moving.
Business context
Elevator systems appear in interviews at Amazon, Google, Uber, and Microsoft because they compress several real control-system concerns into one design: dispatching across a fleet, local car scheduling, state machines, and safety around shared mutable state.
A strong answer separates bank-level dispatch from car-level service. The controller decides which car should answer a hall call. The chosen car then serves its ordered stop queues using a SCAN or LOOK style rule. Floor indicators and displays observe state changes rather than owning scheduling logic.
Functional Requirements
Support a building with a configurable minimum floor, maximum floor, and elevator count.
Accept external hall requests containing the source floor and desired direction.
Accept internal car requests containing the elevator id and destination floor.
Dispatch hall calls to an elevator through a pluggable scheduling strategy.
Maintain per-car request queues so each car can continue in its current direction before reversing.
Move cars through states such as idle, moving up, moving down, and doors open.
Advance the simulation with a tick that moves every car by at most one floor.
Validate floor ranges and reject invalid elevator ids or impossible hall directions.
Non-Functional Requirements
Scheduling quality
A hall call should usually go to the car with the lowest estimated pickup cost, preferring cars already moving toward the caller in the requested direction.
Concurrency safety
Hall calls, car calls, and ticks may arrive from different button panels or a scheduler thread. The controller and each elevator need clear synchronization boundaries.
Extensibility
Nearest-car dispatch, zoning, VIP priority, destination dispatch, and energy-saving policies should be replaceable without rewriting Elevator.
Responsiveness
Submit operations should do small in-memory work: choose a car, enqueue a stop, and return quickly. Physical movement happens over ticks.
Observability
Floor displays, car panels, and monitoring systems should learn about current floor, direction, and door state through update events or snapshots.
Requirement Clarification
QAre we designing one elevator or a bank of elevators?
A bank of elevators. The controller receives hall calls and assigns one elevator; each elevator owns its own stop queues and movement state.
QDo hall calls include direction?
Yes. A person outside the car asks for up or down, so the dispatch strategy can prefer cars already moving the right way.
QDo internal car requests need direction?
No. Inside the car, the passenger selects a destination floor. Direction is derived from the car current floor and current service plan.
QIs this a real-time hardware controller?
No. Model the domain and scheduling logic. Hardware buttons, motors, sensors, and doors are adapters around the core model.
QShould the controller be a global singleton?
Treat it as one coordinator per elevator bank. The reference Java keeps it owned by Building for testability, while production dependency injection would register exactly one controller for that bank.
QHow much scheduling sophistication is expected?
Start with nearest-car dispatch at the bank level and SCAN or LOOK behavior inside each car. Then discuss zoning, load, priority, and fairness as extensions.
UML Class Diagram
Sequence Diagram
Entity Identification
Building
Public facade for panels, tests, and simulations. It validates floor ranges and forwards button presses to the single controller for this elevator bank.
ElevatorController
Bank coordinator. It owns the elevator list, delegates hall-call assignment to a DispatchStrategy, routes car calls by elevator id, and advances all cars on each tick.
Elevator
Car aggregate. It stores current floor, direction, lifecycle state, and two ordered stop queues, then decides how to move or open doors on each tick.
Request
Base value for a requested floor. HallRequest adds desired direction; CarRequest adds the elevator id that received the destination selection.
DispatchStrategy
Policy interface for selecting an elevator for a hall call. NearestCarStrategy is the default implementation in the reference code.
Direction
Small enum for movement intent: up, down, or idle. It also exposes opposite for policies that need reversal logic.
ElevatorState
Explicit lifecycle enum for idle, moving up, moving down, and doors open. It keeps door-open behavior visible instead of hiding it in booleans.
Display observer
Production-facing role for floor indicators and car panels. It should subscribe to current-floor, direction, and door-state changes instead of influencing scheduling.
Design Patterns Used
ElevatorState makes the car lifecycle explicit: idle, moving up, moving down, and doors open. The reference uses an enum state machine; a larger implementation can promote each state into a concrete state class.
DispatchStrategy separates bank-level scheduling from controller flow. NearestCarStrategy can be replaced with LOOK, zoning, load-aware, or priority scheduling without changing Elevator.
There should be one authoritative ElevatorController per elevator bank. The reference keeps that controller owned by Building for testability; production dependency injection can register it as the bank singleton.
Floor displays, car displays, and telemetry should observe state snapshots after movement or door changes. They must not poll or mutate elevator stop queues.
Step-by-Step Design
1Split hall requests from car requests
A hall call has floor plus desired direction. A car call has elevator id plus destination floor. Keeping the two request types separate avoids guessing intent later.
abstract class Request { private final int floor; protected Request(int floor) { this.floor = floor; } } class HallRequest extends Request { private final Direction direction; HallRequest(int floor, Direction direction) { super(floor); this.direction = direction; } }2Keep SCAN or LOOK ordering inside the elevator
Use one ascending set for upward stops and one descending set for downward stops. The car continues in its current direction while stops remain, then reverses when needed.
class Elevator { private final NavigableSet<Integer> upStops = new TreeSet<>(); private final NavigableSet<Integer> downStops = new TreeSet<>(Collections.reverseOrder()); private int currentFloor; synchronized void addStop(int floor) { if (floor > currentFloor) { upStops.add(floor); } else if (floor < currentFloor) { downStops.add(floor); } else { openDoors(); } } }3Dispatch hall calls through a strategy
The controller should not know the scoring formula. It asks DispatchStrategy for a car; NearestCarStrategy scores every car by estimated pickup distance and direction compatibility.
class NearestCarStrategy implements DispatchStrategy { public Elevator chooseElevator(List<Elevator> elevators, HallRequest request) { return elevators.stream() .min(Comparator.comparingInt(elevator -> elevator.estimatedDistanceTo(request))) .orElseThrow(() -> new IllegalStateException("no elevators available")); } }4Drive a visible car and door state machine
Each tick either chooses a direction, moves one floor, opens doors at a requested stop, or returns to idle. Door-open is a first-class state so displays and tests can observe it.
5Use one controller per bank and synchronize entry points
Building owns one ElevatorController for the bank. Controller methods are synchronized, and Elevator mutators are synchronized, so dispatch, car-call routing, and ticking do not interleave into corrupt queues.
6Publish display updates as observer notifications
A production system should emit snapshots after movement and door changes. Displays observe those snapshots; they do not choose elevators or inspect internal stop sets.
interface ElevatorObserver { void onChanged(int elevatorId, int floor, Direction direction, ElevatorState state); } class FloorDisplay implements ElevatorObserver { public void onChanged(int elevatorId, int floor, Direction direction, ElevatorState state) { render(elevatorId, floor, direction, state); } }
Complete Java Implementation
Explanation of Every Class
Direction
Movement-intent enum with UP, DOWN, and IDLE. The opposite method supports policies that need to reverse direction cleanly.
ElevatorState
Lifecycle enum for IDLE, MOVING_UP, MOVING_DOWN, and DOORS_OPEN. The isMoving helper keeps movement checks readable.
Request
Abstract base value that stores and validates a requested floor. It prevents negative floors before a request reaches scheduling code.
HallRequest
External request from a floor panel. It stores the desired direction and rejects IDLE because a hall call must mean up or down.
CarRequest
Internal request from inside a specific car. It carries the elevator id plus destination floor, leaving direction derivation to the elevator.
Elevator
The core car model. It stores bounds, current floor, current direction, state, and two ordered stop sets. addStop enqueues a destination; step moves one floor or opens doors; estimatedDistanceTo supports dispatch scoring.
DispatchStrategy
Scheduling interface used by the controller to choose an elevator for a HallRequest. This is the main seam for replacing nearest-car with zoning, LOOK, or load-aware policies.
NearestCarStrategy
Default strategy that picks the elevator with the smallest estimatedDistanceTo score. The Elevator score penalizes cars moving away or serving the opposite direction.
ElevatorController
Bank coordinator. It owns a copy of the elevator list, routes hall calls through DispatchStrategy, routes car calls by id, and ticks every car. Its public methods are synchronized.
Building
Facade for clients and simulations. It creates the elevators, installs NearestCarStrategy, validates floor ranges, exposes hall and car button methods, and advances time with runOneTick.
Dry Run
Sample input
Building floors 0 to 10 with two elevators, both starting at floor 0. Events: hall up at 3, hall up at 7, tick, passenger in elevator 1 selects floor 9.
| Step | Event | Controller decision | Elevator 1 | Elevator 2 | Result |
|---|---|---|---|---|---|
| 1 | pressHallButton(3, UP) | Nearest car chooses E1 by tie order | upStops {3} | idle at 0 | Return elevator id 1 |
| 2 | pressHallButton(7, UP) | E1 is already moving toward call, E2 is idle at 0 | upStops {3, 7} | idle at 0 | Return elevator id 1 |
| 3 | runOneTick() | Controller ticks every car | moves from 0 to 1, MOVING_UP | stays IDLE | No stop served yet |
| 4 | selectFloor(1, 9) | Route car call to E1 | upStops {3, 7, 9} | idle at 0 | Destination queued |
| 5 | two more ticks | Controller ticks every car | reaches 3, DOORS_OPEN | stays IDLE | Hall call at 3 served |
| 6 | next tick after doors open | E1 chooses direction again | continues MOVING_UP toward 7 and 9 | stays IDLE | SCAN behavior resumes |
The key interview point is that the controller assigns hall calls, but E1 owns the ordered stop queue after assignment. New car calls merge into the same direction queue while the car is moving.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| submitHallCall | O(E + log S) | O(1) | E elevators are scored by the dispatch strategy; enqueueing the chosen floor is O(log S). |
| submitCarCall | O(E + log S) | O(1) | The reference scans for the elevator id, then inserts the destination into one ordered stop set. |
| tick | O(E log S) | O(1) | Each elevator moves at most one floor and may remove a served stop from a TreeSet. |
| estimatedDistanceTo | O(1) | O(1) | Uses current floor, direction, and request direction to compute a penalty-adjusted distance. |
E is number of elevators and S is pending stops in one elevator. A production controller would keep elevators in a map by id to make car calls O(log S), and advanced dispatch may cost more if it simulates future routes.
Extensibility
New dispatch algorithm
Implement DispatchStrategy for zoning, LOOK, destination dispatch, VIP priority, load-aware scoring, or energy-saving night mode. Controller flow stays the same.
Richer car state
Promote ElevatorState enum values into state objects if door timers, overload, maintenance, emergency stop, or fire-service mode require state-specific behavior.
Display and telemetry observers
Add observers that receive snapshots after addStop, step, and openDoors. Floor displays and metrics can update without reading private queues.
Multiple elevator banks
Introduce Bank or Zone aggregates, each with its own singleton controller and strategy. A building-level router chooses the bank first.
Persistence and replay
Store requests, state transitions, and served stops in an event log so operations can replay incidents and recover after controller restarts.
Alternative Designs
Central global scheduler
Keep all pending hall and car requests in the controller, and compute complete routes for every elevator on each decision.
Tradeoffs
Can optimize globally, but the controller becomes complex and highly contended. The reference keeps local car queues simpler and easier to reason about.
Pure SCAN without nearest-car dispatch
Assign each hall call to a fixed car or zone and let that car run SCAN locally.
Tradeoffs
Very predictable and simple, but can leave an idle nearby car unused while another busy car owns the zone.
Destination dispatch
Ask passengers for destination before boarding, group compatible riders, and assign a car based on route clustering.
Tradeoffs
Reduces stops in busy buildings, but changes the request model and requires richer kiosk and passenger-flow handling.
Actor per elevator
Run each Elevator as an actor with a mailbox; the controller sends assignment messages and receives snapshots.
Tradeoffs
Excellent isolation and concurrency, but adds asynchronous delivery, ordering, and failure-handling complexity.
Common Mistakes
- ×
Mixing dispatch and movement by letting ElevatorController directly manipulate stop queues and current floor.
- ×
Treating hall and car requests as the same object, losing the requested hall direction.
- ×
Using one unsorted list of stops, causing cars to bounce inefficiently instead of serving in a SCAN or LOOK order.
- ×
Representing doors as a boolean and forgetting the DOORS_OPEN lifecycle state.
- ×
Hard-coding nearest-car logic in the controller instead of behind DispatchStrategy.
- ×
Ignoring concurrent hall calls and ticks, which can corrupt queues or assign based on stale state.
- ×
Letting floor displays poll private elevator fields instead of observing published snapshots.
- ×
Creating multiple controllers for the same bank, which splits the source of truth for assignments.
Follow-up Interview Questions
QHow would you implement LOOK instead of simple nearest-car dispatch?
Keep local elevator queues ordered by direction, but in DispatchStrategy score the projected pickup using current route endpoints instead of raw floor distance. LOOK avoids traveling to the building edge when no stop exists there.
QHow do you prevent a hall call from being assigned twice under concurrency?
Make request submission atomic at the controller boundary. In a distributed setup, store hall requests with an assigned elevator id using a compare-and-set or database transaction.
QWhere should door timing live?
In the car state machine. DOORS_OPEN can hold a timer or become a DoorOpenState object that consumes ticks until the close condition is met.
QHow would displays update in real time?
Publish immutable snapshots after state transitions. Floor displays, car panels, and telemetry subscribe as observers and render without changing scheduling state.
QHow do you handle elevator capacity or overload?
Add load to the elevator snapshot and scoring function. If overloaded, reject new car movement, keep doors open, and avoid assigning hall calls to that car.
QWhat changes for multiple banks or zones?
Introduce a BuildingRouter or BankController layer. It chooses the bank or zone first; within each bank, the existing ElevatorController and DispatchStrategy remain unchanged.
Production Considerations
Safety and hardware integration
Real systems must integrate door sensors, motor controllers, brake status, fire-service mode, emergency stops, and interlocks. The LLD core should expose safe commands, not talk directly to raw hardware.
Threading model
The reference uses synchronized methods. Production systems often use a single event loop or actor per car to make ordering explicit and avoid lock-order deadlocks.
Fairness and starvation
Nearest-car can starve distant calls during traffic peaks. Add age-based penalties or zone balancing so old requests become increasingly expensive to ignore.
Observability
Emit events for request accepted, assigned, car moved, door opened, door closed, and request served. Dashboards should show wait time, travel time, stops per trip, and failure rates.
Controller availability
One logical singleton controller per bank does not mean one fragile process. Use leader election or hot standby so exactly one leader assigns calls while another can take over.
What Interviewers Look For
Did you separate external hall calls from internal car calls?
Can you explain the difference between bank-level dispatch and car-level SCAN or LOOK serving?
Is the dispatch policy behind a Strategy interface rather than hard-coded in the controller?
Did you model the door lifecycle explicitly with DOORS_OPEN instead of hidden booleans?
Can you identify the concurrency boundary for call submission and ticking?
Did you describe one controller per bank and observer-style display updates without coupling displays to queues?
Quiz
0/6 answered
1.Why does HallRequest store a direction while CarRequest does not?
2.What is the main benefit of DispatchStrategy?
3.Why use separate upStops and downStops ordered sets?
4.What should happen when an elevator reaches a requested floor?
5.What is the best role for floor displays?
6.Why should there be one logical controller per elevator bank?
Practice Variants
Implement LOOK-aware dispatch
IntermediateModify the strategy so it estimates pickup based on a car current route endpoint and pending stops, not just current floor distance.
Add display observers
IntermediateCreate an observer interface, publish immutable elevator snapshots after every state transition, and attach floor and in-car displays.
Add capacity and overload handling
AdvancedTrack passenger load, refuse movement when overloaded, keep doors open, and make DispatchStrategy avoid overloaded cars.
Model emergency and maintenance modes
AdvancedExtend the state machine so emergency stop and maintenance remove a car from dispatch while preserving safe door and movement behavior.
Flashcards
Cheat Sheet
Entities: Building facade, ElevatorController bank coordinator, Elevator car aggregate, Request hierarchy, Direction, ElevatorState, DispatchStrategy.
Requests: HallRequest = floor plus direction; CarRequest = elevator id plus destination.
Scheduling: Controller uses Strategy to assign hall calls; Elevator uses ordered up and down stop sets for SCAN or LOOK style service.
State: Direction captures travel intent; ElevatorState captures lifecycle: IDLE, MOVING_UP, MOVING_DOWN, DOORS_OPEN.
Concurrency: Synchronize controller submissions and elevator mutation, or replace locks with an event loop or actor per car.
Patterns: State for car lifecycle, Strategy for dispatch, Singleton for one controller per bank, Observer for displays and telemetry.
Complexity: Hall call O(E) plus O(log S) enqueue, car call O(E + log S), tick O(E log S).
References
- BookDesign Patterns: Elements of Reusable Object-Oriented Software — Gamma, Helm, Johnson, and Vlissides
- DocsElevator algorithm
- BookJava Concurrency in Practice — Brian Goetz
- DocsRefactoring Guru — Observer Pattern