Design an Elevator System

Why interviewers like the elevator problem

The elevator system is the second most common low-level design (LLD) case study after the parking lot, and it is harder. A parking lot is mostly about storing things and charging for them. An elevator system is about behaviour over time: cars move, doors open and close, new requests arrive while a car is already moving, and a central controller must decide which car answers which call.

That makes it a good test of three skills:

1. Modelling state. An elevator is idle, moving up, moving down or standing with its doors open, and what it does next depends on which of these it is in. Interviewers look for the State pattern or at least a clean state machine, not a pile of boolean flags like isMoving, isGoingUp and doorsOpen that can contradict each other.
2. Choosing an algorithm. Which floor should a car visit next, and which car should take a new call? Interviewers want you to name and compare approaches: first-come-first-served, nearest car, SCAN and LOOK.
3. Separating the parts. The car, the scheduling rule, the dispatcher that assigns calls and the clock that drives the simulation should be separate, so each can change alone.

This lesson builds a complete Java simulation of two elevators in a ten-floor building. It runs a scripted morning of six passengers, prints every stop, measures waiting time, swaps in a different dispatch strategy, and shows how button presses from many threads reach a single-threaded controller safely. If State and Strategy are new to you, read Behavioural patterns first.

Problem statement

Design the control software for a bank of elevators in a building. People press an up or down button on a floor; a car arrives, they get in and press their destination floor inside the car. The system must decide which car serves each floor call and in which order each car visits its floors, while keeping cars safe and passengers' waiting times low.

Clarifying questions and assumed requirements

Two terms come up constantly, so define them now:

• A hall call is a request made by pressing up or down on a floor. It has a floor and a direction, but the system does not yet know the destination.
• A car call is a request made by pressing a floor button inside a car. It belongs to that car and only has a floor.

This split matters. Hall calls need a decision about which car serves them; car calls are already owned by a car.

Functional requirements

1. Accept hall calls from any floor and assign each to one car.
2. Accept car calls inside each car.
3. Move each car one floor per tick, stopping at floors it must serve.
4. Open the doors at a stop, let riders out and waiting passengers going the same way in, then close and continue.
5. Never move a car beyond the top or bottom floor.
6. Allow the dispatch rule to be replaced without touching the cars.

Non-functional requirements

• Fairness: every call is eventually served; no request waits forever.
• Efficiency: keep average waiting and trip times low.
• Safety: a car never moves with its doors open; it never leaves the shaft.
• Thread safety: buttons are pressed from many threads; car state must stay consistent.
• Testability: time is simulated, so a full run is deterministic and fast.

Core use cases

1. A passenger on floor 3 presses up. The dispatcher assigns the call to a car. The car arrives, opens, the passenger enters and presses 8.
2. A car moving up passes floor 5 where someone pressed up: it stops on the way.
3. Someone on floor 9 presses down while the only nearby car is moving up from floor 2 with nothing above it: the car goes up to 9, turns around and serves the call going down.
4. A car finishes all its stops and becomes idle.
5. The operator switches the dispatch rule from nearest car to another rule.
6. Many people press buttons at once; no press is lost.

Scheduling inside one car: FCFS, SSTF, SCAN and LOOK

Before assigning calls to cars, decide how one car orders its stops. This is the same problem a hard disk faces when ordering head movements, and the algorithm names come from there (see Storage and I/O).

• FCFS (first come, first served): visit floors in the order requested. Simple, fair, wasteful.
• SSTF (shortest seek time first): always go to the nearest pending floor. Efficient on average, but a floor far from a busy cluster can starve, meaning it waits indefinitely because closer requests keep arriving.
• SCAN: move in one direction all the way to the end of the building, serving every requested floor on the way, then reverse. This is the classic "elevator algorithm". No starvation, but the car travels to the top floor even when nobody needs it.
• LOOK: like SCAN, but reverse at the last requested floor in the current direction instead of the building's end. This is what real elevators approximate and what our code implements.

Worked example

A car is at floor 4, moving up. Pending requests arrived in this order: 7, 2, 6. The top floor is 9. Count the floors travelled by each algorithm.

FCFS : 4 -> 7 -> 2 -> 6        3 + 5 + 4         = 12 floors
SSTF : 4 -> 6 -> 7 -> 2        2 + 1 + 5         =  8 floors
SCAN : 4 -> 6 -> 7 -> 9 -> 2   2 + 1 + 2 + 7     = 12 floors
LOOK : 4 -> 6 -> 7 -> 2        2 + 1 + 5         =  8 floors

SSTF and LOOK tie here, and both beat FCFS and SCAN by four floors. SCAN pays for its trip to floor 9 where nobody asked to go. The difference between SSTF and LOOK appears under continuous load: if new requests keep arriving at floors 5 and 6 while the car is near them, SSTF keeps bouncing between them and the passenger at floor 2 waits indefinitely. LOOK commits to a direction, so floor 2 is served as soon as the upward sweep finishes.

How LOOK is represented in code

Each car keeps two sorted sets:

• up: floors to stop at while travelling up.
• down: floors to stop at while travelling down.

A hall call "floor 5, up" goes into up. A hall call "floor 5, down" goes into down. A car call is placed by comparing with the current floor: above goes into up, below into down. Java's TreeSet keeps floors sorted and answers "is there any stop above floor f?" with higher(f) in O(log n) time.

When moving up, the car stops at floor f if f is in up. It also stops if nothing at all is requested above f and f is in down: that is the LOOK turning point, where the car picks up a downward passenger and reverses. Moving down is symmetric.

Dispatching across cars

The dispatcher decides which car gets each hall call. This is a policy that buildings tune, so it belongs behind a Strategy interface:

interface DispatchStrategy {
    Elevator choose(List<Elevator> elevators, HallCall call);
}

Common strategies:

Our NearestCarStrategy computes a cost for each car and picks the cheapest (lowest index on a tie):

car idle                                   cost = |car - floor|
car moving up, call is UP at or above it   cost = floor - car       (on the way)
car moving up, anything else               cost = (end - car) + |end - floor|
car moving down: mirror image
where end = furthest pending stop in the car's current direction

The "anything else" case models the car finishing its current run and then travelling back to the caller.

Worked example of the cost function

At tick 1 in the demo, the call is "floor 5, down". Car E1 is at floor 1 moving up with one stop, floor 3. Car E2 is at floor 8 with its doors open, going down.

E1: moving up, call is DOWN -> not on the way
    end = 3, cost = (3 - 1) + |3 - 5| = 2 + 2 = 4
E2: going down, call is DOWN and 5 <= 8 -> on the way
    cost = 8 - 5 = 3
E2 wins with cost 3.

The program's log shows hall call 5 DOWN -> E2, matching this.

Entities and relationships

                    +-------------------+
 buttons on any --> |    Dispatcher     |  inbox: ConcurrentLinkedQueue
 thread  submit()   |-------------------|
                    | drainAndAssign()  |---uses--> DispatchStrategy
                    +-------------------+             ^        ^
                             | 1..*                   |        |
                             v                NearestCar   RoundRobin
                    +-------------------+
                    |     Elevator      |---has 1--> ElevatorState
                    |-------------------|              ^  ^  ^  ^
                    | floor, direction  |   Idle  MovingUp  MovingDown
                    | up: TreeSet       |                  DoorsOpen
                    | down: TreeSet     |
                    | riders: Passenger*|
                    +-------------------+
                             |
                             v boards/alights via
                    +-------------------+       +-------------+
                    |     Building      |------>|  Passenger  |
                    | waiting per floor |  0..* | from, to    |
                    +-------------------+       +-------------+
 Simulation: for each tick -> arrivals -> drain inbox -> tick every car

In a real product you would also see Door, Display, HallButton, CarButton and a Motor interface. They are hardware adapters. They matter in an interview only to show that the controller talks to hardware through interfaces, so it can be tested with fakes.

Design decisions and patterns

State pattern for each car

The State pattern represents each state as an object with its own behaviour; the context object (the elevator) delegates to whichever state object it currently holds. Changing state means replacing that object.

                  stops exist
     +--------+  --------------->  +-------------+
     |  IDLE  |                    | MOVING_UP / |
     +--------+  <---------------  | MOVING_DOWN |
        ^  |       no stops left   +-------------+
        |  | call on this floor          |  reached a stop
        |  v                             v
     +-------------------------------------+
     |             DOORS_OPEN              |
     |  riders out, same-direction in,     |
     |  then close and pick next state     |
     +-------------------------------------+

Each tick of a state does one thing:

• Idle: if there is a call on this floor, open the doors. Otherwise, if any stop exists, switch to moving toward the nearest one and move one floor this tick.
• Moving up / down: move one floor, then decide whether to stop here (LOOK rule).
• Doors open: if someone just called this floor in a matching direction, stay open. Otherwise close, pick the next state using LOOK (prefer continuing in the current direction), and move one floor this tick.

