15 - Design an Elevator

🎁 Twenty people press the elevator button at the same time on different floors. Which elevator goes where? This is an algorithm and state machine problem, not a distributed systems one.

Elevator design is an object-oriented design (OOD) problem, not a distributed systems problem. The challenge is dispatching multiple elevators efficiently to minimize wait time. It tests state machine design, scheduling algorithms, and handling concurrent requests. A different kind of system design question that appears in interviews at Google, Amazon, and Microsoft.

Elevator Requirements

Elevator Functional Requirements

• Handle hall calls (user presses up/down button on a floor)
• Handle car calls (user presses destination floor inside elevator)
• Dispatch the optimal elevator for each hall call
• Move elevators between floors, opening/closing doors
• Support 4-8 elevators in a 50-floor building

Elevator Non-Functional Requirements

Elevator Scope Exclusions

• Elevator hardware control (motor, sensors, door mechanisms)
• Multi-building management from a central system
• Predictive maintenance and fault detection

Elevator State Machine

No estimation step for this problem. Elevator design is an OOD (object-oriented design) problem. The challenge is algorithms and state management, not scale or storage. Traffic is bounded by building size (50 floors, 200 requests/min).

Each elevator is a state machine with clear transitions:

         ┌──────────┐
         │   IDLE   │
         └────┬─────┘
              │ (request received)
              ▼
         ┌──────────┐
    ┌───►│  MOVING  │◄───┐
    │    │  (UP/DN) │    │
    │    └────┬─────┘    │
    │         │ (arrived)│
    │         ▼          │
    │    ┌──────────┐    │
    │    │  STOPPED │────┘ (more stops in queue)
    │    │  (doors  │
    │    │   open)  │
    │    └────┬─────┘
    │         │ (no more stops)
    └─────────┘ → IDLE

States: IDLE (no requests), MOVING_UP, MOVING_DOWN, STOPPED (doors open)

Elevator Deep Dive

SCAN Algorithm

The baseline: move in one direction, serve all requests in that direction, then reverse.

Elevator on floor 5, moving UP, stops: [7, 12, 15]
  New request: floor 9 UP → insert: [7, 9, 12, 15]
  New request: floor 3 DOWN → serve after reversing

Why it works: Fair (every floor reached within two sweeps), predictable, no starvation. Same algorithm disk drives use for head scheduling.

Elevator Dispatch

With multiple elevators, score each one for a new hall call:

Score = estimated time to reach the requesting floor

Factors:
  - Distance from current position to request floor
  - Direction: moving toward request in same direction? (best)
  - Direction: moving toward but opposite direction? (must reverse first)
  - Direction: moving away? (must finish trip + come back)
  - Current load: nearly full? Skip it.

Assign to the elevator with the lowest score.

Example: Floor 12 presses UP.

• Elevator A: floor 10, moving UP → score: 2 (will pass by)
• Elevator B: floor 13, moving DOWN → score: 13 (must go down, reverse, come back)
• Elevator C: floor 20, IDLE → score: 8 (just distance)

→ Assign to Elevator A.

Two Queues Per Elevator

Each elevator maintains:

• Current direction stops: serve these now
• Opposite direction stops: serve after reversing

Moving UP from floor 5:
  up_stops:   [7, 9, 12]    ← serve now
  down_stops: [10, 4, 2]    ← serve after reversing at 12

This prevents unnecessary direction changes mid-trip.

Peak Traffic: Morning Rush

8-9 AM: everyone goes from lobby to their office floor. Standard SCAN performs poorly because all requests start from floor 1.

Solutions:

• Zoning: Elevator A serves floors 1-15, B serves 16-30, C serves 31-50. Fewer stops per trip.
• Destination dispatch: Passengers enter their floor at the lobby (not just up/down). System groups passengers going to similar floors into the same car.

Emergency Handling

FIRE MODE:
  → All elevators return to lobby
  → Doors open, passengers exit
  → Elevators go out of service
  → Only firefighter key re-enables

EMERGENCY STOP:
  → Stop motor immediately
  → Move to nearest floor if between floors
  → Open doors

Key Takeaways

• Each elevator is a state machine

  IDLE → MOVING → STOPPED → IDLE. Explicit states and transitions make the system testable and predictable.

• SCAN algorithm is the baseline

  Serve all requests in one direction, then reverse. Fair, no starvation, simple. Multi-elevator systems build scoring on top of this.

• Direction-aware scoring is key to good dispatch

  An elevator moving toward a request in the same direction is far better than a closer one moving away. Always factor in direction and remaining stops.

• Two queues per elevator prevent unnecessary reversals

  Current-direction stops served now. Opposite-direction stops queued for after reversal. Clean separation.

• Peak traffic needs special strategies

  Morning rush (everyone from lobby) breaks standard algorithms. Zoning and destination dispatch reduce stops per trip dramatically.

Want the full design? The example "Elevator System at Scale" covers capacity/weight awareness, destination dispatch implementation, monitoring metrics, and power failure handling.