LayoffReady

Design an Elevator System

Hardobject-oriented design · design patterns · state pattern · strategy pattern · scheduling · concurrency · java⏱ 14 min readAsked at Amazon, Microsoft, Google, Uber, BloombergUpdated

Model a bank of elevators with hall and car calls, a pluggable dispatcher, LOOK-style stop ordering and a State-pattern car that moves, opens doors, idles and goes into maintenance.

Requirements

The elevator question looks simple, but it mixes three separate problems: modelling (cars, floors, buttons), scheduling (which car answers a call, and in what order a car visits its stops) and behaviour over time (a car is moving, stopped with doors open, idle or out of service). A strong answer keeps those three concerns in different classes.

Functional

  • A building has floors 0..N-1 and M elevator cars.
  • Hall calls: on each floor, a passenger presses UP or DOWN. The system assigns exactly one car.
  • Car calls: inside a car, a passenger presses a destination floor. Only that car serves it.
  • A car keeps moving in its current direction while it still has stops ahead, then reverses (the LOOK algorithm).
  • Doors open at each stop for a short dwell time, then close.
  • A car can be put into maintenance; it stops taking calls and its unserved hall calls are handed to other cars.

Non-functional

  • Requests arrive concurrently from many button panels while the cars are moving.
  • The dispatch policy must be swappable (nearest car, zoning, peak-hour modes) without touching car logic.
  • Behaviour must be deterministic and testable, so time is modelled as discrete ticks (one tick = one floor of travel).

Out of scope (confirm first)

  • Weight sensors, fire/emergency modes, door obstruction sensors, destination-dispatch keypads, physical motor control.
Tip

Ask early: "Do hall buttons have a direction?" Almost always yes, and that single fact is what makes direction-aware scheduling (and the LOOK algorithm) necessary.

Core Entities

Entity Responsibility Key fields
Direction (enum) UP, DOWN or IDLE; knows its opposite -
HallCall (record) A request from a floor panel floor, direction
Elevator One car: position, direction, pending stops; delegates behaviour to its current state id, floor, direction, carStops, upHall, downHall, state
ElevatorState Behaviour for one tick in a given mode interface
IdleState, MovingState, DoorsOpenState, MaintenanceState Concrete car states dwell counter for doors
DispatchStrategy Chooses which car takes a hall call interface
LookCostStrategy Estimates travel cost respecting each car's sweep -
ElevatorController Facade: accepts hall/car calls, dispatches, advances time cars, strategy

A car keeps three stop sets instead of one. Car calls (carStops) are served in either direction because the rider just wants to get out. Hall calls are split into upHall and downHall because a person waiting to go down should not be picked up by a car that is heading up, except at the turnaround point.

Class Diagram

classDiagram
  class Direction {
    <<enumeration>>
    UP
    DOWN
    IDLE
    +opposite() Direction
  }
  class HallCall {
    +int floor
    +Direction direction
  }
  class Elevator {
    -int id
    -int floor
    -Direction direction
    -TreeSet carStops
    -TreeSet upHall
    -TreeSet downHall
    -ElevatorState state
    +addCarCall(int) boolean
    +addHallCall(HallCall) boolean
    +step(int) void
    +shouldStopHere() boolean
    +pickDirection() Direction
    +enterMaintenance() List
  }
  class ElevatorState {
    <<interface>>
    +step(Elevator, int) void
    +acceptsRequests() boolean
  }
  class IdleState
  class MovingState
  class DoorsOpenState {
    -int ticksLeft
  }
  class MaintenanceState
  class DispatchStrategy {
    <<interface>>
    +select(List, HallCall) Optional
  }
  class LookCostStrategy {
    +cost(Elevator, HallCall) int
  }
  class ElevatorController {
    -List cars
    -DispatchStrategy strategy
    +requestElevator(int, Direction, int) void
    +selectFloor(int, int) void
    +step(int) void
    +setMaintenance(int, int) void
  }

  ElevatorState <|.. IdleState
  ElevatorState <|.. MovingState
  ElevatorState <|.. DoorsOpenState
  ElevatorState <|.. MaintenanceState
  DispatchStrategy <|.. LookCostStrategy
  Elevator --> ElevatorState
  Elevator --> Direction
  ElevatorController "1" *-- "many" Elevator
  ElevatorController --> DispatchStrategy
  ElevatorController ..> HallCall : creates

Design Patterns Used

