vishal maurya

LLD Series: Elevator System (LLD)

Overview

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

1. Problem statement and how it is asked

"Design an elevator system for a building with N floors and M elevators. Users press hall buttons (floor + direction) and cabin buttons (destination). Decide which elevator serves a request, and how each elevator moves." Often phrased as "design the controller / scheduler" and asked to "make it easy to swap scheduling algorithms". Classic at Amex, PayU, Visa machine-coding rounds (also Uber/Flipkart style). Evaluators look for: State pattern, Strategy for dispatch, clean separation of controller vs. car, and thread safety.

2. Requirements clarification

Functional

  • M elevators, floors 0..N. Hall call = (floor, UP/DOWN); cabin call = destination floor.
  • Dispatcher assigns a hall call to one elevator; elevator serves stops along its direction (SCAN/LOOK), reverses when nothing ahead.
  • Door open on arrival at a stop. Non-functional: concurrent requests from many floors; pluggable dispatch algorithm; deterministic/testable (tick-driven simulation). Assumptions: unlimited capacity (no weight), instant door open/close, one tick = one floor of travel, no fire/maintenance mode. Out of scope: UI, door sensors, weight limits, destination-dispatch groups (mentioned in follow-ups), express/zoned elevators.

3. Entities and class diagram

+---------------------+ 1      * +--------------------------+
| ElevatorController  |--------->|        Elevator          |
|---------------------|          |--------------------------|
| strategy            |          | id, currentFloor         |
| requestElevator()   |          | TreeSet<Integer> stops   |
| selectFloor()       |          | ElevatorState state      |
| tick()              |          | addStop() / step()       |
+----------+----------+          +------------+-------------+
           | uses                              | has-a (State pattern)
           v                                   v
 <<interface>> DispatchStrategy       <<interface>> ElevatorState
 select(elevators,floor,dir)          step(Elevator), direction()
     ^            ^                      ^        ^         ^
     |            |                      |        |         |
NearestCar   RoundRobin             IdleState MovingUp  MovingDown
 Strategy     Strategy                        State      State

Enum: Direction {UP, DOWN, IDLE}.

4. Design patterns and why

PatternWhereWhy / alternative rejected
StateIdle / MovingUp / MovingDownReplaces if (direction==UP) ... else ... branching in step(); each state owns its transition rules. Rejected: enum + switch (grows with DoorOpen, Maintenance, EmergencyStop states and violates OCP).
StrategyDispatchStrategyAlgorithm swappable at runtime (nearest car, round robin, least loaded, zoning). Rejected: hard-coded in controller.
Facade/ControllerElevatorControllerSingle entry point for the outside world.
(Mention) Observerdoor/arrival eventsCould publish arrival events for displays; not needed for core.

Scheduling inside a car: LOOK/SCAN via a sorted TreeSet (serve all stops in current direction, then reverse) - better than FCFS (zig-zag, starvation of distant but convenient stops) and SSTF (starves far floors).

5. Code

All files are in the default package. Compiled with javac *.java, run with java Main.

Direction.java

public enum Direction { UP, DOWN, IDLE }

ElevatorState.java

/** State pattern: behaviour of one simulation tick depends on the current state. */
public interface ElevatorState {
    void step(Elevator elevator);   // called with elevator's monitor held
    Direction direction();
}

IdleState.java

public class IdleState implements ElevatorState {
    public void step(Elevator e) {
        if (e.stops().isEmpty()) return;
        int cur = e.getCurrentFloor();
        if (e.stops().contains(cur)) { e.arrive(); return; }
        Integer up = e.stops().ceiling(cur), down = e.stops().floor(cur);
        boolean goUp = down == null || (up != null && up - cur <= cur - down);
        e.setState(goUp ? new MovingUpState() : new MovingDownState());
    }
    public Direction direction() { return Direction.IDLE; }
}

MovingUpState.java

public class MovingUpState implements ElevatorState {
    public void step(Elevator e) {
        if (e.stops().contains(e.getCurrentFloor())) { e.arrive(); return; }
        if (e.stops().ceiling(e.getCurrentFloor()) == null) {      // nothing above: reverse or idle
            e.setState(e.stops().isEmpty() ? new IdleState() : new MovingDownState());
            return;
        }
        e.moveTo(e.getCurrentFloor() + 1);
    }
    public Direction direction() { return Direction.UP; }
}

MovingDownState.java

public class MovingDownState implements ElevatorState {
    public void step(Elevator e) {
        if (e.stops().contains(e.getCurrentFloor())) { e.arrive(); return; }
        if (e.stops().floor(e.getCurrentFloor()) == null) {
            e.setState(e.stops().isEmpty() ? new IdleState() : new MovingUpState());
            return;
        }
        e.moveTo(e.getCurrentFloor() - 1);
    }
    public Direction direction() { return Direction.DOWN; }
}

Elevator.java

Lock granularity: one monitor per elevator. A hall call touches exactly one car, so cars never contend with each other; step() and addStop() on the same car serialize so the TreeSet is never mutated mid-iteration.

import java.util.TreeSet;

