Design a multi-elevator dispatcher

01The design, in the six-step framework

1. Requirements and use cases

A building has N floors and M cars. A person presses up or down on a floor; the dispatcher assigns that hall call to one car and repeated presses do nothing new. Different times of day need different assignment rules: least loaded, nearest car, a morning peak favouring the lobby. A car can break down at any moment; its assigned calls move to other cars without losing their place in time. If every car is down, calls wait and are not lost. Operators can read average wait to compare rules.

Out of scope: the door and direction detail of a single car, which is the elevator controller. Car behaviour here is deliberately simple, so the dispatch logic can be seen. Reported senior variants add peak traffic, fairness, fault tolerance and a simulation strategy.

Constraints: the assignment rule changes at runtime; a rule can never send a passenger to a broken car; everything is tick-driven, so a simulation replays deterministically; a call is assigned to one car and never served twice.

2. Core entities and relationships

• Dispatcher: owns the cars and the current strategy, takes hall calls and car failures, and advances time.
• Car: position, mode (CarMode), and assigned calls. It serves what is here or moves one floor.
• HallCall: an immutable call that keeps its original press time across reassignments.
• AssignmentStrategy: picks a car. NearestCar, LeastLoaded and MorningPeak are examples.
• CarDriver: how a car actually moves. SimulatedDriver counts moves; real hardware would implement the same protocol.

The dispatcher composes cars, while cars aggregate immutable call values that can move between them. That move is why a call is a value object and not a part of a car.

3. Interfaces and key methods

@dataclass(frozen=True)
class HallCall:
    floor: int
    direction: Direction
    pressed_at: int                     # tick of the press; kept across reassignment

class AssignmentStrategy(Protocol):
    def choose(self, cars: Sequence["Car"], call: HallCall) -> "Car | None":
        """Contract: return an IN_SERVICE car from `cars`, or None; never mutate."""

class CarDriver(Protocol):
    def move(self, delta: int) -> None: ...

class Dispatcher:
    def __init__(self, cars: Sequence["Car"], strategy: AssignmentStrategy) -> None: ...
    def set_strategy(self, strategy: AssignmentStrategy) -> None: ...
    def hall_call(self, floor: int, direction: Direction) -> None: ...
    def car_failed(self, car_id: str) -> None:
        """Take a car out of service and reassign its hall calls."""
    def tick(self) -> None: ...

Invariants: each pending hall call is held by exactly one in-service car or by _unassigned; a car that is out of service holds no calls and is never stepped; pressed_at never changes; _pending contains a button exactly until a car serves it.

4. Design patterns and the choices behind them

Strategy, swapped at runtime

The force is that the best rule depends on the hour. Each rule is a strategy, and a schedule calls set_strategy at 8:30. Adding an evening rule is a new class, which is the open-closed extension from one lift to many, and is why this seam is the design's main extensibility point. MorningPeak shows strategies composing: it handles lobby calls and delegates the rest.

A contract every strategy must honour

The dispatcher trusts choose completely. Liskov substitution here means every implementation must return only an in-service car or None, and must not mutate anything. A rule that returned a broken car would type-check and strand a passenger. The contract is written on the protocol, and a shared test runs against every strategy. serving gives all of them the same filter.

Bridge between car logic and hardware

Car behaviour and motor control vary independently: the same dispatch logic runs against a simulator today and a hardware vendor's controller tomorrow. Keeping CarDriver as a separate protocol is a small bridge. Subclassing Car per vendor would multiply with every behavioural variant.

Failure as a state transition

A mode on the car plus one car_failed event centralises recovery: mark it down, take its calls, and reassign them oldest first through the normal path. No special recovery logic exists, so a strategy change applies to recovery too. Because pressed_at stays, the metrics report the real wait, and fairness rules see the true age.

Observer for measurement

A served call is announced through on_served, so metrics or a display can attach without the dispatcher knowing them (observer).

5. Core flow and code

1. Two cars, A at floor 0 and B at floor 9, under NearestCar. hall_call(8, DOWN) records the button and creates a HallCall at tick 0.
2. choose filters to serving cars and picks B, one floor away. B holds the call.
3. A second press at floor 8 finds the key in _pending and returns.
4. tick: B moves to 8. Next tick B serves the call, so it leaves _pending, is recorded with its wait of 2 ticks, and listeners fire.
5. If car_failed("B") runs before that, B goes out of service, its call is passed through _assign, and A receives it with the original pressed_at.
6. If A also fails, choose returns None and the call sits in _unassigned until car_restored.

from __future__ import annotations
from dataclasses import dataclass, field
from enum import Enum, auto
from typing import Callable, Protocol, Sequence

class Direction(Enum):
    UP = 1; DOWN = -1

class CarMode(Enum):
    IN_SERVICE = auto(); OUT_OF_SERVICE = auto()

@dataclass(frozen=True)
class HallCall:
    floor: int
    direction: Direction
    pressed_at: int

class CarDriver(Protocol):
    def move(self, delta: int) -> None: ...

class SimulatedDriver:
    def __init__(self) -> None:
        self.moves = 0
    def move(self, delta: int) -> None:
        self.moves += 1