Why this is better than flags: with boolean moving, goingUp, doorsOpen there are eight combinations, and some are illegal (moving with doors open). With a state object, illegal combinations simply do not exist. Adding an EMERGENCY_STOP or MAINTENANCE state is one new class; existing states only change where they must transition into it.

The states hold no data of their own, so each is a single shared instance (IdleState.INSTANCE). The per-car data lives on the elevator.

Strategy for dispatch

Dispatch is a policy, and buildings change it (morning up-peak, lunch, evening down-peak). Dispatcher holds a volatile DispatchStrategy that can be replaced at runtime, and the cars know nothing about it.

Single-threaded core with a thread-safe inbox

Buttons are pressed on many threads. Rather than locking every elevator, the design confines all car state to one simulation thread. Buttons call dispatcher.submit(call), which adds to a ConcurrentLinkedQueue. At the start of each tick the simulation thread drains the queue and assigns calls. This is the event loop or single-writer design, used by many real controllers and by systems such as Redis. Details are in the concurrency section.

Ticks instead of real time

The simulation advances in discrete ticks. One tick is "move one floor" or "keep doors open". This makes every run deterministic, so you can write tests like "Asha waits exactly 2 ticks", and lets you compare strategies on the same script.

Complete Java implementation

Save as ElevatorDemo.java, compile with javac ElevatorDemo.java and run java ElevatorDemo. Java 17 or later is needed for records.

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

enum Direction { UP, DOWN, IDLE }

record HallCall(int floor, Direction direction) {}

final class Passenger {
    final String name; final int from, to; final int requestTick;
    int boardTick = -1, alightTick = -1;
    Passenger(String name, int from, int to, int requestTick) {
        if (from == to) throw new IllegalArgumentException("from == to");
        this.name = name; this.from = from; this.to = to; this.requestTick = requestTick;
    }
    Direction direction() { return to > from ? Direction.UP : Direction.DOWN; }
}

// ---------- State pattern ----------

interface ElevatorState {
    void tick(Elevator e, int now);
    String name();
}

final class IdleState implements ElevatorState {
    static final IdleState INSTANCE = new IdleState();
    public String name() { return "IDLE"; }
    public void tick(Elevator e, int now) {
        if (!e.hasStops()) return;
        if (e.claimStopHere(now, true)) return;           // a call on the floor we are parked at
        e.setState(e.nearestStop() > e.floor() ? MovingUpState.INSTANCE : MovingDownState.INSTANCE);
        e.state().tick(e, now);                           // start moving in this same tick
    }
}

final class MovingUpState implements ElevatorState {
    static final MovingUpState INSTANCE = new MovingUpState();
    public String name() { return "MOVING_UP"; }
    public void tick(Elevator e, int now) {
        e.moveBy(+1);
        int f = e.floor();
        if (e.up().remove(f)) { e.openDoors(Direction.UP, now); return; }
        boolean nothingAbove = e.up().higher(f) == null && e.down().higher(f) == null;
        if (nothingAbove && e.down().remove(f)) { e.openDoors(Direction.DOWN, now); return; }  // LOOK: turn here
        if (nothingAbove) e.setState(IdleState.INSTANCE);  // calls were withdrawn; stop safely
    }
}

final class MovingDownState implements ElevatorState {
    static final MovingDownState INSTANCE = new MovingDownState();
    public String name() { return "MOVING_DOWN"; }
    public void tick(Elevator e, int now) {
        e.moveBy(-1);
        int f = e.floor();
        if (e.down().remove(f)) { e.openDoors(Direction.DOWN, now); return; }
        boolean nothingBelow = e.down().lower(f) == null && e.up().lower(f) == null;
        if (nothingBelow && e.up().remove(f)) { e.openDoors(Direction.UP, now); return; }
        if (nothingBelow) e.setState(IdleState.INSTANCE);
    }
}

final class DoorsOpenState implements ElevatorState {
    static final DoorsOpenState INSTANCE = new DoorsOpenState();
    public String name() { return "DOORS_OPEN"; }
    public void tick(Elevator e, int now) {
        int f = e.floor();
        boolean above = e.up().higher(f) != null || e.down().higher(f) != null;
        boolean below = e.up().lower(f) != null || e.down().lower(f) != null;
        boolean nothingAhead = e.direction() == Direction.UP ? !above : !below;
        if (e.claimStopHere(now, nothingAhead)) return;   // someone called this floor while doors were open
        e.closeDoors(now);
        ElevatorState next;
        if (e.direction() == Direction.UP) next = above ? MovingUpState.INSTANCE : below ? MovingDownState.INSTANCE : IdleState.INSTANCE;
        else next = below ? MovingDownState.INSTANCE : above ? MovingUpState.INSTANCE : IdleState.INSTANCE;
        e.setState(next);
        if (next != IdleState.INSTANCE) next.tick(e, now);
        else e.setDirection(Direction.IDLE);
    }
}

