Design an Elevator System

An elevator control system decides, for every button press in a building, which car should answer and in what order floors get served. There are no servers to shard and no petabytes to store — the entire question is algorithms and state machines applied to a physical system. Interviewers use it to test three things: can you model a stateful machine cleanly (a car with doors, direction, and load), can you reason about a scheduling algorithm and its failure modes (starvation, thrashing), and can you keep safety invariants separate from optimization logic.

It is a staple beginner question precisely because there is nowhere to hide behind buzzwords. Candidates who answer "first come, first served" and stop have missed the question; candidates who explain why elevators sweep in one direction — and what breaks that rule — stand out.

The building: a bank of 8 elevators in a 40-floor office tower serving ~10,000 trips/day. Morning rush concentrates traffic from the lobby to upper floors; lunch reverses it.

Functional requirements

• Accept hall calls (up/down buttons on each floor) and car calls (target floor pressed inside a car).
• Dispatch the best car to each hall call to minimize average wait time.
• Handle car fault states by re-assigning that car's pending calls to other cars.
• Support service modes: independent service, fire service, and maintenance lockout.

Non-functional requirements

• Average passenger wait under 30 seconds at peak load.
• Dispatch decision computed in under 100ms per hall call.
• Safety invariants (doors, overload) can never be violated by scheduler bugs — fail closed.
• System keeps operating with any single car — or the dispatcher itself — failed.

One clarification worth making: a hall call only says up or down, not the destination. The system learns the target floor only after the passenger boards and presses a car button. (If the interviewer offers destination-input panels in the lobby, that changes the problem — you can group passengers by destination — but assume classic two-button halls unless told otherwise.)

10,000 trips/day is about one hall call every 3–4 seconds on average, with rush-hour peaks of maybe a few calls per second. Any single process handles this; the 100ms dispatch budget exists for passenger experience (the hall lantern should light immediately), not because computation is expensive.

What is actually scarce is car-seconds: a car takes real time to travel 40 floors and every stop costs roughly 10 seconds of door cycling. The scheduler's job is to spend that scarce physical capacity well. This is why the interesting content of this interview is the algorithm, the state machine, and failure handling — say so, and do not spend time on databases or horizontal scaling. The system state (8 cars × position, direction, door state, pending calls) fits in a few kilobytes of memory.

Model each car as a state machine before touching scheduling — it is the foundation everything else sits on.

States: IDLE, MOVING_UP, MOVING_DOWN, DOORS_OPENING, DOORS_OPEN, DOORS_CLOSING, plus out-of-service states: FAULTED, MAINTENANCE, FIRE_SERVICE, INDEPENDENT.

Legal transitions encode the safety rules: the only path from DOORS_OPEN to MOVING_* runs through DOORS_CLOSING → doors-locked confirmation. There is deliberately no transition from any doors-open state to any moving state.

The requirement says scheduler bugs can never violate safety — which dictates an architecture, not just careful coding. Put safety in a layer below the dispatcher:

• The car controller (in real systems, dedicated hardware plus interlocks) owns the state machine and refuses illegal transitions. It treats dispatcher output as suggestions: "go to floor 23" is obeyed only when the doors are locked and the car is under its weight limit.
• The dispatcher optimizes assignments but physically cannot command "move with doors open" — no such input exists on the controller's interface.
• Fail closed: on any fault or lost heartbeat, a car stops at the next floor, opens its doors, and takes itself out of the dispatch pool. A stopped elevator is safe; an optimally-scheduled one that moves with open doors is not.

Service modes are top-priority states that bypass scheduling entirely: fire service recalls the car to a designated floor and gives control to firefighters; independent serves only in-car buttons; maintenance locks the car out of the pool.

Start with a single car and a stream of floor requests. The naive strategy is FCFS — serve requests in arrival order. Walk through why it fails: a car at floor 1 gets requests for 30, then 2, then 28. FCFS travels 1→30→2→28, about 85 floors of movement for three stops. The car ping-pongs across the building, and average wait explodes.

The fix is the same idea disk schedulers use: sweep. Keep moving in one direction, serving every pending request you pass, and only then reverse.

• SCAN: sweep all the way to the top floor, then all the way to the bottom, like a windshield wiper — even if the upper floors have no requests.
• LOOK: same sweep, but reverse as soon as no requests remain ahead in the current direction. This is what real elevators do — it is SCAN without the wasted travel to empty extremes.

Same example under LOOK: 1→2→28→30, about 29 floors. Implementation is simple: keep two sorted sets of pending stops (above and below current position); while moving up, serve the ascending set; when it empties, flip direction.

