LLD · Simulation

Elevator Control System

Class design, SCAN movement, and dispatch logic for interview LLD. Aligned with Hello Interview — Elevator.

An elevator system manages multiple lifts serving floors. The controller dispatches hall calls; each elevator maintains its own stop queue and moves in discrete time steps via step(). This note covers requirements, entities, pseudocode, and concurrency tradeoffs.

1. Problem understanding and requirements

Prompt: “Design an elevator control system for a building.” Clarify before coding — scale, call types, simulation model, and what is out of scope.

Clarifying questions (interview script)

Scale: 3 elevators, 10 floors (0–9), fixed for now.
Hall calls: Classic UP/DOWN buttons (not destination dispatch panels).
Inside elevator: Multiple destination floors allowed.
Time model: Simulation with step() / tick() — not hardware interrupts.
Invalid input: Reject bad floors; current-floor request = no-op.
Out of scope: Capacity, weight sensors, doors, emergency stops.

Feature	Requirement
Capacity	3 elevators, floors 0–9
Hall call	Floor + direction (UP / DOWN)
Destination	Floor only (selected inside the elevator)
Simulation	`controller.step()` advances all elevators one tick
Validation	Return `false` for invalid floor; ignore same-floor requests

2. Core entities

Three classes — each owns the data it knows best (Information Expert).

ElevatorController — entry point; receives hall calls; picks which elevator to dispatch; runs step() on all elevators.
Elevator — one lift: current floor, direction, request set; movement logic. Does not know about other elevators.
Request — value object: target floor + type (PICKUP_UP, PICKUP_DOWN, DESTINATION).

// Who talks to whom Client / Simulation → ElevatorController.requestElevator(floor, type) → ElevatorController.requestDestination(elevatorId, floor) → ElevatorController.step() → for each Elevator: elevator.step()

3. Enums and value objects

Enums prevent invalid states (e.g., a “moving” request type).

