Design an Elevator System — Low-Level Design

Problem framing

Multi-floor building with multiple cars. Two kinds of requests: hall calls (passenger on floor presses UP/DOWN), car calls (passenger inside presses destination). Car must serve pending stops efficiently — not arrival order but sweeping one direction (SCAN/LOOK). Safety: doors don't close on people, no overload, emergencies preempt.

Design pressure: scheduling (which car answers a hall call?), per-car movement (in what order does this car serve its stops?), concurrency between many simultaneous requests.

Clarifying questions

Floors + cars count. Direction-aware hall buttons (separate UP/DOWN) or single. Internal destination buttons. Special features (express, freight, VIP). Capacity / safety. Persistence. Scheduling goal (avg wait or longest wait).

Assumptions

20 floors, 4 cars. Direction-aware hall buttons. Internal destination buttons inside each car. Standard cars (express/freight as extensions). Capacity + door-obstruction safety in scope. Emergency/maintenance as extensions. In-memory single instance. Optimize average wait time.

Core entities

ElevatorSystem: receives hall calls, dispatches via SchedulingStrategy. Holds list of Elevators + strategy. Elevator: one car. Current floor, direction, state, RequestQueue. Worker loop moves between stops in SCAN/LOOK order. HallCall: floor, direction, timestamp. CarCall: floor, source elevator id. Direction enum: UP, DOWN, IDLE. ElevatorState enum: IDLE, MOVING, DOOR_OPEN, OUT_OF_SERVICE. SchedulingStrategy interface: NearestCarStrategy, LookStrategy. DoorController interface: open, close, isObstructed. SafetyMonitor: weight, door obstruction, emergency.

Scheduling — picking a car

Cost function: distance(car, hall call floor) + direction-mismatch penalty (if car moving away) + load penalty (if near capacity) + idle bonus.

LookStrategy formalizes: prefer cars already moving in requested direction that haven't passed the calling floor. Fall back to idle, nearest. Last resort, cars moving opposite direction (after sweep finishes).

Well-known LOOK / SCAN-elevator approach — what real elevators use. Naive FIFO ('whichever free next') gives terrible wait times.

LookStrategy.pickCar: minBy cost. Cost = distance + (0 if moving toward in same direction; 5 if idle; 20 if moving away).

Per-car state machine + SCAN/LOOK movement

State machine: IDLE → MOVING (on addStop) → DOOR_OPEN (arrived) → MOVING (more stops in current direction) or IDLE (no more). Emergency → OUT_OF_SERVICE.

Movement rule: sweep current direction until no more stops in that direction, then reverse.

Elevator.addStop(floor, dir): synchronized; queue.add; if IDLE, set direction toward floor, state MOVING.

Elevator.step() called once per tick: synchronized. Get nextStop from queue; if none, IDLE. If currentFloor == target, openDoor. Else move one floor toward target.

openDoor: state DOOR_OPEN, door.open, wait for close (with obstruction check), door.close, removeStopAt currentFloor, state IDLE if queue empty else MOVING.

RequestQueue: two TreeSet for stops above/below; nextStop returns next floor in current direction, falls back to other side when exhausted.

End-to-end flow

P1 at F5 presses UP → Sys calls Sched.pickCar → picks E1 (idle at F1, distance 4) → E1.addStop(5, UP).

P2 at F12 presses DOWN → Sys.pickCar picks E2 (already going UP, will reverse at top) → E2.addStop(12, DOWN).

Loop: E1 climbs to F5, opens door. E2 finishes UP sweep, reverses to F12.

Concurrency

Two boundaries:

1. 1

   Dispatcher receiving hall calls: many threads call pressHallButton. Mostly stateless; serialize cost computation. pickCar reads snapshots (currentFloor, direction, state) — cheap, consistent. Mark volatile or small per-car lock.

2. 2

   Per-car queue mutation: stops arrive while worker moves. addStop synchronized; step() synchronized. Lock granularity per-car; cars don't block each other.

Worker model: one dedicated thread per car (ScheduledExecutorService fixed-rate per car) drives step() loop. Each tick = one floor or one door cycle. Real systems use real time; model uses tick-based simulation.

Safety, priority, observability

Safety:

• Overweight: blocks door close until weight drops; refuses to start moving
• Door obstruction: re-opens door; close timeout retries with audible warning
• Emergency stop: all cars OUT_OF_SERVICE; open nearest door at next floor
• Fire mode: all cars to ground floor, stop, ignore calls

Priority:

• VIP override: marker on hall call boosts scheduling priority
• Maintenance: car removed from cars for duration; in-flight calls reassigned

Observability:

• Per-call wait time (press → door open)
• Per-car utilization (% moving / idle)
• Number of reverses (high = choppy scheduling)
• Histogram of stops per ride

Metrics let you tune the cost function without guessing.

Trade-offs and alternatives

• Greedy LOOK + cost function vs full optimization — greedy within 10-20% of optimal; full is NP-ish, not worth it for ~4-8 cars
• Direction-aware vs single button per floor — direction-aware schedules smarter; single simpler but worse
• Tick-based vs event-driven simulation — tick easier to test; event-driven more efficient but harder
• One worker thread per car vs central scheduler — per-car gives isolation and parallelism
• Static dispatch vs dynamic re-assignment — advanced systems re-assign mid-flight; modest gain, more complexity
• Express elevators / banks — partition dispatcher; extension

Recommendation

Build an ElevatorSystem dispatcher that uses a SchedulingStrategy interface (LOOK with a cost function combining distance, direction match, load) to pick the best car for each hall call. Each Elevator runs its own state machine and serves stops in SCAN/LOOK order via a RequestQueue with two sorted sets (up/down stops). Run one worker thread per car so cars don't block each other; per-car synchronized methods protect queue mutation. Inject DoorController and SafetyMonitor as interfaces — makes overweight, obstruction, and emergency modes natural. Direction-aware hall buttons enable better scheduling. Track per-call wait time and per-car reverses to tune the cost function.