// ---------- Elevator ----------

final class Elevator {
    private final String id;
    private final int minFloor, maxFloor;
    private int floor;
    private Direction direction = Direction.IDLE;
    private ElevatorState state = IdleState.INSTANCE;
    private final TreeSet<Integer> up = new TreeSet<>(), down = new TreeSet<>();
    private final List<Passenger> riders = new ArrayList<>();
    private final Building building;

    Elevator(String id, int startFloor, int minFloor, int maxFloor, Building building) {
        this.id = id; this.floor = startFloor; this.minFloor = minFloor; this.maxFloor = maxFloor;
        this.building = building;
    }

    void addHallCall(HallCall c) { (c.direction() == Direction.UP ? up : down).add(c.floor()); }

    void addCarCall(int target) {
        if (target > floor) up.add(target);
        else if (target < floor) down.add(target);
    }

    /**
     * If the current floor is a pending stop, serve it now. A call in the current direction is always
     * served; a call in the opposite direction only when reversing is allowed (LOOK turning point).
     */
    boolean claimStopHere(int now, boolean allowReverse) {
        Direction preferred = direction == Direction.DOWN ? Direction.DOWN : Direction.UP;
        TreeSet<Integer> first = preferred == Direction.UP ? up : down;
        TreeSet<Integer> second = preferred == Direction.UP ? down : up;
        if (first.remove(floor)) { openDoors(preferred, now); return true; }
        if (allowReverse && second.remove(floor)) {
            openDoors(preferred == Direction.UP ? Direction.DOWN : Direction.UP, now);
            return true;
        }
        return false;
    }

    void moveBy(int delta) {
        int next = floor + delta;
        if (next < minFloor || next > maxFloor) throw new IllegalStateException(id + " would leave the shaft");
        floor = next;
    }

    void openDoors(Direction servingDirection, int now) {
        direction = servingDirection;
        state = DoorsOpenState.INSTANCE;
        List<String> out = new ArrayList<>(), in = new ArrayList<>();
        for (Iterator<Passenger> it = riders.iterator(); it.hasNext(); ) {
            Passenger p = it.next();
            if (p.to == floor) { p.alightTick = now; out.add(p.name); it.remove(); }
        }
        for (Passenger p : building.board(floor, servingDirection)) {
            p.boardTick = now; riders.add(p); in.add(p.name); addCarCall(p.to);
        }
        building.log(now, id + " opens at " + floor + " going " + servingDirection
                + (out.isEmpty() ? "" : ", out " + out) + (in.isEmpty() ? "" : ", in " + in)
                + "  stops up" + up + " down" + down);
    }

    void closeDoors(int now) { /* hook for door sensors; nothing to do in the simulation */ }

    boolean hasStops() { return !up.isEmpty() || !down.isEmpty(); }

    int nearestStop() {
        int best = -1, bestDist = Integer.MAX_VALUE;
        for (TreeSet<Integer> s : List.of(up, down))
            for (int f : s) if (Math.abs(f - floor) < bestDist) { best = f; bestDist = Math.abs(f - floor); }
        return best;
    }

    /** Furthest pending stop in the current direction, or the current floor. */
    int endOfRun() {
        if (direction == Direction.UP) return Math.max(floor, Math.max(up.isEmpty() ? floor : up.last(), down.isEmpty() ? floor : down.last()));
        if (direction == Direction.DOWN) return Math.min(floor, Math.min(up.isEmpty() ? floor : up.first(), down.isEmpty() ? floor : down.first()));
        return floor;
    }

    String id() { return id; }
    int floor() { return floor; }
    Direction direction() { return direction; }
    void setDirection(Direction d) { direction = d; }
    ElevatorState state() { return state; }
    void setState(ElevatorState s) {
        state = s;
        if (s == MovingUpState.INSTANCE) direction = Direction.UP;
        if (s == MovingDownState.INSTANCE) direction = Direction.DOWN;
    }
    TreeSet<Integer> up() { return up; }
    TreeSet<Integer> down() { return down; }
}

// ---------- Strategy pattern for dispatch ----------

interface DispatchStrategy {
    Elevator choose(List<Elevator> elevators, HallCall call);
    String name();
}

