Design an Elevator System

Scope it first

"Design an elevator" is two problems wearing one prompt: object model (states, requests, doors) and scheduling (which elevator answers, in what order). Clarify both: "N elevators, M floors, hall calls (up/down button on a floor) + cabin calls (floor button inside), optimize average wait — ignore weight sensors and maintenance mode, OK?"

The two request types are the first real modeling decision — they carry different information: a hall call is (floor, direction); a cabin call is just (floor). Conflating them breaks scheduling later.

Entities & relationships

• ElevatorSystem is the facade: receives calls, delegates "who goes?" to a DispatchStrategy, ticks the world via step().
• Elevator owns its position, direction, door and stop set — and is a textbook state machine: IDLE → MOVING_UP / MOVING_DOWN → STOPPED(doors) → …. Transitions live in one place; "can't move with doors open" becomes an invariant, not a scattered if.
• DispatchStrategy (Strategy pattern, like the parking lot's spot assignment): nearest-available, least-loaded, same-direction-first — swappable without touching the elevator.

Here's that state machine drawn out — note what's missing: there is no arrow from MOVING to DOORS_OPEN's neighbor states that skips STOPPED, and no arrow out of DOORS_OPEN while moving. Illegal transitions simply don't exist in the diagram, which is the whole point of the State pattern:

Now drive that machine yourself. Step through a call → arrive → doors → idle cycle, then add an illegal event (an arrive while still Idle) and watch it get refused — the invariant "can't arrive when you never moved" is enforced by the absence of a transition, not a scattered if.

The scheduling insight: SCAN, not FIFO

Serving requests in arrival order (FIFO) makes the cabin ping-pong: 2 → 9 → 3 → 8 wastes everyone's time. Real elevators run SCAN (the "elevator algorithm" — disk drives borrowed it from elevators): keep moving in the current direction, servicing every stop in that direction; reverse only when none remain.

The data structure follows from the algorithm: not a queue but two sorted sets per elevator — stops above (served ascending while going up) and stops below (descending while going down). In code:

class Elevator:
    def __init__(self, id):
        self.id, self.floor, self.direction = id, 0, Direction.IDLE
        self.up_stops = SortedSet()      # or a min-heap
        self.down_stops = SortedSet()    # or a max-heap

    def add_stop(self, floor):
        if floor > self.floor: self.up_stops.add(floor)
        elif floor < self.floor: self.down_stops.add(floor)

    def step(self):                      # one tick of the state machine
        if self.direction == Direction.UP:
            self.floor += 1
            if self.floor in self.up_stops:
                self.up_stops.remove(self.floor)
                self.open_doors()        # state: STOPPED
            if not self.up_stops:        # exhausted this direction
                self.direction = (Direction.DOWN if self.down_stops
                                  else Direction.IDLE)
        # ... mirrored for DOWN

A simple, defensible DispatchStrategy: prefer elevators already moving toward the call in the same direction (cost = distance), then idle ones (distance), then opposite-direction ones (distance to their reversal point

• back). Naming that cost function out loud is the senior move; the exact formula matters less.

Where the patterns live

• State — the elevator's lifecycle. Guards illegal transitions (MOVING → doors open) structurally.
• Strategy — dispatch policy, and door-dwell policy if pressed.
• Observer — floor displays and hall-button lamps subscribe to elevator events rather than being polled.
• Singleton (resist it) — one ElevatorSystem, but inject it; tests will thank you.

Think it through like the interview

Walk a scenario + the concurrency question

"User on floor 6 presses DOWN; elevator A is at 3 going up with stops 9; B is idle at 8." Dispatch: A is moving away-then-toward (cost ≈ (9−3) + (9−6) = 9), B is idle at distance 2 → B. B: IDLE → MOVING_DOWN, stops 6; arrives, doors open; user presses 1 → cabin call adds 1 to down-stops; continues down. SCAN means if someone on 4 presses DOWN meanwhile, B collects them en route — no extra trip.

Concurrency follow-up: hall calls arrive from many floors while elevators tick. Same answer family as the parking lot's last spot: serialize mutations — a lock (or single-threaded event loop) around assign-and-add-stop so a call is assigned exactly once, and make step() atomic per elevator. One elevator's state is touched by one thread at a time.

Practice — level up

An elevator controller is a scheduler: given the pending requests and the car's position, pick the next stop — then serve a sweep efficiently. These drills are that same "choose the next job" decision.