41 — LLD: Elevator / Lift System

Frequently Asked at Salesforce — Reported repeatedly in SMTS technical rounds (2024-2026).

Understanding the Problem

Design a control system for a building with several elevators serving many floors. External panels on each floor press Up or Down. Internal panels inside the car press a destination. A central dispatcher routes external requests to the best car, and each car independently moves, opens doors, and switches direction.

What is the Elevator problem?

It is the canonical State-pattern exercise. Each car has distinct behaviour in Idle, MovingUp, MovingDown, and DoorsOpen modes, and the dispatcher scores which car should handle a new request without stalling passengers mid-travel.

---

Requirements

Clarifying Questions

You: How do we resolve ties between equally close cars?

Interviewer: Prefer idle, then lowest ID.

Scoring strategy needs an idleBonus component.

You: Can a passenger inside redirect the car?

Interviewer: They can add stops but not reverse direction mid-travel.

State-pattern canAccept enforces direction invariants.

You: Do we need VIP or express modes?

Interviewer: Not for v1.

Scoped out but the interface must allow it later.

You: Event-driven simulation or a real-time ticker?

Interviewer: Tick-based — a step is called every simulated second.

Simplifies testability; each state has an onTick.

You: Multiple controllers or one?

Interviewer: One central dispatcher.

Singleton dispatcher.

You: Capacity limits?

Interviewer: Yes, ten passengers per car. Reject external assignment if full.

isFull() gates canAccept.

Final Requirements

1. N elevator cars, F floors.
2. External requests carry a direction; internal requests carry a destination.
3. Dispatcher scores every car and assigns the best one.
4. Each car transitions through Idle → MovingUp/MovingDown → DoorsOpen → Idle.
5. Passengers inside may add stops in the current direction.
6. Full cars do not accept new external requests.
7. Thread-safe dispatch and tick.

Out of scope: emergency, fire-service mode, cross-building networking, physical safety interlocks.

---

Core Entities and Relationships

Entity	Responsibility
Direction	Enum: Up, Down, Idle.
ExternalRequest	{floor, direction} from a floor panel.
InternalRequest	Destination floor from inside the car.
ElevatorStateHandler	Per-state behaviour for onTick and canAccept.
IdleState / MovingUpState / MovingDownState / DoorsOpenState	Concrete state classes.
ElevatorCar	Owns floor, direction, stops, capacity, occupants.
ScoringStrategy	Pluggable cost function (nearest, fewest-stops).
Dispatcher	Receives requests, scores cars, adds stops.

Why a class per state? Because each state answers canAccept and onTick differently. A switch statement works for two states but rots as features are added.

Why a pluggable ScoringStrategy? Salesforce loves pluggability. Peak-hour optimisation later swaps in a different strategy without touching the dispatcher.

Design is iterative — start with one strategy and two states, evolve.

---

Class Design

ElevatorCar

State:

• id: int
• floor: int
• direction: Direction
• stops: Set<int>
• capacity: int, occupants: int
• state: ElevatorStateHandler

Methods:

• tick() — delegate to state
• addStop(floor)
• canAccept(req) — combines capacity and state rules

ElevatorStateHandler (interface)

Methods:

• onTick(car) — advance one step
• canAccept(car, req) — can this state take the new request?

Dispatcher

Methods:

• dispatch(req) — score all cars, add stop on the winner
• tick() — fire every car's onTick

Design principles at play:

• State Pattern — behaviour changes with state, not with flags.
• Strategy Pattern — ScoringStrategy is pluggable.
• Single Responsibility — car moves, dispatcher routes, states decide acceptance.
• Open/Closed — adding ExpressState or MaintenanceState requires zero changes to existing states.

---

Implementation

Core Logic: Dispatch

The subtle edge case is mid-travel requests: a car moving up at floor 5 should not accept an up-request from floor 3. The floor-3 user wants to go up, but this car is past them. MovingUpState.canAccept enforces req.floor >= car.floor.

Bad approach: always pick nearest car.

• Breaks mid-travel rule; passengers already inside get detoured.

Good approach: filter by canAccept first, then score by distance.

• Correct, O(N·log N) with a sort; fine for a few cars.

