Low Level Design: Elevator System (Scheduling Algorithms + Code)

The elevator question looks like a parking lot problem with moving parts, and that is exactly why interviewers like it. Parking lot tests whether you can model nouns. Elevator tests whether you can model time: a system whose state changes every second, whose requests arrive while it is in motion, and whose correctness depends on an algorithm, not just a class diagram.

Candidates usually fail it in one of three ways: they treat every button press as "go to floor N" and lose the direction, they write an if-else forest instead of states, or they cannot explain how their scheduler behaves when a request arrives mid-journey. This guide fixes all three, ending in a deterministic Java simulation you can dry-run on a whiteboard. If you are new to LLD rounds in general, skim the LLD interview guide first.

Clarifying Requirements for an Elevator System

Open with questions that change the design. A building with one car is a scheduling problem; a building with eight cars is a dispatching problem layered on top.

Functional requirements

1. A person on a floor presses UP or DOWN; some car arrives, opens doors and leaves in that direction.
2. A person inside presses a destination; that car stops there.
3. Cars serve stops in an efficient, fair order (no starvation).
4. Cars can be put into maintenance and are then excluded from dispatch.
5. The system reports each car's floor, direction and state (for floor displays).

Non-functional requirements

Thread safety for buttons pressed concurrently, extensibility for new dispatch policies (zoning, energy saving), and testability, which is why the simulation is tick-driven rather than Thread.sleep-driven. Tick-driven code produces the same output every run, so you can assert on it.

Hall Calls vs Car Calls: The Distinction That Matters

A hall call is made outside the elevator: "I am on floor 6 and I want to go DOWN". It belongs to the building, not to any car, until the dispatcher assigns it. A car call is made inside: "take me to floor 2". It belongs to exactly one car and cannot be reassigned.

Why this matters: if a car is on floor 3 going up to 9 and someone on floor 6 has pressed DOWN, a correct elevator does not stop at 6 on the way up. That passenger wants to go down; stopping would either make them ride up to 9 first or make them wait at an open door. A model where hall calls are just "floor numbers" cannot express this. So each car keeps two sorted sets:

• upStops: floors where the car must stop while travelling up (UP hall calls, and car calls above the current floor).
• downStops: floors where it must stop while travelling down (DOWN hall calls, and car calls below).

A TreeSet<Integer> gives O(log n) insert and O(log n) "next stop above/below" queries through ceiling, floor, headSet and tailSet, which is exactly what the scheduler needs.

Elevator Scheduling Algorithms: FCFS, SSTF, SCAN and LOOK

Elevator scheduling borrows directly from disk-arm scheduling in operating systems; SCAN is literally nicknamed "the elevator algorithm". If you have studied it in the OS interview questions context, the trade-offs are the same.

A worked comparison

One car is on floor 5 in a building with floors 0–10. Pending stops, in the order they were requested: 2, 9, 7, 1, 8, 3. Count floors travelled:

On this static batch SSTF and LOOK tie at 12, and a candidate who stops here might conclude SSTF is fine. The difference shows up only when requests keep arriving, which is what real buildings do.

Why SSTF starves passengers

Put the car at floor 5, a passenger waiting at floor 0, and a stream of people on floors 4 and 6 pressing buttons every few seconds (a busy office floor around lunch). SSTF always prefers 4 or 6 because they are 1 floor away versus 5. The person on floor 0 can wait indefinitely. LOOK fixes this structurally: once the car commits to going down, it keeps going down until there is nothing below, so the ground floor is served within one sweep. The worst-case wait is bounded by roughly two full traversals of the shaft.

Why SCAN wastes travel

SCAN goes to floor 10 even though nobody needs floor 10. In a 40-floor tower that is a lot of energy and wait time. LOOK keeps SCAN's fairness and drops the useless leg. Implement LOOK, and mention SCAN only to show you know where it comes from.

The Dispatcher: Which Elevator Answers a Hall Call?

With multiple cars, each hall call is assigned to exactly one car. The simplest acceptable policy is "nearest car", but nearest by distance is wrong when the nearest car is moving away. A better policy estimates time to arrival:

