Design an elevator system

01Simulation, not hardware

02Analogy: elevator as a shared bus

03Clarifying questions → locked requirements

• How many cars / floors? → 3 elevators, floors 0–9.
• Hall vs cabin? → Hall = floor + UP/DOWN; cabin = DESTINATION floor.
• Time model? → Discrete step() advances all cars.
• Invalid floors? → Reject (return false). Current-floor request = no-op.
• Out of scope → doors, weight limits, emergency stop, UI.

04Entities: ElevatorController, Elevator, Request

• ElevatorController — owns the fleet; request_elevator + step.
• Elevator — current_floor, direction (UP/DOWN/IDLE), pending requests; add_request, step.
• Request — floor + type. Not an IRequestHandler.

05Class design

from enum import Enum, auto
from dataclasses import dataclass

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

class RequestType(Enum):
    PICKUP_UP = auto()
    PICKUP_DOWN = auto()
    DESTINATION = auto()

@dataclass(frozen=True)
class Request:
    floor: int
    type: RequestType

class Elevator:
    def __init__(self, car_id: int, floors: int = 10):
        self.id = car_id
        self.floors = floors
        self.current_floor = 0
        self.direction = Direction.IDLE
        self.requests: set[Request] = set()

    def add_request(self, req: Request) -> bool: ...
    def step(self) -> None: ...
    def has_requests_ahead(self, direction: Direction) -> bool: ...

class ElevatorController:
    def __init__(self, num_cars: int = 3, floors: int = 10):
        self.floors = floors
        self.elevators = [Elevator(i, floors) for i in range(num_cars)]

    def request_elevator(self, floor: int, req_type: RequestType) -> bool: ...
    def step(self) -> None:
        for e in self.elevators:
            e.step()

enum Direction { UP, DOWN, IDLE }
enum RequestType { PICKUP_UP, PICKUP_DOWN, DROPOFF }

class Request {
    final int floor; final RequestType type;
    Request(int floor, RequestType type) { this.floor = floor; this.type = type; }
}

class ElevatorCar {
    int id, floor; Direction dir; Set<Integer> stops;
    // tick / addStop / ...
}

class ElevatorController {
    int floors; List<ElevatorCar> cars;
    // boolean requestElevator(int floor, RequestType type)
    // void step()
}

06requestElevator, selectBestElevator, SCAN step

def request_elevator(self, floor: int, req_type: RequestType) -> bool:
    if not (0 <= floor < self.floors):
        return False
    req = Request(floor, req_type)
    best = self._select_best_elevator(req)
    return best.add_request(req)

def _select_best_elevator(self, req: Request) -> Elevator:
    # v1: nearest car by absolute floor distance (deterministic tie-break by id)
    return min(
        self.elevators,
        key=lambda e: (abs(e.current_floor - req.floor), e.id),
    )

def has_requests_ahead(self, direction: Direction) -> bool:
    if direction is Direction.UP:
        return any(r.floor > self.current_floor for r in self.requests)
    if direction is Direction.DOWN:
        return any(r.floor < self.current_floor for r in self.requests)
    return False

def step(self) -> None:
    # Case 1: idle with nothing pending
    if not self.requests:
        self.direction = Direction.IDLE
        return

    # Case 2: idle with work — pick nearest request, set direction (tie → lower floor)
    if self.direction is Direction.IDLE:
        target = min(self.requests, key=lambda r: (abs(r.floor - self.current_floor), r.floor))
        if target.floor == self.current_floor:
            self._stop_here()
            return
        self.direction = Direction.UP if target.floor > self.current_floor else Direction.DOWN

    # Case 3: stop if a request matches this floor + compatible direction
    if self._should_stop_here():
        self._stop_here()
        return  # doors/open this tick; move next tick

    # Case 4: reverse when nothing ahead
    if not self.has_requests_ahead(self.direction):
        self.direction = Direction.DOWN if self.direction is Direction.UP else Direction.UP
        return

    # Case 5: move one floor
    self.current_floor += 1 if self.direction is Direction.UP else -1

boolean requestElevator(int floor, RequestType reqType) {
    if (floor < 0 || floor >= floors) return false;
    Request req = new Request(floor, reqType);
    ElevatorCar best = selectBestElevator(req);
    if (best == null) return false;
    best.addStop(floor);
    return true;
}

// selectBestElevator: prefer IDLE closest, else same-direction cars (SCAN-ish)
// car.tick: stop/dwell/move one floor under car lock if concurrent hall calls exist

07Verification tick trace

1. Car 0 idle on 0. Hall UP on 3 → assigned to car 0.
2. step → direction UP, floor 1; step → 2; step → 3, stop, clear request.
3. Cabin DESTINATION 5 → continue UP; step to 4 then 5, stop.
4. Meanwhile hall DOWN on 4 — either collect on reverse or after policy check; state your rule.

• Happy: Idle car at 1; hall UP@3 assigned; car moves 1→2→3, stops, then serves cabin destination.
• Failure: Hall call on invalid floor rejected; assigning to a car in MAINTENANCE skipped.
• Concurrency: User presses hall while step() runs — request enqueue is locked; car reads a stable snapshot each tick.

08Extensibility

• Express elevator — car that only serves a subset of floors; filter in select_best / add_request.
• removeRequest — cancel a pending floor (passenger changed mind).
• Concurrency — lock around dispatch + add_request, or queue pending hall calls and drain on the simulation thread. Don’t pretend SCAN alone is thread-safe.

