0

Design an elevator control system

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Design an elevator control system

Companies: Amazon, Waymo

Difficulty: Hard

Problem statement

Model a bank of elevators: hall and car requests, a dispatching strategy, direction and door states, and capacity limits.

Requirements

  • Floors 0..N-1 and a bank of M identical cars that serve every floor.
  • Hall calls: a person on a floor presses UP or DOWN. The controller gives the call to exactly one car. Pressing the same button again adds nothing.
  • Car calls: a passenger inside a car picks a floor. That stop belongs to that car only.
  • Dispatching is pluggable. The default picks the cheapest car: an idle car, or one already moving toward the floor in the call's direction, beats a car that must finish its sweep first.
  • Each car runs SCAN: keep going one way while stops lie ahead, then reverse. It stops for a hall call only if the call goes its way, or at its turnaround point.
  • Doors open only when the car is stopped; a car never moves with doors open. Time is a discrete tick: one tick moves one floor, opens the doors or closes them.
  • Capacity: a load sensor reports weight. Above 100% the doors stay open (overload buzzer). Above 80% the car takes no new hall calls. A car can go out of service; its hall calls move to other cars.
  • Out of scope: motor control and real timing, fire/emergency modes, destination-dispatch keypads, express zones, persistence, UI.

Core objects

  • Direction (enum: UP, DOWN, IDLE) and DoorState (enum: OPEN, CLOSED): car movement, hall-call direction, doors.
  • HallCall (value object): floor + direction. Hashable, so duplicate presses collapse.
  • Elevator: one car. Owns floor, direction, door, load, car stops and assigned hall calls; runs SCAN each tick.
  • DispatchStrategy (ABC): picks a car for a hall call. NearestCarStrategy is the default: lowest estimated cost wins, ties go to the car with fewer calls.
  • ElevatorSystem: the controller. Takes requests, dispatches, retries calls no car could take, re-dispatches when a car fails, and drives the tick. One lock guards all shared state.

Class design

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"system","x":0,"y":0,"width":260,"height":170,"label":{"text":"ElevatorSystem\ncars, assigned, pending\nhall_request()\ncar_request()\nset_out_of_service()\nstep()"}},
 {"type":"rectangle","id":"elevator","x":480,"y":0,"width":260,"height":170,"label":{"text":"Elevator\nfloor, direction, door\nload_kg, car_stops\nadd_car_stop()\nassign(call)\nstep()"}},
 {"type":"rectangle","id":"hallcall","x":940,"y":50,"width":180,"height":70,"label":{"text":"HallCall"}},
 {"type":"rectangle","id":"dispatch","x":0,"y":340,"width":260,"height":100,"label":{"text":"DispatchStrategy\n(abstract)\nchoose(cars, call)"}},
 {"type":"rectangle","id":"nearest","x":480,"y":350,"width":260,"height":80,"label":{"text":"NearestCarStrategy\ncost(car, call)"}},
 {"type":"arrow","id":"sys-elev","x":260,"y":85,"width":220,"height":0,"start":{"id":"system"},"end":{"id":"elevator"},"label":{"text":"owns 1..*"}},
 {"type":"arrow","id":"elev-call","x":740,"y":85,"width":200,"height":0,"start":{"id":"elevator"},"end":{"id":"hallcall"},"label":{"text":"has 0..*"}},
 {"type":"arrow","id":"sys-disp","x":130,"y":170,"width":1,"height":170,"start":{"id":"system"},"end":{"id":"dispatch"},"label":{"text":"uses"}},
 {"type":"arrow","id":"near-disp","x":480,"y":390,"width":-220,"height":0,"start":{"id":"nearest"},"end":{"id":"dispatch"},"label":{"text":"extends"}}
]}

Key flows

1. Hall call (floor 5, DOWN)

  1. ElevatorSystem.hall_request(5, DOWN) rejects unknown floors, IDLE, UP on the top floor and DOWN on the bottom one.
  2. If HallCall(5, DOWN) is already in assigned, it returns that car (a repeated press changes nothing). Otherwise DispatchStrategy.choose scores the cars that are in service and not full. If none qualifies, the call goes to pending, and each step() retries it.
  3. The chosen car's assign(call) stores the call and recomputes direction; the controller records assigned[call] = car_id.

