Elevator System: State Machines Meet SCAN Dispatch

7.1Problem Statement

Design the control system for a building with multiple elevator cars serving many floors. Someone standing on a floor presses a hall button and states a direction; someone already inside a car presses a destination button. The system must route both kinds of requests to the right car, in the right order, without ever devolving into a pile of booleans.

Functional requirements:

• External (hall) requests: a button on a floor with a direction — UP or DOWN. The caller has no car yet; the system must find one.
• Internal (cabin) requests: a destination-floor button inside a car. The caller is already inside a specific car.
• A central dispatcher assigns each hall request to the most suitable car.
• Each car has a state: IDLE / MOVING_UP / MOVING_DOWN / DOORS_OPEN / MAINTENANCE.
• A car services its pending stops in a sensible order — the SCAN / elevator algorithm: keep going one direction, servicing everything on the way, then reverse — not strictly FIFO.

Non-functional requirements / constraints:

• The dispatch/scheduling strategy must be pluggable: nearest-car, least-load, direction-aware SCAN-scoring all need to drop in without touching the dispatcher.
• Car movement must be driven by state objects (the State pattern), never by a bag of booleans like movingUp / doorsOpen.
• Concurrency: many requests arrive simultaneously from different floors and must be handled safely.

Expected public interface:

enum class Direction { UP, DOWN, IDLE };

class DispatchStrategy {              // Strategy
public:
    virtual int selectCar(const HallRequest&, const std::vector<Elevator>&) = 0;
    virtual ~DispatchStrategy() = default;
};

class ElevatorController {
public:
    void requestElevator(int floor, Direction dir);   // external/hall call
    void step();                                       // advance the simulation one tick
};

class Elevator {
public:
    void addStop(int floor);                           // internal/cabin call
    void move();                                        // delegates to current state
    int  currentFloor() const;
    Direction direction() const;
};

What the interviewer is really testing:

• Whether you cleanly separate a hall request (needs dispatching to some car) from a cabin request (already bound to one car), and route each through a different entry point.
• A genuine State pattern for the car's mode, paired with a genuine Strategy for "which car answers this call" — two separate seams, not one tangled if-ladder.
• The request-ordering logic. Producing naive FIFO service is treated as a red flag at the SDE-3 level; SCAN is the expected answer.

Follow-up questions to expect:

1. Multiple cars with load balancing and a shared dispatcher.
2. Express / VIP elevators and floor restrictions (e.g. service floors).
3. Maintenance mode taking a car out of rotation safely.
4. Capacity / weight limits and skipping full cars.

7.2How to Approach

Mine the constraints before naming a single class

The prompt hands you the architecture if you read it literally. "Car movement is driven by state objects" names the State pattern for one axis: which mode is this car in right now. "The dispatch strategy must be pluggable" names the Strategy pattern for a completely different axis: given a hall call, which car should answer it. "Services requests in a sensible order (SCAN), not strictly FIFO" is the algorithmic differentiator the problem statement explicitly warns you about. And "hall request" versus "cabin request" is telling you there are two distinct entry points into the system, not one queue.

Nouns become classes

Circle the nouns — building, car, floor, hall request, cabin request, direction, dispatcher, state, strategy — and the class list falls out almost mechanically: a Direction enum; a HallRequest holding a floor and a direction; an ElevatorState interface with five concrete states (Idle, MovingUp, MovingDown, DoorsOpen, Maintenance); an Elevator that is the State pattern's Context — current floor, direction, current state, and its pending stops; a DispatchStrategy interface with a concrete NearestCarStrategy; and an ElevatorController that owns the fleet plus the injected strategy and drives the simulation. Spotting the Context+State triangle (Elevator + ElevatorState) and the Strategy seam (ElevatorController + DispatchStrategy) side by side is what makes the rest of the design feel inevitable rather than memorized.

Pin the interface, then work bottom-up from the leaves

Lock the public contract before internals. Elevator::move() should contain no logic of its own — it forwards to whatever state is current: state_->move(*this). ElevatorController::requestElevator() should be equally thin, forwarding to the injected strategy rather than deciding anything itself. If either of those hot methods grows an if, logic has leaked out of the abstraction it belongs in.