Worked example. Floors 0–10. Car A is at floor 2 going UP with a stop at 8. Car B is at floor 7, idle. A hall call arrives: floor 5, UP.

• Car A: moving up, floor 5 is ahead and the call is UP, so cost = 3 + (1 stop × 2) = 5.
• Car B: idle, cost = |7 − 5| = 2.

B wins. Now change the call to floor 5, DOWN: A would have to go to 8 and come back, cost = 6 + 3 + 2 = 11; B is still 2. Now move B: it is at floor 9 going UP to a stop at 10. For the DOWN call at 5, B must reach 10 and come back: 1 + 5 + 2 = 8, which still beats A at 11. These numbers are heuristics, and that is fine to say in the interview: production controllers tune these weights against simulated traffic.

Because the policy will change (zoning for tall buildings, "park idle cars at the lobby" in the morning rush, energy-saving modes at night), the dispatcher is a Strategy. You inject LeastCostDispatcher today and ZonedDispatcher tomorrow.

State Pattern: Modelling the Elevator Lifecycle

An elevator's response to the same event depends on what it is doing. A tick while moving means "advance one floor and check whether to stop". A tick while doors open means "count down the dwell timer". A tick in maintenance means nothing. That is the definition of the State pattern: behaviour varies with internal state, so each state becomes a class with the same interface.

Without the pattern you get a method like if (doorsOpen) {...} else if (moving && direction == UP) {...} else if (maintenance) ... that grows with every new mode. With it, adding fire-service mode means adding one class and the transitions into it. The vending machine LLD is the purest State pattern exercise if you want more practice.

Elevator System Class Design

Full Java Code for the Elevator System

Single file, Java 17+, run with java ElevatorDemo.java. The simulation advances one floor per tick and holds doors open for two ticks.

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

public class ElevatorDemo {

    enum Direction { UP, DOWN, NONE }

    sealed interface Request permits HallCall, CarCall { }
    record HallCall(int floor, Direction direction) implements Request { }
    record CarCall(int elevatorId, int floor) implements Request { }

    // ===================== State pattern =====================
    interface ElevatorState {
        void tick(Elevator e);
        String name();
    }

    static final class IdleState implements ElevatorState {
        static final IdleState INSTANCE = new IdleState();
        public void tick(Elevator e) {
            Direction d = e.chooseDirection();
            if (e.takeStopAtCurrentFloor(d)) {      // someone is waiting right here
                e.openDoors();
                return;
            }
            e.setDirection(d);
            if (d != Direction.NONE) {
                e.setState(MovingState.INSTANCE);
                MovingState.INSTANCE.tick(e);         // start moving this tick
            }
        }
        public String name() { return "IDLE"; }
    }

    static final class MovingState implements ElevatorState {
        static final MovingState INSTANCE = new MovingState();
        public void tick(Elevator e) {
            if (!e.hasWorkInDirection()) {            // defensive: nothing ahead any more
                e.setState(IdleState.INSTANCE);
                return;
            }
            e.moveOneFloor();
            if (e.shouldStopHere()) {
                e.serveCurrentFloor();
                e.openDoors();
            }
        }
        public String name() { return "MOVING"; }
    }

    static final class DoorsOpenState implements ElevatorState {
        static final DoorsOpenState INSTANCE = new DoorsOpenState();
        public void tick(Elevator e) {
            if (e.decrementDoorTimer() == 0) e.setState(IdleState.INSTANCE);
        }
        public String name() { return "DOORS_OPEN"; }
    }

    static final class MaintenanceState implements ElevatorState {
        static final MaintenanceState INSTANCE = new MaintenanceState();
        public void tick(Elevator e) { /* ignores everything until resumed */ }
        public String name() { return "MAINTENANCE"; }
    }

    // ===================== Elevator (State context) =====================
    static final class Elevator {
        static final int DOOR_TICKS = 2;

        private final int id;
        private int currentFloor;
        private Direction direction = Direction.NONE;
        private ElevatorState state = IdleState.INSTANCE;
        private int doorTicksLeft;
        private final TreeSet<Integer> upStops = new TreeSet<>();
        private final TreeSet<Integer> downStops = new TreeSet<>();

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