/** Direction-aware nearest car: cheap if the car will pass the floor on its way, expensive otherwise. */
final class NearestCarStrategy implements DispatchStrategy {
    public String name() { return "nearest-car"; }

    static int cost(Elevator e, HallCall c) {
        int f = c.floor(), cur = e.floor();
        switch (e.direction()) {
            case IDLE: return Math.abs(cur - f);
            case UP:
                if (c.direction() == Direction.UP && f >= cur) return f - cur;   // on the way
                int top = e.endOfRun();
                return (top - cur) + Math.abs(top - f);                        // finish run, come back
            default:
                if (c.direction() == Direction.DOWN && f <= cur) return cur - f;
                int bottom = e.endOfRun();
                return (cur - bottom) + Math.abs(f - bottom);
        }
    }

    public Elevator choose(List<Elevator> elevators, HallCall call) {
        Elevator best = null; int bestCost = Integer.MAX_VALUE;
        for (Elevator e : elevators) {
            int c = cost(e, call);
            if (c < bestCost) { best = e; bestCost = c; }                      // ties: lower index wins
        }
        return best;
    }
}

/** Baseline for comparison: hand calls out in turn, ignoring position. */
final class RoundRobinStrategy implements DispatchStrategy {
    private int next = 0;
    public String name() { return "round-robin"; }
    public Elevator choose(List<Elevator> elevators, HallCall call) {
        return elevators.get(next++ % elevators.size());
    }
}

// ---------- Dispatcher and building ----------

final class Dispatcher {
    private final List<Elevator> elevators;
    private volatile DispatchStrategy strategy;
    // Buttons on any thread enqueue; only the simulation thread drains, so elevator state is single-threaded.
    private final Queue<HallCall> inbox = new ConcurrentLinkedQueue<>();

    Dispatcher(List<Elevator> elevators, DispatchStrategy strategy) {
        this.elevators = elevators; this.strategy = strategy;
    }

    void submit(HallCall c) { inbox.add(c); }

    int drainAndAssign(Building b, int now) {
        int n = 0;
        for (HallCall c; (c = inbox.poll()) != null; n++) {
            Elevator e = strategy.choose(elevators, c);
            e.addHallCall(c);
            if (b != null) b.log(now, "hall call " + c.floor() + " " + c.direction() + " -> " + e.id());
        }
        return n;
    }
}

final class Building {
    private final Map<Integer, List<Passenger>> waiting = new HashMap<>();
    private final boolean verbose;
    Building(boolean verbose) { this.verbose = verbose; }

    void arrive(Passenger p, Dispatcher d) {
        waiting.computeIfAbsent(p.from, k -> new ArrayList<>()).add(p);
        d.submit(new HallCall(p.from, p.direction()));
    }

    List<Passenger> board(int floor, Direction d) {
        List<Passenger> here = waiting.getOrDefault(floor, new ArrayList<>()), boarding = new ArrayList<>();
        for (Iterator<Passenger> it = here.iterator(); it.hasNext(); ) {
            Passenger p = it.next();
            if (p.direction() == d) { boarding.add(p); it.remove(); }
        }
        return boarding;
    }

    void log(int now, String msg) { if (verbose) System.out.printf("t=%2d  %s%n", now, msg); }
}

final class Simulation {
    static List<Passenger> script() {
        return List.of(
                new Passenger("Asha", 3, 8, 0),
                new Passenger("Ravi", 8, 1, 0),
                new Passenger("Meera", 5, 0, 1),
                new Passenger("Kiran", 0, 6, 2),
                new Passenger("Dev", 9, 2, 4),
                new Passenger("Lata", 2, 7, 6));
    }

    static void run(DispatchStrategy strategy, boolean verbose) {
        Building b = new Building(verbose);
        List<Elevator> cars = List.of(new Elevator("E1", 0, 0, 9, b), new Elevator("E2", 7, 0, 9, b));
        Dispatcher d = new Dispatcher(cars, strategy);
        List<Passenger> people = script();
        int now = 0;
        for (; now < 100; now++) {
            for (Passenger p : people) if (p.requestTick == now) b.arrive(p, d);
            d.drainAndAssign(b, now);
            for (Elevator e : cars) e.state().tick(e, now);
            final int t = now;
            if (people.stream().allMatch(p -> p.alightTick >= 0 && p.alightTick <= t)) break;
        }
        int totalWait = 0, totalTrip = 0;
        if (verbose) System.out.println("passenger  wait  ride");
        for (Passenger p : people) {
            int wait = p.boardTick - p.requestTick, ride = p.alightTick - p.boardTick;
            totalWait += wait; totalTrip += wait + ride;
            if (verbose) System.out.printf("%-9s %5d %5d%n", p.name, wait, ride);
        }
        System.out.printf("%s: all delivered by t=%d, total wait %d, average wait %.2f, average trip %.2f%n",
                strategy.name(), now, totalWait, totalWait / (double) people.size(), totalTrip / (double) people.size());
    }
}

