Cruxly › Low-level design › LLD Exercises

Elevator Bank

a scheduler with no right answer — only defensible policies

Prompt: design the control system for a bank of 4 elevators in a 20-floor building. Handle external calls (floor + direction) and internal requests (target floor). Assign elevators to calls.

45 minutes. There is no optimal scheduler; the exercise is making the policy replaceable and the state machine airtight.

Applying the five moves: nouns are Car, Call (external: floor + direction) and Request (internal: target floor) — kept as two distinct types is itself a modelling decision, not a formality, because a scheduler that conflates them cannot express "car already moving up shouldn't take a downward call." The invariant is "a car's state transition graph has no path to an illegal state" (moving and idle simultaneously, doors open while moving) — state it before any scheduling logic. The interface seam is the scheduling policy itself, AssignmentStrategy or equivalent, because "no optimal scheduler" is the prompt telling you this will be swapped and argued about. The concurrency sentence: calls arrive from many floors concurrently, and the assignment decision has to be atomic per car or two calls can both believe they claimed the same idle car.

Scope, and the two request types that are not the same

In scope: 4 cars, 20 floors, external calls (floor + up/down), internal requests (target floor), assignment policy, per-car movement. Out: door timing, weight sensors, fire-service override, power loss. Name them; fire override in particular is a genuinely different design and interviewers respect the distinction.

External and internal requests are structurally different, and conflating them is the first trap.

An external call (floor 7, UP) belongs to the bank. Any car may serve it, and choosing which is the scheduling problem. A second person pressing the same button must not create a second request.
An internal request (car 2, floor 12) belongs to that car. There is nothing to schedule — it joins that car's stop set.

A model with one Request type and a nullable carId conflates them and every method then starts with a null check. Two types, two paths.

Estimate, briefly. 20 floors, 4 cars, a few hundred requests an hour. This is tiny. Say so: "the data volumes here are trivial, so every decision should be made on correctness and extensibility, not performance." It prevents the wasted minutes candidates spend optimising a 20-element scan.

The per-car state machine

enum Direction { UP, DOWN, IDLE }

class Car { int id; int currentFloor; Direction direction; TreeSet<Integer> stopsAbove; // sorted, above current TreeSet<Integer> stopsBelow; // sorted, below current }

Two sorted sets instead of one queue is the load-bearing choice. A car travelling up should serve floors 5, 7, 12 in that order regardless of the order the buttons were pressed — a FIFO queue gets this wrong and produces the behaviour everyone recognises as a badly-programmed elevator. Sorted sets give "next stop in my current direction" as a single first() call, and the set semantics deduplicate a floor requested twice for free.

The data structure isn't an implementation detail here — it's the difference between an elevator that feels correct and one that doesn't.

The invariants:

A car moving UP serves stopsAbove in ascending order and does not reverse while any remain.
currentFloor changes by exactly 1 per tick; a car cannot teleport.
A floor appears at most once per car (set, not list).
direction == IDLE if and only if both sets are empty.

Invariant 1 is the one that makes an elevator feel correct rather than random, and invariant 4 is the one that makes IDLE trustworthy — an IDLE car with pending stops is the bug that strands people.

Transitions:

tick(): if direction == UP: move up one floor if currentFloor in stopsAbove: open doors, remove it if stopsAbove empty: direction = stopsBelow.isEmpty() ? IDLE : DOWN ... mirror for DOWN

Make the illegal state unrepresentable rather than guarded: with two directional sets, "moving up while the next stop is below me" cannot be expressed. That is a stronger guarantee than an assert.

Scheduling — the part with no correct answer

This is why the problem is interesting. Every policy is defensible and every one sacrifices something. Put it behind an interface immediately:

interface Scheduler { Car assign(ExternalCall call, List<Car> cars); }

Nearest car. Pick the car with the smallest |currentFloor - call.floor|. Obvious and wrong in a specific way: the nearest car may be travelling the opposite direction, so it must finish its run and come back — arriving later than a farther car already heading toward the caller. Distance is not time.

Nearest car moving toward the call, same direction (chosen). Prefer cars that will pass the floor anyway in the requested direction; among those, the nearest. Fall back to idle cars, then to any car. This is the classic elevator (SCAN/LOOK) discipline and it is what real buildings approximate. Its sacrifice: a call at a floor with no car ever passing it can wait a long time under steady traffic — it is not starvation-free.

Minimum estimated time. Simulate each car's remaining route and pick the lowest arrival estimate. Better on average and the most defensible if pressed. Cost: the estimate is a model that can be wrong, and it is substantially more code to get right under 45 minutes.

Say the sacrifice of whichever you pick. That sentence is the difference between "I chose SCAN" and "I chose SCAN, it is not starvation-free, and here is when that bites." The second is an engineer.

Starvation fix, if asked: age each pending call and let waiting time override the policy past a threshold. This is a second policy layered on the first, and it belongs behind the same interface.

Concurrency, and the shape of the whole system

Requests arrive from button presses (many threads); cars advance on a timer (one thread, or one per car).

The cleanest model is a single-threaded control loop with an inbound queue, and it is worth arguing for rather than defaulting to locks:

requests (many threads) → concurrent queue → control loop (1 thread) → cars

The loop drains the queue, assigns new external calls via the Scheduler, then ticks every car. No car state is ever touched by two threads, so no locks exist at all and the invariants above are trivially maintained. With 4 cars and 20 floors, one thread is many orders of magnitude more capacity than needed.

Proposing this and explaining why — the shared state is tiny and the workload is trivial, so eliminating concurrency beats managing it — is a stronger answer than a correct lock hierarchy. Interviewers are checking whether you reach for locks reflexively or reason about whether you need them.

What has to be thread-safe: only the inbound queue. One class, one well-understood concern.

The one race that remains: two people press UP on floor 7. Both enqueue an identical call. Dedupe on insert — a Set of pending (floor, direction) pairs — or the bank assigns two cars to one call and one arrives to an empty floor. Small, real, and frequently missed.

How to say it in the interview

"Two things drive this: the state machine per car has to make an illegal transition unrepresentable, and scheduling has no right answer — so it goes behind an interface and I defend one policy while naming what it sacrifices."

Checklist

Modelled external and internal requests as different types with different paths
Used two direction-partitioned sorted sets rather than a FIFO queue
Stated the per-car invariants, including IDLE iff no pending stops
Made illegal transitions unrepresentable rather than guarded by asserts
Put scheduling behind an interface before choosing a policy
Explained why nearest-by-distance is wrong (direction, not distance, decides arrival time)
Named what the chosen policy sacrifices — SCAN is not starvation-free
Argued for a single-threaded control loop instead of defaulting to locks
Deduplicated identical external calls on insert

Practice this interactively