enum Direction { UP, DOWN, IDLE } enum RequestType { PICKUP_UP, PICKUP_DOWN, DESTINATION } class Request { int floor RequestType type Request(int floor, RequestType type) { this.floor = floor this.type = type } // Value object: equals/hashCode on (floor, type) }

4. Class design

Elevator

Use a Set<Request> for stops — automatic dedup when multiple passengers press the same floor.

class Elevator { int id int currentFloor // 0..9 Direction direction // UP | DOWN | IDLE Set<Request> requests void addRequest(Request req) { if (req.floor == currentFloor) return // no-op requests.add(req) } void removeRequest(int floor, RequestType type) { ... } void step() { // movement + stop logic (see §6) } }

ElevatorController

class ElevatorController { List<Elevator> elevators // size 3 boolean requestElevator(int floor, RequestType hallType) { if (!isValidFloor(floor)) return false if (hallType == DESTINATION) return false // hall only Request req = new Request(floor, hallType) Elevator best = selectBestElevator(req) best.addRequest(req) return true } boolean requestDestination(int elevatorId, int floor) { if (!isValidFloor(floor)) return false Elevator e = elevators.get(elevatorId) e.addRequest(new Request(floor, DESTINATION)) return true } void step() { for (Elevator e : elevators) e.step() } }

5. Dispatch: picking the best elevator

When floor 5 presses UP, the controller assigns one elevator.

Strategy	Idea	Problem
Nearest	Min distance to floor	May pick an elevator moving away from the call
Direction-aware	Prefer elevator moving toward floor in same direction	Ignores whether the lift has already passed the floor
Request-aware (best)	Direction + position: elevator will pass the floor before reversing	Slightly more code — preferred in interviews

Trap: same direction + nearest is not enough

You are on floor 4 and press DOWN (want ground). Elevator A is on floor 3 going DOWN.

Naive logic says: same direction, distance = 1 → pick A. Wrong. A is below you and already moving away — it passed floor 4 on the way down. It will not stop for your DOWN call unless it reverses far below.

Correct rule for DOWN hall call at floor F: pick an elevator that is above F and going DOWN (currentFloor > F), or IDLE and can reach F. Symmetrically for UP: elevator must be below F and going UP (currentFloor < F).

Elevator selectBestElevator(Request req) { // Priority 1: elevator that will naturally pass req.floor // UP call at F → elevator going UP AND currentFloor < F // DOWN call at F → elevator going DOWN AND currentFloor > F Elevator candidate = findServingElevator(req) if (candidate != null) return candidate // Priority 2: nearest IDLE elevator candidate = findNearestIdle(req.floor) if (candidate != null) return candidate // Priority 3: nearest elevator (will reverse via SCAN later) return findNearest(req.floor) }

Example: Hall call at floor 3 UP. Elevator A at floor 1 going UP → good. Elevator B at floor 6 going DOWN → worse; it must reverse before serving 3 UP.

6. Movement: SCAN (scanning) algorithm

SCAN (scanning / elevator algorithm): the lift keeps moving in one direction, checking each floor along the path. It services every stop in that direction. When no requests remain ahead, if requests exist in the opposite direction it reverses; otherwise it goes IDLE.

This beats FIFO (which causes thrashing — bouncing between distant floors).

void Elevator.step() { if (requests.isEmpty()) { direction = IDLE return } if (direction == IDLE) { Request nearest = findNearestRequest() direction = (nearest.floor > currentFloor) ? UP : DOWN } if (shouldStop()) { removeMatchingRequestsAtCurrentFloor() return // stopping costs one full tick } if (!hasRequestsAhead(direction)) { if (hasRequestsInOppositeDirection(direction)) { direction = flip(direction) // reverse — one full tick } else { direction = IDLE } return } // scan: move one floor in current direction currentFloor += (direction == UP) ? 1 : -1 }

Direction-aware stopping

Only stop for hall calls that match travel direction.

boolean shouldStop() { for (Request req : requests) { if (req.floor != currentFloor) continue if (req.type == DESTINATION) return true if (req.type == PICKUP_UP && direction == UP) return true if (req.type == PICKUP_DOWN && direction == DOWN) return true } return false } boolean hasRequestsAhead(Direction dir) { for (Request req : requests) { if (dir == UP && req.floor > currentFloor) return true if (dir == DOWN && req.floor < currentFloor) return true } return false }

7. Simulation loop

// Driver (tests or demo) controller.requestElevator(0, PICKUP_UP) // lobby wants up controller.requestDestination(0, 7) // passenger in elevator 0 for (int t = 0; t < 100; t++) { controller.step() printState() }

8. Concurrency

Real systems get hall calls while step() runs. Two risks: concurrent modification of requests, and two threads assigning the same idle elevator.

Option A — Mutex: Lock around requestElevator() and step(). Simple and correct; threads may wait.
Option B — Drain queue: Thread-safe inbound queue per elevator; at start of step(), drain into the internal Set. Separates writes from movement reads.

// Option B sketch ConcurrentLinkedQueue<Request> inbound void addRequest(Request req) { inbound.add(req) } void step() { drainInboundIntoSet() // ... SCAN logic }

9. Extensibility and interview depth

Express elevator: boolean isExpress on Elevator; controller routes floors 0, 5, 9 only to that lift.
Cancel request: removeRequest(floor, type) — trivial with a Set; next step() skips if removed.
Junior: Entities + basic movement loop.
Mid: SCAN + clean IDLE → UP/DOWN transitions.
Senior: Dispatch tradeoffs, concurrency, express/cancel extensions.

Quick revision

Scope: 3 elevators, floors 0–9, step() simulation; no doors/capacity.
Entities: Controller (dispatch), Elevator (movement), Request (floor + type).
Request types: PICKUP_UP, PICKUP_DOWN, DESTINATION.
Dispatch: Serving elevator → idle nearest → any nearest.
Dispatch trap: Floor 4 DOWN, elevator on floor 3 going DOWN — same direction and nearest, but bad pick (already passed floor 4). DOWN call needs elevator above you; UP call needs elevator below you.
SCAN / scanning: Lift moves in one direction, checks each floor; serves all stops that way; when none ahead, reverse if opposite requests exist, else IDLE.
Movement: Stop only if hall-call direction matches travel direction.
State: Set<Request> for dedup; IDLE when queue empty.
Concurrency: Mutex (simple) or per-tick drain queue (scalable).
vs FIFO: SCAN avoids thrashing; standard for real elevator systems.