/** One car. All mutable state guarded by this object's monitor (per-elevator lock granularity). */
public class Elevator {
    private final int id, minFloor, maxFloor;
    private int currentFloor;
    private ElevatorState state = new IdleState();
    private final TreeSet<Integer> stops = new TreeSet<>();   // sorted => SCAN/LOOK in O(log n)

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

    public synchronized void addStop(int floor) {
        if (floor < minFloor || floor > maxFloor) throw new IllegalArgumentException("Bad floor " + floor);
        stops.add(floor);
    }
    public synchronized void step() { state.step(this); }

    // ---- used by states (called under the monitor) ----
    TreeSet<Integer> stops() { return stops; }
    void setState(ElevatorState s) { this.state = s; }
    void moveTo(int floor) { this.currentFloor = floor; }
    void arrive() {
        stops.remove(currentFloor);
        System.out.println("  E" + id + " DOOR OPEN at floor " + currentFloor);
    }

    // ---- read-only views for strategies / logging ----
    public int getId() { return id; }
    public synchronized int getCurrentFloor() { return currentFloor; }
    public synchronized Direction getDirection() { return state.direction(); }
    public synchronized int pendingStops() { return stops.size(); }
    public synchronized String describe() {
        return "E" + id + "[floor=" + currentFloor + ", " + state.direction() + ", stops=" + stops + "]";
    }
}

DispatchStrategy.java

import java.util.List;

/** Strategy: which elevator serves a hall call. */
public interface DispatchStrategy {
    Elevator select(List<Elevator> elevators, int floor, Direction requested);
}

NearestCarStrategy.java

import java.util.*;

/** Cost = distance, plus penalty if the car is moving away / opposite direction, plus load tie-break. */
public class NearestCarStrategy implements DispatchStrategy {
    public Elevator select(List<Elevator> elevators, int floor, Direction requested) {
        return elevators.stream()
            .min(Comparator.comparingInt((Elevator e) -> cost(e, floor, requested)).thenComparingInt(Elevator::getId))
            .orElseThrow(() -> new IllegalStateException("No elevators"));
    }
    private int cost(Elevator e, int floor, Direction req) {
        int cur = e.getCurrentFloor(), dist = Math.abs(cur - floor);
        Direction d = e.getDirection();
        int penalty;
        if (d == Direction.IDLE) penalty = 0;
        else if (d == Direction.UP && floor >= cur && req != Direction.DOWN) penalty = 0;   // on its way
        else if (d == Direction.DOWN && floor <= cur && req != Direction.UP) penalty = 0;
        else penalty = 20;                                                                   // must finish sweep first
        return dist + penalty + e.pendingStops();
    }
}

RoundRobinStrategy.java

import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

public class RoundRobinStrategy implements DispatchStrategy {
    private final AtomicInteger next = new AtomicInteger();
    public Elevator select(List<Elevator> elevators, int floor, Direction requested) {
        return elevators.get(Math.floorMod(next.getAndIncrement(), elevators.size()));
    }
}

ElevatorController.java

import java.util.List;

public class ElevatorController {
    private final List<Elevator> elevators;
    private volatile DispatchStrategy strategy;

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

    /** Hall button pressed outside. */
    public Elevator requestElevator(int floor, Direction dir) {
        Elevator e = strategy.select(elevators, floor, dir);
        e.addStop(floor);
        System.out.println("Hall call floor " + floor + " " + dir + " -> E" + e.getId());
        return e;
    }
    /** Cabin button pressed inside. */
    public void selectFloor(Elevator e, int dest) {
        e.addStop(dest);
        System.out.println("Cabin E" + e.getId() + " selects floor " + dest);
    }
    /** One simulation tick; in production a scheduled executor per car. */
    public void tick() { elevators.forEach(Elevator::step); }
    public void printStatus(String label) {
        StringBuilder sb = new StringBuilder(label + ": ");
        elevators.forEach(e -> sb.append(e.describe()).append("  "));
        System.out.println(sb.toString().trim());
    }
}

Main.java (demo)

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        List<Elevator> cars = List.of(new Elevator(1, 0, 10), new Elevator(2, 0, 10), new Elevator(3, 0, 10));
        ElevatorController c = new ElevatorController(cars, new NearestCarStrategy());

        Elevator a = c.requestElevator(3, Direction.UP);       // all idle at 0 -> tie -> E1
        Elevator b = c.requestElevator(8, Direction.DOWN);     // E1 has a stop (load), E2 idle -> E2
        for (int t = 1; t <= 3; t++) { System.out.println("tick " + t); c.tick(); }
        c.printStatus("after 3 ticks");
        System.out.println("tick 4"); c.tick();                // E1 arrives at 3, door opens
        c.selectFloor(a, 7);                                   // passenger boards E1, wants 7
        c.requestElevator(5, Direction.UP);                    // E1 at 3 moving up/idle -> picks up en route
        for (int t = 5; t <= 14; t++) { System.out.println("tick " + t); c.tick(); }
        c.printStatus("final");

        System.out.println("-- concurrency: 3 threads fire hall calls while ticking --");
        Thread[] th = new Thread[3];
        for (int i = 0; i < 3; i++) { final int f = i * 3 + 1;
            th[i] = new Thread(() -> c.requestElevator(f, Direction.UP)); th[i].start(); }
        for (Thread t : th) t.join();
        int total = cars.stream().mapToInt(Elevator::pendingStops).sum();
        System.out.println("total pending stops registered = " + total);
    }
}