Pattern Where Why it is justified
State ElevatorState and its four implementations What a car does on each tick depends entirely on its mode. Without State, step() becomes a large switch that every new mode (fire service, VIP, door-hold) must edit
Strategy DispatchStrategy Buildings use different policies: nearest car, zoning (car A serves floors 0-10), up-peak mode in the morning. Each is a new class
Facade ElevatorController Button panels only call requestElevator / selectFloor; they never see stop sets or states
Value objects HallCall record, Direction enum Immutable, safe to pass between threads and to store in sets

Two levels of scheduling

Interviewers often blur these, so separate them explicitly:

  1. Dispatch (system level): which car should answer a hall call? This is the DispatchStrategy.
  2. Sequencing (car level): in what order should one car visit its stops? This is the LOOK rule inside Elevator.

The classic disk-scheduling algorithms map directly onto sequencing. SCAN sweeps all the way to the end of the building before reversing; LOOK reverses as soon as there is nothing further ahead, which is what real elevators do. FCFS (serve in arrival order) is simple but makes the car zig-zag, and shortest-seek-first can starve a passenger at the far end of the building.

Insight

The LOOK rule is three lines: stop at a floor if a car call is there, or a hall call in the same direction is there, or a hall call in the opposite direction is there and nothing lies further ahead (that floor is the turnaround point).

The LookCostStrategy estimates how many floors a car must travel to reach a caller:

  • Idle car: plain distance.
  • Car already heading toward the caller in the same direction: plain distance, because the caller is "on the way".
  • Otherwise: distance to the car's farthest stop in its current direction, plus the distance back to the caller.

Ties are broken by fewer pending stops, then by car id, which keeps the result deterministic.

Java Implementation

One compilable Main.java (Java 17+). Time advances with step(tick); in production a scheduler thread would call it every few hundred milliseconds.

java
import java.util.*;
import java.util.function.IntConsumer;

enum Direction {
    UP, DOWN, IDLE;

    Direction opposite() {
        return this == UP ? DOWN : this == DOWN ? UP : IDLE;
    }
}

record HallCall(int floor, Direction direction) {}

interface ElevatorState {
    String label();
    void step(Elevator car, int tick);
    default boolean acceptsRequests() { return true; }
    default boolean doorsOpen() { return false; }
}

class IdleState implements ElevatorState {
    public String label() { return "IDLE"; }

    public void step(Elevator car, int tick) {
        if (car.serveCurrentFloor()) { car.openDoors(tick); return; }
        Direction next = car.pickDirection();
        if (next == Direction.IDLE) return;
        car.setDirection(next);
        car.setState(new MovingState());
        car.getState().step(car, tick);            // start moving in this same tick
    }
}

class MovingState implements ElevatorState {
    public String label() { return "MOVING"; }

    public void step(Elevator car, int tick) {
        if (!car.hasStopsBeyond(car.getDirection())) {      // nothing ahead: re-plan
            Direction next = car.pickDirection();
            car.setDirection(next);
            if (next == Direction.IDLE) { car.setState(new IdleState()); return; }
        }
        car.moveOneFloor();
        if (car.shouldStopHere()) {
            car.serveCurrentFloor();
            car.openDoors(tick);
        }
    }
}

class DoorsOpenState implements ElevatorState {
    private int ticksLeft;

    DoorsOpenState(int dwellTicks) { this.ticksLeft = dwellTicks; }

    public String label() { return "DOORS_OPEN"; }
    public boolean doorsOpen() { return true; }

    public void step(Elevator car, int tick) {
        if (--ticksLeft > 0) return;
        Direction next = car.pickDirection();
        car.setDirection(next);
        car.setState(next == Direction.IDLE ? new IdleState() : new MovingState());
    }
}

class MaintenanceState implements ElevatorState {
    public String label() { return "MAINTENANCE"; }
    public boolean acceptsRequests() { return false; }
    public void step(Elevator car, int tick) { }
}

class Elevator {
    private static final int DOOR_DWELL_TICKS = 2;

    private final int id;
    private final int minFloor;
    private final int maxFloor;
    private int floor;
    private Direction direction = Direction.IDLE;
    private ElevatorState state = new IdleState();
    private final TreeSet<Integer> carStops = new TreeSet<>();
    private final TreeSet<Integer> upHall = new TreeSet<>();
    private final TreeSet<Integer> downHall = new TreeSet<>();

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

