Elevator System

medium · state machine, SCAN scheduling

Brief-reported interview attribution (unverified): Amazon, Microsoft

How to approach an LLD round

Requirements

  • 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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.

  2. The GraderCharacter joke · No posting date

    Your solution is correct. Your variable names are a crime scene.

  3. TryGetValueCharacter joke · No posting date

    I found the bug. It was me. I was the bug.