Design it yourself · Chapter 23

Elevator system

Design an elevator system in a machine-coding interview: hall and car calls, LOOK scheduling per car, a swappable dispatch strategy, full Java and Python code, and thread safety.

AdvancedInterview priority: High55 min
On this page
  1. The problem: one queue, first come first served
  2. 1. Clarify the requirements
  3. 2. Find the entities
  4. 3. How one car orders its stops: SCAN and LOOK
  5. 4. Which car goes: the dispatch strategy
  6. 5. The class design
  7. 6. The code
  8. 7. Concurrency
  9. 8. Extensions the interviewer will ask for
  10. When not to over-design
  11. In the interview
  12. Quiz

The problem: one queue, first come first served

"Design an elevator system" sounds like a simulation, but the interviewer wants to see two separate decisions made well: which car answers a call, and in what order a car visits its floors. The first attempt usually merges both into one queue:

class Elevator {
    Queue<Integer> requests = new LinkedList<>();
    void request(int floor) { requests.add(floor); }
    void run() {
        while (!requests.isEmpty()) moveTo(requests.poll());   // first come, first served
    }
}

Requests for floors 9, 1, 8, 2 arrive in that order, and the car goes 9 → 1 → 8 → 2: 9 + 8 + 7 + 6 = 30 floors of travel, passing floors where people are waiting. It also ignores direction: someone on floor 5 who pressed "down" gets picked up by a car on its way up. And with several cars, who decides which one goes?

Serving the same four floors in sweeps (up to 9 stopping at 8, then down stopping at 2 and 1) from floor 0 is 9 + 8 = 17 floors of travel instead of 30.

1. Clarify the requirements

Clarify the building and the two kinds of button

  1. “Design an elevator system.” First, clarify. How many elevators and floors? People press an up or down button on a floor, called a hall call, or a floor number inside the car. A controller decides which elevator answers each call.
Your turn: scope it

The interviewer says "Design an elevator system for an office building." Write 5–6 questions you would ask, then the requirements you would agree on and what's out of scope.

Compare with our answer

Questions worth asking: How many cars and floors? Do all cars serve all floors? Hall buttons with up/down, or destination keypads in the lobby? Is there a capacity or weight limit? What happens in an emergency or fire? Is the goal shortest wait, shortest trip, or energy? Do we simulate time or drive real motors?

A strong answer mentions: the difference between hall calls (floor + direction) and car calls (floor) · several cars and a dispatcher · direction-aware stopping · a swappable dispatch rule · emergency stop and maintenance mode · a simulated clock (ticks) for testability.

The agreed list for this page:

FunctionalDetail
BuildingN cars, F floors (0 = lobby); every car serves every floor
Hall callA button on a floor: (floor, UP or DOWN). The controller assigns it to one car
Car callA floor button inside a car; goes to that car only
MovementEach car visits its stops in sweeps: keep going one way while there are stops ahead, then turn
DirectionA car stops for a hall call only when travelling in the direction the caller wants
TimeA simulated tick: each tick a car either moves one floor or opens its doors

Out of scope: weight sensors, door obstruction, fire service mode, energy optimisation, destination-dispatch keypads. Mention them as extensions.

2. Find the entities

Controller, elevators, requests and a dispatch strategy

  1. The main classes: an ElevatorController, the Elevators it manages, a Request for each button press, and a Direction enum. Which elevator to send is a rule likely to change, so it’s a DispatchStrategy.
  • Nouns → classes: ElevatorController, Elevator (a car), Direction, and requests. In the code a hall call is passed as (floor, direction) rather than a separate Request object; add the class when requests gain more data (timestamp, priority).
  • Verbs → methods: press a hall button → controller.hallCall(floor, dir); press a car button → elevator.pressFloor(f); move → elevator.step(); choose a car → DispatchStrategy.choose(...).

The two decisions map onto two different classes, and that separation is the core of the design:

DecisionWho makes itChanges how often
Which car answers a hall callDispatchStrategy, called by the controllerOften: rush hour, zoning, VIP floors, energy saving
In what order a car visits its stopsThe Elevator itself (LOOK)Rarely: it is a well-known algorithm

3. How one car orders its stops: SCAN and LOOK

The classic elevator algorithm comes from disk scheduling, where a disk head moves across tracks the way a car moves across floors.

Keep going while there are stops ahead, then turn round

  1. Each elevator follows the classic elevator algorithm: keep moving in the current direction, stopping at every requested floor on the way, and only turn around when there are no more stops ahead.