    int getId() { return id; }
    synchronized int getFloor() { return floor; }
    synchronized Direction getDirection() { return direction; }
    synchronized ElevatorState getState() { return state; }
    synchronized void setDirection(Direction d) { direction = d; }
    synchronized void setState(ElevatorState s) { state = s; }
    synchronized boolean isInService() { return state.acceptsRequests(); }
    synchronized int pendingStops() { return carStops.size() + upHall.size() + downHall.size(); }

    private TreeSet<Integer> hallSet(Direction d) { return d == Direction.UP ? upHall : downHall; }

    synchronized boolean addCarCall(int target) {
        if (target < minFloor || target > maxFloor || !state.acceptsRequests()) return false;
        if (target == floor && state.doorsOpen()) return true;    // already here, doors open
        carStops.add(target);
        return true;
    }

    synchronized boolean addHallCall(HallCall call) {
        if (!state.acceptsRequests()) return false;
        if (call.floor() == floor && state.doorsOpen()
                && (direction == call.direction() || direction == Direction.IDLE)) return true;
        hallSet(call.direction()).add(call.floor());
        return true;
    }

    synchronized boolean hasStopsBeyond(Direction d) {
        if (d == Direction.UP) {
            return carStops.higher(floor) != null || upHall.higher(floor) != null || downHall.higher(floor) != null;
        }
        if (d == Direction.DOWN) {
            return carStops.lower(floor) != null || upHall.lower(floor) != null || downHall.lower(floor) != null;
        }
        return false;
    }

    // Farthest pending stop in direction d (used by the dispatcher's cost estimate).
    synchronized int farthestStop(Direction d) {
        int far = floor;
        for (TreeSet<Integer> s : List.of(carStops, upHall, downHall)) {
            if (s.isEmpty()) continue;
            far = d == Direction.UP ? Math.max(far, s.last()) : Math.min(far, s.first());
        }
        return far;
    }

    // LOOK: keep going while there is work ahead, otherwise reverse, otherwise idle.
    synchronized Direction pickDirection() {
        if (direction != Direction.IDLE && hasStopsBeyond(direction)) return direction;
        if (direction != Direction.IDLE && hasStopsBeyond(direction.opposite())) return direction.opposite();
        if (hasStopsBeyond(Direction.UP)) return Direction.UP;
        if (hasStopsBeyond(Direction.DOWN)) return Direction.DOWN;
        return Direction.IDLE;
    }

    synchronized boolean shouldStopHere() {
        if (carStops.contains(floor) || hallSet(direction).contains(floor)) return true;
        return hallSet(direction.opposite()).contains(floor) && !hasStopsBeyond(direction);
    }

    // Clears every request satisfied by stopping here; may flip direction at a turnaround.
    synchronized boolean serveCurrentFloor() {
        boolean served = carStops.remove(floor);
        if (direction == Direction.IDLE) {
            if (upHall.remove(floor)) { direction = Direction.UP; served = true; }
            else if (downHall.remove(floor)) { direction = Direction.DOWN; served = true; }
            return served;
        }
        served |= hallSet(direction).remove(floor);
        if (!hasStopsBeyond(direction) && hallSet(direction.opposite()).remove(floor)) {
            direction = direction.opposite();
            served = true;
        }
        return served;
    }

    synchronized void moveOneFloor() {
        int next = floor + (direction == Direction.UP ? 1 : -1);
        floor = Math.max(minFloor, Math.min(maxFloor, next));
    }

    synchronized void openDoors(int tick) {
        state = new DoorsOpenState(DOOR_DWELL_TICKS);
        System.out.printf("t=%2d  E%d opens doors at floor %d (heading %s)%n", tick, id, floor, direction);
    }

    // Takes the car out of service and returns hall calls that must be re-dispatched.
    synchronized List<HallCall> enterMaintenance() {
        List<HallCall> orphaned = new ArrayList<>();
        upHall.forEach(f -> orphaned.add(new HallCall(f, Direction.UP)));
        downHall.forEach(f -> orphaned.add(new HallCall(f, Direction.DOWN)));
        upHall.clear();
        downHall.clear();
        carStops.clear();
        direction = Direction.IDLE;
        state = new MaintenanceState();
        return orphaned;
    }

    synchronized void step(int tick) { state.step(this, tick); }

    @Override public synchronized String toString() {
        return "E" + id + "@" + floor + " " + state.label();
    }
}

interface DispatchStrategy {
    Optional<Elevator> select(List<Elevator> cars, HallCall call);
}