2. Car call (passenger in car 1 presses 8): car_request(1, 8) → Elevator.add_car_stop(8). An idle car starts toward the stop; a moving car keeps its sweep and picks the stop up on the way or after it reverses.

3. Tick (ElevatorSystem.step → each Elevator.step)

  1. Doors open: if load ≤ capacity, close them and recompute direction; if overloaded, hold them open.
  2. Doors closed and this floor is a stop (car stop, hall call our way, or turnaround point): drop the car stop, take the hall calls answered here, open the doors and return those calls. The controller removes them from assigned, so the next press is a fresh call. An opposite-direction call at the same floor stays with the car until it reverses.
  3. Otherwise move one floor in the current direction (IDLE does not move).

4. Car fails: set_out_of_service(id) stops the car and re-dispatches its hall calls to other cars, or to pending.

{"type":"excalidraw","elements":[
 {"type":"ellipse","id":"init","x":0,"y":210,"width":100,"height":50,"label":{"text":"start"}},
 {"type":"rectangle","id":"idle","x":200,"y":200,"width":180,"height":70,"label":{"text":"Idle"}},
 {"type":"rectangle","id":"up","x":650,"y":0,"width":180,"height":70,"label":{"text":"MovingUp"}},
 {"type":"rectangle","id":"down","x":650,"y":400,"width":180,"height":70,"label":{"text":"MovingDown"}},
 {"type":"rectangle","id":"doors","x":1100,"y":200,"width":180,"height":70,"label":{"text":"DoorsOpen"}},
 {"type":"rectangle","id":"oos","x":190,"y":420,"width":200,"height":70,"label":{"text":"OutOfService"}},
 {"type":"arrow","id":"init-idle","x":100,"y":235,"width":100,"height":0,"start":{"id":"init"},"end":{"id":"idle"}},
 {"type":"arrow","id":"idle-up","x":380,"y":215,"width":270,"height":-170,"start":{"id":"idle"},"end":{"id":"up"},"label":{"text":"stop above"}},
 {"type":"arrow","id":"idle-down","x":380,"y":255,"width":270,"height":170,"start":{"id":"idle"},"end":{"id":"down"},"label":{"text":"stop below"}},
 {"type":"arrow","id":"up-doors","x":830,"y":20,"width":360,"height":180,"points":[[0,0],[360,0],[360,180]],"start":{"id":"up"},"end":{"id":"doors"},"label":{"text":"reached a stop"}},
 {"type":"arrow","id":"down-doors","x":830,"y":450,"width":360,"height":-180,"points":[[0,0],[360,0],[360,-180]],"start":{"id":"down"},"end":{"id":"doors"},"label":{"text":"reached a stop"}},
 {"type":"arrow","id":"doors-up","x":1100,"y":215,"width":-270,"height":-160,"start":{"id":"doors"},"end":{"id":"up"},"label":{"text":"closed, stops above"}},
 {"type":"arrow","id":"doors-down","x":1100,"y":255,"width":-270,"height":160,"start":{"id":"doors"},"end":{"id":"down"},"label":{"text":"closed, stops below"}},
 {"type":"arrow","id":"doors-idle","x":1100,"y":235,"width":-720,"height":0,"start":{"id":"doors"},"end":{"id":"idle"},"label":{"text":"closed, no stops"}},
 {"type":"arrow","id":"doors-hold","x":1280,"y":220,"width":1,"height":30,"points":[[0,0],[130,0],[130,30],[0,30]],"start":{"id":"doors"},"end":{"id":"doors"},"label":{"text":"overloaded (hold)"}},
 {"type":"arrow","id":"idle-oos","x":290,"y":270,"width":1,"height":150,"start":{"id":"idle"},"end":{"id":"oos"},"label":{"text":"maintenance or fault"}}
]}

Code

from __future__ import annotations
import threading
from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import Enum

class Direction(Enum):
    UP = 1
    DOWN = -1
    IDLE = 0

class DoorState(Enum):
    OPEN = "open"
    CLOSED = "closed"

