LLD: Elevator System¶

Difficulty: Intermediate | Time: 40–50 minutes

1. Problem Statement¶

Design the control system for a bank of elevators in a building. A user on any floor can press up/down to request an elevator; a user inside a car can select a destination floor. The system must assign requests to elevators and move each elevator through its stops efficiently.

2. Requirements¶

Functional (in scope):

• N elevators serving F floors
• External request: floor + direction (up/down)
• Internal request: destination floor, made from inside a car
• Each elevator tracks its current floor, direction, and door state
• A dispatcher assigns external requests to the "best" elevator
• Elevator stops at intermediate floors along its current direction if requested

Explicitly out of scope for v1: express elevators serving only certain floor ranges, weight limits, emergency/fire-service mode, multiple dispatch zones.

3. Entities¶

Elevator, ElevatorState (IDLE/MOVING_UP/MOVING_DOWN/DOORS_OPEN), Request (internal/external), Dispatcher, SchedulingStrategy, Building.

4. Class Design¶

classDiagram
    class Direction {
        <<enumeration>>
        UP
        DOWN
        IDLE
    }

    class ElevatorState {
        <<enumeration>>
        IDLE
        MOVING
        DOORS_OPEN
    }

    class Request {
        <<abstract>>
        +floor: int
    }
    class ExternalRequest {
        +direction: Direction
    }
    class InternalRequest

    class Elevator {
        +id: str
        +current_floor: int
        +direction: Direction
        +state: ElevatorState
        +stops: SortedSet~int~
        +add_stop(floor) void
        +step() void
    }

    class SchedulingStrategy {
        <<interface>>
        +select_elevator(elevators, request)* Elevator
    }
    class NearestCarStrategy
    class SameDirectionStrategy

    class Dispatcher {
        +elevators: List~Elevator~
        +strategy: SchedulingStrategy
        +handle_request(request) void
    }

    class Building {
        +dispatcher: Dispatcher
        +floors: int
    }

    Request <|-- ExternalRequest
    Request <|-- InternalRequest
    Dispatcher o-- Elevator : manages
    Dispatcher --> SchedulingStrategy : uses (injected)
    SchedulingStrategy <|.. NearestCarStrategy
    SchedulingStrategy <|.. SameDirectionStrategy
    Building *-- Dispatcher
    Elevator --> Direction
    Elevator --> ElevatorState

stateDiagram-v2
    [*] --> IDLE
    IDLE --> MOVING_UP : add_stop(floor > current_floor)
    IDLE --> MOVING_DOWN : add_stop(floor < current_floor)
    MOVING_UP --> MOVING_UP : step() [more stops above]
    MOVING_DOWN --> MOVING_DOWN : step() [more stops below]
    MOVING_UP --> DOORS_OPEN : step() [current_floor in stops]
    MOVING_DOWN --> DOORS_OPEN : step() [current_floor in stops]
    MOVING_UP --> MOVING_DOWN : step() [no stop ahead, one behind]
    MOVING_DOWN --> MOVING_UP : step() [no stop ahead, one behind]
    DOORS_OPEN --> MOVING_UP : step() [stops remain, next is above]
    DOORS_OPEN --> MOVING_DOWN : step() [stops remain, next is below]
    DOORS_OPEN --> IDLE : step() [no stops remain]

Why Dispatcher is a separate class from Elevator: an individual Elevator should only know how to move itself and manage its own stop set — it should not know how to compare itself against sibling elevators to decide who "wins" a request. That comparison logic is a different responsibility (SRP) and belongs to the Dispatcher, with the actual comparison algorithm pulled out one level further into SchedulingStrategy.

5. Patterns Applied¶

• Strategy for elevator selection — "assign the best elevator" is inherently going to have multiple competing definitions of "best" (nearest idle car vs. same-direction car already passing the floor vs. load-balancing across cars), so Dispatcher depends on SchedulingStrategy, not a hardcoded comparison.
• State (conceptually, even without a formal State class per state) — Elevator.state drives which transitions are legal; door state, movement, and stop-handling are gated by current state, not scattered if checks on flags.
• Explicitly not Observer for now — a plausible extension (notify a floor display when an elevator arrives) would earn it, but the base problem statement doesn't require it.

6. Core Code¶

from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from enum import Enum, auto
from threading import Lock


class Direction(Enum):
    UP = auto()
    DOWN = auto()
    IDLE = auto()


class ElevatorState(Enum):
    IDLE = auto()
    MOVING = auto()
    DOORS_OPEN = auto()


@dataclass
class ExternalRequest:
    floor: int
    direction: Direction


@dataclass
class InternalRequest:
    floor: int