09Common interview pitfalls

• Building a full event-driven distributed system instead of a step()/tick simulation.
• Mixing hall calls (floor+direction) with cabin destination requests in one undifferentiated queue.
• SCAN/LOOK namedrop without explaining elevator state (IDLE/UP/DOWN) and stop selection.
• No model for doors / dwelling — every stop is instantaneous and traces feel fake.
• Single elevator assumptions when the prompt says “system” of cars.
• Ignoring starvation: a pending hall call opposite to current travel never gets a plan.

10Interview script (say this)

1. Clarify floors, number of cars, hall vs cabin buttons, and whether we simulate time with step().
2. v1: multi-car, hall calls with direction, cabin destinations, SCAN-like service, step advances the world.
3. Entities: ElevatorSystem, ElevatorCar (floor, direction, state), HallRequest, DestinationRequest.
4. System assigns hall calls to cars; cars own pending destinations.
5. step(): each car opens/closes if stopping, moves one floor, picks next target via strategy.
6. I’ll sketch SCAN: continue in direction serving stops, then reverse.
7. Trace: hall up on 3 while car idle at 1; cabin presses 5; another hall down on 4.
8. Concurrency note: request submission vs step loop — queue requests under a lock.
9. Extensions: pickup policy Strategy, express cars, maintenance mode taking a car offline.

11Extra verification traces

def step(self):
    for car in self.cars:
        car.tick(self.clock)  # stop/dwell/move one floor
        if car.state == "IDLE":
            req = self.dispatcher.next_for(car)
            if req:
                car.assign(req)

void step() {
    for (ElevatorCar car : cars) {
        car.tick(clock); // stop/dwell/move one floor
        if ("IDLE".equals(car.state)) {
            Request req = dispatcher.nextFor(car);
            if (req != null) car.addStop(req.floor);
        }
    }
}

12Staff-level follow-ups

• Minimize wait time? — Swap AssignmentStrategy; keep ElevatorCar API stable.
• Express elevator? — Car with floor subset filter in dispatcher eligibility.
• Power failure mid-move? — Persist car floor+state; on restart resume IDLE and rebuild queues.
• Peak morning up-peak? — Bias dispatcher to lobby returns — still a strategy, not a rewrite.

13Complete solution (controller + thread-safe requests)

from collections import defaultdict, deque
from enum import Enum, auto
from threading import Lock

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

class Elevator:
    def __init__(self, eid: int, floors: int):
        self.id = eid
        self.floor = 0
        self.dir = Dir.IDLE
        self.stops: set[int] = set()
        self._lock = Lock()

    def add_stop(self, floor: int) -> None:
        with self._lock:
            self.stops.add(floor)

    def step(self) -> None:
        with self._lock:
            if not self.stops:
                self.dir = Dir.IDLE
                return
            # simplified SCAN: move toward nearest stop
            target = min(self.stops, key=lambda f: abs(f - self.floor))
            if target > self.floor:
                self.floor += 1
                self.dir = Dir.UP
            elif target < self.floor:
                self.floor -= 1
                self.dir = Dir.DOWN
            if self.floor in self.stops:
                self.stops.discard(self.floor)

class ElevatorController:
    def __init__(self, elevators: list[Elevator]):
        self.elevators = elevators
        self._lock = Lock()

    def hall_call(self, floor: int, direction: Dir) -> int:
        with self._lock:
            # pick idle or closest moving same way — interview heuristic
            e = min(self.elevators, key=lambda el: abs(el.floor - floor))
            e.add_stop(floor)
            return e.id

    def car_call(self, elevator_id: int, floor: int) -> None:
        el = next(e for e in self.elevators if e.id == elevator_id)
        el.add_stop(floor)

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

enum Dir { UP, DOWN, IDLE }

class Elevator {
    final int id;
    int floor = 0;
    Dir dir = Dir.IDLE;
    final Set<Integer> stops = new HashSet<>();
    private final ReentrantLock lock = new ReentrantLock();

    Elevator(int id, int floors) { this.id = id; }

    void addStop(int floor) {
        lock.lock();
        try { stops.add(floor); }
        finally { lock.unlock(); }
    }

    void step() {
        lock.lock();
        try {
            if (stops.isEmpty()) { dir = Dir.IDLE; return; }
            int target = stops.stream().min(Comparator.comparingInt(f -> Math.abs(f - floor))).get();
            if (target > floor) { floor++; dir = Dir.UP; }
            else if (target < floor) { floor--; dir = Dir.DOWN; }
            stops.remove(floor);
        } finally { lock.unlock(); }
    }
}

class ElevatorController {
    private final List<Elevator> elevators;
    private final ReentrantLock lock = new ReentrantLock();

    ElevatorController(List<Elevator> elevators) { this.elevators = elevators; }

    int hallCall(int floor, Dir direction) {
        lock.lock();
        try {
            Elevator e = elevators.stream()
                .min(Comparator.comparingInt(el -> Math.abs(el.floor - floor))).get();
            e.addStop(floor);
            return e.id;
        } finally { lock.unlock(); }
    }

    void carCall(int elevatorId, int floor) {
        elevators.stream().filter(e -> e.id == elevatorId).findFirst().get().addStop(floor);
    }
}

14Concurrency cases

• Two hall calls — controller lock so assignment reads a consistent elevator snapshot.
• step vs add_stop — elevator lock so the stop set isn’t mutated mid-iteration.
• Don’t lock across sleep/move simulation — hold locks only for state updates; animate movement outside.