@dataclass(frozen=True)
class HallCall:
    floor: int
    direction: Direction  # UP or DOWN only

class Elevator:
    FULL_RATIO = 0.8  # above this load the car takes no new hall calls
    def __init__(self, car_id: int, floors: range, capacity_kg: int) -> None:
        self.car_id, self.floors, self.capacity_kg = car_id, floors, capacity_kg
        self.floor, self.load_kg, self.in_service = floors.start, 0, True  # load_kg: from sensor
        self.direction, self.door = Direction.IDLE, DoorState.CLOSED
        self.car_stops: set[int] = set()
        self.hall_calls: set[HallCall] = set()
    def add_car_stop(self, floor: int) -> None:
        if floor not in self.floors:
            raise ValueError(f"floor {floor} out of range")
        self.car_stops.add(floor)
        self._update_direction()
    def assign(self, call: HallCall) -> None:
        self.hall_calls.add(call)
        self._update_direction()
    def _has_targets(self, d: Direction) -> bool:
        targets = self.car_stops | {c.floor for c in self.hall_calls}
        return any((t - self.floor) * d.value > 0 for t in targets)
    def _update_direction(self) -> None:
        if self.direction is Direction.IDLE or not self._has_targets(self.direction):  # SCAN
            ahead = [d for d in (Direction.UP, Direction.DOWN) if self._has_targets(d)]
            self.direction = ahead[0] if ahead else Direction.IDLE
    def _should_stop_here(self) -> bool:
        here = {c.direction for c in self.hall_calls if c.floor == self.floor}
        if self.floor in self.car_stops or (here and self.direction is Direction.IDLE):
            return True
        return bool(here) and (self.direction in here or not self._has_targets(self.direction))
    def _serve_floor(self) -> set[HallCall]:
        here = {c for c in self.hall_calls if c.floor == self.floor}
        self.hall_calls -= here
        self.car_stops.discard(self.floor)
        self._update_direction()
        if self.direction is Direction.IDLE and here:
            self.direction = next(iter(here)).direction  # light that lantern
        served = {c for c in here if c.direction is self.direction}
        self.hall_calls |= here - served  # the opposite call waits for the reversal
        self.door = DoorState.OPEN
        return served
    def step(self) -> set[HallCall]:  # one tick; returns the hall calls it served
        if not self.in_service:
            return set()
        if self.door is DoorState.OPEN:
            if self.load_kg <= self.capacity_kg:  # overloaded: hold doors, buzz
                self.door = DoorState.CLOSED
                self._update_direction()
            return set()
        if self._should_stop_here():
            return self._serve_floor()
        self.floor += self.direction.value  # IDLE has value 0
        return set()

class DispatchStrategy(ABC):
    @abstractmethod
    def choose(self, cars: list[Elevator], call: HallCall) -> Elevator | None: ...

class NearestCarStrategy(DispatchStrategy):
    def cost(self, car: Elevator, call: HallCall) -> int:
        dist = abs(car.floor - call.floor)
        ahead = (call.floor - car.floor) * car.direction.value >= 0
        on_the_way = car.direction is Direction.IDLE or (ahead and car.direction is call.direction)
        return dist if on_the_way else dist + 2 * len(car.floors)  # finish the sweep first
    def choose(self, cars: list[Elevator], call: HallCall) -> Elevator | None:
        ok = [c for c in cars if c.in_service and c.load_kg < c.capacity_kg * c.FULL_RATIO]
        return min(ok, key=lambda c: (self.cost(c, call), len(c.hall_calls)), default=None)

