Elevator System

Design the control software for a group of elevators in an office tower. Take calls, pick the best elevator, and move each car with a rule that is easy to swap.

Design an elevator system for a 20-floor office building with 4 elevators. People press up or down on a floor, and press a destination inside the car. Show how requests reach elevators and how each elevator decides where to go.

Questions to ask first

  • How many floors and elevators? Assume 20 floors and 4 elevators, all serving every floor.
  • Do we model time? Assume a `tick()` that moves each elevator one floor. A real system gets this from the motor controller.
  • Which buttons exist? Up and down on each floor (a hall call), and floor buttons inside each car (a car call for that car only).
  • Must the dispatch rule change? Yes. The building wants a different rule in the morning rush, so the rule must be swappable at runtime.
  • Do we handle weight limits, fire mode or maintenance? Assume maintenance mode only. Weight and fire mode are extensions.

Requirements

  • Accept a hall call (floor and direction) and assign it to one elevator.
  • Accept a car call (destination floor) inside a specific elevator.
  • Move each elevator one floor per tick. Stop at requested floors in the current direction before turning around.
  • Open the doors on arrival, then continue to the next stop.
  • Let operations take an elevator out of service. It must get no new requests.
  • Let the building switch the dispatch rule without a restart.

Out of scope

  • Motor control, door sensors and hardware timing.
  • Weight limits, fire mode and VIP floors (see the extensions).
  • The lobby display screens.

Entities

  • ElevatorController: elevators, strategy; requestPickup(floor, dir), setStrategy(s), tick()
  • Elevator: currentFloor, direction, state, upStops, downStops; addStop(floor), step()
  • Door: open(), close()
  • Request: floor, direction
  • DispatchStrategy: choose(elevators, request); NearestCarStrategy, ZoneStrategy
  • Direction: UP, DOWN, NONE
  • ElevatorState: IDLE, MOVING, DOORS_OPEN, MAINTENANCE

Classes in the model design

  • ElevatorController (class)
  • Elevator (class)
  • Door (class)
  • Direction (enum)
  • ElevatorState (enum)
  • Request (class)
  • DispatchStrategy (interface)
  • NearestCarStrategy (class)
  • ZoneStrategy (class)

The main use case, step by step

  1. A person on floor 7 presses DOWN. The panel calls `controller.requestPickup(7, DOWN)`, which builds a `Request`.
  2. The controller does not choose by itself. It calls `strategy.choose(elevators, request)` on its current `DispatchStrategy`.
  3. `NearestCarStrategy` skips elevators in MAINTENANCE and scores the rest. The score is the distance, plus a penalty if the car is moving away from floor 7. Elevator 2, at floor 9 going down, wins.
  4. The controller calls `elevator2.addStop(7)`. Floor 7 is below floor 9, so it goes into `downStops`, a sorted set.
  5. Each `tick()` calls `step()` on every elevator. Elevator 2 keeps moving down while `downStops` has floors. This is the LOOK rule: serve every stop ahead, then turn.
  6. At floor 7, `step()` removes 7 from `downStops` and sets the state to DOORS_OPEN. The person enters and presses 1, which calls `addStop(1)` on that elevator directly.

Patterns used

  • Strategy: DispatchStrategy with NearestCarStrategy and ZoneStrategy, held by ElevatorController.. The building wants different rules at different hours. `setStrategy` swaps the rule at runtime, and each rule can be tested alone with fake elevators.
  • State (as an enum with guarded transitions): ElevatorState inside Elevator: IDLE, MOVING, DOORS_OPEN, MAINTENANCE.. Rules like "never move with doors open" and "no new stops in maintenance" are checked in one place. With four states and few actions, an enum is clearer than a full State pattern.
  • Composition: ElevatorController owns its Elevators; each Elevator owns its Door.. A door has no meaning without its car, and the controller creates and stops the cars it manages.

Key code

The dispatch strategy and the controller

public enum Direction { UP, DOWN, NONE }

public record Request(int floor, Direction direction) { }