        int id() { return id; }
        void tick() { state.tick(this); }
        void setState(ElevatorState s) { state = s; }
        void setDirection(Direction d) { direction = d; }

        // ---- requests ----
        void addHallCall(int floor, Direction dir) {
            (dir == Direction.UP ? upStops : downStops).add(floor);
        }

        void addCarCall(int floor) {
            if (floor > currentFloor) upStops.add(floor);
            else if (floor < currentFloor) downStops.add(floor);
            else if (state == MovingState.INSTANCE) {
                // just passing this floor: serve it on the way back
                (direction == Direction.UP ? downStops : upStops).add(floor);
            } else if (state != MaintenanceState.INSTANCE) {
                openDoors();                          // already here: (re)open
            }
        }

        // ---- LOOK scheduling ----
        boolean hasWorkAbove() {
            return !upStops.tailSet(currentFloor, false).isEmpty()
                || !downStops.tailSet(currentFloor, false).isEmpty();
        }

        boolean hasWorkBelow() {
            return !upStops.headSet(currentFloor, false).isEmpty()
                || !downStops.headSet(currentFloor, false).isEmpty();
        }

        boolean hasWorkInDirection() {
            return direction == Direction.UP ? hasWorkAbove()
                 : direction == Direction.DOWN ? hasWorkBelow() : false;
        }

        /** Keep going while there is work ahead; otherwise reverse; otherwise rest. */
        Direction chooseDirection() {
            if (direction != Direction.DOWN && hasWorkAbove()) return Direction.UP;
            if (direction != Direction.UP && hasWorkBelow()) return Direction.DOWN;
            if (hasWorkAbove()) return Direction.UP;
            if (hasWorkBelow()) return Direction.DOWN;
            return Direction.NONE;
        }

        boolean takeStopAtCurrentFloor(Direction d) {
            return switch (d) {
                case UP -> upStops.remove(currentFloor);
                case DOWN -> downStops.remove(currentFloor);
                case NONE -> upStops.remove(currentFloor) | downStops.remove(currentFloor);
            };
        }

        void moveOneFloor() {
            currentFloor += (direction == Direction.UP) ? 1 : -1;
        }

        boolean shouldStopHere() {
            if (direction == Direction.UP) {
                // normal stop, or turnaround at the highest DOWN request
                return upStops.contains(currentFloor)
                    || (downStops.contains(currentFloor) && !hasWorkAbove());
            }
            return downStops.contains(currentFloor)
                || (upStops.contains(currentFloor) && !hasWorkBelow());
        }

        void serveCurrentFloor() {
            boolean removed = (direction == Direction.UP)
                    ? upStops.remove(currentFloor)
                    : downStops.remove(currentFloor);
            if (!removed) {                           // turnaround stop
                upStops.remove(currentFloor);
                downStops.remove(currentFloor);
            }
        }

        void openDoors() {
            doorTicksLeft = DOOR_TICKS;
            state = DoorsOpenState.INSTANCE;
        }

        int decrementDoorTimer() { return --doorTicksLeft; }

        boolean enterMaintenance() {
            if (state != IdleState.INSTANCE || !upStops.isEmpty() || !downStops.isEmpty()) return false;
            state = MaintenanceState.INSTANCE;
            direction = Direction.NONE;
            return true;
        }

        void exitMaintenance() {
            if (state == MaintenanceState.INSTANCE) state = IdleState.INSTANCE;
        }

        // ---- cost estimate used by the dispatcher ----
        int estimateCost(int floor, Direction requested) {
            if (state == MaintenanceState.INSTANCE) return Integer.MAX_VALUE;
            int penalty = (upStops.size() + downStops.size()) * DOOR_TICKS;
            if (direction == Direction.NONE) return Math.abs(currentFloor - floor) + penalty;
            boolean ahead = direction == Direction.UP ? floor >= currentFloor : floor <= currentFloor;
            if (ahead && requested == direction) return Math.abs(floor - currentFloor) + penalty;
            int turn = direction == Direction.UP ? highestStop() : lowestStop();
            return Math.abs(turn - currentFloor) + Math.abs(turn - floor) + penalty;
        }

