Design an Elevator System

1. Problem & Why It's Asked

Harder than Parking Lot because the core challenge isn't matching (spot to vehicle) but scheduling under a moving state — which elevator should answer which call, and in what order should a single elevator serve its queued stops. This tests whether a candidate can model state transitions cleanly and reason about a real scheduling algorithm rather than just CRUD-ing objects.

2. Requirements

Functional:

• N elevators serving M floors in a building.
• External calls: a user on a floor presses up/down.
• Internal calls: a user inside an elevator selects a destination floor.
• Elevator moves toward requests, serving them in a sensible order (not necessarily FIFO — a naive FIFO queue would zigzag inefficiently).

Non-functional:

• Minimize average wait time across all requests.
• Handle concurrent requests arriving while an elevator is mid-transit.
• Extensible to multiple elevators with a dispatch strategy (which elevator answers a given external call).

3. Core Entities & Class Diagram

classDiagram
    class Direction {
        <<enumeration>>
        UP
        DOWN
        IDLE
    }
    class ElevatorState {
        <<enumeration>>
        MOVING
        STOPPED
        IDLE
    }
    class Request {
        +int floor
        +Direction direction
    }
    class Elevator {
        +int id
        +int current_floor
        +Direction direction
        +ElevatorState state
        -SortedSet up_stops
        -SortedSet down_stops
        +add_request(Request)
        +step()
    }
    class ElevatorController {
        -list~Elevator~ elevators
        +request_elevator(floor, direction)
        +select_elevator(floor, direction) Elevator
    }
    ElevatorController "1" --> "*" Elevator
    Elevator --> Direction
    Elevator --> ElevatorState
    Elevator "1" --> "*" Request

4. Design Patterns Used

• State — an elevator's valid next actions depend on whether it's IDLE, MOVING, or STOPPED; modeling this explicitly (rather than a tangle of booleans) is the same reasoning as the Vending Machine problem (see [[OOD Design Patterns]]).
• Strategy for elevator selection — which elevator answers an external call is a swappable policy (nearest-elevator, least-busy, zone-based) — see §8.
• The core scheduling algorithm below is the SCAN / LOOK disk-scheduling algorithm applied to floors instead of disk tracks — worth naming explicitly; it signals you recognize this as a known algorithmic pattern, not an ad hoc invention.

5. The Core Algorithm: SCAN (aka the "elevator algorithm")

