Design an Elevator System

Design an Elevator System

The Elevator problem is where interviewers separate candidates who can draw a class diagram from candidates who can reason about a genuine scheduling algorithm. The hard part isn't Elevator or Floor — it's the controller's decision procedure: given N elevators, M floors, and a stream of internal and external requests, which elevator answers which request, and in what order does a single elevator serve the requests already assigned to it? This guide builds up to the classic SCAN (elevator algorithm) as the answer, then works through the state machine and concurrency around it.

1. Requirements

Functional requirements

• A building has N elevators serving M floors.
• Each floor has external buttons: UP (except top floor) and DOWN (except ground floor).
• Each elevator cabin has internal buttons: one per destination floor, plus door-open/close and emergency stop.
• The controller assigns an external request to the elevator that can serve it most efficiently.
• Each elevator processes its own queue of requests using a scheduling algorithm that avoids needless direction reversals.
• Elevators respect a maximum capacity (weight/occupant count).
• Doors open/close with a timed delay, and re-open if an obstruction is detected.

Non-functional requirements

• Minimize average wait time (time from external button press to an elevator arriving) and average travel time (time from boarding to arrival).
• Fairness: no request should starve because closer, "cheaper" requests keep cutting in line.
• Concurrency-safe: multiple floor button presses and multiple elevator state transitions happen concurrently; the controller's assignment decision must not race with an elevator's own state update.
• Extensible priority: emergency and maintenance modes should override normal scheduling without a rewrite.

2. Actors & Use Cases

Primary use cases

1. External request — passenger on floor 5 presses UP → controller picks the "best" elevator → that elevator adds floor 5 to its queue.
2. Internal request — passenger boards, presses floor 9 → elevator adds floor 9 to its own queue (no controller involved — the elevator already "owns" this passenger).
3. Serve queued requests — elevator moves in one direction, stopping at every requested floor along the way, then reverses only when no further requests exist in the current direction (SCAN).
4. Emergency stop / capacity exceeded — overrides the current queue: elevator stops immediately or refuses to close doors until weight drops.

3. Class Diagram

4. Core Class Design

Enums and Request

enum Direction { UP, DOWN, IDLE }
enum ElevatorState { IDLE, MOVING_UP, MOVING_DOWN, DOOR_OPEN, OUT_OF_SERVICE }
enum RequestType { INTERNAL, EXTERNAL }
 
final class Request {
    final int sourceFloor;
    final Direction direction;      // direction the passenger wants to travel (external) or IDLE (internal)
    final RequestType type;
    final Integer destinationFloor; // known for internal requests, null for external until boarded
 
    Request(int sourceFloor, Direction direction, RequestType type, Integer destinationFloor) {
        this.sourceFloor = sourceFloor;
        this.direction = direction;
        this.type = type;
        this.destinationFloor = destinationFloor;
    }
}

Elevator — state machine + its own SCAN queue

class Elevator {
    private final int id;
    private final int capacity;
    private volatile int currentFloor;
    private volatile ElevatorState state = ElevatorState.IDLE;
    private volatile Direction direction = Direction.IDLE;
    private volatile int currentLoad = 0;
 
    // TreeSet gives O(log n) insert and O(log n) "next floor in this direction" via ceiling()/floor()
    private final NavigableSet<Integer> upStops = new ConcurrentSkipListSet<>();
    private final NavigableSet<Integer> downStops = new ConcurrentSkipListSet<>();
    private final ElevatorDoor door = new ElevatorDoor();
 
    Elevator(int id, int capacity, int startFloor) {
        this.id = id;
        this.capacity = capacity;
        this.currentFloor = startFloor;
    }
 
    /** Called by the controller (external) or by the cabin panel (internal). */
    synchronized void addStop(int floor) {
        if (floor > currentFloor) upStops.add(floor);
        else if (floor < currentFloor) downStops.add(floor);
        else openDoors(); // already there
        if (direction == Direction.IDLE) {
            direction = floor >= currentFloor ? Direction.UP : Direction.DOWN;
            state = direction == Direction.UP ? ElevatorState.MOVING_UP : ElevatorState.MOVING_DOWN;
        }
    }
 