AlgorithmHow it worksGood atWeak at
FCFS (first come, first served)Visit requests in arrival orderSimple, obviously fairZig-zags; long travel
SSTF (shortest seek first)Always go to the nearest requestShort average travelStarvation: a far floor can wait for ever while near requests keep coming
SCANSweep to the top floor, then to the bottom, serving requests on the wayBounded wait; no starvationTravels to the end even when nobody is there
LOOK (used here)Like SCAN, but turn round at the last request in each directionBounded wait, less travelSlightly more bookkeeping

Why LOOK can't starve a floor: a car serves every stop ahead before it turns, and it can't go past the top or bottom floor, so any request is served within at most about two sweeps of the building, however many new requests arrive.

Direction-aware stops

A single set of stops (as in the figure below) stops at a floor whenever the car passes it. That picks up a "down" caller on the way up, who then rides to the top and back. The full code keeps two sets:

  • upStops: floors to stop at while going up (car calls above the car, hall calls for UP).
  • downStops: floors to stop at while going down.

Each tick, a car does one of three things:

  1. If the current floor is in the stop set for its direction, open the doors and remove it.
  2. Otherwise, if there's any stop ahead (in either set), move one floor that way.
  3. Otherwise turn round, and check step 1 again (a "down" call at the topmost stop is served here).

When both sets are empty the car is IDLE; the next call sets its direction towards the nearest stop.

step(): open the doors, move one floor, or turn round

  1. In code, an elevator’s step() moves one floor toward its next stop, opens the doors when it arrives, and turns around or goes idle when there’s nothing left ahead.

4. Which car goes: the dispatch strategy

Dispatch: pick the best car for each hall call

  1. The controller’s job is dispatching: pick the best elevator for each hall call. “Nearest idle car” is a fine start. In the morning rush, a smarter rule spreads cars across the lobby. Because the rule is a strategy, swapping it doesn’t touch anything else.

"Nearest car" is the usual starting point, but plain distance is wrong for moving cars: a car two floors away heading the other way may take longer than an idle car six floors away. The strategy in the code estimates a cost per car:

Car's situationCost estimate
IdleDistance to the call
Moving towards the call, in the caller's directionDistance, plus one for each stop on the way
Anything else (moving away, or wrong direction)Distance to the end of its current sweep, back to the call, plus its number of stops

Other strategies the interviewer may ask about, each a new class behind the same interface:

  • Least busy: the car with the fewest stops; balances wear, ignores distance.
  • Zoning: in tall buildings, cars A–B serve floors 0–20 and C–D serve 0 and 21–40; morning rush sends idle cars back to the lobby.
  • Destination dispatch: passengers enter their destination in the lobby and are grouped by destination, so a car makes fewer stops. Many modern high-rises use this; the input changes from (floor, direction) to (floor, destination).

5. The class design

Class / typeKindResponsibility
DirectionenumUP, DOWN, IDLE
ElevatorentityFloor, direction, upStops and downStops; pressFloor, assign, step, costTo
DispatchStrategyinterfacechoose(cars, floor, direction)
DirectionAwareNeareststrategyThe cost rule above
ElevatorControllerfacadeOwns the cars; hallCall asks the strategy and assigns; tick advances every car

Why each pattern is there: Strategy for dispatch, because it's the rule most likely to change and to be tuned per building; Facade for the controller, because buttons, a building-management screen and tests all call two methods; and the car's own movement could become a State pattern (Idle, MovingUp, MovingDown, DoorsOpen, OutOfService) once doors, overload and maintenance are in scope. With three directions and one rule, an enum is simpler for now.

6. The code

Time is a tick, not a wall clock, so the demo is deterministic and testable. In a building each car would run its own loop calling step() every second or so.

import java.util.*;
import java.util.concurrent.*;

// ---------- Demo (first, so `java ElevatorDemo.java` finds main) ----------
public class ElevatorDemo {
    public static void main(String[] args) throws Exception {
        ElevatorController c = new ElevatorController(3, 10, new DirectionAwareNearest());
        c.car(1).moveTo(5); c.car(2).moveTo(9);              // start positions: A at 0, B at 5, C at 9

        Elevator chosen = c.hallCall(4, Direction.DOWN);       // someone on floor 4 wants to go down
        System.out.println("hall call 4 DOWN -> car " + chosen.name);
        c.runUntilIdle(true);
        chosen.pressFloor(0);                                  // passenger gets in, presses 0
        c.runUntilIdle(true);

        // One car, mixed calls: going up from 2 with car calls 4 and 7, and a hall call DOWN at 3
        ElevatorController one = new ElevatorController(1, 10, new DirectionAwareNearest());
        Elevator a = one.car(0);
        a.moveTo(2); a.pressFloor(4); a.pressFloor(7);
        one.hallCall(3, Direction.DOWN);
        one.hallCall(5, Direction.UP);
        one.runUntilIdle(true);                                // LOOK: up 4, 5, 7, then down to 3

        // Concurrency: 8 threads press 50 random buttons each while the cars run
        ElevatorController busy = new ElevatorController(3, 20, new DirectionAwareNearest());
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 8; t++) {
            final long seed = t;
            fs.add(pool.submit(() -> {
                Random r = new Random(seed);
                for (int i = 0; i < 50; i++) {
                    int f = 1 + r.nextInt(18);
                    busy.hallCall(f, r.nextBoolean() ? Direction.UP : Direction.DOWN);
                    busy.tick();
                }
            }));
        }
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        busy.runUntilIdle(false);                              // throws if any stop is never served
        System.out.println("400 calls from 8 threads: every stop served");
    }
}

