Elevator System

Multi-Elevator Controller

Design a controller for several elevator cars: each car serves its stops in sweeps (the LOOK rule), and a dispatcher picks the car for each hall call through a swappable strategy.

Overview

A building has several elevator cars and a hall button on every floor. A press inside a car says 'take me to floor 7'. A press in the hall says 'I am on floor 3 and want to go down'. The controller must decide which car answers a hall call, and each car must decide which of its stops to serve next. Both decisions are algorithms, and both must stay correct while buttons are pressed from many places at once.

This is one of the harder LLD problems because it mixes a state machine (a car is idle, moving or standing with its doors open), a scheduling rule (in which order to serve stops) and a dispatch rule (which car to send). The trap is to over-build: threads per car, an event bus, a dozen classes. A strong answer keeps a car to a small object with one method that advances one tick, and drives it from a deterministic test.

The scheduling rule interviewers expect is borrowed from disk scheduling. A car keeps moving in its current direction while any stop lies ahead, and reverses only when none does. Requests behind it wait for the next sweep. That rule is called LOOK, and it stops the car from zig-zagging.

Scoping the problem

Before writing code, ask these questions; each answer changes the design a little.

How many cars and floors? — Decides whether dispatch matters at all — A few cars, tens of floors
Do hall buttons have a direction? — A directed call lets the dispatcher avoid a car heading the wrong way — Yes, up and down
Is time simulated in ticks or real? — Ticks make the design testable; real time is a thin wrapper — Ticks: one floor or one door action per tick
Weight or passenger limits? — A full car should skip hall calls — Follow-up, not the core
Express cars or zones? — Changes which cars may serve which floors — Follow-up
Who presses buttons at once? — Cabin, every hall, and the dispatcher: the request set needs a lock — Many threads

The three scheduling rules

FIFO — Serves stops in the order they were pressed — Zig-zags: 9, then 1, then 8 — The obvious first attempt
SCAN — Sweeps to the top floor, then to the bottom, serving stops on the way — Travels to the ends even when nothing is there — Disk arm scheduling
LOOK — Sweeps in one direction while a stop lies ahead, reverses when none does — None of the above; a stop just behind the car waits one sweep — Disk arm scheduling; the usual interview answer

The trace below runs the implementation. One car starts at floor 0 with stops at 5 and 2. While it passes floor 3, someone presses 1. Under LOOK the car finishes the upward sweep first.

1 — 1 — moving up — 2, 5 — Nothing behind, so up
2 — 2 — moving up — 2, 5 — Arrives at a stop
3 — 2 — doors open — 5 — Stop served
4 — 2 — moving — 5 — Doors close
5 — 3 — moving up — 5 — Button 1 is pressed now
6, 7 — 4, 5 — moving up — 1, 5 — 5 still lies ahead, so 1 waits
8 — 5 — doors open — 1 — Stop served
9 — 5 — moving — 1 — Doors close
10 to 13 — 4, 3, 2, 1 — moving down — 1 — Nothing ahead going up, so reverse
14 — 1 — doors open — none — Stop served; order was 2, 5, 1
15 — 1 — idle — none — No stops left

A car is a state machine

Keeping the car to one step() method that does exactly one thing per tick is what makes it testable: a test calls step() in a loop and reads the floor. Real time is a thread that calls step() every second, and nothing else changes.

Dispatch: which car answers a hall call

The dispatcher is a Strategy so the rule can change without touching the cars. NearestCar picks the car with the smallest distance. LookAwareDispatch asks each car for a cost: the distance if the car is idle or already heading toward the floor in the wanted direction, and the distance plus a large penalty if the car would first have to finish a sweep the other way.

A at 5 going up to 9; B idle at 8; call at 5 going down — A (distance 0) — B (cost 3 against 20) — B: A would carry the passenger up to 9 first
Both idle, A at 0 and B at 9; call at 8 — B — B — Same
A at 2 going up; B at 2 going down; call at 6 going up — tie — A — A is already sweeping toward it

Thread safety

Hall buttons, cabin buttons and the dispatcher all call request on a car, and the car's own step reads and changes the same stop set. One Lock per car wraps both. That is the only shared state in the design; the dispatcher reads car positions without a lock and accepts that a car may have moved one floor by the time its choice lands, which is harmless.

A car's stop set — request (many threads), step — step, cost — The car's lock
A car's floor, direction, state — step — cost, displays — Written under the lock; a stale read costs at most one floor of accuracy
The list of cars — nobody after start — dispatcher — None needed

The demo starts 49 threads that each press a different floor on one car, then runs the car until it is idle, and asserts that every floor was served exactly once and in one upward sweep.

What you will be able to do

Explain FIFO, SCAN and LOOK in a sentence each and trace LOOK on a small example.
Write a car as a state machine with one step() method and test it without threads or sleeps.
Separate dispatch (which car) from scheduling (which stop next) and make dispatch a Strategy.
Say exactly which data is shared between threads and where the lock is.
Extend the design to express cars, zones or a weight limit without reopening the car's scheduling code.

Functional requirements

Several cars serve floors 0 to N-1; each car keeps a set of stops from cabin buttons and dispatched hall calls
A car serves its stops with the LOOK rule: keep the direction while a stop lies ahead, reverse when none does
step() advances one tick: move one floor, open the doors at a stop, or close them
hall_call(floor, direction) picks a car through a swappable dispatch strategy and adds the floor to its stops
A request for a floor outside the building is refused
Each car exposes its floor, direction and state for displays

Non-functional requirements

Deterministic: time is a tick, so every scenario is a plain test with no sleeps
Safe for many threads pressing buttons on the same car: one lock per car around its stop set
A new dispatch rule is a new class; the cars do not change
A car does O(stops) work per tick on a small set; a sorted structure would make it O(log n) (see the questions)

Interview questions

Why LOOK rather than SCAN or first-come-first-served?
How would you add express cars that skip floors, or zones?
A thread per car, or one loop that steps every car?
Your car stores stops in a set and calls max() and any() on it. Is that acceptable?
How do you handle a weight limit or a full car?