        private int highestStop() {
            int h = currentFloor;
            if (!upStops.isEmpty()) h = Math.max(h, upStops.last());
            if (!downStops.isEmpty()) h = Math.max(h, downStops.last());
            return h;
        }

        private int lowestStop() {
            int l = currentFloor;
            if (!upStops.isEmpty()) l = Math.min(l, upStops.first());
            if (!downStops.isEmpty()) l = Math.min(l, downStops.first());
            return l;
        }

        @Override public String toString() {
            return "E" + id + "@" + currentFloor + " " + direction + " " + state.name();
        }
    }

    // ===================== Dispatch strategy =====================
    interface DispatchStrategy {
        Elevator select(List<Elevator> elevators, HallCall call);
    }

    static final class LeastCostDispatcher implements DispatchStrategy {
        public Elevator select(List<Elevator> elevators, HallCall call) {
            return Collections.min(elevators,
                Comparator.comparingInt((Elevator e) -> e.estimateCost(call.floor(), call.direction()))
                          .thenComparingInt(Elevator::id));
        }
    }

    // ===================== Controller (single writer) =====================
    static final class ElevatorSystem {
        private final List<Elevator> elevators;
        private final DispatchStrategy dispatcher;
        private final Queue<Request> inbox = new ConcurrentLinkedQueue<>();
        private int time;

        ElevatorSystem(List<Elevator> elevators, DispatchStrategy dispatcher) {
            this.elevators = List.copyOf(elevators);
            this.dispatcher = dispatcher;
        }

        /** Safe to call from any thread (button handlers). */
        void submit(Request r) { inbox.add(r); }

        /** Called by exactly one controller thread. */
        void tick() {
            Request r;
            while ((r = inbox.poll()) != null) dispatch(r);
            for (Elevator e : elevators) e.tick();
            time++;
            System.out.println("t=" + time + "  " + elevators);
        }

        private void dispatch(Request r) {
            if (r instanceof HallCall h) {
                Elevator chosen = dispatcher.select(elevators, h);
                chosen.addHallCall(h.floor(), h.direction());
                System.out.println("  " + h + " assigned to E" + chosen.id());
            } else if (r instanceof CarCall c) {
                elevators.get(c.elevatorId()).addCarCall(c.floor());
            }
        }
    }

    public static void main(String[] args) {
        ElevatorSystem system = new ElevatorSystem(
            List.of(new Elevator(0, 0), new Elevator(1, 10)), new LeastCostDispatcher());

        system.submit(new HallCall(3, Direction.UP));
        system.submit(new HallCall(8, Direction.DOWN));
        for (int i = 0; i < 3; i++) system.tick();

        system.submit(new CarCall(0, 7));   // passenger who boarded E0 at 3
        system.submit(new CarCall(1, 0));   // passenger who boarded E1 at 8
        for (int i = 0; i < 12; i++) system.tick();
    }
}

Design notes on the code

• States are stateless singletons. All data lives on the Elevator; states only hold behaviour, so one instance can serve every car. That is a common and legitimate State pattern variant.
• The turnaround rule lives in shouldStopHere: going up, stop at a DOWN request only if there is no work above it.
• Car calls on the current floor while moving are queued for the return sweep instead of slamming on the brakes.
• Ties in the dispatcher are broken by id, so output is deterministic.

Tick-by-Tick Dry Run

Two cars, floors 0–10. E0 starts at 0, E1 at 10. Before tick 1, a person on floor 3 presses UP and a person on floor 8 presses DOWN.

Dispatch at tick 1. HallCall(3, UP): E0 is idle, cost 3; E1 is idle, cost 7, so E0. HallCall(8, DOWN): E0 is still idle (direction updates during its tick), cost 8 + 1 pending stop × 2 = 10; E1 cost 2, so E1.

Two things to call out while dry-running. First, at tick 4 the car call to 7 arrives while E0's doors are still open at floor 3; because 7 > 3 it lands in upStops, and LOOK continues upward. Second, an idle car keeps its last direction until its next idle tick, which is why E0 shows "UP IDLE" at tick 11 and "NONE IDLE" at tick 12. If the interviewer finds that odd, reset direction when doors close; it is a one-line change.