// ---------- Values ----------
enum Direction { UP, DOWN, IDLE }

// ---------- One car ----------
final class Elevator {
    final String name; final int topFloor;
    private int floor = 0;
    private Direction dir = Direction.IDLE;
    private final TreeSet<Integer> upStops = new TreeSet<>();    // stop here while going up
    private final TreeSet<Integer> downStops = new TreeSet<>();  // stop here while going down

    Elevator(String name, int topFloor) { this.name = name; this.topFloor = topFloor; }

    synchronized int floor() { return floor; }
    synchronized Direction direction() { return dir; }
    synchronized boolean idle() { return upStops.isEmpty() && downStops.isEmpty(); }
    synchronized void moveTo(int f) { floor = f; }                // test setup only

    /** Button inside the car: the direction follows from where the car is now. */
    synchronized void pressFloor(int f) {
        check(f);
        if (f > floor) upStops.add(f);
        else if (f < floor) downStops.add(f);
        else (dir == Direction.DOWN ? downStops : upStops).add(f); // same floor: reopen doors
    }
    /** A hall call assigned to this car by the controller. */
    synchronized void assign(int f, Direction wanted) {
        check(f);
        (wanted == Direction.UP ? upStops : downStops).add(f);
    }

    /** One tick: open doors here, or move one floor. LOOK: turn round only when nothing is ahead. */
    synchronized String step() {
        if (idle()) { dir = Direction.IDLE; return null; }
        if (dir == Direction.IDLE) dir = nearestStop() >= floor ? Direction.UP : Direction.DOWN;
        if (serveHere()) return name + " opens at " + floor + " (" + dir + ")";
        if (!anythingAhead(dir)) {
            dir = (dir == Direction.UP) ? Direction.DOWN : Direction.UP;
            if (serveHere()) return name + " opens at " + floor + " (" + dir + ")";
        }
        floor += (dir == Direction.UP) ? 1 : -1;
        return null;
    }

    /** Rough time to reach floor f, used by dispatch. Counts floors travelled, plus 1 per stop on the way. */
    synchronized int costTo(int f, Direction wanted) {
        if (idle()) return Math.abs(floor - f);
        boolean ahead = dir == Direction.UP ? f >= floor : f <= floor;
        if (ahead && dir == wanted) return Math.abs(floor - f) + stopsBetween(floor, f);
        int end = dir == Direction.UP ? Math.max(maxStop(), floor) : Math.min(minStop(), floor);
        return Math.abs(floor - end) + Math.abs(end - f) + upStops.size() + downStops.size();
    }

    private boolean serveHere() { return (dir == Direction.UP ? upStops : downStops).remove(floor); }
    private boolean anythingAhead(Direction d) {
        return d == Direction.UP ? upStops.higher(floor) != null || downStops.higher(floor) != null
                                 : upStops.lower(floor) != null || downStops.lower(floor) != null;
    }
    private int nearestStop() {
        int best = -1;
        for (TreeSet<Integer> s : List.of(upStops, downStops))
            for (int f : s) if (best < 0 || Math.abs(f - floor) < Math.abs(best - floor)) best = f;
        return best;
    }
    private int maxStop() { return Math.max(upStops.isEmpty() ? 0 : upStops.last(), downStops.isEmpty() ? 0 : downStops.last()); }
    private int minStop() { return Math.min(upStops.isEmpty() ? topFloor : upStops.first(), downStops.isEmpty() ? topFloor : downStops.first()); }
    private int stopsBetween(int a, int b) {
        TreeSet<Integer> s = dir == Direction.UP ? upStops : downStops;
        return s.subSet(Math.min(a, b), false, Math.max(a, b), false).size();
    }
    private void check(int f) { if (f < 0 || f > topFloor) throw new IllegalArgumentException("no floor " + f); }
}