Then build bottom-up, starting with things that depend on nothing else: Direction and HallRequest. A cabin request, notably, needs no class at all — it's just an int destination floor handed to a car you already hold a handle to, via addStop(int). That asymmetry between "a hall request must be dispatched, a cabin request is already inside a car" is the hall-vs-cabin distinction the interviewer is probing. Not every noun in the problem statement deserves a class.

The load-bearing idea: SCAN via two sorted stop-sets

This is the heart of the problem. The naive approach — one FIFO queue of stops serviced in arrival order — is a trap the problem statement calls out directly: a car at floor 3 asked for stops [10, 1, 9] in that order would travel 3→10→1→9, bouncing the length of the shaft twice for no reason.

The fix is two sorted sets of pending stops per car: up_ holds stops at or above the current floor, served ascending; down_ holds stops at or below, served descending. Whichever direction the car is already moving, "the next stop this way" is just the front of the relevant set:

void add(int floor, int currentFloor) {
    if (floor > currentFloor)      up_.insert(floor);
    else if (floor < currentFloor) down_.insert(floor);
}
int nextUp()   const { return *up_.begin(); }     // lowest stop above
int nextDown() const { return *down_.rbegin(); }  // highest stop below

Because the sets stay sorted, finding the next stop in the current direction is O(log n), and the car only reverses once its current direction's set is empty — never mid-journey while work remains ahead. That's SCAN, and it falls out of the data structure rather than a hand-written ordering rule.

Context and states: data lives in Elevator, behavior lives in the states

Elevator (the Context) holds the current floor, direction, its StopBook of pending stops, and a non-owning pointer to whichever state is current — while owning all five state objects as unique_ptr members, since none of them carry per-car data and one instance of each is plenty. Each concrete state answers exactly one question every tick: what do I do, and what do I become? Idle does nothing. MovingUp/MovingDown step one floor toward the next stop in that direction, open the doors on arrival, and flip direction (or go idle) once their set empties. DoorsOpen is a one-tick pause that then resumes whichever direction still has work. Maintenance is frozen until explicitly taken out of rotation. Filling in every mode — including Maintenance doing nothing — is what "no flag soup" actually means: there is no reachable state left undefined.

The Strategy: pluggable dispatch, and where nearest-car alone breaks

NearestCarStrategy scores every car that is either idle or already heading the caller's requested direction, and picks whichever is geographically closest to the hall call. It is a reasonable default, and it is also incomplete on its own: it only ever answers "who is closest to this one request," blind to how many stops a car is already carrying. Under real traffic — a lobby at 9 a.m., say — nearest-car alone happily piles every nearby hall call onto one popular car while a car three floors farther away, but empty, sits idle. Distance is the wrong sole signal once load is uneven.

That gap is exactly the seam the first follow-up exploits: swap in a LeastLoadStrategy that scores by pending-stop count (or a blend of distance and load), and ElevatorController does not change a single line, because dispatch was injected as an interface from the start rather than hardcoded as an if-chain inside the controller.

Concurrency and the remaining follow-ups: seams, not redesigns

Concurrency gets a small, contained answer: one mutex in ElevatorController guarding the shared fleet, held for the duration of requestElevator, pressFloor, and step. The State/Strategy design does not bend to accommodate it.

The remaining follow-ups all resolve onto existing seams rather than new logic paths: multi-car load balancing is a new DispatchStrategy subclass; express/VIP floor restrictions are a predicate the strategy filters candidates on; maintenance mode is already a first-class state, so taking a car out of rotation safely just means finishing its current door cycle and calling setState(maintenance()), while the strategy skips any car reporting that state; capacity limits are one new field on Elevator plus a strategy filter. If every follow-up lands as a new subclass and never a new switch, the abstractions were right.

7.3Whole Solution