    /** One tick of simulated movement — see §6 for the full SCAN logic. */
    synchronized void step() {
        if (state == ElevatorState.OUT_OF_SERVICE) return;
 
        if (direction == Direction.UP) {
            if (upStops.contains(currentFloor)) {
                upStops.remove(currentFloor);
                openDoors();
                return;
            }
            Integer next = upStops.ceiling(currentFloor + 1);
            if (next != null) { currentFloor++; return; }
            direction = downStops.isEmpty() ? Direction.IDLE : Direction.DOWN;
            state = direction == Direction.DOWN ? ElevatorState.MOVING_DOWN : ElevatorState.IDLE;
        } else if (direction == Direction.DOWN) {
            if (downStops.contains(currentFloor)) {
                downStops.remove(currentFloor);
                openDoors();
                return;
            }
            Integer next = downStops.floor(currentFloor - 1);
            if (next != null) { currentFloor--; return; }
            direction = upStops.isEmpty() ? Direction.IDLE : Direction.UP;
            state = direction == Direction.UP ? ElevatorState.MOVING_UP : ElevatorState.IDLE;
        }
    }
 
    private void openDoors() {
        state = ElevatorState.DOOR_OPEN;
        door.open();
        // timer-driven close; see ElevatorDoor
    }
 
    void emergencyStop() {
        state = ElevatorState.OUT_OF_SERVICE;
        direction = Direction.IDLE;
    }
 
    int pendingLoad() { return upStops.size() + downStops.size(); }
    int getCurrentFloor() { return currentFloor; }
    Direction getDirection() { return direction; }
    ElevatorState getState() { return state; }
    int getId() { return id; }
}

ElevatorDoor

class ElevatorDoor {
    enum DoorState { OPEN, CLOSED, OPENING, CLOSING }
    private volatile DoorState state = DoorState.CLOSED;
 
    void open() {
        state = DoorState.OPENING;
        // ... animation/timer delay ...
        state = DoorState.OPEN;
        scheduleAutoClose();
    }
 
    void close() {
        if (obstructionDetected()) { open(); return; } // safety re-open, never close on an obstruction
        state = DoorState.CLOSED;
    }
 
    private void scheduleAutoClose() {
        // executor.schedule(this::close, 4, TimeUnit.SECONDS) in a real implementation
    }
 
    private boolean obstructionDetected() { return false; /* sensor input */ }
}

SchedulingStrategy — which elevator answers this call?

interface SchedulingStrategy {
    Optional<Elevator> selectElevator(List<Elevator> elevators, Request request);
}
 
/**
 * Picks the elevator that can reach the request floor with the least extra travel,
 * preferring elevators already moving TOWARD the request in the SAME direction
 * (classic "nearest car, same direction" heuristic used by real elevator banks).
 */
class NearestCarStrategy implements SchedulingStrategy {
    public Optional<Elevator> selectElevator(List<Elevator> elevators, Request request) {
        return elevators.stream()
                .filter(e -> e.getState() != ElevatorState.OUT_OF_SERVICE)
                .min(Comparator.comparingInt(e -> cost(e, request)));
    }
 
    private int cost(Elevator e, Request request) {
        boolean sameDirection = e.getDirection() == request.direction || e.getDirection() == Direction.IDLE;
        boolean movingToward = isMovingToward(e, request.sourceFloor);
        int distance = Math.abs(e.getCurrentFloor() - request.sourceFloor);
 
        if (sameDirection && movingToward) return distance;               // best case
        if (e.getDirection() == Direction.IDLE) return distance;          // idle car, free to redirect
        return distance + 1000;                                          // penalize wrong-direction cars heavily
    }
 
    private boolean isMovingToward(Elevator e, int floor) {
        if (e.getDirection() == Direction.UP) return floor >= e.getCurrentFloor();
        if (e.getDirection() == Direction.DOWN) return floor <= e.getCurrentFloor();
        return true;
    }
}

ElevatorController

class ElevatorController {
    private final List<Elevator> elevators;
    private final SchedulingStrategy strategy;
 
    ElevatorController(List<Elevator> elevators, SchedulingStrategy strategy) {
        this.elevators = elevators;
        this.strategy = strategy;
    }
 
    void handleExternalRequest(Request request) {
        Optional<Elevator> chosen = strategy.selectElevator(elevators, request);
        if (chosen.isEmpty()) throw new NoElevatorAvailableException();
        chosen.get().addStop(request.sourceFloor);
    }
 
    void handleInternalRequest(int elevatorId, int destinationFloor) {
        elevators.stream()
                .filter(e -> e.getId() == elevatorId)
                .findFirst()
                .ifPresent(e -> e.addStop(destinationFloor));
    }
 
    void tick() {
        elevators.forEach(Elevator::step); // driven by a scheduler, e.g. every 500ms
    }
}

5. Design Patterns Applied

6. Key Algorithms, Concurrency & Edge Cases

SCAN / LOOK: why it beats FCFS