class LookCostStrategy implements DispatchStrategy {
    int cost(Elevator car, HallCall call) {
        int cur = car.getFloor();
        int target = call.floor();
        Direction d = car.getDirection();
        if (d == Direction.IDLE) return Math.abs(cur - target);
        boolean onTheWay = call.direction() == d
                && (d == Direction.UP ? target > cur : target < cur);
        if (onTheWay) return Math.abs(target - cur);
        int turn = car.farthestStop(d);
        return Math.abs(turn - cur) + Math.abs(turn - target);
    }

    public Optional<Elevator> select(List<Elevator> cars, HallCall call) {
        return cars.stream()
                .filter(Elevator::isInService)
                .min(Comparator.comparingInt((Elevator c) -> cost(c, call))
                        .thenComparingInt(Elevator::pendingStops)
                        .thenComparingInt(Elevator::getId));
    }
}

class ElevatorController {
    private final List<Elevator> cars = new ArrayList<>();
    private final DispatchStrategy strategy;
    private final int floors;

    ElevatorController(int floors, int carCount, DispatchStrategy strategy) {
        this.floors = floors;
        this.strategy = strategy;
        for (int i = 1; i <= carCount; i++) cars.add(new Elevator(i, 0, floors - 1, 0));
    }

    synchronized void requestElevator(int floor, Direction dir, int tick) {
        if (floor < 0 || floor >= floors || dir == Direction.IDLE) throw new IllegalArgumentException("bad hall call");
        dispatch(new HallCall(floor, dir), tick);
    }

    private void dispatch(HallCall call, int tick) {
        Optional<Elevator> chosen = strategy.select(cars, call);
        if (chosen.isPresent() && chosen.get().addHallCall(call)) {
            System.out.printf("t=%2d  hall call %d %s -> E%d%n", tick, call.floor(), call.direction(), chosen.get().getId());
        } else {
            System.out.printf("t=%2d  hall call %d %s -> no car available%n", tick, call.floor(), call.direction());
        }
    }

    void selectFloor(int carId, int floor, int tick) {
        boolean ok = car(carId).addCarCall(floor);
        System.out.printf("t=%2d  inside E%d: floor %d %s%n", tick, carId, floor, ok ? "accepted" : "rejected");
    }

    synchronized void setMaintenance(int carId, int tick) {
        List<HallCall> orphaned = car(carId).enterMaintenance();
        System.out.printf("t=%2d  E%d -> maintenance, re-dispatching %s%n", tick, carId, orphaned);
        orphaned.forEach(call -> dispatch(call, tick));
    }

    synchronized void step(int tick) { cars.forEach(c -> c.step(tick)); }

    Elevator car(int id) { return cars.get(id - 1); }
    List<Elevator> getCars() { return Collections.unmodifiableList(cars); }
}

public class Main {
    public static void main(String[] args) {
        ElevatorController ctl = new ElevatorController(10, 2, new LookCostStrategy());
        Map<Integer, List<IntConsumer>> script = new HashMap<>();
        script.computeIfAbsent(0, k -> new ArrayList<>()).add(t -> ctl.requestElevator(6, Direction.DOWN, t));
        script.computeIfAbsent(0, k -> new ArrayList<>()).add(t -> ctl.requestElevator(2, Direction.UP, t));
        script.computeIfAbsent(1, k -> new ArrayList<>()).add(t -> ctl.requestElevator(4, Direction.UP, t));
        script.computeIfAbsent(2, k -> new ArrayList<>()).add(t -> ctl.selectFloor(2, 8, t));
        script.computeIfAbsent(6, k -> new ArrayList<>()).add(t -> ctl.requestElevator(3, Direction.DOWN, t));
        script.computeIfAbsent(9, k -> new ArrayList<>()).add(t -> ctl.selectFloor(1, 0, t));
        script.computeIfAbsent(10, k -> new ArrayList<>()).add(t -> ctl.requestElevator(9, Direction.DOWN, t));
        script.computeIfAbsent(11, k -> new ArrayList<>()).add(t -> ctl.setMaintenance(2, t));
        script.computeIfAbsent(12, k -> new ArrayList<>()).add(t -> ctl.selectFloor(2, 5, t));

        for (int tick = 0; tick <= 30; tick++) {
            final int t = tick;
            script.getOrDefault(tick, List.of()).forEach(action -> action.accept(t));
            ctl.step(tick);
        }
        System.out.println("Final: " + ctl.getCars());
    }
}

Demo output