One synthesized, internally-consistent program: the ElevatorState interface with all five concrete car states, the StopBook SCAN bookkeeping (two sorted sets per car), the Elevator Context that owns and delegates to its states, the DispatchStrategy Strategy interface with a concrete NearestCarStrategy, an ElevatorController orchestrator wired with a mutex, and a driver whose whole point is to disprove FIFO: it requests floor 5, then a cabin stop at 2, then floor 8 — in that arrival order — and the ticked output must show the car stopping at 2, then 5, then 8, never 5 before 2.

// Elevator System -- State pattern (per-car mode) + Strategy pattern (dispatch)
// Two orthogonal axes: which MODE a car is in, and WHICH CAR serves a hall call.
// Builds with any C++17 compiler: g++ -std=c++17 elevator.cpp -o elevator

#include <iostream>
#include <vector>
#include <set>
#include <memory>
#include <mutex>
#include <string>
#include <limits>
#include <cstdlib>

// ---------- Direction & requests ----------
enum class Direction { UP, DOWN, IDLE };

// External call: someone on `floor` wants to travel `dir`. Not yet bound to a car.
struct HallRequest {
    int       floor;
    Direction dir;
};
// NOTE: a *cabin* request needs no class at all -- it is just a destination int
// handed to one specific car via Elevator::addStop(). That asymmetry IS the
// hall-vs-cabin distinction the interviewer is probing.

class Elevator;   // forward declaration -- ElevatorState needs only a reference for now

// ---------- SCAN bookkeeping: two sorted stop-sets per car ----------
class StopBook {
public:
    void add(int floor, int currentFloor) {
        if (floor > currentFloor)      up_.insert(floor);
        else if (floor < currentFloor) down_.insert(floor);
        // floor == currentFloor: caller handles "open here"
    }
    bool hasUp()   const { return !up_.empty(); }
    bool hasDown() const { return !down_.empty(); }
    bool empty()   const { return up_.empty() && down_.empty(); }

    int  nextUp()   const { return *up_.begin(); }     // lowest stop above
    int  nextDown() const { return *down_.rbegin(); }  // highest stop below
    void reachedUp(int f)   { up_.erase(f); }
    void reachedDown(int f) { down_.erase(f); }

private:
    std::set<int> up_;
    std::set<int> down_;
};

// ---------- State pattern: one interface, five car modes ----------
class ElevatorState {
public:
    virtual ~ElevatorState() = default;
    virtual void        move(Elevator&) = 0;      // one simulation tick
    virtual Direction   direction() const = 0;     // what this mode reports
    virtual std::string name() const = 0;
};

// ---------- Context: the physical car ----------
class Elevator {
public:
    Elevator(int id, int startFloor);              // starts IDLE

    // ---- public API ----
    void addStop(int floor) {
        if (floor == floor_) { openDoorsHere(); return; }
        stops_.add(floor, floor_);
        wakeIfIdle();                               // an idle car must pick a direction
    }
    void      move() { state_->move(*this); }       // pure delegation -- one tick
    int       currentFloor() const { return floor_; }
    Direction direction()    const { return dir_; }

    // ---- helpers the STATES use to drive the car ----
    void setState(ElevatorState* s) { state_ = s; }
    ElevatorState* idle();
    ElevatorState* movingUp();
    ElevatorState* movingDown();
    ElevatorState* doorsOpen();
    ElevatorState* maintenance();

    StopBook& stops()         { return stops_; }
    int  floor() const        { return floor_; }
    void stepFloor(int delta) { floor_ += delta; }   // physically move one floor
    void setDirection(Direction d) { dir_ = d; }
    void openDoorsHere();            // erase stop at floor_, go to DoorsOpen
    void wakeIfIdle();               // if currently idle and stops exist, choose a direction

    int  id() const { return id_; }

private:
    int id_;
    int floor_;
    Direction dir_ = Direction::IDLE;
    StopBook stops_;
    std::unique_ptr<ElevatorState> idle_, up_, down_, doors_, maint_;  // car OWNS its states
    ElevatorState* state_ = nullptr;                                   // current (non-owning view)
};

// ---------- Concrete states: each answers "what do I do, and what do I become?" ----------