public class ElevatorDemo {
    public static void main(String[] args) throws Exception {
        System.out.println("== Nearest-car dispatch, LOOK within each car ==");
        Simulation.run(new NearestCarStrategy(), true);
        System.out.println();
        System.out.println("== Same script, round-robin dispatch ==");
        Simulation.run(new RoundRobinStrategy(), false);
        System.out.println();

        System.out.println("== 8 threads press 500 buttons each ==");
        Building quiet = new Building(false);
        List<Elevator> cars = List.of(new Elevator("E1", 0, 0, 9, quiet), new Elevator("E2", 0, 0, 9, quiet));
        Dispatcher d = new Dispatcher(cars, new NearestCarStrategy());
        ExecutorService pool = Executors.newFixedThreadPool(8);
        for (int t = 0; t < 8; t++) {
            final int seed = t;
            pool.submit(() -> {
                for (int i = 0; i < 500; i++)
                    d.submit(new HallCall((seed + i) % 9 + 1, i % 2 == 0 ? Direction.UP : Direction.DOWN));
            });
        }
        pool.shutdown();
        pool.awaitTermination(10, TimeUnit.SECONDS);
        System.out.println("calls drained by the simulation thread: " + d.drainAndAssign(null, 0));
    }
}

The scenario

Two cars: E1 starts at floor 0, E2 at floor 7. Six passengers arrive:

Real output

This is the actual output from Temurin JDK 21:

== Nearest-car dispatch, LOOK within each car ==
t= 0  hall call 3 UP -> E1
t= 0  hall call 8 DOWN -> E2
t= 0  E2 opens at 8 going DOWN, in [Ravi]  stops up[] down[1]
t= 1  hall call 5 DOWN -> E2
t= 2  hall call 0 UP -> E1
t= 2  E1 opens at 3 going UP, in [Asha]  stops up[0, 8] down[]
t= 3  E2 opens at 5 going DOWN, in [Meera]  stops up[] down[0, 1]
t= 4  hall call 9 DOWN -> E1
t= 6  hall call 2 UP -> E2
t= 7  E1 opens at 8 going UP, out [Asha]  stops up[0] down[9]
t= 7  E2 opens at 1 going DOWN, out [Ravi]  stops up[2] down[0]
t= 8  E1 opens at 9 going DOWN, in [Dev]  stops up[0] down[2]
t= 8  E2 opens at 0 going DOWN, out [Meera]  stops up[2] down[]
t=10  E2 opens at 2 going UP, in [Lata]  stops up[7] down[]
t=15  E1 opens at 2 going DOWN, out [Dev]  stops up[0] down[]
t=15  E2 opens at 7 going UP, out [Lata]  stops up[] down[]
t=17  E1 opens at 0 going UP, in [Kiran]  stops up[6] down[]
t=23  E1 opens at 6 going UP, out [Kiran]  stops up[] down[]
passenger  wait  ride
Asha          2     5
Ravi          0     7
Meera         2     5
Kiran        15     6
Dev           4     7
Lata          4     5
nearest-car: all delivered by t=23, total wait 27, average wait 4.50, average trip 10.33

== Same script, round-robin dispatch ==
round-robin: all delivered by t=17, total wait 27, average wait 4.50, average trip 10.33

== 8 threads press 500 buttons each ==
calls drained by the simulation thread: 4000

Tracing the first few ticks by hand

Check the program against your own reasoning:

• Tick 0. Call "3 up": E1 is idle at 0, cost 3; E2 is idle at 7, cost 4. E1 wins. Call "8 down": E1 cost 8, E2 cost 1. E2 wins. E2 is idle, moves up to 8 in the same tick; nothing is requested above 8 and floor 8 is in its down set, so it opens going down. Ravi boards and presses 1, which goes into down. E1 moves to floor 1.
• Tick 1. Call "5 down" goes to E2 with cost 3 (worked example above). E2 closes, chooses to continue down, moves to 7. E1 moves to 2.
• Tick 2. Call "0 up": E1 is at 2 moving up with end of run 3, cost (3-2) + (3-0) = 4. E2 is at 7 moving down with end of run 1, cost (7-1) + |0-1| = 7. E1 wins. E1 moves to 3 and opens going up; Asha boards and presses 8. E1's up set is now [0, 8]: floor 0 is the "0 up" call that it will serve after turning.
• Tick 3. E2 reaches 5 and opens going down. Meera boards.