text
t= 0  hall call 6 DOWN -> E1
t= 0  hall call 2 UP -> E2
t= 1  hall call 4 UP -> E1
t= 1  E2 opens doors at floor 2 (heading UP)
t= 2  inside E2: floor 8 accepted
t= 3  E1 opens doors at floor 4 (heading UP)
t= 6  hall call 3 DOWN -> E1
t= 7  E1 opens doors at floor 6 (heading DOWN)
t= 9  inside E1: floor 0 accepted
t= 9  E2 opens doors at floor 8 (heading UP)
t=10  hall call 9 DOWN -> E2
t=11  E2 -> maintenance, re-dispatching [HallCall[floor=9, direction=DOWN]]
t=11  hall call 9 DOWN -> E1
t=12  inside E2: floor 5 rejected
t=12  E1 opens doors at floor 3 (heading DOWN)
t=17  E1 opens doors at floor 0 (heading DOWN)
t=28  E1 opens doors at floor 9 (heading DOWN)
Final: [E1@9 IDLE, E2@8 MAINTENANCE]

Walkthrough:

  • Both cars start idle at floor 0. The DOWN call at 6 goes to E1 (tie broken by id); the UP call at 2 goes to E2 because E1 now has a pending stop.
  • At t=1 both cars are at floor 1 heading up, so floor 4 (UP) is "on the way" for both at a cost of 3 floors; the tie-breakers pick E1, which stops at 4 before continuing to 6.
  • E1 opens at 6 heading DOWN: floor 6 was a turnaround point, so the car served the DOWN caller and flipped direction.
  • The DOWN call at 3 is on E1's way down, so E1 stops at 3 before its car call to 0. That is LOOK sequencing: stops are visited in sweep order, not arrival order.
  • When E2 goes into maintenance its pending hall call at 9 is re-dispatched to E1, and E2 rejects new car calls. E1 finishes its down sweep, then travels up to 9 and turns around there.
  • Doors stay open for two ticks before the car moves again, which is why E1 reaches floor 9 at t=28 rather than t=26.

Concurrency Considerations

Button presses arrive on many threads while a single scheduler thread calls step. The design keeps this safe and simple:

  • Each Elevator is its own monitor. All reads and writes of position, direction and stop sets are synchronized, so a hall call added mid-tick cannot corrupt a TreeSet or be lost between shouldStopHere and serveCurrentFloor.
  • States call back into the car while holding the car's lock. Java monitors are reentrant, so this is safe, and the state objects themselves have no shared mutable data.
  • Dispatch is serialized by synchronizing requestElevator and setMaintenance on the controller. The cost estimate reads several cars, so without that lock two simultaneous calls could both pick a car that is just entering maintenance. addHallCall returns false for an out-of-service car, which is a second line of defence.
  • Lock ordering: the controller lock is always taken before a car lock, never the reverse, so no deadlock is possible.
Warning

A cost estimate is a snapshot; the car keeps moving after you read it. That is acceptable because the estimate only picks a car, while the car's own LOOK logic decides when to stop. Never let the dispatcher write a car's direction or floor directly.

At higher scale, replace locks with a single-threaded event loop per car: button threads push commands onto a BlockingQueue, and the car thread drains it at the start of each tick. That removes locking from the hot path and makes the car's behaviour easy to replay for debugging.

Extensions

Requirement Change
Capacity / weight limit Add load to Elevator; a full car skips hall calls (car calls still served); the dispatcher adds a penalty for heavily loaded cars
Morning up-peak UpPeakStrategy sends idle cars back to the lobby and prefers cars already at floor 0
Zoning in tall buildings ZonedStrategy maps floor ranges to subsets of cars
Destination dispatch Hall panels accept a destination; the request becomes (from, to) so the dispatcher groups riders going to similar floors
Fire service / emergency New EmergencyState: ignore hall calls, go to the recall floor, open doors
Displays and lanterns Observer: Elevator publishes floor and direction changes; floor displays subscribe
Door obstruction DoorsOpenState resets its dwell counter when a sensor event arrives

Interview Tips

  • Separate the two scheduling questions out loud: "which car" (dispatch strategy) and "which order" (LOOK inside the car).
  • Explain why hall calls carry a direction and why that leads to separate up/down stop sets.
  • Draw the state machine (Idle → Moving → DoorsOpen → Moving or Idle, with Maintenance from anywhere) before writing code.
  • Compare FCFS, SCAN and LOOK briefly; choose LOOK and say why (no wasted travel, no starvation).
  • Use discrete ticks so behaviour is deterministic; mention a real implementation would drive ticks from a scheduler.
  • Volunteer the maintenance case: orphaned hall calls must be re-dispatched or riders wait forever.

References

My notes saved in this browser