Great approach: same filter, but use idleBonus and directionAlignmentBonus inside ScoringStrategy so the scorer tells the whole story.

• Encapsulated; easy to swap at peak hours.

Verification

Three cars: C1 idle at 3, C2 MovingUp at 5 with stop {8}, C3 idle at 7.

1. External up request from floor 6. canAccept: C1 true, C2 true (5 ≤ 6 ≤ 8 — wait, C2 is moving up past floor 5 so floor 6 is ahead), C3 true but going down would mean reversing. Scores (nearest + idleBonus): C1 = 3 + (-1) = 2, C2 = 1 + 0 = 1, C3 = 1 + (-1) = 0. Winner C3. Stop added.
2. Tick: C2 floor becomes 6, then 7, 8 (DoorsOpen); C3 goes up to 6.
3. After DoorsOpen 3 ticks, C2 transitions to Idle because stops empty.

Thread Safety

• dispatch reads shared cars and mutates stops — guard each car with its own lock.
• Scoring under a read-only view, then tryAddStop on the winner atomically.
• Ticking and dispatching must not interleave arbitrarily — either a single-threaded dispatch loop or a per-car lock held during tick.
• For multi-building deployments, partition cars across dispatcher shards.

Complete Code Implementation

Java

import java.util.*;
import java.util.concurrent.*;

enum Direction { UP, DOWN, IDLE }

record ExternalRequest(int floor, Direction direction) {}

interface ElevatorStateHandler {
    String name();
    void onTick(ElevatorCar car);
    boolean canAccept(ElevatorCar car, ExternalRequest req);
}

class IdleState implements ElevatorStateHandler {
    public String name() { return "IDLE"; }
    public void onTick(ElevatorCar car) {
        Integer next = car.pickNextStop();
        if (next == null) return;
        if (next > car.floor) { car.direction = Direction.UP; car.setState(new MovingUpState()); }
        else { car.direction = Direction.DOWN; car.setState(new MovingDownState()); }
    }
    public boolean canAccept(ElevatorCar c, ExternalRequest r) { return true; }
}

class MovingUpState implements ElevatorStateHandler {
    public String name() { return "MOVING_UP"; }
    public void onTick(ElevatorCar car) {
        car.floor++;
        if (car.stops.remove(car.floor)) car.setState(new DoorsOpenState());
        else if (car.stops.isEmpty()) { car.direction = Direction.IDLE; car.setState(new IdleState()); }
    }
    public boolean canAccept(ElevatorCar c, ExternalRequest r) {
        return r.direction() == Direction.UP && r.floor() >= c.floor;
    }
}

class MovingDownState implements ElevatorStateHandler {
    public String name() { return "MOVING_DOWN"; }
    public void onTick(ElevatorCar car) {
        car.floor--;
        if (car.stops.remove(car.floor)) car.setState(new DoorsOpenState());
        else if (car.stops.isEmpty()) { car.direction = Direction.IDLE; car.setState(new IdleState()); }
    }
    public boolean canAccept(ElevatorCar c, ExternalRequest r) {
        return r.direction() == Direction.DOWN && r.floor() <= c.floor;
    }
}

class DoorsOpenState implements ElevatorStateHandler {
    private int ticks = 0;
    public String name() { return "DOORS_OPEN"; }
    public void onTick(ElevatorCar car) {
        if (++ticks >= 3) {
            if (car.stops.isEmpty()) { car.direction = Direction.IDLE; car.setState(new IdleState()); }
            else if (car.direction == Direction.UP) car.setState(new MovingUpState());
            else car.setState(new MovingDownState());
        }
    }
    public boolean canAccept(ElevatorCar c, ExternalRequest r) { return false; }
}

class ElevatorCar {
    public final int id;
    public int floor = 0;
    public Direction direction = Direction.IDLE;
    public final Set<Integer> stops = ConcurrentHashMap.newKeySet();
    public int capacity = 10, occupants = 0;
    private ElevatorStateHandler state = new IdleState();
    private final Object lock = new Object();