Naive FIFO service of requests in arrival order causes needless zigzagging (go to floor 8, then floor 2, then floor 9 — passing floor 8's neighborhood twice). SCAN: continue in the current direction, picking up all stops along the way, until no more requests exist in that direction — then reverse.

flowchart TD
    A[Elevator moving UP] --> B{Any stops<br/>above current floor?}
    B -- yes --> C[Move to next stop above,<br/>serve it]
    C --> B
    B -- no --> D{Any pending requests<br/>below?}
    D -- yes --> E[Reverse to DOWN,<br/>same logic]
    D -- no --> F[Go IDLE]

This is why the implementation below keeps stops in two sorted sets (up-stops, down-stops) rather than one FIFO queue — sorted order lets the elevator always serve the nearest stop in its current direction of travel, not the oldest request.

6. Implementation

from enum import Enum
from dataclasses import dataclass, field
from sortedcontainers import SortedSet   # or bisect.insort on a plain list


class Direction(Enum):
    UP = "up"
    DOWN = "down"
    IDLE = "idle"


class ElevatorState(Enum):
    MOVING = "moving"
    STOPPED = "stopped"
    IDLE = "idle"


@dataclass
class Request:
    floor: int
    direction: Direction


class Elevator:
    def __init__(self, elevator_id: int, num_floors: int):
        self.id = elevator_id
        self.current_floor = 0
        self.direction = Direction.IDLE
        self.state = ElevatorState.IDLE
        self.up_stops: SortedSet = SortedSet()
        self.down_stops: SortedSet = SortedSet()

    def add_request(self, floor: int) -> None:
        if floor > self.current_floor:
            self.up_stops.add(floor)
        elif floor < self.current_floor:
            self.down_stops.add(floor)
        if self.direction == Direction.IDLE:
            self.direction = Direction.UP if floor >= self.current_floor else Direction.DOWN

    def step(self) -> None:
        """Advance one floor per tick, serving stops via SCAN."""
        if self.direction == Direction.UP:
            if self.up_stops:
                next_stop = self.up_stops[0]
                self._move_toward(next_stop)
                if self.current_floor == next_stop:
                    self.up_stops.remove(next_stop)
                    self.state = ElevatorState.STOPPED
            elif self.down_stops:
                self.direction = Direction.DOWN       # reverse — SCAN turnaround
            else:
                self.direction = Direction.IDLE
                self.state = ElevatorState.IDLE

        elif self.direction == Direction.DOWN:
            if self.down_stops:
                next_stop = self.down_stops[-1]        # nearest below, i.e. largest remaining
                self._move_toward(next_stop)
                if self.current_floor == next_stop:
                    self.down_stops.remove(next_stop)
                    self.state = ElevatorState.STOPPED
            elif self.up_stops:
                self.direction = Direction.UP
            else:
                self.direction = Direction.IDLE
                self.state = ElevatorState.IDLE

    def _move_toward(self, target: int) -> None:
        if self.current_floor < target:
            self.current_floor += 1
        elif self.current_floor > target:
            self.current_floor -= 1
        self.state = ElevatorState.MOVING


class ElevatorController:
    def __init__(self, num_elevators: int, num_floors: int):
        self.elevators = [Elevator(i, num_floors) for i in range(num_elevators)]

    def request_elevator(self, floor: int, direction: Direction) -> Elevator:
        chosen = self.select_elevator(floor, direction)
        chosen.add_request(floor)
        return chosen

    def select_elevator(self, floor: int, direction: Direction) -> Elevator:
        """Nearest-idle-first, falling back to nearest-same-direction."""
        idle = [e for e in self.elevators if e.state == ElevatorState.IDLE]
        candidates = idle if idle else [
            e for e in self.elevators if e.direction in (direction, Direction.IDLE)
        ]
        pool = candidates if candidates else self.elevators
        return min(pool, key=lambda e: abs(e.current_floor - floor))

7. Concurrency

• External/internal requests can arrive from multiple threads (multiple floor buttons, multiple in-cab panels) while step() is being called on a scheduler tick — add_request() mutating up_stops/down_stops concurrently with step() reading them needs a lock per elevator (omitted above for readability, but call it out explicitly in an interview — "I'd wrap add_request and step in a per-elevator lock, not a global one, so elevators don't serialize against each other unnecessarily").
• select_elevator() reads shared state (current_floor, direction) across all elevators — for a single controller instance this is a read-mostly path and generally safe with per-elevator locks alone, but at true scale (many controller replicas) this becomes a distributed coordination problem, not just a threading one.

8. Elevator Selection Strategies (Strategy pattern payoff)

9. Edge Cases

• All elevators busy, going the wrong direction — a call must wait; select_elevator's fallback (candidates if candidates else self.elevators) ensures some elevator is always assigned rather than the call being dropped, even if it means the assigned elevator finishes its current direction first.
• Overweight/door-obstruction sensors — out of scope for the scheduling logic itself, but worth naming as a real input that would pause step() for a given elevator (hold in STOPPED state longer than a normal dwell time).
• Power/emergency mode — all elevators return to a designated floor and stop responding to normal requests; a real system models this as another ElevatorState, not a special case bolted onto step().

10. Interview Drills

1. Why sorted sets for stops instead of a single FIFO queue? — FIFO serves requests in arrival order, which can zigzag (floor 8 → floor 2 → floor 9). Sorted sets let the elevator always serve the nearest stop in its current direction of travel, which is the SCAN algorithm and matches how real elevators actually behave.
2. A call comes in for floor 5, going down, while the elevator is at floor 3 going up with a stop at floor 8 queued. — Depends on the elevator's design philosophy: a simple SCAN implementation won't serve floor 5's down call until it finishes going up to 8 and reverses; a "look-ahead" LOOK variant could special-case picking up a compatible-direction call along the way, but that adds real complexity — naming which trade-off you're making here is the interview-scoring moment.
3. Design the API for "reserve this elevator for exclusive use" (freight/service mode). — Add an exclusive: bool flag on Elevator; select_elevator() filters exclusive-mode elevators out of the normal candidate pool entirely, and a separate authorized-call path is the only thing that can target it.

Cross-links

[[OOD Design Patterns]] · [[SOLID Principles]] · [[Parking Lot]] · [[Vending Machine]]