class ElevatorSystem:
    def __init__(self, cars: list[Elevator], strategy: DispatchStrategy) -> None:
        self.cars = {c.car_id: c for c in cars}
        self.strategy, self.floors = strategy, cars[0].floors
        self.assigned: dict[HallCall, int] = {}
        self.pending: set[HallCall] = set()  # calls no car could take yet
        self._lock = threading.Lock()
    def hall_request(self, floor: int, direction: Direction) -> int | None:
        # Rejects IDLE, unknown floors, UP on the top floor and DOWN on the bottom one.
        if direction is Direction.IDLE or {floor, floor + direction.value} - set(self.floors):
            raise ValueError("invalid hall call")
        call = HallCall(floor, direction)
        with self._lock:
            if call in self.assigned:
                return self.assigned[call]  # repeated press is idempotent
            return self._dispatch(call)
    def _dispatch(self, call: HallCall) -> int | None:
        self.assigned.pop(call, None)
        car = self.strategy.choose(list(self.cars.values()), call)
        if car is None:
            self.pending.add(call)
            return None
        car.assign(call)
        self.assigned[call] = car.car_id
        return car.car_id
    def car_request(self, car_id: int, floor: int) -> None:
        with self._lock:
            self.cars[car_id].add_car_stop(floor)
    def set_out_of_service(self, car_id: int) -> None:
        with self._lock:
            car = self.cars[car_id]
            car.in_service = False
            orphans, car.hall_calls = car.hall_calls, set()
            for call in orphans:
                self._dispatch(call)
    def step(self) -> None:
        with self._lock:
            retry, self.pending = self.pending, set()
            for call in retry:
                self._dispatch(call)
            for car in self.cars.values():
                for call in car.step():
                    self.assigned.pop(call, None)

if __name__ == "__main__":
    system = ElevatorSystem([Elevator(i, range(10), 800) for i in range(3)], NearestCarStrategy())
    print(system.hall_request(5, Direction.DOWN))  # 0: all idle at floor 0, first car wins the tie
    system.car_request(1, 8)
    for _ in range(12):
        system.step()
    print([(c.car_id, c.floor, c.direction.name, c.door.name) for c in system.cars.values()])
    # [(0, 5, 'IDLE', 'CLOSED'), (1, 8, 'IDLE', 'CLOSED'), (2, 0, 'IDLE', 'CLOSED')]

Design patterns

  • Strategy: DispatchStrategy keeps the dispatch decision out of the controller. Nearest-car, zoning, round-robin or an energy-saving policy plug in without touching Elevator. Rush-hour behavior is just another strategy picked by time of day.
  • Mediator: buttons never talk to cars. ElevatorSystem sits between them, owns the call-to-car mapping, and is the single place that dispatches, retries and re-dispatches.
  • State (implicit): what a car does on a tick depends on (door, direction, in_service), following the state diagram. With more modes (fire service, inspection) I would move each into a CarState class so step() stops growing branches.
  • Value object: HallCall is frozen and hashable, which makes repeated presses idempotent and lets calls be dict keys.

Extensions

  • Destination dispatch (riders key in their floor in the lobby): add DestinationCall(origin, dest); the strategy groups riders by destination and gives both stops to one car. Elevator already mixes hall calls and car stops.
  • Real hardware timing: replace the tick with events from a hardware adapter (arrived(floor), doors_closed, door_obstructed). Controller and strategy stay the same; an obstructed door becomes another hold condition next to overload.
  • Fire recall: a system mode that clears hall calls, gives every car one stop at the recall floor and disables dispatch. With the State pattern this is a FireRecallState per car.
  • Smarter dispatch: add stops in between and expected load to the cost, and reassign a call when a better car frees up, using the same path as set_out_of_service. Cars that skip floors get their own floors, and the strategy filters on it.

Interviewer expectations

Mid-level (L4)

  • Separates hall calls from car calls; models Elevator, direction and door enums, and a controller.
  • Implements SCAN correctly and never moves with doors open.
  • Has a working nearest-car dispatcher and rejects invalid floors.

Senior (L5)

  • Makes dispatch a Strategy and explains the cost function, including the penalty for a car moving away.
  • Gets the subtle cases right: opposite-direction call served at the turnaround, duplicate presses collapse, overload holds the doors, a nearly full car takes no hall calls.
  • Guards shared state with a lock and explains the threading model (request threads plus one tick loop).

Staff (L6+)

  • Covers failure: re-dispatch when a car dies, calls nobody can take yet (pending plus retry), passengers already inside.
  • Compares policies on wait time (average and worst case), energy, and up-peak traffic; knows when destination dispatch wins.
  • Keeps the controller hardware-independent and plans testing: a traffic simulator that checks invariants such as "no movement with doors open" and "every call is eventually served".

Sign in to comment, vote or remix.