    public ElevatorCar(int id) { this.id = id; }
    public synchronized void setState(ElevatorStateHandler s) { this.state = s; }
    public synchronized void tick() { state.onTick(this); }
    public void addStop(int f) { stops.add(f); }
    public Integer pickNextStop() {
        if (stops.isEmpty()) return null;
        return stops.stream().min(Comparator.comparingInt(s -> Math.abs(s - floor))).orElseThrow();
    }
    public boolean isFull() { return occupants >= capacity; }
    public synchronized boolean canAccept(ExternalRequest r) { return !isFull() && state.canAccept(this, r); }
    public String stateName() { return state.name(); }
}

interface ScoringStrategy { int score(ElevatorCar car, ExternalRequest req); }

class NearestCarStrategy implements ScoringStrategy {
    public int score(ElevatorCar c, ExternalRequest r) {
        if (!c.canAccept(r)) return Integer.MAX_VALUE;
        int base = Math.abs(c.floor - r.floor());
        return base + (c.direction == Direction.IDLE ? -1 : 0);
    }
}

class Dispatcher {
    private final List<ElevatorCar> cars;
    private final ScoringStrategy strategy;
    public Dispatcher(List<ElevatorCar> cars, ScoringStrategy s) { this.cars = cars; this.strategy = s; }

    public ElevatorCar dispatch(ExternalRequest req) {
        ElevatorCar best = null; int bestScore = Integer.MAX_VALUE;
        for (ElevatorCar c : cars) {
            int s = strategy.score(c, req);
            if (s < bestScore) { best = c; bestScore = s; }
        }
        if (best != null) best.addStop(req.floor());
        return best;
    }
    public void tick() { for (ElevatorCar c : cars) c.tick(); }
}

C++

#include <algorithm>
#include <climits>
#include <memory>
#include <mutex>
#include <set>
#include <vector>

enum class Direction { Up, Down, Idle };
struct ExternalRequest { int floor; Direction direction; };

class ElevatorCar;
struct StateHandler {
    virtual const char* name() = 0;
    virtual void onTick(ElevatorCar& car) = 0;
    virtual bool canAccept(ElevatorCar& car, const ExternalRequest& r) = 0;
};

class ElevatorCar {
public:
    int id, floor = 0, capacity = 10, occupants = 0;
    Direction direction = Direction::Idle;
    std::set<int> stops;
    std::mutex mu;
    std::shared_ptr<StateHandler> state;

    explicit ElevatorCar(int id_);
    void tick() { std::lock_guard<std::mutex> g(mu); state->onTick(*this); }
    void setState(std::shared_ptr<StateHandler> s) { state = s; }
    void addStop(int f) { std::lock_guard<std::mutex> g(mu); stops.insert(f); }
    int pickNextStop() {
        if (stops.empty()) return -1;
        return *std::min_element(stops.begin(), stops.end(), [&](int a, int b){
            return std::abs(a - floor) < std::abs(b - floor);
        });
    }
    bool isFull() { return occupants >= capacity; }
    bool canAccept(const ExternalRequest& r) {
        std::lock_guard<std::mutex> g(mu);
        return !isFull() && state->canAccept(*this, r);
    }
};

class IdleState : public StateHandler {
public:
    const char* name() override { return "IDLE"; }
    void onTick(ElevatorCar& car) override;
    bool canAccept(ElevatorCar&, const ExternalRequest&) override { return true; }
};
class MovingUpState : public StateHandler {
public:
    const char* name() override { return "MOVING_UP"; }
    void onTick(ElevatorCar& car) override;
    bool canAccept(ElevatorCar& c, const ExternalRequest& r) override {
        return r.direction == Direction::Up && r.floor >= c.floor;
    }
};
class MovingDownState : public StateHandler {
public:
    const char* name() override { return "MOVING_DOWN"; }
    void onTick(ElevatorCar& car) override;
    bool canAccept(ElevatorCar& c, const ExternalRequest& r) override {
        return r.direction == Direction::Down && r.floor <= c.floor;
    }
};
class DoorsOpenState : public StateHandler {
    int ticks = 0;
public:
    const char* name() override { return "DOORS_OPEN"; }
    void onTick(ElevatorCar& car) override;
    bool canAccept(ElevatorCar&, const ExternalRequest&) override { return false; }
};