class IdleState : public ElevatorState {
public:
    void move(Elevator&) override { /* nothing pending; stay put */ }
    Direction direction() const override { return Direction::IDLE; }
    std::string name() const override { return "IDLE"; }
};

class MovingUpState : public ElevatorState {
public:
    void move(Elevator& e) override {
        if (!e.stops().hasUp()) {                  // nothing left above
            if (e.stops().hasDown()) { e.setDirection(Direction::DOWN); e.setState(e.movingDown()); }
            else                     { e.setDirection(Direction::IDLE); e.setState(e.idle()); }
            return;
        }
        int target = e.stops().nextUp();
        if (e.floor() == target) { e.openDoorsHere(); return; }   // arrived -> doors
        e.stepFloor(+1);                                          // climb one floor
        if (e.floor() == target) e.openDoorsHere();
    }
    Direction direction() const override { return Direction::UP; }
    std::string name() const override { return "MOVING_UP"; }
};

class MovingDownState : public ElevatorState {
public:
    void move(Elevator& e) override {
        if (!e.stops().hasDown()) {
            if (e.stops().hasUp()) { e.setDirection(Direction::UP); e.setState(e.movingUp()); }
            else                   { e.setDirection(Direction::IDLE); e.setState(e.idle()); }
            return;
        }
        int target = e.stops().nextDown();
        if (e.floor() == target) { e.openDoorsHere(); return; }
        e.stepFloor(-1);
        if (e.floor() == target) e.openDoorsHere();
    }
    Direction direction() const override { return Direction::DOWN; }
    std::string name() const override { return "MOVING_DOWN"; }
};

class DoorsOpenState : public ElevatorState {
public:
    void move(Elevator& e) override {
        // doors were open this tick; close and resume whichever way still has work
        if (e.stops().hasUp() && e.direction() != Direction::DOWN) {
            e.setDirection(Direction::UP);   e.setState(e.movingUp());
        } else if (e.stops().hasDown()) {
            e.setDirection(Direction::DOWN); e.setState(e.movingDown());
        } else if (e.stops().hasUp()) {
            e.setDirection(Direction::UP);   e.setState(e.movingUp());
        } else {
            e.setDirection(Direction::IDLE); e.setState(e.idle());
        }
    }
    Direction direction() const override { return Direction::IDLE; } // physically stopped
    std::string name() const override { return "DOORS_OPEN"; }
};

class MaintenanceState : public ElevatorState {
public:
    void move(Elevator&) override { /* frozen until taken out of maintenance */ }
    Direction direction() const override { return Direction::IDLE; }
    std::string name() const override { return "MAINTENANCE"; }
};

// ---------- Wire the Context: constructor + accessors + shared transition helpers ----------

Elevator::Elevator(int id, int startFloor) : id_(id), floor_(startFloor) {
    idle_  = std::make_unique<IdleState>();
    up_    = std::make_unique<MovingUpState>();
    down_  = std::make_unique<MovingDownState>();
    doors_ = std::make_unique<DoorsOpenState>();
    maint_ = std::make_unique<MaintenanceState>();
    state_ = idle_.get();           // start IDLE
}
ElevatorState* Elevator::idle()        { return idle_.get(); }
ElevatorState* Elevator::movingUp()    { return up_.get(); }
ElevatorState* Elevator::movingDown()  { return down_.get(); }
ElevatorState* Elevator::doorsOpen()   { return doors_.get(); }
ElevatorState* Elevator::maintenance() { return maint_.get(); }

void Elevator::openDoorsHere() {
    stops_.reachedUp(floor_);     // erase the stop here from whichever set held it
    stops_.reachedDown(floor_);
    setState(doorsOpen());
}
void Elevator::wakeIfIdle() {
    if (state_ != idle_.get()) return;              // already moving / in doors
    if (stops_.hasUp())        { dir_ = Direction::UP;   setState(movingUp()); }
    else if (stops_.hasDown()) { dir_ = Direction::DOWN; setState(movingDown()); }
}