@dataclass
class Car:
    car_id: str
    driver: CarDriver
    floor: int = 0
    mode: CarMode = CarMode.IN_SERVICE
    calls: set[HallCall] = field(default_factory=set)

    def in_service(self) -> bool:
        return self.mode is CarMode.IN_SERVICE

    def load(self) -> int:
        return len(self.calls)

    def step(self) -> list[HallCall]:
        """Serve calls here, else move one floor toward the oldest call."""
        here = {c for c in self.calls if c.floor == self.floor}
        if here:
            self.calls -= here
            return sorted(here, key=lambda c: c.pressed_at)
        if self.calls:
            target = min(self.calls, key=lambda c: c.pressed_at).floor
            delta = 1 if target > self.floor else -1
            self.driver.move(delta)
            self.floor += delta
        return []

class AssignmentStrategy(Protocol):
    def choose(self, cars: Sequence[Car], call: HallCall) -> Car | None: ...

def serving(cars: Sequence[Car]) -> list[Car]:
    return [c for c in cars if c.in_service()]

class NearestCar:
    def choose(self, cars: Sequence[Car], call: HallCall) -> Car | None:
        return min(serving(cars), key=lambda c: (abs(c.floor - call.floor), c.load(), c.car_id), default=None)

class LeastLoaded:
    def choose(self, cars: Sequence[Car], call: HallCall) -> Car | None:
        return min(serving(cars), key=lambda c: (c.load(), abs(c.floor - call.floor), c.car_id), default=None)

class MorningPeak:
    """Up-peak: cars return to the lobby; lobby calls go to the car already nearest it."""
    def __init__(self, lobby: int = 0, fallback: AssignmentStrategy | None = None) -> None:
        self.lobby, self.fallback = lobby, fallback or LeastLoaded()
    def choose(self, cars: Sequence[Car], call: HallCall) -> Car | None:
        if call.floor == self.lobby and call.direction is Direction.UP:
            return NearestCar().choose(cars, call)
        return self.fallback.choose(cars, call)

class Dispatcher:
    def __init__(self, cars: Sequence[Car], strategy: AssignmentStrategy) -> None:
        self._cars = {c.car_id: c for c in cars}
        self._strategy = strategy
        self._unassigned: list[HallCall] = []
        self._pending: set[tuple[int, Direction]] = set()
        self.now = 0
        self.served: list[tuple[str, HallCall, int]] = []      # car, call, tick served
        self._listeners: list[Callable[[str, HallCall], None]] = []

    def on_served(self, listener: Callable[[str, HallCall], None]) -> None:
        self._listeners.append(listener)

    def set_strategy(self, strategy: AssignmentStrategy) -> None:
        self._strategy = strategy

    def hall_call(self, floor: int, direction: Direction) -> None:
        key = (floor, direction)
        if key in self._pending:
            return                               # the button is already lit
        self._pending.add(key)
        self._assign(HallCall(floor, direction, self.now))

    def _assign(self, call: HallCall) -> None:
        car = self._strategy.choose(list(self._cars.values()), call)
        if car is None:
            self._unassigned.append(call)        # every car down: hold, do not drop
        else:
            car.calls.add(call)

    def car_failed(self, car_id: str) -> None:
        car = self._cars[car_id]
        car.mode = CarMode.OUT_OF_SERVICE
        orphaned, car.calls = sorted(car.calls, key=lambda c: c.pressed_at), set()
        for call in orphaned:
            self._assign(call)                   # pressed_at is kept: fairness survives

    def car_restored(self, car_id: str) -> None:
        self._cars[car_id].mode = CarMode.IN_SERVICE
        waiting, self._unassigned = self._unassigned, []
        for call in waiting:
            self._assign(call)

    def tick(self) -> None:
        self.now += 1
        for car in self._cars.values():
            if not car.in_service():
                continue
            for call in car.step():
                self._pending.discard((call.floor, call.direction))
                self.served.append((car.car_id, call, self.now))
                for listener in self._listeners:
                    listener(car.car_id, call)

    def average_wait(self) -> float:
        waits = [t - c.pressed_at for _, c, t in self.served]
        return sum(waits) / len(waits) if waits else 0.0

6. Extensions, concurrency and what interviewers probe

• Destination dispatch: passengers enter the destination in the lobby. HallCall gains a target, and a strategy groups passengers by floor. The dispatcher stays the same.
• Reassigning for better fit: an assignment made at press time can go stale. A periodic pass could move calls between cars, trading stability for wait time.
• Fairness under peak: NearestCar can starve far floors in a rush. Add an age boost: any call older than a threshold goes to the nearest car regardless of load.
• Concurrency: presses come from many threads. Feed events through one queue drained at each tick, so all state is touched by one thread; this also keeps replay deterministic.
• Simulation testing: since everything is tick-driven, replay a recorded morning through each strategy and compare average_wait; this is the reported senior answer on how to choose (see designing for unit tests). Test first: duplicate press, failure mid-trip, all cars down then restored.
• Common mistake: an if mode == "peak" inside the dispatcher, and dropping or re-timestamping a failed car's calls.

02Where this question was reported

• LLD Mastery · Google-tagged (Medium); load balancing across lifts
• LLD Mastery · Google-tagged; Open/Closed extension from single lift