Low-level design · Schedulers and queues
Elevator system with priority scheduling
- Reported once
- SDE-2 (L5)
- State
- Strategy
- Scheduler
- 1 source
One candidate write-up. Treat it as a single data point.
Design the classes and public methods of an elevator system for a building, and explain what each class is responsible for. The reported follow-up is to schedule requests by priority.
Restated in our own words, not a quote from Amazon or any page. The answer below is written for this site.
Clarify first
Pin the scope down before you name a single class.
Clarify these before designing:
- How many elevators and floors, and is the building one bank or several zones?
- Are there two kinds of request: a call button on a floor (with a direction) and a floor button inside a car?
- What does priority mean: a fire or service mode, a VIP floor, or a request that has waited long?
- Do we model time, or only the order of events?
Assumed scope. The report names only the class design and a priority-scheduling follow-up. Spreading calls over several cars, using each request's direction and each car's state, and the numeric priority are this answer's reading of it. In: one bank of elevators, hall calls with a direction and a numeric priority, car calls, a state machine per car, and a swappable dispatch rule, all advanced by explicit ticks. Out: door sensors, weight, a real clock, and fault handling, which come up as extensions.
Entities and relationships
Who owns what, and who talks to whom.
- Controller owns the elevators, the pending request list and the dispatch strategy. It validates floors, orders pending requests and advances time with
step. - Elevator has an id, a floor, a direction, a set of stops, a queue limit and a state (IDLE, UP, DOWN, OPEN). It moves one floor per tick and opens its doors at a stop.
- Request is a hall call: a floor, a direction, a priority and an arrival id.
- DispatchStrategy is the interface: given the elevators and a request, choose one or none. NearestCar picks the lowest travel cost. LeastBusy picks the car with the fewest stops, with travel cost as the tiebreak.
The controller has many elevators and many pending requests, and uses exactly one strategy at a time.
The design
The class map, the main flow and the patterns that earn their place.
- A rider presses a hall button, which creates a request with a floor, a direction and a priority.
- The request waits in the pending list, ordered by priority and then arrival.
- Each tick the controller offers pending requests to the dispatch strategy in that order.
- The chosen car receives the floor as a stop, unless every car is full.
- The car keeps its direction while stops lie ahead, opens the doors at a stop and then continues.
Open on the whiteboardAll 3 diagrams on one tidy board, with a step-by-step walkthrough.
The design separates three things that change for different reasons: the movement rules of one car, the choice of which car answers a call, and the order in which waiting calls are considered.
State machine. Each Elevator is in one of four states. From IDLE it goes UP or DOWN when a stop exists, or straight to OPEN when called at its own floor. UP and DOWN go to OPEN when the car reaches a stop. OPEN goes back to UP, DOWN or IDLE on the next tick, depending on what is left. The rule for direction is the classic sweep: keep going the same way while any stop is ahead, otherwise turn toward the nearest stop. That is why a car heading to 8 still stops at 5 on the way.
Dispatch strategy. The controller asks strategy.choose(elevators, request). NearestCar uses a travel cost. A car with no stop to visit costs the plain gap. A busy car has a heading, the direction it will take next, and costs the gap when the floor lies that way and the request has the same direction, the gap plus a penalty when the request has the opposite direction, and the distance to its turning point plus the way back when the floor lies behind it. LeastBusy spreads load instead. Swapping them is one call and needs no change to Elevator or the controller.
A call from inside a car goes through press, which adds a stop to that car directly and skips dispatch. It ignores the queue limit, because a rider already inside must be able to pick a floor, and it throws for an unknown car or floor.
Priority. Each tick the controller sorts pending requests by priority, highest first, then by arrival id, and offers them to the strategy in that order. Dispatch gives each car at most maxQueue distinct stops, and a floor a car already has costs no extra slot, so when cars are full the lower priority calls stay pending while a higher priority call takes the next free slot.
Determinism. Nothing reads a clock. step is the only thing that advances time, so a test can run ten ticks and compare snapshots.
Trade-off. Stops are plain floors, not floor plus direction, so a car can stop for a rider who wants the other direction. The wrong-way penalty makes the strategy avoid that, but a fuller model keeps separate up and down stop sets. A real controller also needs door timers, load limits and an emergency mode that overrides the queue.
The code
Runnable JavaScript, with the checks it passes.
const WRONG_WAY = 10;
class Elevator {
constructor(id, floor = 0, maxQueue = 4) {
this.id = id;
this.floor = floor;
this.maxQueue = maxQueue;
this.state = "IDLE";
this.dir = 0;
this.stops = new Set();
this.served = [];
}
canTake(floor) {
return this.stops.has(floor) || this.stops.size < this.maxQueue;
}
addStop(floor) {
this.stops.add(floor);
}
ahead(dir) {
for (const stop of this.stops) if ((stop - this.floor) * dir > 0) return true;
return false;
}
chooseDirection() {
if (this.dir !== 0 && this.ahead(this.dir)) return this.dir;
let best = 0;
let bestGap = Infinity;
for (const stop of this.stops) {
const gap = Math.abs(stop - this.floor);
if (gap > 0 && gap < bestGap) {
bestGap = gap;
best = Math.sign(stop - this.floor);
}
}
return best;
}
openDoors() {
this.stops.delete(this.floor);
this.served.push(this.floor);
this.state = "OPEN";
if (this.stops.size === 0) this.dir = 0;
}
step() {
if (this.stops.has(this.floor)) return this.openDoors();
this.dir = this.chooseDirection();
if (this.dir === 0) {
this.state = "IDLE";
return;
}
this.floor += this.dir;
this.state = this.dir > 0 ? "UP" : "DOWN";
if (this.stops.has(this.floor)) this.openDoors();
}
}
function travelCost(elevator, request) {
const gap = request.floor - elevator.floor;
const dir = elevator.chooseDirection();
if (dir === 0) return Math.abs(gap);
if (dir * gap >= 0) return Math.abs(gap) + (dir === request.dir ? 0 : WRONG_WAY);
let turn = elevator.floor;
for (const stop of elevator.stops) {
const beyond = (stop - elevator.floor) * dir > 0;
if (beyond && Math.abs(stop - elevator.floor) > Math.abs(turn - elevator.floor)) turn = stop;
}
return Math.abs(turn - elevator.floor) + Math.abs(turn - request.floor);
}
function cheapest(elevators, request, costOf) {
let best = null;
let bestCost = Infinity;
for (const elevator of elevators) {
if (!elevator.canTake(request.floor)) continue;
const cost = costOf(elevator, request);
if (cost < bestCost) {
best = elevator;
bestCost = cost;
}
}
return best;
}
class NearestCar {
choose(elevators, request) {
return cheapest(elevators, request, travelCost);
}
}
class LeastBusy {
choose(elevators, request) {
return cheapest(elevators, request, (e, r) => e.stops.size * 100 + travelCost(e, r));
}
}
class Controller {
constructor(floors, elevators, strategy) {
this.floors = floors;
this.elevators = elevators;
this.strategy = strategy;
this.pending = [];
this.nextId = 1;
this.ticks = 0;
}
setStrategy(strategy) {
this.strategy = strategy;
}
request(floor, dir, priority = 0) {
if (floor < 0 || floor >= this.floors) throw new RangeError("no such floor");
if (dir !== 1 && dir !== -1) throw new RangeError("direction must be 1 or -1");
const request = { id: this.nextId++, floor, dir, priority };
this.pending.push(request);
return request.id;
}
press(elevatorId, floor) {
if (floor < 0 || floor >= this.floors) throw new RangeError("no such floor");
const elevator = this.elevators.find((e) => e.id === elevatorId);
if (!elevator) throw new RangeError("no such elevator");
elevator.addStop(floor);
}
dispatch() {
const order = [...this.pending].sort((a, b) => b.priority - a.priority || a.id - b.id);
this.pending = [];
for (const request of order) {
const elevator = this.strategy.choose(this.elevators, request);
if (elevator) elevator.addStop(request.floor);
else this.pending.push(request);
}
}
step() {
this.dispatch();
for (const elevator of this.elevators) elevator.step();
this.ticks++;
}
run(maxTicks) {
for (let i = 0; i < maxTicks && !this.settled(); i++) this.step();
return this.ticks;
}
settled() {
return (
this.pending.length === 0 &&
this.elevators.every((e) => e.stops.size === 0 && e.state !== "UP" && e.state !== "DOWN")
);
}
snapshot() {
return this.elevators.map((e) => e.id + ":" + e.floor + ":" + e.state);
}
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Extend it
The change requests an interviewer throws next.
- How would you add a fire or maintenance mode that takes a car out of dispatch and sends it to the ground floor?
- How would you make the stop set direction-aware, so an upward rider is never picked up by a car going down?
- How would you stop a low priority request from starving forever behind a stream of high priority ones?
- How would you divide a tall building into zones, with some cars serving only certain floors?
- How would you add a third dispatch rule that minimises the average waiting time, and how would you test that it beats the others?
Where candidates slip
The mistakes this problem punishes.
Common mistakes on this problem:
- Modelling the elevator as methods like
goUpandgoDownwith no explicit state, so the transitions and the open-door case are scattered through if statements. - Using real timers or sleeping to simulate movement. Step by ticks so the behaviour is repeatable.
- Hard-coding nearest-car dispatch inside the controller, which leaves nowhere to plug in the priority follow-up.
- Ignoring direction: assigning a downward call to a car that is passing the floor going up.
- Reversing a car that still has stops ahead, which makes riders ride past their floor.
- Letting a priority request jump a full car without saying what happens to the displaced requests.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.