FCFS (first-come-first-served) serves requests in arrival order regardless of position — an elevator at floor 1 asked to go to floor 10 might get redirected to floor 2, then floor 9, then floor 3, thrashing direction on every request. Worst-case wait time is unbounded.

SCAN ("elevator algorithm") sweeps in one direction, serving every pending request along the way, and only reverses when no further requests exist ahead in the current direction. LOOK is the practical refinement: reverse as soon as there's nothing further requested in the current direction, rather than sweeping all the way to floor 0/M like pure SCAN does.

The Elevator.step() method in §4 implements exactly this: upStops.ceiling(currentFloor + 1) finds the next stop at or above the current floor in O(log n) via a NavigableSet, and direction only flips to DOWN once upStops is exhausted. This is the interview-critical piece — naming "SCAN/LOOK" without the TreeSet/NavigableSet mechanics behind it is half credit.

Handling simultaneous requests without double-assignment

Two floor buttons pressed in the same tick must not both compute findBestElevator against a stale view and both pick the same "closest idle" car. Two defensible fixes:

1. Serialize assignment — handleExternalRequest runs inside a synchronized block (or single-threaded assignment queue) on the controller, so cost computation and addStop happen atomically per request. Simple, and assignment volume is low relative to elevator movement.
2. Reserve-then-confirm — the controller marks a candidate elevator as "provisionally assigned" before computing cost for the next request, so back-to-back requests in the same tick don't both target the same idle car.

// Simplest correct fix: make the whole assignment decision one atomic operation.
synchronized void handleExternalRequest(Request request) {
    Optional<Elevator> chosen = strategy.selectElevator(elevators, request);
    chosen.ifPresent(e -> e.addStop(request.sourceFloor));
}

Priority overrides: emergency, capacity, maintenance

class PriorityAwareElevator extends Elevator {
    // Emergency stop bypasses the normal queue entirely — see Elevator.emergencyStop().
    // Capacity: cabin panel refuses new internal requests, and the door controller
    // refuses to close, once currentLoad >= capacity.
}

• Capacity exceeded: the door subsystem holds the door open (or re-opens) and rejects further internal requests until weight sensors report room — modeled as a guard in ElevatorDoor.close() and Elevator.addStop(), not as a special elevator state.
• Emergency stop: emergencyStop() transitions straight to OUT_OF_SERVICE, discarding queued stops for that car; the controller's SchedulingStrategy naturally excludes it from elevators.stream().filter(e -> e.getState() != OUT_OF_SERVICE).
• Handicapped priority: modeled as a Request field (priority: NORMAL | ACCESSIBILITY) that NearestCarStrategy factors into cost() — e.g., prefer a car with more available floor space, or hold doors open longer — without inventing a parallel scheduling path.

Other edge cases worth naming

• All elevators busy, request during peak load: the request simply waits in whichever elevator's upStops/downStops it was added to — SCAN guarantees it will eventually be served, bounding worst-case wait by (roughly) one full sweep of the building.
• Elevator taken out of service mid-sweep with pending stops: those stops must be reassigned to another elevator by the controller, not silently dropped.
• Same floor, opposite direction requests: floor 5 UP and floor 5 DOWN are two distinct Requests that may be served by two different elevators — never coalesce them into one.

7. Trade-offs & Extensions

Natural extensions an interviewer may probe:

• Zoning: assign each elevator a preferred floor range during off-peak hours, falling back to bank-wide assignment during peak — a second SchedulingStrategy implementation.
• Destination dispatch (modern office buildings): passengers enter their destination before boarding, letting the controller group passengers heading to the same floors into the same car — changes Request to always carry a destinationFloor, even for what was previously an "external" request.
• Double-deck elevators: two cabins per shaft — would require modeling Elevator as owning two independently-doored cabins sharing one drive mechanism.
• Predictive pre-positioning: send idle elevators to floors with historically high request volume (e.g., ground floor at 9am) — an additional background strategy operating on idle cars only.

Interview Questions

• Walk through why SCAN/LOOK is preferred over FCFS for elevator scheduling, with a concrete example of FCFS thrashing direction.
• Why does NearestCarStrategy penalize elevators moving in the wrong direction rather than simply excluding them?
• What data structure backs upStops/downStops, and why does it need to support ceiling()/floor() specifically?
• How do you prevent two external requests arriving in the same instant from both being assigned to the same idle elevator?
• Where does capacity-exceeded logic live, and why is it modeled as a door-close guard rather than a new ElevatorState?
• How would "destination dispatch" (entering your floor before boarding) change the Request model and the controller's assignment logic?
• If a maintenance operator takes an elevator out of service mid-sweep, what has to happen to its pending stops?