// ---------- What varies: which car answers a hall call ----------
interface DispatchStrategy {
    Elevator choose(List<Elevator> cars, int floor, Direction wanted);
}

/** Cheapest car: idle cars by distance; moving cars only cheap if already heading there the right way. */
final class DirectionAwareNearest implements DispatchStrategy {
    public Elevator choose(List<Elevator> cars, int floor, Direction wanted) {
        Elevator best = null; int bestCost = Integer.MAX_VALUE;
        for (Elevator e : cars) {
            int cost = e.costTo(floor, wanted);
            if (cost < bestCost) { best = e; bestCost = cost; }
        }
        return best;
    }
}

// ---------- The controller ----------
final class ElevatorController {
    private final List<Elevator> cars = new ArrayList<>();
    private volatile DispatchStrategy strategy;

    ElevatorController(int count, int floors, DispatchStrategy strategy) {
        for (int i = 0; i < count; i++) cars.add(new Elevator(String.valueOf((char) ('A' + i)), floors - 1));
        this.strategy = strategy;
    }
    Elevator car(int i) { return cars.get(i); }
    void setStrategy(DispatchStrategy s) { strategy = s; }

    /** Called from any thread when a hall button is pressed. */
    Elevator hallCall(int floor, Direction wanted) {
        Elevator e = strategy.choose(cars, floor, wanted);   // reads a snapshot; a slightly stale one is fine
        e.assign(floor, wanted);
        return e;
    }

    /** In a real building each car runs its own loop; here one tick advances every car. */
    void tick(boolean log) {
        for (Elevator e : cars) { String event = e.step(); if (log && event != null) System.out.println("  " + event); }
    }
    void tick() { tick(false); }

    int runUntilIdle(boolean log) {
        int n = 0;
        while (cars.stream().anyMatch(e -> !e.idle())) {
            tick(log);
            if (++n > 10_000) throw new IllegalStateException("cars never went idle");
        }
        return n;
    }
}

Both print:

hall call 4 DOWN -> car B
  B opens at 4 (DOWN)
  B opens at 0 (DOWN)
  A opens at 4 (UP)
  A opens at 5 (UP)
  A opens at 7 (UP)
  A opens at 3 (DOWN)
400 calls from 8 threads: every stop served

In the first scenario car B is idle at floor 5, one floor away, so it wins over A (at 0) and C (at 9). In the second, car A is at floor 2 going up with car calls 4 and 7, a hall call for UP at 5 and one for DOWN at 3. It doesn't stop at 3 on the way up, because that caller wants to go down; it serves 4, 5 and 7, turns, and collects the floor-3 caller on the way down.

7. Concurrency

Buttons are pressed on many threads, and each car runs its own loop. The races:

RaceWhat goes wrongFix in the code above
A button press while the car is mid-step()A stop is added to a set being read; TreeSet and Python set are not thread-safe, so the set can be corrupted or the stop lostEvery method on Elevator is synchronized (an RLock in Python): one car's state changes one call at a time
Dispatch reads car positions that change immediately afterThe chosen car has moved one floor; the cost estimate is slightly staleAccepted on purpose: dispatch is a heuristic, and LOOK still serves the stop. Never hold every car's lock while choosing
Two people press the same hall buttonTwo assignmentsThe stop sets are sets, so a duplicate is ignored; a real controller also lights the button once
Controller locks car A then car B, while another thread locks B then ADeadlockThe controller never holds two car locks at once: costTo locks and releases each car in turn

Two standard structures, worth naming:

  • Lock per car (used here): simple, and cars never block each other.
  • Command queue per car: buttons put commands on a BlockingQueue (Java) or queue.Queue (Python), and the car's loop is the only thread that touches its state. No locks on the car's fields at all; this is the actor style many real controllers use.

8. Extensions the interviewer will ask for

  • Maintenance mode: an outOfService flag (or state) that makes costTo return infinity, so dispatch never picks the car; its assigned hall calls are reassigned.
  • Destination dispatch: hallCall(floor, destination); the strategy groups passengers going to nearby floors into the same car.
  • VIP or freight priority: a priority on requests and a strategy that serves priority calls first, with a cap so others aren't starved.
  • Display panels: Observer: each car publishes floor and direction changes; hall displays and the building-management screen subscribe.
  • Express zones: a servedFloors set per car, checked by the strategy and by pressFloor (a button for an unserved floor is not lit).