What the numbers teach

Kiran waited 15 ticks. When the "0 up" call was assigned at tick 2, E1's run ended at floor 3, so E1 looked cheap. Then Asha pressed 8, and at tick 4 Dev's "9 down" call was also given to E1, which carried E1 to the top of the building before it could return for Kiran. The cost estimate was correct when it was made and wrong soon after. This is a real weakness of greedy, assign-once dispatch, and it explains why round robin happened to finish this particular script sooner (tick 17 against 23) with the same total wait. (Run round robin with logging on and you will see it simply moves the pain: it hands Meera's call to E1, which is busy going up, and Meera waits 11 ticks instead of 2.)

Do not conclude that round robin is better: on a six-person script, luck dominates. The right conclusions are that strategies must be measured on realistic traffic, and that a production dispatcher re-evaluates unserved hall calls every tick and moves them to a better car when the estimate changes. That is exactly the extension interviewers ask for next, and the design supports it because hall calls live in the dispatcher's hands before cars serve them.

Concurrency considerations

Where the threads are

In a real building, each button panel, each car's door sensor and the operator console can be separate threads or separate devices sending messages. The controller must handle them all without corrupting car state.

Option 1: lock every elevator

Each Elevator method is synchronized; the dispatcher locks each car while computing costs. This works, but the dispatcher reads every car's state while that car might be moving, so it must lock all cars together to get a consistent picture, in a fixed order to avoid deadlock. Locks then spread through all the code.

Option 2: confinement plus a queue (what the code uses)

Thread confinement means some data is only ever touched by one thread, so it needs no locks. Here, cars, stop sets and passengers are touched only by the simulation thread. The only shared object is the dispatcher's inbox, a ConcurrentLinkedQueue, which is a lock-free thread-safe queue. Producers (buttons) call add; the single consumer (the simulation thread) calls poll until it is empty.

 button thread 1 --+
 button thread 2 --+--> [ inbox queue ] --> simulation thread:
 button thread N --+                         drain, assign, tick all cars

The demo's last section proves no press is lost: 8 threads each submit 500 calls concurrently, and the simulation thread drains exactly 4,000.

Visibility of the strategy field

strategy is volatile so that when an operator thread swaps it, the simulation thread sees the new object on its next read. Without volatile, the Java memory model allows the simulation thread to keep using a cached old reference.

Safety rules live in one place

moveBy throws if the car would leave the shaft, and only moving states call it, so a car can never move while in DOORS_OPEN. In a real system, hardware interlocks enforce this too; the software check is a second line of defence.

Extensions interviewers ask, and how the design absorbs them

1. Re-dispatching stale assignments. Keep pending hall calls in the dispatcher, not only in cars. Each tick, recompute costs; if another car is now cheaper by a margin, move the call. The margin avoids flapping between cars. Only the Dispatcher changes.

2. Capacity and weight. Add capacity to Elevator. Building.board takes the remaining space, and passengers left behind keep their hall call active (resubmit it). The cost function adds a penalty for full cars.

3. Emergency stop and fire mode. New states: EmergencyState ignores calls and holds; FireServiceState returns every car to the ground floor and opens the doors. The operator console triggers the transition. Existing states are untouched.

4. Maintenance mode. A MaintenanceState that the dispatcher skips; choose filters cars whose state is maintenance.

5. Zoning, express elevators. Give each car a set of floors it serves. The strategy filters cars that serve the call's floor. Express cars skip floors in their state's stop decision.

6. Peak-hour modes. In the morning up-peak, park idle cars in the lobby; in the evening, park them on upper floors. That is a new strategy plus an "idle parking floor" policy, swapped by time of day.

7. Destination dispatch. Hall calls carry the destination. The strategy groups passengers with nearby destinations into one car. The HallCall record gains a field; the strategy changes.

8. Door timing and obstruction. Doors-open becomes a counter of ticks; a door sensor event resets it. An ObstructedState can be added if the door is held too long.

9. Many buildings or real hardware. Replace the tick loop with real timers, and replace moveBy with a Motor interface. The states still decide; adapters perform.

Common mistakes

• Boolean flags instead of states, allowing impossible combinations like moving with doors open.
• A single queue of floors per car served in arrival order (FCFS), causing zig-zags.
• Nearest-floor-first scheduling without naming starvation.
• Mixing dispatch and car logic so the car decides which hall calls to take; then two cars both come.
• Ignoring the direction of hall calls. A passenger going down should not board a car going up; the code boards only same-direction passengers.
• Locking each car from many threads and creating deadlocks, when a single event loop is simpler.
• Using real Thread.sleep for movement in the core logic, making tests slow and flaky.
• Forgetting the reversal case: a "9 down" call while the car is moving up from 2 must be served at the top, then the car turns.

Interview questions

Q1. Why use the State pattern for an elevator?

An elevator's reaction to a tick or a call depends on whether it is idle, moving or has its doors open. The State pattern puts each behaviour in its own class and makes illegal combinations, such as moving with doors open, impossible to represent. New modes like emergency or maintenance become new classes rather than new branches in a giant switch.

Q2. What is the difference between SCAN and LOOK?

Both sweep in one direction serving requests, then reverse. SCAN travels to the end of the building before reversing; LOOK reverses at the last requested floor in the current direction. LOOK saves the wasted trip to an end floor nobody asked for, which is why real elevators behave like LOOK.

Q3. Why not always go to the nearest requested floor?

That is SSTF, and it can starve a floor far from a busy cluster: new nearby requests keep winning. LOOK commits to a direction, so every floor is reached within one sweep in each direction.

Q4. How do you decide which elevator answers a hall call?

A dispatcher with a pluggable strategy. My default is a direction-aware nearest-car cost: cheap if the car will pass the floor in the requested direction on its current run, otherwise the distance to finish the run and come back. Ties go to a fixed order for determinism.

Q5. How do you represent pending stops?

Two sorted sets per car, one for stops served going up and one for going down. Hall calls go into the set matching their direction; car calls go into up or down by comparing with the current floor. TreeSet.higher and lower answer "anything above or below?" in logarithmic time.

Q6. How is thread safety handled?

Car state is confined to one simulation thread, so it needs no locks. Buttons on other threads submit hall calls to a lock-free concurrent queue that the simulation thread drains at the start of each tick. The strategy reference is volatile so a swap is visible immediately.

Q7. What if a passenger presses the floor the car is already on?

For a car call, the code ignores it because the car is already there. For a hall call while the doors are open in the matching direction, the doors-open state notices on its next tick, keeps the doors open and boards the passenger.

Q8. How would you add capacity limits?

Add a capacity to the car and let boarding admit only as many as fit. Passengers left behind still need service, so their hall call is resubmitted. The dispatcher penalises full cars in its cost function.

Q9. How would you test this?

Deterministic ticks make it straightforward: run a scripted scenario and assert stop order and wait times. Unit-test each state's transitions in isolation, the cost function with hand-computed cases, and edge cases such as calls at the top and bottom floors and a call on the car's current floor.

Q10. Your nearest-car strategy gave one passenger a long wait. Why, and how do you fix it?

The assignment was made once, using the car's run at that moment, and later car calls extended that run. Fix it by keeping unserved hall calls in the dispatcher and re-evaluating every tick, moving a call to another car only when the improvement exceeds a threshold to avoid flapping.

Q11. How would you implement fire service mode?

A new state that cancels all calls, drives the car to the designated floor, opens the doors and stays there until a firefighter key switch changes it. The dispatcher stops assigning calls to cars in that state. No other state class needs internal changes beyond the transition into it.

Q12. Why is the simulation tick-based?

Ticks make behaviour deterministic and fast to test, and they let you compare strategies on the same input. A real controller replaces the loop with timers and hardware events, while the states and strategies stay the same.

Q13. What would change with 50 cars in a skyscraper?

Zoning or sky lobbies, so each car serves a range of floors; destination dispatch to group passengers; and possibly one actor per car with the dispatcher sending messages. The State and Strategy structure stays the same.

Key takeaways

• Separate hall calls (floor plus direction, need a car) from car calls (floor, already owned by a car).
• Model each car as a state machine with the State pattern; illegal combinations disappear.
• Schedule within a car with LOOK, using two sorted stop sets, and be able to compare it with FCFS, SSTF and SCAN on a worked example.
• Put dispatch behind a Strategy so policies can change by time of day or building.
• Confine car state to one thread and feed it through a concurrent queue; it is simpler and safer than locks everywhere.
• Simulate with ticks so runs are deterministic and testable.
• Greedy one-time assignment goes stale; re-dispatching pending calls is the natural improvement.

Next lesson

Continue with Design a movie ticket booking system.