Actual output (compiled with javac, run with java)

Hall call floor 3 UP -> E1
Hall call floor 8 DOWN -> E2
tick 1
tick 2
tick 3
after 3 ticks: E1[floor=2, UP, stops=[3]]  E2[floor=2, UP, stops=[8]]  E3[floor=0, IDLE, stops=[]]
tick 4
Cabin E1 selects floor 7
Hall call floor 5 UP -> E2
tick 5
  E1 DOOR OPEN at floor 3
tick 6
tick 7
  E2 DOOR OPEN at floor 5
tick 8
tick 9
tick 10
  E1 DOOR OPEN at floor 7
tick 11
  E2 DOOR OPEN at floor 8
tick 12
tick 13
tick 14
final: E1[floor=7, IDLE, stops=[]]  E2[floor=8, IDLE, stops=[]]  E3[floor=0, IDLE, stops=[]]
-- concurrency: 3 threads fire hall calls while ticking --
Hall call floor 1 UP -> E3
Hall call floor 7 UP -> E1
Hall call floor 4 UP -> E1
total pending stops registered = 3

Reading the output: E1 (all idle, tie broken by lowest id) takes floor 3; E2 takes 8 because E1 now carries load. The hall call at 5 goes to E2, which is mid-sweep upward at floor 4 and passes floor 5 on its way to 8, so it stops there (LOOK in action) instead of E1, which is idle at 3 with a pending cabin stop. In the concurrent section the exact assignment depends on thread timing, but the total of 3 registered stops is invariant.

6. Key flows

Hall call (5, UP)
User -> Controller.requestElevator(5,UP)
          -> strategy.select(elevators,5,UP)   // reads each car's floor/direction
          <- Elevator E2
          -> E2.addStop(5)  [synchronized]
Tick loop:  Controller.tick() -> for each car: car.step() [synchronized]
              state.step(car):  MovingUp -> moveTo(floor+1) ... stops.contains(floor)? -> arrive() -> door open
              no stop ahead & stops non-empty -> setState(MovingDown); empty -> Idle
Cabin: User -> Controller.selectFloor(E1,7) -> E1.addStop(7)

7. Extensibility

  • New algorithm (zoning, destination dispatch, energy saving): new DispatchStrategy, controller.setStrategy(...); no existing change.
  • New state (DoorOpen with dwell time, Maintenance, Emergency): new ElevatorState class; only transition points that enter it change.
  • Capacity: add canAccept() to Elevator and filter inside strategy.
  • Peak-hour modes: PeakStrategy that parks idle cars at lobby (decorator over strategy).

8. Concurrency and edge cases

  • Per-elevator monitor; strategy reads (getCurrentFloor, getDirection) are individually synchronized, so the snapshot across cars is approximately consistent. This is acceptable: a slightly stale choice only affects efficiency, not correctness, since the chosen car's addStop is atomic. Rejected: global lock (serializes all floors and ticks).
  • Production: one scheduled thread per car (or a single scheduler thread) calls step(); request threads only call addStop.
  • Edge cases: request for current floor (Idle handles by arrive()); duplicate stops (Set dedupes); invalid floor (exception); request while car reverses; all cars busy (still assigned - queued stops); direction-aware pickup (hall call UP shouldn't be served by a car going DOWN past it - penalty in cost, though a full implementation keeps separate up/down sets per car).
  • Known simplification: stops are direction-agnostic; a passenger wanting DOWN picked up by an UP car would be on a wrong-direction ride. Mention it and say you would split into upStops/downStops.

9. Follow-ups and model answers

  • Why State pattern over enum? Behaviour differs per state and states grow; each class tests independently.
  • How to prevent starvation? LOOK serves every stop within one sweep; add aging if strategy keeps favouring nearby cars.
  • Destination dispatch (user enters floor at lobby)? Strategy receives (from,to) and groups passengers with the same direction/zone; Request object instead of int.
  • Distribute / persist? A building is physically local; run the controller on an embedded node, persist pending stops in a WAL/local DB for restart recovery; for multi-building fleets, a central service sends requests via a queue per building.
  • Fault tolerance? Health state in Elevator; strategy filters out OUT_OF_SERVICE; redistribute its stops via controller.
  • Complexity: dispatch O(M); addStop O(log S); step O(log S); S = pending stops.
  • Unit testing? Tick-driven simulation, no sleeps; inject strategy.

10. Common mistakes and rubric

Red flags: god class Elevator with giant switch; Thread.sleep in business logic; global synchronized on controller; no abstraction for the algorithm; ignoring direction; unbounded LinkedList queue FCFS with no justification; returning internal collections. Rubric (10 pts): requirements/clarifying questions 1; entity model 2; State pattern 2; Strategy dispatch 2; thread safety reasoning 1; runnable demo/testing 1; extensibility discussion 1.