// ---------- Strategy pattern: pluggable "which car serves this hall call?" ----------
class DispatchStrategy {
public:
    virtual ~DispatchStrategy() = default;
    virtual int selectCar(const HallRequest&, const std::vector<Elevator>&) = 0;   // returns car index
};

class NearestCarStrategy : public DispatchStrategy {
public:
    int selectCar(const HallRequest& req, const std::vector<Elevator>& cars) override {
        int best = -1, bestDist = std::numeric_limits<int>::max();
        for (int i = 0; i < static_cast<int>(cars.size()); ++i) {
            const Elevator& c = cars[i];
            // prefer cars idle, or already moving toward the request in the same direction
            bool suitable = c.direction() == Direction::IDLE
                         || c.direction() == req.dir;
            if (!suitable) continue;
            int dist = std::abs(c.currentFloor() - req.floor);
            if (dist < bestDist) { bestDist = dist; best = i; }
        }
        if (best == -1) best = 0;   // fallback: everyone busy the wrong way -> car 0
        return best;
    }
};

// ---------- Orchestrator: owns the cars + the strategy, routes calls, ticks the sim ----------
class ElevatorController {
public:
    ElevatorController(int numCars, std::unique_ptr<DispatchStrategy> strategy)
        : strategy_(std::move(strategy)) {
        for (int i = 0; i < numCars; ++i)
            cars_.emplace_back(i, /*startFloor=*/0);
    }

    // external/hall call: pick a car via the strategy, then push the stop onto it
    void requestElevator(int floor, Direction dir) {
        std::lock_guard<std::mutex> lock(mtx_);
        HallRequest req{floor, dir};
        int idx = strategy_->selectCar(req, cars_);
        cars_[idx].addStop(floor);          // assigned car will SCAN to it
    }

    // cabin call: passenger already inside car `carId`
    void pressFloor(int carId, int dest) {
        std::lock_guard<std::mutex> lock(mtx_);
        cars_[carId].addStop(dest);
    }

    void step() {                            // advance every car one tick
        std::lock_guard<std::mutex> lock(mtx_);
        for (auto& c : cars_) c.move();
    }

    const Elevator& car(int i) const { return cars_[i]; }

private:
    std::vector<Elevator> cars_;
    std::unique_ptr<DispatchStrategy> strategy_;
    std::mutex mtx_;                         // guards cars_ against concurrent requests
};

// ---------- Driver: proves SCAN, not FIFO ----------
int main() {
    ElevatorController controller(/*numCars=*/1, std::make_unique<NearestCarStrategy>());

    // Car starts at floor 0. Requests arrive "out of order": hall(5,UP), cabin(2), hall(8,UP).
    controller.requestElevator(5, Direction::UP);
    controller.pressFloor(0, 2);     // cabin request inside car 0
    controller.requestElevator(8, Direction::UP);

    // SCAN must serve them ascending: 2, then 5, then 8 -- never 5, 2, 8 (that would be FIFO).
    for (int tick = 0; tick < 12; ++tick) {
        controller.step();
        const Elevator& c = controller.car(0);
        std::cout << "tick " << tick << ": floor " << c.currentFloor() << "\n";
    }
    return 0;
}

State pattern

One interface (ElevatorState), several concrete implementations (Idle, MovingUp, MovingDown, DoorsOpen, Maintenance), and one Context (Elevator) that holds a pointer to the current state and delegates its hot method to it. The car's own code never branches on "what mode am I in" — the current state object is the answer.

Strategy pattern

One interface (DispatchStrategy), one or more interchangeable policies (NearestCarStrategy, and later LeastLoadStrategy), and one context (ElevatorController) that asks the injected strategy "which car?" and never hardcodes the rule itself.

SCAN (elevator algorithm)

Keep serving stops in the current direction of travel until none remain ahead, then reverse. Implemented here as two sorted sets of pending stops (up_, down_) so "next stop this way" is an O(log n) lookup instead of an O(n) scan or a FIFO bounce.

lock_guard / RAII

A stack object that acquires a mutex on construction and releases it on destruction, including on an exception path. ElevatorController uses one around every method that touches the shared fleet, keeping the concurrency answer entirely at the orchestrator boundary.