ElevatorCar::ElevatorCar(int id_) : id(id_), state(std::make_shared<IdleState>()) {}

void IdleState::onTick(ElevatorCar& car) {
    int next = car.pickNextStop();
    if (next < 0) return;
    if (next > car.floor) { car.direction = Direction::Up; car.setState(std::make_shared<MovingUpState>()); }
    else { car.direction = Direction::Down; car.setState(std::make_shared<MovingDownState>()); }
}
void MovingUpState::onTick(ElevatorCar& car) {
    car.floor++;
    if (car.stops.erase(car.floor)) car.setState(std::make_shared<DoorsOpenState>());
    else if (car.stops.empty()) { car.direction = Direction::Idle; car.setState(std::make_shared<IdleState>()); }
}
void MovingDownState::onTick(ElevatorCar& car) {
    car.floor--;
    if (car.stops.erase(car.floor)) car.setState(std::make_shared<DoorsOpenState>());
    else if (car.stops.empty()) { car.direction = Direction::Idle; car.setState(std::make_shared<IdleState>()); }
}
void DoorsOpenState::onTick(ElevatorCar& car) {
    if (++ticks >= 3) {
        if (car.stops.empty()) { car.direction = Direction::Idle; car.setState(std::make_shared<IdleState>()); }
        else if (car.direction == Direction::Up) car.setState(std::make_shared<MovingUpState>());
        else car.setState(std::make_shared<MovingDownState>());
    }
}

struct ScoringStrategy { virtual int score(ElevatorCar& c, const ExternalRequest& r) = 0; };
class NearestCarStrategy : public ScoringStrategy {
public:
    int score(ElevatorCar& c, const ExternalRequest& r) override {
        if (!c.canAccept(r)) return INT_MAX;
        int base = std::abs(c.floor - r.floor);
        return base + (c.direction == Direction::Idle ? -1 : 0);
    }
};

class Dispatcher {
    std::vector<std::shared_ptr<ElevatorCar>> cars;
    std::shared_ptr<ScoringStrategy> strategy;
public:
    Dispatcher(std::vector<std::shared_ptr<ElevatorCar>> c, std::shared_ptr<ScoringStrategy> s)
        : cars(std::move(c)), strategy(std::move(s)) {}
    std::shared_ptr<ElevatorCar> dispatch(const ExternalRequest& req) {
        std::shared_ptr<ElevatorCar> best; int bestScore = INT_MAX;
        for (auto& c : cars) {
            int s = strategy->score(*c, req);
            if (s < bestScore) { best = c; bestScore = s; }
        }
        if (best) best->addStop(req.floor);
        return best;
    }
    void tick() { for (auto& c : cars) c->tick(); }
};

TypeScript

enum Direction { Up = 1, Down = -1, Idle = 0 }

interface ExternalRequest { floor: number; direction: Direction; }

interface ElevatorStateHandler {
  readonly name: "IDLE" | "MOVING_UP" | "MOVING_DOWN" | "DOORS_OPEN";
  onTick(car: ElevatorCar): void;
  canAccept(car: ElevatorCar, req: ExternalRequest): boolean;
}

class IdleState implements ElevatorStateHandler {
  readonly name = "IDLE" as const;
  onTick(car: ElevatorCar) {
    const next = car.pickNextStop();
    if (next === null) return;
    car.setDirection(next > car.floor ? Direction.Up : Direction.Down);
    car.setState(next > car.floor ? new MovingUpState() : new MovingDownState());
  }
  canAccept(_car: ElevatorCar, _req: ExternalRequest) { return true; }
}

class MovingUpState implements ElevatorStateHandler {
  readonly name = "MOVING_UP" as const;
  onTick(car: ElevatorCar) {
    car.floor += 1;
    if (car.stops.has(car.floor)) {
      car.stops.delete(car.floor);
      car.setState(new DoorsOpenState());
    } else if (car.stops.size === 0) {
      car.setDirection(Direction.Idle);
      car.setState(new IdleState());
    }
  }
  canAccept(car: ElevatorCar, req: ExternalRequest) {
    return req.direction === Direction.Up && req.floor >= car.floor;
  }
}