One subtlety earns points: a hall call has a direction. A car sweeping up should stop at floor 15's up call, but not its down call — picking up a down-bound passenger while heading up drags them the wrong way and adds a stop for everyone aboard. Serve a hall call only when the car's sweep direction matches the call's direction (or when the call's floor is the reversal point).

With 8 cars, a new hall call needs an owner. The classic baseline is nearest-car dispatch: assign the call to the closest elevator. It fails in an obvious way — the nearest car may be moving away, full, or already committed to many stops.

The standard answer is a cost function: for each in-service car, estimate the time it would take to serve this call, and assign the call to the cheapest car.

cost(car, call) ≈ travel time to the call floor (respecting current direction and LOOK order) + ~10s door-cycle time × stops already committed before reaching it + penalty if the car is near its weight limit

Evaluating a closed-form estimate across 8 cars is microseconds of work — comfortably inside the 100ms dispatch budget. Assignments should be re-evaluated while the call is still unserved: if a better car becomes available (a car ahead of it faults, or finishes early), reassign. Only the final commitment (the car decelerating for the floor) is irrevocable.

Starvation avoidance. Pure cost minimization has a failure mode: a call on a quiet floor (say floor 37 at lunch) keeps losing the cost comparison as new, cheaper calls arrive, and waits indefinitely. Two standard guards:

• Aging: subtract a growing amount from a call's cost the longer it waits (e.g., after 45–60 seconds it wins any comparison). Simple and sufficient for the 30-second average-wait target — remember averages hide tails, and the aged call is the tail.
• Assignment stickiness: once a car is en route, do not steal it for a marginally cheaper new call; reassign only on significant cost improvements or car failure. This prevents thrashing, the fleet-level cousin of starvation.

Morning rush (up-peak). From 8–10am nearly all traffic is lobby → upper floors, and generic dispatching underperforms because the real bottleneck becomes lobby loading throughput. Peak-mode tactics:

• Return-to-lobby: when a car empties upstairs, send it back to the lobby immediately instead of idling — the next demand is predictably there.
• Sector/zoning: dedicate cars to floor bands (cars 1–4 serve floors 2–20, cars 5–8 serve 21–40). Each car makes fewer stops per round trip, so round-trip time drops and lobby throughput rises — at the cost of longer waits for the rare off-pattern call.
• Detect the peak either by schedule (weekday mornings) or dynamically (sustained lobby up-call rate above a threshold). Lunch is the mirror image: down-peak, position idle cars at upper floors.

Mentioning up-peak unprompted is a strong signal — it shows you connected the traffic pattern in the requirements to a scheduling-mode change rather than treating the algorithm as static.

The requirements demand the system survives any single car failure and a dispatcher failure. Handle each explicitly.

A car faults. Its controller fails closed (stop at next floor, open doors, leave the pool) and the dispatcher observes the state change via heartbeat/telemetry. Recovery is straightforward because of a key distinction: the dispatcher can re-assign the car's pending hall calls to other cars via the normal cost function — but car calls (passengers already inside who pressed buttons) cannot be reassigned; those passengers exit at the fault floor and press a fresh hall call. Making this distinction shows you understand what state lives where.

The dispatcher faults. Cars must not stop working when the coordinator dies:

• Each car keeps a copy of its own assigned calls and continues serving them with LOOK — assignments already made keep progressing.
• Degraded mode for new calls: hall call buttons broadcast on the shared bus; with no dispatcher heartbeat, every car sees every call and applies a deterministic claim rule (e.g., the car with the lowest cost claims it; ties broken by car ID). Service quality drops toward independent operation, but no button goes dead.
• Run a standby dispatcher that takes over on heartbeat loss. State reconstruction is easy — the fleet state is small and cars re-report position and pending calls on request, so the standby can rebuild the world in seconds rather than replicating state continuously.

1. FCFS as the final answer. Serving floors in request order makes the car ping-pong across 40 floors. If you name only one algorithm, name LOOK.
2. Blurring hall calls and car calls. They have different information (direction only vs exact floor), different owners (dispatcher vs car), and different fault behavior (reassignable vs not).
3. Safety inside the scheduler. The requirement says scheduler bugs cannot violate safety — that forces interlocks into a lower layer, not an if-statement in dispatch code.
4. Ignoring starvation. Any cost-minimizing dispatcher starves quiet floors without aging. Interviewers ask "can any request wait forever?" — have the answer ready.
5. No story for dispatcher failure. Central coordination is fine, but the requirements explicitly demand the system survives it. Degraded self-scheduling plus a standby is a complete answer.
6. Treating the load as constant. The prompt hands you the morning rush; a static algorithm leaves the biggest wait-time win on the table.
7. Scaling the wrong thing. Proposing distributed databases and message brokers for 8 cars and 10,000 trips/day misreads where the difficulty lives.