class Elevator:
    def __init__(self, elevator_id: str, num_floors: int):
        self.id = elevator_id
        self.num_floors = num_floors
        self.current_floor = 0
        self.direction = Direction.IDLE
        self.state = ElevatorState.IDLE
        self._stops: set[int] = set()
        self._lock = Lock()

    def add_stop(self, floor: int) -> None:
        if not 0 <= floor < self.num_floors:
            raise ValueError(f"floor {floor} is outside this building (0..{self.num_floors - 1})")
        with self._lock:
            self._stops.add(floor)
            if self.direction == Direction.IDLE:
                self.direction = Direction.UP if floor > self.current_floor else Direction.DOWN
                self.state = ElevatorState.MOVING

    def step(self) -> None:
        """Advance one floor toward the next stop; called on a timer/event loop."""
        with self._lock:
            if self.state == ElevatorState.DOORS_OPEN:
                # doors close on this tick; movement (if any) happens next tick
                if self._stops:
                    self.state = ElevatorState.MOVING
                else:
                    self.state = ElevatorState.IDLE
                    self.direction = Direction.IDLE
                return

            if not self._stops:
                self.state = ElevatorState.IDLE
                self.direction = Direction.IDLE
                return

            if self.current_floor in self._stops:
                self._stops.discard(self.current_floor)
                self.state = ElevatorState.DOORS_OPEN
                return                          # door handling is a separate step; simplified here

            # reverse if no remaining stop lies ahead in the current direction
            if self.direction == Direction.UP and not any(f > self.current_floor for f in self._stops):
                self.direction = Direction.DOWN
            elif self.direction == Direction.DOWN and not any(f < self.current_floor for f in self._stops):
                self.direction = Direction.UP

            if self.direction == Direction.UP:
                self.current_floor += 1
            elif self.direction == Direction.DOWN:
                self.current_floor -= 1

    def snapshot(self) -> "ElevatorSnapshot":
        """A single locked read of every field the scheduler needs together.

        Taking one lock here — instead of `step()`'s lock plus separate calls
        to `distance_to`/`is_moving_toward` each re-acquiring it — guarantees
        floor, direction, and state all come from the *same* instant, not
        three snapshots interleaved with a concurrently running `step()`.
        """
        with self._lock:
            return ElevatorSnapshot(self.id, self.current_floor, self.direction, self.state)


@dataclass(frozen=True)
class ElevatorSnapshot:
    elevator_id: str
    current_floor: int
    direction: Direction
    state: ElevatorState

    def distance_to(self, floor: int) -> int:
        return abs(self.current_floor - floor)

    def is_moving_toward(self, floor: int, direction: Direction) -> bool:
        if self.direction != direction:
            return False
        if direction == Direction.UP:
            return self.current_floor <= floor
        if direction == Direction.DOWN:
            return self.current_floor >= floor
        return False


class SchedulingStrategy(ABC):
    @abstractmethod
    def select_elevator(self, elevators: list[Elevator], request: ExternalRequest) -> Elevator: ...


class NearestCarStrategy(SchedulingStrategy):
    """Prefer an idle car nearest the request; fall back to a car already headed that way."""

    def select_elevator(self, elevators: list[Elevator], request: ExternalRequest) -> Elevator:
        snapshots = {e.id: e.snapshot() for e in elevators}  # one consistent read per elevator
        candidates = [e for e in elevators if snapshots[e.id].state == ElevatorState.IDLE] or [
            e for e in elevators if snapshots[e.id].is_moving_toward(request.floor, request.direction)
        ] or elevators                            # last resort: everyone's a candidate
        return min(candidates, key=lambda e: snapshots[e.id].distance_to(request.floor))


class Dispatcher:
    def __init__(self, elevators: list[Elevator], strategy: SchedulingStrategy):
        self.elevators = elevators
        self.strategy = strategy                  # injected — see Dependency Inversion

    def handle_external_request(self, request: ExternalRequest) -> Elevator:
        chosen = self.strategy.select_elevator(self.elevators, request)
        chosen.add_stop(request.floor)
        return chosen

    def handle_internal_request(self, elevator: Elevator, request: InternalRequest) -> None:
        elevator.add_stop(request.floor)

7. Edge Cases¶

8. Concurrency¶

Multiple floor-call buttons and multiple in-car destination buttons can fire concurrently across a real system, and multiple Elevator.step() calls (one timer tick per car) may run on separate threads. Two hazards:

1. add_stop racing with step on the same elevator — a stop could be added to _stops in the middle of a step() iterating or mutating that set. Fixed here by wrapping both in the same per-elevator Lock, the same pattern as ParkingSpot.try_occupy in Parking Lot: one lock guards every read and write of _stops and direction together, not just the write.

2. The dispatcher assigning two requests to the same elevator "simultaneously" isn't actually a race the way spot-double-booking was — an elevator can legitimately be assigned multiple stops, that's normal operation. The real hazard is select_elevator reading current_floor/direction/state on multiple elevators while step() threads are concurrently mutating those same fields — a classic read-while-write race that could pick a stale "nearest" elevator, or worse, combine a floor read before a step() tick with a direction read after it. The fix implemented above: Elevator.snapshot() takes _lock once and returns all three fields from that single critical section; distance_to/is_moving_toward then read only the immutable ElevatorSnapshot, never the live elevator, so the strategy can't observe a torn read across two different instants.

9. Extensibility¶

Interview Questions¶

Key Takeaways¶

Previous: Parking Lot | Next: LRU Cache