When not to over-design

  • One car, a few floors: skip the dispatch strategy entirely; the controller is the car.
  • If the interviewer cares about scheduling, spend time on LOOK, the direction-aware sets and fairness, and keep dispatch to one sentence.
  • Don't model motors, acceleration or door timing unless asked; a tick that moves one floor is the right level of detail.

In the interview

Your turn: spot the bug

A candidate's car keeps one sorted set of stops and this step(). Find at least three problems.

void step() {
    if (stops.isEmpty()) return;
    int target = stops.first();                        // lowest requested floor
    if (floor == target) { stops.remove(target); openDoors(); return; }
    floor += (target > floor) ? 1 : -1;
}
Compare with our answer

The problems: (1) it always heads for the lowest stop, so a car at floor 8 with stops 9 and 1 goes down to 1 first, then back up to 9; with new low requests arriving, floor 9 can wait for ever (starvation). (2) It ignores direction: it opens at floors it is merely passing only if they happen to be the lowest, and it can't tell an UP hall call from a DOWN one. (3) The direction field is never updated, so dispatch can't estimate cost. (4) Nothing is synchronised, and a TreeSet modified by a button thread during step() is a data race.

synchronized String step() {
    if (idle()) { dir = Direction.IDLE; return null; }
    if (dir == Direction.IDLE) dir = nearestStop() >= floor ? Direction.UP : Direction.DOWN;
    if (serveHere()) return name + " opens at " + floor;          // stop set for the current direction
    if (!anythingAhead(dir)) {                                     // LOOK: turn only when nothing is ahead
        dir = (dir == Direction.UP) ? Direction.DOWN : Direction.UP;
        if (serveHere()) return name + " opens at " + floor;
    }
    floor += (dir == Direction.UP) ? 1 : -1;
    return null;
}

A strong answer mentions: lowest-first is not an elevator algorithm and can starve floors · keep a direction and continue while stops remain ahead (LOOK) · separate up and down stops for hall-call direction · the direction is needed by dispatch · locking the car's state against button threads.

Your turn: the requirement changes

The building owner adds a rule: between 8:00 and 9:30, at least one idle car must always wait at the lobby, and cars C and D should only answer calls above floor 10. What changes, and what stays the same?

Compare with our answer

A strong answer mentions:

  • A new dispatch strategy (MorningRush) that applies the zoning rule (C and D only for floors above 10, plus the lobby) and otherwise delegates to DirectionAwareNearest.
  • A scheduler that swaps the strategy at 8:00 and 9:30 (or a TimeOfDayStrategy that picks per call, given the time).
  • Lobby parking: when a car goes idle and no car is at or heading to the lobby, the controller assigns it a stop at floor 0. That's a controller policy run on each tick, not part of LOOK.
  • Elevator and its LOOK logic don't change; nor does the button code.
  • Testing it with a simulated clock: a scenario at 8:15 checks C never takes floor 4, and that a car returns to the lobby.
Elevator system on one page
  • Two decisions: which car (a DispatchStrategy) and the order of stops (LOOK, inside each car).
  • Buttons: hall call = (floor, direction), assigned by the controller; car call = floor, for that car.
  • Stops: separate upStops and downStops; stop only for callers going your way.
  • LOOK: serve what's ahead, turn when nothing is; bounded wait. SSTF can starve; FCFS zig-zags; SCAN goes to the end needlessly.
  • Dispatch cost: idle → distance; heading there the right way → distance + stops between; otherwise via the end of the sweep.
  • Time as ticks for deterministic tests; each car's loop calls step().
  • Concurrency: lock per car (or a command queue per car); dispatch reads a slightly stale snapshot; never hold two car locks.
  • Real-world: reassign calls from broken cars, re-dispatch, capacity, emergency mode, morning-rush lobby parking and zoning.
Interactive labPractise it: dispatch the cars and survive the morning rushOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. Car A is idle at floor 9. Car B is at floor 6 moving up to floor 12. A hall call arrives: floor 4, going DOWN. With the direction-aware cost rule, which car should be sent?

2. Why do production elevators use a SCAN or LOOK style algorithm instead of always going to the nearest requested floor?

3. A car going up from floor 2 has a hall call at floor 5 for DOWN, and a car call for floor 8. What should happen at floor 5 on the way up?

4. Buttons are pressed on several threads while each car's loop calls step(). The controller's hallCall computes a cost for every car, then assigns the call. Which locking approach is safest?

5. Car C breaks down and is switched to maintenance while three hall calls are assigned to it. What should the design do?

6. During the morning rush all four cars end up on upper floors and the lobby queue grows. Which change fits the design best?

7. Why does the design advance time in ticks instead of using Thread.sleep and the wall clock inside Elevator?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.