Elevator System
medium · state machine, SCAN scheduling
Brief-reported interview attribution (unverified): Amazon, Microsoft
How to approach an LLD roundRequirements
- Functional: accept floor requests; move one floor per step; serve requests in SCAN order (keep going the current way while requests lie that way); report floor, direction and pending requests.
- Non-functional: a request must never be lost or served twice; the direction policy must be replaceable without touching the elevator; the elevator is shared state.
- Out of scope: multiple elevators and dispatching, weight limits, door timing, fire service mode.
Statement
Design one elevator for a building of num_floors floors, numbered
0 to num_floors - 1 (ground floor = 0). The elevator has a current floor, a
direction ("up", "down", "idle"), and a set of requested floors. request(floor)
adds a floor (returns False for an out-of-range floor, True otherwise).
step() advances the elevator by exactly one floor, or serves the floor it is
already on. The elevator uses SCAN scheduling: it keeps moving in its current
direction while any requested floor lies that way, and only reverses when no
requested floor remains in that direction.
class Elevator:
def __init__(self, num_floors):
def request(self, floor):
# -> True if accepted, False if the floor is out of range
def step(self):
# advance one floor, or serve the current floor if it is requested
def status(self):
# -> {"floor": int, "direction": "up"|"down"|"idle", "pending": sorted list of floors}Rules. A step() with no pending requests does nothing and leaves the direction
"idle". If the elevator is standing on a requested floor, that step serves it
(removes the request, doors open) and the elevator does not move. After serving a
floor, the direction is "up" if any pending floor is above, "down" if any is
below, else "idle". A request for the current floor is served on the next step.
When the elevator arrives at a requested floor by moving, the request is cleared in
the same step.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
Direction (up/down/idle). SchedulingStrategy (ABC interface; chooses the direction; SRP) with ScanStrategy (OCP — FCFS or LOOK swap in as a new strategy). Elevator holds the state (floor, direction, pending targets) and delegates policy to the strategy (DIP). Pattern: Strategy (scheduling).
Public demo
# Public demo: run after implementing the class API above.
e = Elevator(21)
print(e.request(21))
print(e.request(-1))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
Requests arrive from many floors while the car moves: request and step must not interleave mid-update, or a target can be added after the car decides it has none left. Guard both with one lock per elevator (the car is a single actor; a lock per car is enough). The reference is a deterministic simulation; the lock is described here.
Trade-offs & extensions
SCAN is fairer than FCFS but can still starve a request at the far end if new requests keep arriving. Extending: a multi-elevator Dispatcher that assigns each request to the nearest car, and a Door state machine for open/close timing.
Starter code
from abc import ABC, abstractmethod
class Direction:
pass
class SchedulingStrategy(ABC):
@abstractmethod
def choose_direction(self, elevator):
"""Implement the return value and rules in the API contract."""
pass
class ScanStrategy(SchedulingStrategy):
def choose_direction(self, elevator):
"""Implement the return value and rules in the API contract."""
pass
class Elevator:
def __init__(self, num_floors, strategy=None):
"""Initialize the state described in the problem."""
pass
def request(self, floor):
"""-> True if accepted, False if the floor is out of range"""
pass
def step(self):
"""advance one floor, or serve the current floor if it is requested"""
pass
def status(self):
"""-> {"floor": int, "direction": "up"|"down"|"idle", "pending": sorted list of floors}"""
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter