Designing an elevator system is a classic Low-Level Design (LLD) machine coding round question. It tests an engineer's ability to manage complex state transitions, design thread-safe concurrent systems, and implement highly optimized scheduling algorithms.
A naive approach to scheduling, such as First-Come-First-Serve (FCFS), causes the elevator car to bounce wildly between distant floors, creating catastrophic wait times and massive mechanical wear-and-tear. In this comprehensive guide, we will architect a highly scalable, multi-car elevator control system utilizing the industry-standard SCAN scheduling algorithm, SOLID-compliant Java models, and concurrent dispatch mechanics.
System Requirements and Goals
To build a professional elevator control system, we must establish strict functional and operational boundaries.
1. Functional Requirements
- Multi-Elevator Control: Intelligently orchestrate $M$ elevator cars across $N$ floors in a skyscraper.
- External Hall Calls: Manage requests from passengers standing on floors pressing
UPorDOWNcall buttons. - Internal Car Calls: Allow passengers inside a specific car to select destination floors.
- Intelligent Passenger Pickups: Elevators must pick up passengers on their way if they are travelling in the same direction.
- Real-time Status Displays: Continuously export the location (floor) and moving direction of each active elevator car.
2. Non-Functional Constraints
- Minimized Wait & Travel Time: The scheduling algorithm must optimize average passenger wait and transit times.
- Starvation-Free (Fairness): No passenger or floor request should wait indefinitely due to constant pickups elsewhere.
- High Concurrency: The system must handle thousands of simultaneous button presses from multiple floors without state corruption.
- Decoupled Strategy: The dispatch algorithm must be easily swappable at runtime to support different zoning layouts (e.g. low-rise vs high-rise towers).
3. Sizing and Capacity Math
Let's conduct an operational capacity estimation for a 50-story high-rise building equipped with 8 elevator cars during morning rush hour:
-
Total Floors ($N$): 50
-
Elevator Cars ($M$): 8
-
Simultaneous Passenger Calls: At peak, up to $200$ button presses occur every 10 seconds.
-
Suitability Score Calculation: To allocate the most optimal car for an incoming request, the dispatcher calculates a Suitability Score (SS) for each car: $$\text{SS} = (N - d) + \text{DirectionPenalty}$$ Where:
- $d$ is the absolute distance (in floors) between the elevator car and the request floor.
- $\text{DirectionPenalty}$ is:
- $0$ (No Penalty): If the car is moving towards the request floor and is in the same direction.
- $10$: If the car is IDLE.
- $20$: If the car is moving away from the request floor or in the opposite direction.
For example, if a user on Floor 10 requests an
UPride:- Car A: Floor 6, moving
UP($d = 4$). $\text{SS} = (50 - 4) + 0 = 46$. - Car B: Floor 15, moving
DOWN($d = 5$). $\text{SS} = (50 - 5) + 20 = 25$. - Car C: Floor 10, IDLE ($d = 0$). $\text{SS} = (50 - 0) + 10 = 40$.
Car A is selected over the idle Car C because Car A is already moving in the desired direction and is extremely close, making it the most efficient choice to pick up the passenger on its path. This math forms the core of high-throughput dispatch algorithms.
API Design and Interface Contracts
Clients and external displays interact with the elevator control system using standard REST and WebSocket protocols.
1. Request an Elevator (Hall Call)
POST /v1/elevator/hall-call
Request Payload:
{
"request_floor": 10,
"direction": "UP",
"source_timestamp_ms": 1778942000000
}
Response Payload (202 Accepted):
{
"request_id": "req-98765-abc",
"assigned_elevator_id": "car-3",
"estimated_arrival_seconds": 12,
"status": "QUEUED"
}
2. Select Destination Floor (Car Call)
POST /v1/elevator/car-call
Request Payload:
{
"elevator_id": "car-3",
"destination_floor": 22
}
Response Payload (200 OK):
{
"elevator_id": "car-3",
"active_destination_queue": [12, 18, 22],
"status": "MOVING"
}
High-Level Design Architecture
The elevator control system separates physical car mechanics from global routing strategies to ensure modularity and extensibility.
1. Class Diagram (Component Schema)
The system is modeled using clear object-oriented boundaries. The ElevatorSystem acts as the primary facade, delegating request routing to Dispatcher (which implements the Swappable Strategy Design Pattern), and controlling the individual ElevatorCar actors.
classDiagram
class ElevatorSystem {
-List~ElevatorCar~ cars
-Dispatcher dispatcher
+requestElevator(int floor, Direction dir)
}
class Dispatcher {
-DispatchStrategy strategy
+assignRequest(List~ElevatorCar~ cars, Request req)
}
class DispatchStrategy {
<<interface>>
+selectOptimalCar(List~ElevatorCar~ cars, Request req) ElevatorCar
}
class SuitabilityDispatchStrategy {
+selectOptimalCar(List~ElevatorCar~ cars, Request req) ElevatorCar
}
class ElevatorCar {
-int id
-int currentFloor
-Direction direction
-ElevatorState state
-TreeSet~Integer~ upQueue
-TreeSet~Integer~ downQueue
+addDestination(int floor)
+run()
}
ElevatorSystem *-- ElevatorCar
ElevatorSystem *-- Dispatcher
Dispatcher *-- DispatchStrategy
DispatchStrategy <|.. SuitabilityDispatchStrategy
2. Sequence Flow of a Hall Call
The diagram below details the operational flow of a user pressing the UP button on Floor 10, calculating the optimal car allocation, and waking up the car's sweep thread.
sequenceDiagram
autonumber
actor User as Passenger on Floor 10
participant System as ElevatorSystem
participant Dispatcher as Dispatcher
participant Strategy as SuitabilityDispatchStrategy
participant Car as ElevatorCar (ID: 3)
User->>System: Press "UP" button on Floor 10
System->>Dispatcher: processHallCall(10, UP)
Dispatcher->>Strategy: selectOptimalCar(cars, 10, UP)
Note over Strategy: Loop over cars and compute Suitability Score
Strategy-->>Dispatcher: Car ID 3 (Optimal)
Dispatcher->>Car: addDestination(10)
Note over Car: Insert 10 into upQueue (TreeSet)
Car->>Car: Wake up processing sweep thread
Car-->>System: Confirmation (Assigned Car 3)
System-->>User: Display: "Car 3 arriving in 12s"
Low-Level Design & Component Mechanics
To ensure a production-ready, SOLID-compliant implementation, we write the full set of elevator control entities in Java.
1. Java Low-Level Class Structure
package com.codesprintpro.elevator;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
// 1. Enums defining states and directions
enum Direction {
UP,
DOWN,
IDLE
}
enum ElevatorState {
MOVING,
STOPPED,
MAINTENANCE
}
// 2. Class representing passenger request parameters
class Request {
private final int sourceFloor;
private final Direction direction;
public Request(int sourceFloor, Direction direction) {
this.sourceFloor = sourceFloor;
this.direction = direction;
}
public int getSourceFloor() { return sourceFloor; }
public Direction getDirection() { return direction; }
}
// 3. Thread-safe Elevator Car Class implementing SCAN algorithm
class ElevatorCar implements Runnable {
private final int id;
private int currentFloor = 0;
private Direction direction = Direction.IDLE;
private ElevatorState state = ElevatorState.STOPPED;
// TreeSet automatically sorts floor destinations to optimize sweep order
private final TreeSet<Integer> upQueue = new TreeSet<>();
private final TreeSet<Integer> downQueue = new TreeSet<>(Collections.reverseOrder());
public ElevatorCar(int id) {
this.id = id;
}
public int getId() { return id; }
public synchronized int getCurrentFloor() { return currentFloor; }
public synchronized Direction getDirection() { return direction; }
public synchronized ElevatorState getState() { return state; }
public synchronized void setState(ElevatorState state) { this.state = state; }
// Adds a floor destination to the appropriate SCAN queue
public synchronized void addDestination(int floor) {
if (floor == currentFloor) return;
if (floor > currentFloor) {
upQueue.add(floor);
if (direction == Direction.IDLE) {
direction = Direction.UP;
}
} else {
downQueue.add(floor);
if (direction == Direction.IDLE) {
direction = Direction.DOWN;
}
}
// Wake up sweep thread
notifyAll();
}
@Override
public void run() {
while (true) {
try {
synchronized (this) {
while (upQueue.isEmpty() && downQueue.isEmpty() && direction == Direction.IDLE) {
state = ElevatorState.STOPPED;
wait(); // Sleep until a new request wakes up the thread
}
state = ElevatorState.MOVING;
}
if (direction == Direction.UP) {
processSweep(upQueue, Direction.UP);
} else if (direction == Direction.DOWN) {
processSweep(downQueue, Direction.DOWN);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
break;
}
}
}
private void processSweep(TreeSet<Integer> queue, Direction activeDir) throws InterruptedException {
while (true) {
Integer nextFloor;
synchronized (this) {
if (queue.isEmpty()) {
// Reverse sweep direction if current queue is empty
direction = (activeDir == Direction.UP) ? Direction.DOWN : Direction.UP;
if (upQueue.isEmpty() && downQueue.isEmpty()) {
direction = Direction.IDLE;
}
break;
}
nextFloor = queue.first();
}
// Simulate physical movement between floors
while (currentFloor != nextFloor) {
Thread.sleep(1000); // 1 second to travel 1 floor
synchronized (this) {
if (activeDir == Direction.UP) {
currentFloor++;
} else {
currentFloor--;
}
System.out.println("Elevator " + id + " reached Floor " + currentFloor);
}
}
// Stop at floor to let passengers enter/exit
synchronized (this) {
queue.remove(nextFloor);
System.out.println("Elevator " + id + " STOPPED at Floor " + currentFloor + ". Opening Doors.");
Thread.sleep(1500); // Door open delay
}
}
}
}
// 4. Strategy Pattern interface for dynamic dispatching
interface DispatchStrategy {
ElevatorCar selectElevator(List<ElevatorCar> cars, Request request);
}
// 5. Suitability score dispatch implementation
class SuitabilityDispatchStrategy implements DispatchStrategy {
private final int totalFloors;
public SuitabilityDispatchStrategy(int totalFloors) {
this.totalFloors = totalFloors;
}
@Override
public ElevatorCar selectElevator(List<ElevatorCar> cars, Request request) {
ElevatorCar bestCar = null;
int highestScore = -1;
for (ElevatorCar car : cars) {
if (car.getState() == ElevatorState.MAINTENANCE) continue;
int dist = Math.abs(car.getCurrentFloor() - request.getSourceFloor());
int penalty = 20; // Default penalty for opposite direction
if (car.getDirection() == Direction.IDLE) {
penalty = 10;
} else if (car.getDirection() == request.getDirection()) {
if ((request.getDirection() == Direction.UP && car.getCurrentFloor() <= request.getSourceFloor()) ||
(request.getDirection() == Direction.DOWN && car.getCurrentFloor() >= request.getSourceFloor())) {
penalty = 0; // Optimal: moving in same direction and hasn't passed floor yet
}
}
int score = (totalFloors - dist) - penalty;
if (score > highestScore) {
highestScore = score;
bestCar = car;
}
}
return bestCar;
}
}
// 6. Central Controller coordinating matching and execution loops
class ElevatorSystemController {
private final List<ElevatorCar> cars = new CopyOnWriteArrayList<>();
private final DispatchStrategy dispatchStrategy;
public ElevatorSystemController(int carCount, int totalFloors) {
this.dispatchStrategy = new SuitabilityDispatchStrategy(totalFloors);
for (int i = 1; i <= carCount; i++) {
ElevatorCar car = new ElevatorCar(i);
cars.add(car);
// Launch elevator car thread
new Thread(car).start();
}
}
public void requestElevator(int floor, Direction direction) {
Request req = new Request(floor, direction);
ElevatorCar optimalCar = dispatchStrategy.selectElevator(cars, req);
if (optimalCar != null) {
System.out.println("Assigned request on Floor " + floor + " to Elevator " + optimalCar.getId());
optimalCar.addDestination(floor);
} else {
System.out.println("No active elevator cars available.");
}
}
public List<ElevatorCar> getCars() { return cars; }
}
2. SCAN Algorithm Mechanics (The Elevator Algorithm)
A naive scheduler processes requests in First-In-First-Out (FIFO) sequence. If the elevator is on Floor 5, and gets requests in the sequence [1, 45, 2, 48], it will travel up and down the building repeatedly, wasting huge amounts of time and electricity.
The SCAN algorithm processes requests in continuous sweeps.
- When moving
UP, the elevator processes all requested floors in ascending order (using our JavaTreeSetupQueue). - It continues sweeping upward until the
upQueueis completely exhausted. - Once the top destination is served, it reverses direction to
DOWNand sweeps downward, serving requests in descending order (usingdownQueue). - This sweeps boundary model bounds wait time and guarantees that no floor request suffers from starvation.
Scaling Challenges & Production Bottlenecks
Transitioning this multi-car engine to a massive real-world physical deployment exposes several critical bottlenecks:
1. Concurrent Dispatcher Thread Lock Contention
During peak morning hours, thousands of users on different floors press hall buttons simultaneously. If the central dispatcher uses a single, global synchronization lock to select the best car, requests will queue up on backend thread pools, causing input processing latency to exceed several seconds.
Mitigation (Fine-Grained Read-Write Locks):
We separate the read operations from write operations using Java's ReentrantReadWriteLock.
- Querying elevator locations and directions to compute suitability scores only requires acquiring a Read Lock, allowing hundreds of concurrent threads to evaluate score equations simultaneously.
- We only acquire a Write Lock during the brief millisecond window when we write a destination key into the assigned car's
TreeSet, maximizing throughput and eliminating lock bottlenecks.
2. High-Rise Skyscraper Elevator Starvation
In 100-story buildings, keeping all elevators in a single, open pool results in poor performance: cars will cluster on lower floors to serve high volumes of traffic, leaving passengers on upper floors waiting indefinitely.
Mitigation (Static Floor Zoning): We implement static Zoning Strategies (as encapsulated by our Strategy Design Pattern):
- Express Cars: Service only the ground floor (lobby) and then travel directly to floors 70-100.
- Low-Rise Zone: Service only floors 1-35.
- Mid-Rise Zone: Service only floors 36-69. This partition sharding bounds elevator travel distance and guarantees rapid turnaround times for all occupants.
Technical Trade-offs & Strategic Compromises
Selecting elevator scheduling algorithms requires balancing computational complexity with customer comfort constraints.
| Algorithm Choice | Average Wait Time | Starvation Risk | Mechanical Wear-and-Tear | Implementation Complexity |
|---|---|---|---|---|
| FCFS (First-Come) | Extremely High | Zero (Strict Fairness) | Extremely High | Ultra-Low |
| SSTF (Shortest Seek) | Low | High (Middle floor focus) | Medium | Low |
| SCAN (Sweep) | Low (Highly balanced) | Zero | Low (Saves sweeps) | Medium |
| Zoned Destination | Optimal | Zero | Lowest | High |
SCAN vs. Shortest Seek Time First (SSTF)
SSTF always moves the elevator to the closest requested floor. While this works well under low traffic, under heavy load, it creates a severe hotspot: if passengers on floors 4, 5, and 6 keep making requests, the car will oscillate between those floors indefinitely, starving a passenger waiting on Floor 45. SCAN guarantees fairness. By enforcing full upward and downward sweeps, it bounds the maximum wait time mathematically, ensuring no passenger is left stranded.
Failure Scenarios and Fault Tolerance
Elevators are safety-critical systems, and the low-level controller must handle mechanical faults instantly.
1. Elevator Car Mechanical Outage
If a physical elevator car experiences a door failure or motor stall, it must be isolated immediately without hanging its assigned passengers.
Fault Tolerance Strategy:
- Elevator cars continuously stream heartbeats to the central controller.
- If a sensor detects an anomaly or a heartbeat times out, the controller transitions the car's state to
MAINTENANCE. - The dispatcher immediately extracts all pending requests from the failed car's queues and injects them back into the global pool for redistribution to active, healthy cars.
2. Fire Alarm Emergency Evacuation
Under a fire event, the standard scheduling algorithm must be overridden immediately to save lives.
Fault Tolerance Strategy:
- The central controller registers an observer to the building's emergency alert bus.
- Upon receiving a fire event, the controller overrides all dispatching queues, clears all player requests, drives all elevator cars to the ground lobby floor, opens the doors, and transitions the system status to
EMERGENCY_HALT.
Staff Engineer Perspective
Verbal Script & Mock Interview
Mock Interview Dialogue
Interviewer: "Welcome! Today, we want to design the low-level architecture for an elevator system operating in a skyscraper. The system should manage multiple elevator cars and handle passengers standing on floors calling rides. How would you structure this?"
Candidate: *"To design a resilient and highly optimized elevator system, I will focus on three core objectives: clean object-oriented class representation that adheres to SOLID principles, a starvation-free scheduling algorithm using the SCAN sweep pattern, and a thread-safe concurrent execution model.
I will model the system using these primary entities:
ElevatorCar: Represents the physical car. To execute the SCAN algorithm, each car runs in its own background thread and maintains twoTreeSetqueues—upQueueanddownQueue. TheTreeSetautomatically keeps floor destinations sorted (ascending for UP, descending for DOWN) to ensure we sweep the building efficiently.DispatchStrategy: An interface that allows us to abstract and swap routing algorithms at runtime. During peak hours, we can utilize a suitability score strategy, while during off-peak hours we can switch to zone-based scheduling.ElevatorSystemController: The central facade that coordinates hall requests, invokes the dispatch strategy to select the best car, and manages active threads."*
Interviewer: "Excellent. Tell me about your dispatching logic. How does the system determine which elevator car is best suited for an incoming request?"
Candidate: *"The dispatcher evaluates the state of all healthy elevator cars and assigns a Suitability Score to each based on three parameters: distance to the request floor, the car's current moving direction, and the direction the user wants to go.
The optimal scenario is when an elevator is already moving towards the request floor in the same direction. For instance, if a user on Floor 10 wants to go UP, and Car 3 is currently on Floor 6 moving UP, it receives a perfect suitability score because it can seamlessly pick up the passenger on its path.
Conversely, if a car is moving away from the floor or in the opposite direction, we apply a heavy penalty. If a car is idle, we apply a minor penalty. We calculate these scores in constant time, select the car with the highest score, and inject the floor destination into its sweep queue."*
Interviewer: "That is a very clean scoring algorithm. How do you handle concurrency when hundreds of users press buttons simultaneously?"
Candidate: *"In a high-concurrency real-world skyscraper, we must prevent race conditions and lock bottlenecks.
Within each ElevatorCar, adding a destination is synchronized to ensure thread-safe updates to our TreeSet queues. However, locking the entire dispatcher during a suitability calculation would block input handling.
To solve this, I implement a Read-Write Locking pattern. Since calculating suitability scores only requires reading the location and direction variables of the cars, we acquire a shared Read Lock, allowing hundreds of requests to evaluate score equations concurrently. We only acquire an exclusive Write Lock during the brief millisecond when we write the selected floor destination to the assigned car's queue.
Additionally, we use completely stateless backend controllers, persisting match queues in Redis, ensuring that if a server pod fails, any other pod can restore the queue state instantly and continue operation."*
Interviewer: "Outstanding. Your understanding of concurrent design patterns, data structure efficiency, and real-world failure modes is exemplary."