Design an Elevator System, Low Level Design (LLD) Interview
A multi-elevator controller where a dispatcher picks the best car for each hall request and every car runs a SCAN/LOOK scheduler over separate up and down queues driven by a state machine.
Asked at: Asked in machine coding / LLD rounds at Uber, Amazon, Google, Flipkart, Swiggy, PhonePe, Atlassian, and most product-company SDE2/SDE3 loops. It is one of the three or four "default" elevator-class OOD problems alongside Parking Lot and Vending Machine.
Why this is asked
It is a compact problem that still forces real OOD thinking. The interviewer wants to see whether you separate the two distinct concerns: dispatching (which car should serve a hall call) versus scheduling (in what order does one car serve its stops). It tests a clean state machine (idle, moving up, moving down, door open), a non-trivial algorithm (SCAN/LOOK with directional queues), and the discipline to model hall buttons versus car buttons correctly. It also has natural concurrency angles (many threads pressing buttons while cars move) and natural extension points (express cars, peak-hour modes) that let a strong candidate show pattern fluency through Strategy and State without over-engineering.
Requirements
Functional
- A building has N floors and M elevator cars. Floors are numbered (for example 0 to N-1, or include basements as negatives).
- Hall calls: a person on a floor presses UP or DOWN. This is a request with a source floor and a desired direction, but no destination yet.
- Car calls: a person inside a car presses a destination floor button. This is a request with a target floor only.
- A central dispatcher receives every hall call and assigns it to exactly one car using a cost function (estimated time / distance, considering current direction).
- Each car independently schedules its assigned stops using SCAN/LOOK: keep moving in the current direction, stopping at every requested floor in order, then reverse when there is nothing further ahead.
- Each car maintains two sorted sets of target floors: an up queue and a down queue.
- A car moves floor by floor; when it reaches a target floor it opens the door, waits, then closes and continues.
- Display the current floor and direction of each car (for the indicator panels).
- When a car has no pending requests it becomes idle (optionally returns to a home/lobby floor).
- Emergency stop and out-of-service must remove a car from dispatch consideration.
Constraints & non-functional
- Single building, single machine, in-memory simulation. No persistence or network required for the core round.
- Dispatcher must never assign a hall call to a car that is out of service or in emergency.
- A car must finish all stops in its current direction before reversing (no thrashing back and forth).
- Door open duration and floor travel time are configurable but treated as discrete ticks in the simulation.
- Thread-safe: button presses can arrive from many threads concurrently while a controller thread advances cars.
- Optimize for low average wait time and avoid starvation of any floor.
Core classes & entities
Building
Top-level aggregate. Holds all elevator cars, the floor range, and the dispatcher. Entry point for hall calls coming from floor panels.
attrs: int minFloor, int maxFloor, List<ElevatorCar> cars, Dispatcher dispatcher
methods: void requestElevator(int floor, Direction dir) // hall call, ElevatorCar getCar(int id), void step() // advance the whole simulation one tick
ElevatorCar
A single physical car. Owns its current floor, its state, its two directional queues, and the scheduling logic. Knows how to step one tick: move, open door, or idle.
attrs: int id, int currentFloor, Direction direction // UP, DOWN, IDLE, ElevatorState state // current State object, TreeSet<Integer> upStops, TreeSet<Integer> downStops, DoorState door, int capacity, boolean inService
methods: void addStop(int floor) // from a car-button press or dispatcher assignment, void step() // delegate to state.step(this), int nextStopInCurrentDirection(), boolean hasWorkAhead(), void openDoor(), void closeDoor(), List<Integer> pendingStops()
Dispatcher
Chooses which car serves a hall call. Pure assignment policy; holds no car state. Uses a SchedulingStrategy / cost function over all in-service cars.
attrs: List<ElevatorCar> cars, DispatchStrategy strategy
methods: ElevatorCar selectCar(int floor, Direction dir), int estimateCost(ElevatorCar car, int floor, Direction dir)
Request
Value object for a pending call. Hall calls carry direction; car calls carry only a target floor. Lets the dispatcher and scheduler treat both uniformly.
attrs: int floor, Direction direction // null/NONE for a car call, RequestType type // HALL or CAR, long createdAtTick
methods: boolean isHallCall(), boolean isCarCall()
ElevatorState
State pattern interface. Each concrete state (Idle, MovingUp, MovingDown, DoorOpen) defines what one step does and which transitions are legal. Keeps ElevatorCar.step() free of giant if/else.
methods: void step(ElevatorCar car), void onStopAdded(ElevatorCar car, int floor), ElevatorState next(ElevatorCar car)
DispatchStrategy
Strategy interface for car selection. Swappable: nearest-car, LOOK-aware cost, peak-up-mode, express-cars. Decouples policy from the dispatcher mechanics.
methods: ElevatorCar pickCar(List<ElevatorCar> cars, Request req)
Display
Observer of a car. Renders current floor and direction to floor and in-car indicator panels. Updated whenever the car moves or changes direction.
attrs: ElevatorCar car
methods: void update(int floor, Direction dir)
Relationships
- Building → composition → ElevatorCar. Building owns its cars; cars do not exist without the building.
- Building → composition → Dispatcher. Building owns one dispatcher that routes all hall calls.
- Dispatcher → association → ElevatorCar. Dispatcher reads car state (floor, direction, load) to score them but does not own them.
- Dispatcher → composition → DispatchStrategy. Dispatcher delegates the actual selection to a pluggable strategy (Strategy pattern).
- ElevatorCar → composition → ElevatorState. Each car holds its current state object; the car delegates step() to it (State pattern).
- ElevatorState → association → ElevatorState. States transition to one another via next(): Idle to MovingUp/MovingDown, MovingX to DoorOpen, DoorOpen back to MovingX or Idle.
- ElevatorCar → association → Request. A car's queues are derived from requests; car-button presses create CAR requests on that car.
- ElevatorCar → association → Display. Displays observe a car and re-render on movement (Observer pattern).
Design patterns used
State in ElevatorState with concrete IdleState, MovingUpState, MovingDownState, DoorOpenState. ElevatorCar.step() delegates to the current state.
A car's behaviour on each tick depends entirely on its mode, and the legal transitions are well defined (you cannot open the door while moving, you cannot reverse mid-direction with work ahead). Encoding this as State objects keeps step() small and makes adding a MaintenanceState or EmergencyState a localized change instead of editing one giant switch.
Strategy in DispatchStrategy (nearest-car, LOOK-cost, peak-mode) injected into Dispatcher; optionally a separate scheduling strategy inside the car.
Car selection policy is the part interviewers most want to vary. Strategy lets you start with a simple nearest-idle-car heuristic and swap in a LOOK-aware cost function or morning-rush up-peak policy without touching the dispatcher or the cars. It is the clean answer to 'how would you change the algorithm later'.
Observer in Display objects subscribe to an ElevatorCar; the car notifies them on floor change and direction change.
Multiple indicator panels (inside the car, on each floor) need to reflect car position without the car knowing about UI. Observer decouples the car from however many displays exist.
Singleton (or single owned instance) in The Dispatcher / ElevatorController for one building.
There is exactly one authority assigning hall calls per building. A single shared instance prevents two dispatchers double-assigning the same call. In an interview, prefer a single owned instance over a global Singleton so it stays testable, but call out the intent.
Command (optional extension) in Wrapping each button press as a Request/Command object placed on a queue.
Treating presses as first-class command objects makes them easy to log, replay for testing, prioritize, and process off a thread-safe queue, which is exactly what the concurrency requirement needs.
Enums
Key API / methods
void Building.requestElevator(int floor, Direction dir)Hall call entry point. Builds a HALL Request, asks the dispatcher to select a car, and adds the floor as a stop on that car. Idempotent for repeated presses of the same button.
ElevatorCar Dispatcher.selectCar(int floor, Direction dir)Scores every in-service car with the active strategy and returns the lowest-cost car. Returns null only if every car is out of service.
void ElevatorCar.addStop(int floor)Inserts the floor into upStops or downStops depending on its position relative to currentFloor and the car's direction. Used by both car-button presses and dispatcher assignments.
void ElevatorCar.step()Advances the car one tick by delegating to its current ElevatorState. The simulation/controller calls this on every car each tick.
int ElevatorCar.nextStopInCurrentDirection()Returns the nearest target floor ahead in the current direction (LOOK behaviour), or a sentinel if none remain so the car can reverse or go idle.
int Dispatcher.estimateCost(ElevatorCar car, int floor, Direction dir)Cost function: cheap if the car is already heading toward the floor in the matching direction, expensive if it must finish the opposite direction first or is far away. Penalize out-of-service implicitly by excluding them.
Code skeleton
// ---- Enums ----
enum Direction { UP, DOWN, IDLE }
enum RequestType { HALL, CAR }
enum CarStatus { IN_SERVICE, OUT_OF_SERVICE, EMERGENCY }
// ---- Request value object ----
class Request {
final int floor;
final Direction direction; // meaningful only for HALL calls
final RequestType type;
final long createdAtTick;
Request(int floor, Direction dir, RequestType type, long tick) {
this.floor = floor; this.direction = dir; this.type = type; this.createdAtTick = tick;
}
}
// ---- State pattern ----
interface ElevatorState {
void step(ElevatorCar car);
ElevatorState next(ElevatorCar car);
}
class IdleState implements ElevatorState {
public void step(ElevatorCar car) { /* sit still, maybe drift to lobby */ }
public ElevatorState next(ElevatorCar car) {
if (!car.hasAnyWork()) return this;
int target = car.closestPendingStop();
car.setDirection(target > car.currentFloor ? Direction.UP : Direction.DOWN);
return car.getDirection() == Direction.UP ? new MovingUpState() : new MovingDownState();
}
}
class MovingUpState implements ElevatorState {
public void step(ElevatorCar car) {
if (car.upStops.contains(car.currentFloor)) { car.arriveAndOpen(); return; }
car.currentFloor++; // one floor per tick
car.notifyDisplays();
if (car.upStops.contains(car.currentFloor)) car.arriveAndOpen();
}
public ElevatorState next(ElevatorCar car) {
if (car.door.isOpen()) return new DoorOpenState();
if (car.hasStopsAbove()) return this; // LOOK: keep going up
if (car.hasStopsBelow()) { // nothing above, reverse
car.setDirection(Direction.DOWN); return new MovingDownState();
}
car.setDirection(Direction.IDLE); return new IdleState();
}
}
// MovingDownState is the mirror image of MovingUpState.
class DoorOpenState implements ElevatorState {
int ticksOpen = 0;
public void step(ElevatorCar car) { ticksOpen++; }
public ElevatorState next(ElevatorCar car) {
if (ticksOpen < car.doorDwellTicks) return this;
car.closeDoor();
if (car.getDirection() == Direction.UP) return new MovingUpState();
if (car.getDirection() == Direction.DOWN) return new MovingDownState();
return new IdleState();
}
}
// ---- Elevator car ----
class ElevatorCar {
final int id;
int currentFloor = 0;
Direction direction = Direction.IDLE;
final TreeSet<Integer> upStops = new TreeSet<>();
final TreeSet<Integer> downStops = new TreeSet<>();
final Door door = new Door();
int doorDwellTicks = 3;
CarStatus status = CarStatus.IN_SERVICE;
private ElevatorState state = new IdleState();
private final List<Display> displays = new ArrayList<>();
private final Object lock = new Object();
void addStop(int floor) {
synchronized (lock) {
if (floor > currentFloor) upStops.add(floor);
else if (floor < currentFloor) downStops.add(floor);
else if (state instanceof IdleState) arriveAndOpen(); // already here
}
}
void step() {
synchronized (lock) {
state.step(this);
state = state.next(this);
}
}
void arriveAndOpen() {
upStops.remove(currentFloor);
downStops.remove(currentFloor);
openDoor();
}
boolean hasStopsAbove() { return upStops.ceiling(currentFloor + 1) != null; }
boolean hasStopsBelow() { return downStops.floor(currentFloor - 1) != null; }
boolean hasAnyWork() { return !upStops.isEmpty() || !downStops.isEmpty(); }
int closestPendingStop() {
Integer up = upStops.ceiling(currentFloor), down = downStops.floor(currentFloor);
if (up == null) return down;
if (down == null) return up;
return Math.abs(up - currentFloor) <= Math.abs(down - currentFloor) ? up : down;
}
void openDoor() { door.open(); }
void closeDoor() { door.close(); }
void setDirection(Direction d) { this.direction = d; notifyDisplays(); }
Direction getDirection() { return direction; }
void notifyDisplays() { for (Display d : displays) d.update(currentFloor, direction); }
}
// ---- Strategy + Dispatcher ----
interface DispatchStrategy { ElevatorCar pick(List<ElevatorCar> cars, Request req); }
class NearestLookStrategy implements DispatchStrategy {
public ElevatorCar pick(List<ElevatorCar> cars, Request req) {
ElevatorCar best = null; int bestCost = Integer.MAX_VALUE;
for (ElevatorCar c : cars) {
if (c.status != CarStatus.IN_SERVICE) continue;
int cost = cost(c, req);
if (cost < bestCost) { bestCost = cost; best = c; }
}
return best;
}
// Cheap when the car is moving toward the call in the same direction.
private int cost(ElevatorCar c, Request req) {
int d = Math.abs(c.currentFloor - req.floor);
boolean sameWay = c.direction == req.direction || c.direction == Direction.IDLE;
boolean ahead = (req.direction == Direction.UP && req.floor >= c.currentFloor) ||
(req.direction == Direction.DOWN && req.floor <= c.currentFloor);
if (c.direction == Direction.IDLE) return d;
if (sameWay && ahead) return d;
return d + 1000; // must finish current sweep first: heavy penalty
}
}
class Dispatcher {
private final List<ElevatorCar> cars;
private final DispatchStrategy strategy;
Dispatcher(List<ElevatorCar> cars, DispatchStrategy s) { this.cars = cars; this.strategy = s; }
ElevatorCar selectCar(int floor, Direction dir) {
Request req = new Request(floor, dir, RequestType.HALL, System.nanoTime());
return strategy.pick(cars, req);
}
}
// ---- Building (entry point) ----
class Building {
final List<ElevatorCar> cars;
final Dispatcher dispatcher;
Building(List<ElevatorCar> cars, Dispatcher d) { this.cars = cars; this.dispatcher = d; }
void requestElevator(int floor, Direction dir) { // HALL call
ElevatorCar car = dispatcher.selectCar(floor, dir);
if (car != null) car.addStop(floor);
// else: all cars down -> queue or reject gracefully
}
void pressFloorInsideCar(int carId, int target) { // CAR call
cars.get(carId).addStop(target);
}
void step() { for (ElevatorCar c : cars) c.step(); } // one simulation tick
}How it works
Start with the split that separates a good answer from a mediocre one: dispatching versus scheduling. The Dispatcher decides which car answers a hall call. Each ElevatorCar decides the order it visits its own stops. Keep those two responsibilities in different classes and the rest falls into place.
A hall call comes in through Building.requestElevator(floor, dir). The Building hands it to the Dispatcher, which runs the active DispatchStrategy over every in-service car. The strategy scores each car with a cost function: a car already idle is cheap (cost equals distance), a car moving toward the floor in the same direction and with the floor still ahead of it is also cheap, and a car heading the wrong way or that must finish its current sweep first gets a heavy penalty so it loses. The lowest-cost car wins and the floor is added to that car as a stop. This is where direction matters: a person pressing DOWN on floor 8 should be caught by a car already descending through 8, which the cost function naturally favours.
Inside the chosen car, addStop() routes the floor into one of two TreeSets, upStops or downStops, based on whether the floor is above or below the current position. TreeSet gives sorted order and free de-duplication, which kills the duplicate-press edge case for free. Car-button presses (someone inside picking a destination) go through the exact same addStop path, so hall calls and car calls converge cleanly.
Movement is the State pattern. Every tick the controller calls car.step(), which delegates to the current ElevatorState. MovingUpState advances one floor, opens the door if the new floor is a target, and on next() checks for any stop still above (LOOK: keep climbing). Only when nothing remains above does it reverse to MovingDownState, and only when both queues are empty does it fall to IdleState. This is exactly the SCAN/LOOK guarantee: the car sweeps fully in one direction, serving every requested floor in order, then turns around. It never thrashes back and forth, because the next() transition refuses to reverse while work remains ahead. DoorOpenState simply counts dwell ticks, then closes and resumes the same direction.
Concurrency lives in the car. Button presses arrive from many threads while one controller thread advances time, so addStop() and step() are guarded by a per-car lock, and the queues are touched only under that lock. Displays observe each car and re-render on every floor or direction change, so the indicator panels stay correct without the car knowing anything about the UI. The end result: requests flow in from any thread, the dispatcher places each on the best car, each car independently runs a correct LOOK sweep, and the whole building advances one honest tick at a time.
Edge cases & gotchas
- Hall call on the floor the car is currently sitting at and idle: open the door immediately, do not waste a tick moving.
- Car-button press for the current floor while door is open: extend door-open time or re-open, do not schedule a redundant move.
- Request for a floor behind the current direction of travel: it must wait in the opposite-direction queue and be served on the return sweep, never cause an immediate reversal while stops remain ahead (this is the core LOOK rule).
- Direction matters for hall calls: someone pressing DOWN on floor 8 should ideally be picked up by a car already descending past 8, not a car going up that happens to be closer.
- Starvation: a low-traffic top floor must eventually be served. Pure nearest-car can starve it under heavy mid-building load, so the cost function must factor in request age or guarantee both sweeps complete.
- All cars out of service / emergency: dispatcher returns no car; the hall call must be queued or rejected gracefully, not throw.
- Capacity full: a car at capacity should skip new hall pickups but still honor its existing car-button drop-offs.
- Duplicate presses: pressing UP twice, or two people pressing the same button, must not create duplicate stops (queues are sets, not lists).
- Boundary floors: at the top floor direction can only be DOWN, at the bottom only UP. Guard against scheduling a stop outside [minFloor, maxFloor].
- Mid-flight reassignment: if a closer car becomes available after assignment, a naive design leaves the call stuck on a slow car. Decide explicitly whether reassignment is allowed (usually keep it simple: assign once).