class MovingDownState implements ElevatorStateHandler {
  readonly name = "MOVING_DOWN" as const;
  onTick(car: ElevatorCar) {
    car.floor -= 1;
    if (car.stops.has(car.floor)) {
      car.stops.delete(car.floor);
      car.setState(new DoorsOpenState());
    } else if (car.stops.size === 0) {
      car.setDirection(Direction.Idle);
      car.setState(new IdleState());
    }
  }
  canAccept(car: ElevatorCar, req: ExternalRequest) {
    return req.direction === Direction.Down && req.floor <= car.floor;
  }
}

class DoorsOpenState implements ElevatorStateHandler {
  readonly name = "DOORS_OPEN" as const;
  private ticksOpen = 0;
  onTick(car: ElevatorCar) {
    this.ticksOpen += 1;
    if (this.ticksOpen >= 3) {
      car.setState(car.stops.size === 0 ? new IdleState() :
        car.direction === Direction.Up ? new MovingUpState() : new MovingDownState());
    }
  }
  canAccept(_c: ElevatorCar, _r: ExternalRequest) { return false; }
}

class ElevatorCar {
  floor = 0;
  direction: Direction = Direction.Idle;
  stops = new Set<number>();
  capacity = 10;
  occupants = 0;
  private state: ElevatorStateHandler = new IdleState();

  constructor(public readonly id: number) {}
  setState(s: ElevatorStateHandler) { this.state = s; }
  setDirection(d: Direction) { this.direction = d; }
  tick() { this.state.onTick(this); }
  addStop(floor: number) { this.stops.add(floor); }
  pickNextStop(): number | null {
    if (this.stops.size === 0) return null;
    return [...this.stops].sort((a, b) => Math.abs(a - this.floor) - Math.abs(b - this.floor))[0];
  }
  isFull() { return this.occupants >= this.capacity; }
  stateName() { return this.state.name; }
  canAccept(req: ExternalRequest) { return !this.isFull() && this.state.canAccept(this, req); }
}

interface ScoringStrategy { score(car: ElevatorCar, req: ExternalRequest): number; }
class NearestCarStrategy implements ScoringStrategy {
  score(car: ElevatorCar, req: ExternalRequest): number {
    if (!car.canAccept(req)) return Number.POSITIVE_INFINITY;
    const base = Math.abs(car.floor - req.floor);
    const idleBonus = car.direction === Direction.Idle ? -1 : 0;
    return base + idleBonus;
  }
}

class Dispatcher {
  constructor(private cars: ElevatorCar[], private strategy: ScoringStrategy) {}
  dispatch(req: ExternalRequest): ElevatorCar | null {
    let best: ElevatorCar | null = null;
    let bestScore = Number.POSITIVE_INFINITY;
    for (const c of this.cars) {
      const s = this.strategy.score(c, req);
      if (s < bestScore) { best = c; bestScore = s; }
    }
    if (best) best.addStop(req.floor);
    return best;
  }
  tick() { for (const c of this.cars) c.tick(); }
}

---

Extensibility

1. "Express mode that skips odd floors"

Introduce ExpressMovingUpState that only considers even floors in stops. Because setState is a single call, peak-hour mode toggle becomes a dispatcher-level flag.

class ExpressMovingUpState extends MovingUpState {
  onTick(car: ElevatorCar) {
    car.floor += 1;
    if (car.floor % 2 === 0 && car.stops.has(car.floor)) {
      car.stops.delete(car.floor);
      car.setState(new DoorsOpenState());
    }
  }
}

2. "Peak-hour optimisation"

Swap ScoringStrategy at runtime. Morning rush favours cars near the lobby; evening rush prioritises descending cars.

3. "Emergency floor priority"

A PriorityRequest with a preempt flag. Dispatcher.dispatch short-circuits on preempt and clears the winner's pending stops. Keeps the request interface additive.

---

What is Expected at Each Level

Level	Expectations
Mid	One elevator, direction switching via if-else, passes a basic test.
Senior / SMTS	Multi-car with State + Strategy, correctly enforces mid-travel direction rules, explicit ticking model, mentions per-car locks.
Staff	Peak-hour profiling, simulation-driven capacity planning, fault tolerance when a car goes offline, multi-building partitioning.