public interface DispatchStrategy {
    Elevator choose(List<Elevator> elevators, Request request);
}

public final class NearestCarStrategy implements DispatchStrategy {
    private final int floors;
    public NearestCarStrategy(int floors) { this.floors = floors; }

    @Override
    public Elevator choose(List<Elevator> elevators, Request r) {
        return elevators.stream()
            .filter(e -> e.state() != ElevatorState.MAINTENANCE)
            .min(Comparator.comparingInt(e -> cost(e, r)))
            .orElseThrow(() -> new IllegalStateException("No elevator in service"));
    }

    // Distance, plus a penalty when the car is moving away from the caller.
    private int cost(Elevator e, Request r) {
        int at = e.currentFloor();
        boolean onTheWay = switch (e.direction()) {
            case NONE -> true;
            case UP -> r.floor() >= at && r.direction() == Direction.UP;
            case DOWN -> r.floor() <= at && r.direction() == Direction.DOWN;
        };
        return Math.abs(at - r.floor()) + (onTheWay ? 0 : 2 * floors);
    }
}

public final class ElevatorController {
    private final List<Elevator> elevators;
    private volatile DispatchStrategy strategy;   // swapped at runtime

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

    public void setStrategy(DispatchStrategy s) { this.strategy = s; }

    public Elevator requestPickup(int floor, Direction dir) {
        Elevator chosen = strategy.choose(elevators, new Request(floor, dir));
        chosen.addStop(floor);
        return chosen;
    }

    public void tick() { elevators.forEach(Elevator::step); }
}

Elevator: the LOOK movement rule

public final class Elevator {
    private final int id;
    private int currentFloor;
    private Direction direction = Direction.NONE;
    private ElevatorState state = ElevatorState.IDLE;
    private final TreeSet<Integer> upStops = new TreeSet<>();    // floors above us
    private final TreeSet<Integer> downStops = new TreeSet<>();  // floors below us

    public Elevator(int id, int startFloor) { this.id = id; this.currentFloor = startFloor; }

    public synchronized void addStop(int floor) {
        if (state == ElevatorState.MAINTENANCE) throw new IllegalStateException("Elevator " + id + " is out of service");
        if (floor > currentFloor) upStops.add(floor);
        else if (floor < currentFloor) downStops.add(floor);
        else state = ElevatorState.DOORS_OPEN;                   // already here
    }

    /** One tick: close the doors, pick a direction, move one floor, open at a stop. */
    public synchronized void step() {
        if (state == ElevatorState.MAINTENANCE) return;
        direction = nextDirection();
        if (direction == Direction.NONE) { state = ElevatorState.IDLE; return; }
        currentFloor += direction == Direction.UP ? 1 : -1;
        TreeSet<Integer> ahead = direction == Direction.UP ? upStops : downStops;
        state = ahead.remove(currentFloor) ? ElevatorState.DOORS_OPEN : ElevatorState.MOVING;
    }

    // LOOK: keep going while stops remain ahead; turn only when none are left.
    private Direction nextDirection() {
        if (direction == Direction.UP && !upStops.isEmpty()) return Direction.UP;
        if (direction == Direction.DOWN && !downStops.isEmpty()) return Direction.DOWN;
        if (!upStops.isEmpty()) return Direction.UP;
        if (!downStops.isEmpty()) return Direction.DOWN;
        return Direction.NONE;
    }

    public synchronized void setInService(boolean on) {
        if (on) { if (state == ElevatorState.MAINTENANCE) state = ElevatorState.IDLE; return; }
        upStops.clear();                                         // real systems finish the trip first
        downStops.clear();
        direction = Direction.NONE;
        state = ElevatorState.MAINTENANCE;
    }

    public synchronized int currentFloor() { return currentFloor; }
    public synchronized Direction direction() { return direction; }
    public synchronized ElevatorState state() { return state; }
}

Deep dives

Which elevator answers a hall call?

Weak: Send every call to elevator 1, or pick one at random. It is easy to code. But people wait for a car on the far side of the building while another one stands idle next to them.