Concurrency: Many Buttons, One Controller

The tempting approach is to make Elevator methods synchronized and let button threads call addCarCall directly. It works, but the dispatcher then reads several cars' state while each might be changing, so the cost estimates race, and you start reasoning about lock ordering across cars.

The cleaner design is single-writer: every external event becomes an immutable Request pushed onto a ConcurrentLinkedQueue. One controller thread owns all elevator state, drains the queue at the start of each tick, dispatches, then advances every car. No locks in the scheduling logic, no torn reads, and the same input sequence always produces the same output. In production you drive the tick with a scheduler:

ScheduledExecutorService controller = Executors.newSingleThreadScheduledExecutor();
controller.scheduleAtFixedRate(system::tick, 0, 1, TimeUnit.SECONDS);

// button handler threads, hardware callbacks, the mobile app, etc.
system.submit(new HallCall(6, Direction.DOWN));

This is the same idea behind event loops and actor systems, and naming it shows maturity. If the interviewer wants a lock-based answer anyway, use one ReentrantLock per car and always acquire them in id order inside the dispatcher to avoid deadlock. The Java concurrency interview guide covers lock ordering and executors in more depth.

Extensions Interviewers Ask

Capacity and overload

Track current load (passenger count or kilograms). When full, the car keeps serving car calls but skips hall calls; the dispatcher's cost for a full car becomes infinite for new hall calls, and the hall call is reassigned. That requires remembering which stops are hall calls, so store hall calls in a separate map from floor to direction instead of mixing them into the stop sets.

Re-dispatching on maintenance or breakdown

With hall calls tracked separately, putting a car into maintenance can return its unserved hall calls to the system inbox for reassignment. Car calls cannot be moved; passengers in a failing car are an emergency-mode concern.

Fire-service mode

A new FireServiceState: cancel all calls, go to the lobby without stopping, open doors, then respond only to car calls from a firefighter key. Because of the State pattern, this is additive.

Destination dispatch

Many modern towers replace up/down buttons with a keypad in the lobby: you enter your destination and the system tells you which car to take. Dispatching becomes a grouping problem (put people going to nearby floors in the same car). Your Request becomes DestinationCall(from, to) and the dispatcher becomes a different Strategy; the car's LOOK logic is unchanged.

Zoning and traffic modes

For tall buildings: low-rise cars serve 0–20, high-rise cars 0 and 21–40. Morning up-peak mode parks idle cars at the lobby; evening down-peak mode parks them at upper floors. These are dispatcher strategies plus an "idle parking" policy, and can be switched at runtime by time of day.

Observer for displays

Floor displays and the lobby panel subscribe to car events (floor changed, doors opened). The controller publishes after each tick. Keeping displays out of the Elevator class preserves single responsibility, a point covered in the SOLID principles guide.

How to Present the Elevator Design in an Interview

1. Requirements (5 min). Confirm hall calls have a direction, number of cars, and that you will simulate in ticks.
2. Scheduling choice (5 min). Compare FCFS, SSTF and LOOK in two sentences each; pick LOOK and explain starvation.
3. States and classes (5 min). Draw the state diagram, name the Strategy for dispatch.
4. Code (20–25 min). Elevator with two TreeSets, the four states, the dispatcher, the controller loop.
5. Dry run and follow-ups (5–10 min). Walk one scenario including a mid-journey request; then concurrency and one extension.

What separates strong answers

• They handle the turnaround case (highest request is a DOWN call) without being prompted.
• They explain why LOOK over SSTF, with the starvation argument, not just "LOOK is standard".
• They make the simulation deterministic and say why that matters for tests.
• They keep dispatching out of the Elevator class: a car should not know about other cars.

Red flags interviewers note

• A single Queue<Integer> of floors served FIFO.
• Hall calls with no direction.
• One thread per elevator with Thread.sleep and shared mutable state.
• No answer to "what happens if someone presses a button while the car is moving?"

Once you can build this, related machine coding problems feel familiar: the parking lot exercises concurrency on shared resources, and the general approach for timed rounds is in the machine coding round guide. For pattern vocabulary, keep the top 10 design patterns handy.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.