Good: Nearest car. Score each elevator by distance, and add a penalty when it is moving away from the caller. This needs only the floor and direction of each car, and it gives sensible results.

Great: Keep the rule behind DispatchStrategy and offer more than one. In the morning rush, a ZoneStrategy sends cars 1 and 2 to floors 1 to 10 and cars 3 and 4 to floors 11 to 20. At other times, nearest car works well. Large towers use destination dispatch: people enter their floor in the lobby, and the system groups people going to nearby floors.

Trade-off: Smarter rules need more data and are harder to test. A strategy interface lets you start with nearest car and add others without touching the controller or Elevator.

Which floor next, inside one elevator?

Weak: First come, first served: visit floors in the order they were pressed. A car goes to 2, then 18, then 3, then 17, and spends most of its time travelling empty.

Good: SCAN, the rule disk drives used: go up to the top floor, then down to the bottom, stopping at requested floors on the way. No request waits forever. But the car travels to the ends even when nobody needs it.

Great: LOOK: keep going in the current direction while there are stops ahead, then turn. Two sorted sets make it simple: upStops for floors above and downStops for floors below. A TreeSet finds the next stop in O(log n) time. A complete answer also remembers the hall direction, so a DOWN call at floor 7 is not served while the car goes up.

Trade-off: LOOK can make someone at the far end wait longer when traffic is heavy in one area. Real systems add a maximum waiting time. Mention it; you rarely need to code it.

Thread safety: buttons, ticks and the dispatcher

Weak: No locks. A button press calls addStop on one thread while the tick thread runs step(). TreeSet is not thread safe, so a stop can be lost or the set can throw an exception.

Good: Make addStop, step and the getters on Elevator synchronized. Each elevator is its own lock, so elevators never block each other. This is the minimum an interviewer expects.

Great: Give each elevator one thread that takes commands from a BlockingQueue. A blocking queue is a thread-safe queue where the taker waits until an item arrives. Button presses only add commands. All state changes then happen on one thread, so Elevator's fields need no lock. The dispatcher reads a snapshot of each car taken at one moment.

Trade-off: The queue design scales and is easy to reason about, but it needs more code and a clean shutdown. In a 90-minute round, synchronized methods are usually enough. Describe the queue as the next step.

Now add one more feature

  • Now add a weight limit. Add `currentLoadKg` and `maxLoadKg` to Elevator. A full car refuses new hall calls, so the strategy filters out full cars. Car calls from people already inside still work.
  • Now add fire mode. Add a FIRE value to ElevatorState. On an alarm, the controller sends every car to the ground floor, opens the doors and ignores all buttons. Only the state checks in Elevator change, plus one controller method.
  • Now add service elevators that only some floors may call. Give each Elevator a set of allowed floors. The strategy skips cars that cannot serve the floor. The controller does not change.
  • Now show each car's floor on a lobby display. Elevator publishes a floor-changed event and displays subscribe to it (the observer pattern). Elevator does not know how many displays exist.

What each level is expected to show

SDE-1: Controller, Elevator, Request, Direction and a state enum with clear fields. A working nearest-car choice and a simple up-then-down movement rule. Knows the dispatch rule should sit behind an interface.

SDE-2: A `DispatchStrategy` that can be swapped at runtime, the LOOK rule with sorted stop sets, and a state diagram with guards (no moving with doors open, no stops in maintenance). Has a clear thread-safety story and discusses zoning or destination dispatch.

Common mistakes

  • Putting the dispatch rule inside ElevatorController as one long method, so a new rule means editing the controller.
  • Mixing hall calls and car calls. A hall call picks an elevator; a car call already belongs to one elevator.
  • Keeping one queue of floors in arrival order, so the car moves up and down without need.
  • Using booleans like `isMoving` and `doorOpen` instead of one state. Nothing stops both being true.
  • Forgetting maintenance, so the dispatcher keeps sending calls to a car that is out of service.
  • Sharing a `TreeSet` between the button thread and the tick thread without any lock.

Lessons behind this answer