> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.
# Case Study: Elevator System
> Complete low-level design for a multi-elevator system with smart scheduling
**Difficulty**: 🟡 Intermediate | **Time**: 45 minutes | **Patterns**: Strategy, State, Observer
## 🎯 Problem Statement
Design an elevator system for a building that can:
* Handle multiple elevators
* Optimize elevator assignment for efficiency
* Support different scheduling algorithms
* Handle concurrent requests from multiple floors
**Why This Problem?** Elevator design tests your ability to handle **state machines**, **scheduling algorithms**, and **concurrency**. It is a favorite at companies like Uber and Amazon because it mirrors real dispatching problems -- how do you assign limited resources (elevators) to competing requests (floors) while minimizing wait time? The scheduling algorithm choice is essentially a Strategy pattern decision, and the interviewer wants to see you reason about trade-offs: FCFS is fair but inefficient, SCAN prevents starvation but increases maximum wait time, and LOOK is efficient but harder to implement.
***
## 📋 Step 1: Clarify Requirements
**Interview Tip**: Elevator problems can range from simple to extremely complex. Clarify the scope!
### Questions to Ask the Interviewer
| Category | Question | Impact on Design |
| ------------- | ---------------------------------- | ---------------------------- |
| **Scale** | How many elevators and floors? | Data structures, concurrency |
| **Algorithm** | Which scheduling algorithm? | Strategy pattern selection |
| **Features** | VIP/express elevators? | Additional elevator types |
| **Capacity** | Weight limits? Max passengers? | Capacity checking logic |
| **Emergency** | Fire mode? Emergency stop? | State machine complexity |
| **UI** | Display current floor in elevator? | Observer pattern for updates |
### Functional Requirements
* Support N elevators and M floors
* Handle up/down requests from floors (hall buttons)
* Handle floor selection from inside elevator (car buttons)
* Display current floor and direction
* Handle door open/close operations
* Emergency stop functionality
### Non-Functional Requirements
* Minimize average wait time
* Minimize travel time (optimize scheduling)
* Handle concurrent requests thread-safely
* Graceful degradation if elevator fails
***
## 🧩 Step 2: Identify Core Objects
**Key Insight**: The elevator controller uses **Strategy Pattern** for scheduling algorithms - you can swap between FCFS, SCAN, and LOOK algorithms without changing the core logic.
Elevator, Door, Floor, Button
ElevatorController, Scheduler
FloorRequest, ElevatorRequest
### Entity-Responsibility Mapping
| Entity | Responsibilities | Pattern |
| -------------------- | ------------------------------- | ---------------- |
| `Elevator` | Move, track floor, manage doors | State Pattern |
| `Door` | Open/close with safety checks | State Pattern |
| `ElevatorController` | Coordinate all elevators | Singleton |
| `SchedulingStrategy` | Assign elevator to request | Strategy Pattern |
| `FloorDisplay` | Show elevator positions | Observer Pattern |
### Scheduling Algorithms
| Algorithm | Description | Best For |
| ----------- | -------------------------------------- | ---------------- |
| **FCFS** | First come, first served | Simple buildings |
| **SCAN** | Elevator goes one direction until end | Medium buildings |
| **LOOK** | Like SCAN but reverses at last request | Most efficient |
| **Nearest** | Assign closest idle elevator | Low traffic |
***
## 📐 Step 3: Class Diagram
```
┌─────────────────────────────────────────────────────────────┐
│ ElevatorController │
├─────────────────────────────────────────────────────────────┤
│ - elevators: List │
│ - scheduler: SchedulingStrategy │
│ - floorRequests: Queue │
├─────────────────────────────────────────────────────────────┤
│ + requestElevator(floor, direction): void │
│ + assignElevator(request): Elevator │
│ + getStatus(): List │
└─────────────────────────────────────────────────────────────┘
│
│ 1..*
▼
┌─────────────────────────────────────────────────────────────┐
│ Elevator │
├─────────────────────────────────────────────────────────────┤
│ - id: int │
│ - currentFloor: int │
│ - direction: Direction │
│ - state: ElevatorState │
│ - destinationFloors: SortedSet │
│ - door: Door │
├─────────────────────────────────────────────────────────────┤
│ + addDestination(floor): void │
│ + move(): void │
│ + openDoor(): void │
│ + closeDoor(): void │
└─────────────────────────────────────────────────────────────┘
│
│ 1
▼
┌─────────────────────────────────────────────────────────────┐
│ Door │
├─────────────────────────────────────────────────────────────┤
│ - state: DoorState │
├─────────────────────────────────────────────────────────────┤
│ + open(): void │
│ + close(): void │
│ + isOpen(): bool │
└─────────────────────────────────────────────────────────────┘
```
## Step 4: Implementation
### Enums and Constants
```python theme={null}
from enum import Enum
from typing import Optional, List, Set
from dataclasses import dataclass
from abc import ABC, abstractmethod
import threading
import time
from sortedcontainers import SortedList
class Direction(Enum):
UP = 1
DOWN = -1
IDLE = 0
class ElevatorState(Enum):
MOVING = 1
STOPPED = 2
MAINTENANCE = 3
class DoorState(Enum):
OPEN = 1
CLOSED = 2
OPENING = 3
CLOSING = 4
# Building configuration
NUM_FLOORS = 10
NUM_ELEVATORS = 3
FLOOR_HEIGHT_METERS = 3
ELEVATOR_SPEED = 1 # floors per second
DOOR_OPERATION_TIME = 2 # seconds
```
### Request Classes
```python theme={null}
@dataclass
class FloorRequest:
"""Request from a floor button (external)"""
floor: int
direction: Direction
timestamp: float
def __hash__(self):
return hash((self.floor, self.direction))
@dataclass
class ElevatorRequest:
"""Request from inside elevator (internal)"""
destination_floor: int
elevator_id: int
timestamp: float
```
### Door Class
```python theme={null}
class Door:
def __init__(self):
self._state = DoorState.CLOSED
self._lock = threading.Lock()
@property
def state(self) -> DoorState:
return self._state
def open(self):
with self._lock:
if self._state == DoorState.CLOSED:
self._state = DoorState.OPENING
time.sleep(0.5) # Simulate opening
self._state = DoorState.OPEN
def close(self):
with self._lock:
if self._state == DoorState.OPEN:
self._state = DoorState.CLOSING
time.sleep(0.5) # Simulate closing
self._state = DoorState.CLOSED
def is_open(self) -> bool:
return self._state == DoorState.OPEN
```
### Elevator Class
```python theme={null}
class Elevator:
def __init__(self, elevator_id: int, total_floors: int):
self.id = elevator_id
self.total_floors = total_floors
self._current_floor = 1
self._direction = Direction.IDLE
self._state = ElevatorState.STOPPED
self.door = Door()
# Two sorted lists for efficient destination management
self._up_stops: SortedList = SortedList()
self._down_stops: SortedList = SortedList()
self._lock = threading.Lock()
@property
def current_floor(self) -> int:
return self._current_floor
@property
def direction(self) -> Direction:
return self._direction
@property
def state(self) -> ElevatorState:
return self._state
def add_destination(self, floor: int):
"""Add a floor to visit"""
with self._lock:
if floor == self._current_floor:
return
if floor > self._current_floor:
if floor not in self._up_stops:
self._up_stops.add(floor)
else:
if floor not in self._down_stops:
self._down_stops.add(floor)
# Update direction if idle
if self._direction == Direction.IDLE:
self._update_direction()
def _update_direction(self):
"""Determine next direction based on pending stops"""
if self._up_stops:
self._direction = Direction.UP
elif self._down_stops:
self._direction = Direction.DOWN
else:
self._direction = Direction.IDLE
def get_next_stop(self) -> Optional[int]:
"""Get the next floor to stop at"""
if self._direction == Direction.UP and self._up_stops:
return self._up_stops[0] # Nearest up
elif self._direction == Direction.DOWN and self._down_stops:
return self._down_stops[-1] # Nearest down
return None
def move(self):
"""Move elevator one step towards destination"""
if self._state == ElevatorState.MAINTENANCE:
return
if self.door.is_open():
return # Can't move with open doors
next_stop = self.get_next_stop()
if next_stop is None:
self._update_direction()
return
self._state = ElevatorState.MOVING
# Move one floor
if self._direction == Direction.UP:
self._current_floor += 1
elif self._direction == Direction.DOWN:
self._current_floor -= 1
print(f"Elevator {self.id} at floor {self._current_floor}")
# Check if we should stop
if self._should_stop():
self._stop()
def _should_stop(self) -> bool:
"""Check if elevator should stop at current floor"""
if self._direction == Direction.UP:
return self._current_floor in self._up_stops
elif self._direction == Direction.DOWN:
return self._current_floor in self._down_stops
return False
def _stop(self):
"""Stop at current floor"""
self._state = ElevatorState.STOPPED
# Remove from destination lists
if self._current_floor in self._up_stops:
self._up_stops.remove(self._current_floor)
if self._current_floor in self._down_stops:
self._down_stops.remove(self._current_floor)
# Open door
self.door.open()
print(f"Elevator {self.id} stopped at floor {self._current_floor}, doors open")
time.sleep(DOOR_OPERATION_TIME)
self.door.close()
print(f"Elevator {self.id} doors closed")
# Update direction
self._update_direction()
def get_status(self) -> dict:
return {
"id": self.id,
"current_floor": self._current_floor,
"direction": self._direction.name,
"state": self._state.name,
"pending_stops": len(self._up_stops) + len(self._down_stops)
}
def distance_to(self, floor: int) -> int:
"""Calculate distance to a floor considering direction"""
return abs(floor - self._current_floor)
def can_serve(self, floor: int, direction: Direction) -> bool:
"""Check if elevator can efficiently serve this request"""
if self._state == ElevatorState.MAINTENANCE:
return False
if self._direction == Direction.IDLE:
return True
# Going up and floor is above, or going down and floor is below
if self._direction == Direction.UP:
return floor >= self._current_floor and direction == Direction.UP
else:
return floor <= self._current_floor and direction == Direction.DOWN
```
### Scheduling Strategies
```python theme={null}
class SchedulingStrategy(ABC):
"""Strategy pattern for elevator scheduling"""
@abstractmethod
def select_elevator(self, elevators: List[Elevator],
request: FloorRequest) -> Optional[Elevator]:
pass
class FCFSScheduler(SchedulingStrategy):
"""First Come First Serve - assign to first available"""
def select_elevator(self, elevators: List[Elevator],
request: FloorRequest) -> Optional[Elevator]:
for elevator in elevators:
if elevator.state != ElevatorState.MAINTENANCE:
return elevator
return None
class ShortestSeekScheduler(SchedulingStrategy):
"""Assign to nearest elevator"""
def select_elevator(self, elevators: List[Elevator],
request: FloorRequest) -> Optional[Elevator]:
best_elevator = None
min_distance = float('inf')
for elevator in elevators:
if elevator.state == ElevatorState.MAINTENANCE:
continue
distance = elevator.distance_to(request.floor)
if distance < min_distance:
min_distance = distance
best_elevator = elevator
return best_elevator
class SCANScheduler(SchedulingStrategy):
"""
SCAN (Elevator) Algorithm:
Prefers elevators already moving in the right direction
"""
def select_elevator(self, elevators: List[Elevator],
request: FloorRequest) -> Optional[Elevator]:
best_elevator = None
best_score = float('inf')
for elevator in elevators:
if elevator.state == ElevatorState.MAINTENANCE:
continue
score = self._calculate_score(elevator, request)
if score < best_score:
best_score = score
best_elevator = elevator
return best_elevator
def _calculate_score(self, elevator: Elevator, request: FloorRequest) -> float:
"""Lower score = better fit"""
distance = elevator.distance_to(request.floor)
# Prefer idle elevators nearby
if elevator.direction == Direction.IDLE:
return distance
# Prefer elevators moving towards the floor in the right direction
if elevator.can_serve(request.floor, request.direction):
return distance * 0.5 # 50% bonus
# Penalty for elevators moving away
return distance * 2
```
### Elevator Controller
```python theme={null}
class ElevatorController:
"""Central controller for all elevators"""
def __init__(self, num_elevators: int, num_floors: int,
scheduler: SchedulingStrategy = None):
self.num_floors = num_floors
self.elevators = [
Elevator(i, num_floors) for i in range(num_elevators)
]
self.scheduler = scheduler or SCANScheduler()
self._pending_requests: List[FloorRequest] = []
self._lock = threading.Lock()
self._running = False
def request_elevator(self, floor: int, direction: Direction):
"""Called when someone presses up/down button on a floor"""
if floor < 1 or floor > self.num_floors:
raise ValueError(f"Invalid floor: {floor}")
request = FloorRequest(
floor=floor,
direction=direction,
timestamp=time.time()
)
with self._lock:
# Select best elevator
elevator = self.scheduler.select_elevator(self.elevators, request)
if elevator:
elevator.add_destination(floor)
print(f"Assigned elevator {elevator.id} for floor {floor} ({direction.name})")
else:
# All elevators busy/maintenance - queue the request
self._pending_requests.append(request)
print(f"All elevators busy, request queued")
def select_floor(self, elevator_id: int, floor: int):
"""Called when someone presses a floor button inside elevator"""
if floor < 1 or floor > self.num_floors:
raise ValueError(f"Invalid floor: {floor}")
if elevator_id < 0 or elevator_id >= len(self.elevators):
raise ValueError(f"Invalid elevator: {elevator_id}")
self.elevators[elevator_id].add_destination(floor)
print(f"Elevator {elevator_id}: selected floor {floor}")
def run(self):
"""Main loop - run in separate thread"""
self._running = True
while self._running:
for elevator in self.elevators:
elevator.move()
# Process pending requests
self._process_pending_requests()
time.sleep(1) # Simulate time between movements
def _process_pending_requests(self):
"""Try to assign pending requests"""
with self._lock:
still_pending = []
for request in self._pending_requests:
elevator = self.scheduler.select_elevator(self.elevators, request)
if elevator:
elevator.add_destination(request.floor)
else:
still_pending.append(request)
self._pending_requests = still_pending
def stop(self):
self._running = False
def get_status(self) -> List[dict]:
return [e.get_status() for e in self.elevators]
def set_maintenance(self, elevator_id: int, maintenance: bool):
"""Put elevator in/out of maintenance mode"""
if elevator_id < 0 or elevator_id >= len(self.elevators):
return
elevator = self.elevators[elevator_id]
elevator._state = (ElevatorState.MAINTENANCE if maintenance
else ElevatorState.STOPPED)
```
### Display Panel
```python theme={null}
class DisplayPanel:
"""Display showing elevator status"""
def __init__(self, controller: ElevatorController):
self.controller = controller
def show(self):
"""Display current status of all elevators"""
print("\n" + "=" * 50)
print("ELEVATOR STATUS")
print("=" * 50)
for status in self.controller.get_status():
direction_arrow = {
"UP": "↑",
"DOWN": "↓",
"IDLE": "○"
}[status["direction"]]
print(f"Elevator {status['id']}: "
f"Floor {status['current_floor']} "
f"{direction_arrow} "
f"[{status['state']}] "
f"({status['pending_stops']} stops)")
print("=" * 50)
```
## Step 5: Usage Example
```python theme={null}
import threading
# Create controller with 3 elevators and 10 floors
controller = ElevatorController(
num_elevators=3,
num_floors=10,
scheduler=SCANScheduler()
)
# Create display
display = DisplayPanel(controller)
# Start elevator system in background
controller_thread = threading.Thread(target=controller.run)
controller_thread.start()
# Simulate requests
controller.request_elevator(floor=5, direction=Direction.UP)
controller.request_elevator(floor=3, direction=Direction.DOWN)
controller.select_floor(elevator_id=0, floor=8)
time.sleep(2)
display.show()
# Person gets in on floor 5, wants to go to floor 9
controller.select_floor(elevator_id=0, floor=9)
time.sleep(5)
display.show()
# Stop the system
controller.stop()
controller_thread.join()
```
## Scheduling Algorithm Comparison
| Algorithm | Pros | Cons | Best For |
| ----------------- | -------------------------- | ------------------- | ------------------- |
| **FCFS** | Simple, fair | Can be inefficient | Low traffic |
| **Shortest Seek** | Minimizes wait for nearest | Starvation possible | Medium traffic |
| **SCAN** | No starvation, efficient | Longer max wait | High traffic |
| **LOOK** | More efficient than SCAN | Complex | High-rise buildings |
## Key Design Decisions
Different buildings have different needs. A hospital may want FCFS for fairness (no patient should wait indefinitely), while a high-rise office may want SCAN for throughput during rush hour. Strategy pattern allows swapping algorithms without changing core logic -- the ElevatorController delegates scheduling to a SchedulingStrategy interface, and the concrete algorithm is injected. This also enables A/B testing: you could run SCAN on elevators 1-2 and LOOK on elevators 3-4, measure average wait times, and switch the entire building to the winner. In an interview, saying "I would use Strategy here so the building operator can choose the scheduling algorithm at deployment time" immediately demonstrates Open/Closed Principle awareness.
Separating up and down stops allows efficient retrieval of the next stop in each direction. A single list would require filtering by direction each time.
Multiple threads can request elevators simultaneously (buttons on different floors). Locks prevent race conditions when modifying elevator state.
**Interview Extension**: Be ready to discuss VIP/priority floors, weight limits, fire emergency mode, or energy-efficient algorithms that minimize empty trips.
***
## Interview Deep-Dive Questions
**Strong answer:**
* **FCFS** is the naive baseline: requests are served in arrival order. It fails badly in a 40-floor building because an elevator on floor 1 might get dispatched to floor 38, then floor 2, then floor 37 -- constant full-length traversals. Average wait time degrades linearly with building height.
* **Shortest Seek** (nearest first) minimizes immediate wait but causes **starvation**. If a steady stream of requests arrives near floor 5, a person waiting on floor 30 may never get served. This is the classic "shortest job first starvation" problem from OS scheduling.
* **SCAN** (elevator algorithm) sweeps fully in one direction then reverses. It guarantees bounded wait time (at most 2 full sweeps) but wastes time traveling to the physical top/bottom even when no requests exist above/below.
* **LOOK** fixes SCAN's waste by reversing at the *last request* in each direction, not at the physical boundary. It is the standard real-world choice for most buildings. Its failure mode is **bunching under asymmetric load**: if floors 1-5 generate 80% of traffic (lobby, cafeteria, gym), LOOK spends most of its time in that range and upper floors see degraded service.
* The real-world answer is rarely a single algorithm. Modern systems like Otis Compass use **destination dispatch** -- passengers enter their destination floor *before* boarding, and the controller groups passengers going to similar floors into the same elevator. This converts the problem from scheduling to batching and reduces stops per trip by 30-50%.
* **Example:** In a hospital, you might use FCFS for fairness (emergency floors should not be starved), while in a commercial high-rise you would use LOOK with zone-based partitioning (elevators 1-3 serve floors 1-20, elevators 4-6 serve floors 21-40).
**Red flag answer:** Listing the algorithms from a textbook without discussing failure modes, or saying "SCAN is the best" without qualifying for what scenario. Also a red flag: not mentioning starvation as a concern for shortest seek.
**Follow-ups:**
1. How would you modify LOOK to handle the asymmetric load problem where one floor (like the lobby at 9 AM) generates 10x the traffic of all other floors combined?
2. What metrics would you instrument in production to decide whether to switch scheduling algorithms -- and could you make the switch at runtime?
**Strong answer:**
* The two-list design mirrors how the SCAN/LOOK algorithm thinks about the world: "what do I need to service in my current direction, and what is waiting for the return trip?" With a single sorted set, every time the elevator needs its next stop, it must filter the entire set by comparing each floor against the current floor and direction. That is O(n) per lookup instead of O(1).
* With two sorted lists, the next stop going up is always `_up_stops[0]` (minimum element) and the next stop going down is always `_down_stops[-1]` (maximum element). Both are O(1) lookups on a sorted container. This is the key performance insight.
* The trade-off is **complexity in the add\_destination logic**. When the elevator is going UP and someone inside presses a floor *below* the current floor, that floor goes into `_down_stops` and will be serviced on the return trip. If you get this assignment wrong, you introduce bugs where floors are never visited or visited in the wrong sweep.
* There is a subtle correctness issue in the current code: `add_destination` decides up vs. down based solely on whether the floor is above or below `current_floor`, ignoring the current direction. If the elevator is on floor 5 going UP and someone requests floor 3, it correctly goes into `_down_stops`. But if someone requests floor 7 while the elevator is going DOWN, it goes into `_up_stops` -- which is correct for the next sweep but means it will not be served until the elevator finishes its downward sweep and reverses. Whether this is a bug or a feature depends on your scheduling semantics.
* **Example:** Think of it like a printer's duplex mode. Pages to print on the forward pass go in one queue, pages for the reverse pass go in another. Mixing them into one queue would require sorting logic on every page.
**Red flag answer:** "Two lists are just an optimization" without explaining *what* operation they optimize or *how* the O(1) lookup works. Also a red flag: suggesting a single list "for simplicity" without acknowledging the scan cost.
**Follow-ups:**
1. What happens if the elevator is at floor 10 going DOWN with `_down_stops = [7, 3]`, and a new request comes in for floor 8 going UP? Which list does floor 8 go into, and when does the passenger get picked up?
2. If you needed to support priority requests (e.g., VIP floors that jump the queue), how would you modify the two-list data structure?
**Strong answer:**
* `time.sleep()` inside a lock is a **concurrency killer**. The Door's `open()` method holds `self._lock` and then sleeps for 0.5 seconds. During that sleep, any other thread trying to call `open()` or `close()` on the same door is blocked -- which is fine for a single door. But the real problem is upstream: the `Elevator._stop()` method calls `door.open()`, sleeps for `DOOR_OPERATION_TIME` (2 seconds), then calls `door.close()`. During those 3 total seconds of sleep, the elevator's thread is completely blocked.
* In the `ElevatorController.run()` loop, each elevator's `move()` is called sequentially. If elevator 0 stops and opens its door, the entire controller loop stalls for 3 seconds. Elevators 1 and 2 cannot move during that time -- passengers on other elevators literally freeze in place while one elevator loads passengers.
* The fix is **event-driven or async architecture**. Replace `time.sleep()` with state transitions and timers. The door has states CLOSED -> OPENING -> OPEN -> CLOSING -> CLOSED, and each transition is triggered by a timer callback, not a blocking sleep. The elevator run loop checks `if door.state == OPEN and time_since_opened > DOOR_TIMEOUT: door.close()` on each tick without blocking.
* Alternatively, run each elevator in its own thread (the code almost does this but does not). Then door operations on elevator 0 only block elevator 0's thread. But this introduces coordination complexity when multiple elevators need to make decisions based on shared state (like pending requests).
* **Example:** Real elevator controllers use a PLC (programmable logic controller) running a scan cycle. Each cycle reads all inputs (buttons, sensors), evaluates state machines, and sets outputs (motor direction, door commands). Nothing ever blocks -- it is a pure event loop running at 10-50ms cycle time.
**Red flag answer:** "sleep is just for simulation" -- true, but the interviewer is testing whether you can identify the architectural impact. Also a red flag: suggesting `asyncio` without explaining how it would integrate with the existing thread-based design.
**Follow-ups:**
1. If you switch to an event-driven model, how do you handle the edge case where a passenger holds the door open (interrupting the CLOSING -> CLOSED transition)?
2. Redesign the `Elevator.move()` and `Elevator._stop()` methods to be non-blocking, using only state checks and time comparisons instead of sleep.
**Strong answer:**
* The 0.5 multiplier says "an elevator already moving toward you is twice as good as an idle one at the same distance." But that ignores a critical factor: **the elevator's existing stop queue**. An elevator going UP at floor 3 with stops at floors 5, 8, and 12 is NOT equivalent to an idle elevator at floor 3, because it will stop three times before potentially reaching your floor.
* The correct score for a same-direction elevator should factor in the number of intermediate stops and the time cost per stop (door open + dwell + door close, roughly 5-8 seconds each). A better formula: `score = distance + (num_intermediate_stops * STOP_PENALTY)` where intermediate stops are destinations between the elevator's current floor and the request floor.
* For an opposite-direction elevator, the score should account for the full remaining travel in the current direction, the reversal, and then the distance to the request. It is not simply `distance * 2` -- it is `distance_to_last_stop_in_current_direction + distance_from_that_stop_to_request_floor + (num_remaining_stops * STOP_PENALTY)`.
* For idle elevators, the score is simply `distance` since there are no intermediate stops and no direction overhead.
* The 0.5 magic number also fails at boundary conditions. An idle elevator 1 floor away scores 1.0, but an elevator 10 floors away moving toward you scores 5.0. The idle elevator is clearly better, and the scoring correctly reflects that. But an idle elevator 10 floors away scores 10.0, while a same-direction elevator 8 floors away with zero intermediate stops scores 4.0 -- now the moving elevator wins, but only because we ignored the fact it might pick up new passengers at intermediate floors.
* **Example:** The Destination Dispatch systems (ThyssenKrupp TWIN, Otis Compass) use estimated time of arrival (ETA) as the score, not distance. ETA accounts for travel speed, acceleration/deceleration profiles, door operation times, and passenger loading estimates.
**Red flag answer:** "0.5 seems reasonable as a heuristic" without analyzing when it breaks. Also a red flag: not considering intermediate stops in the score calculation, which is the entire point of SCAN vs. shortest-seek.
**Follow-ups:**
1. How would you estimate the STOP\_PENALTY dynamically instead of using a constant -- for example, during rush hour when more passengers board at each stop?
2. If you compute ETA-based scores, that computation takes time. At what point does the scoring overhead itself become a bottleneck, and how would you approximate it?
**Strong answer:**
* Fire mode is a **global state transition** that overrides all normal behavior. The key design insight is that it is not just "go to floor 1" -- there are strict safety sequencing requirements mandated by fire codes (ASME A17.1 in the US).
* **Phase 1 (Recall):** On fire alarm signal, all elevators cancel their current destinations, ignore all new button presses, close doors immediately (overriding door-hold buttons), and travel non-stop to the designated recall floor (usually lobby, but can be alternate if fire is on the lobby floor). Elevators must not stop at any intermediate floor, even if passengers press buttons.
* **Phase 2 (Firefighter Operation):** Once recalled, elevators lock out normal operation. Only a physical key switch allows a firefighter to manually control one elevator with limited functionality (no automatic door close -- doors only close when the firefighter holds the button, preventing them from being trapped).
* **Implementation:** Add an `EMERGENCY` state to `ElevatorState`. In the `ElevatorController`, add a `trigger_fire_mode(fire_floor: int)` method that (1) sets a global `fire_mode = True` flag, (2) determines the recall floor (lobby unless fire is at lobby, then use alternate), (3) for each elevator: clears `_up_stops` and `_down_stops`, force-closes doors, adds recall floor as sole destination, transitions state to EMERGENCY. The `move()` method checks `if self._state == EMERGENCY and self._current_floor == recall_floor: stop and disable`.
* **The critical edge case** is an elevator that is between floors when the alarm triggers. It must complete travel to the nearest floor (you cannot stop between floors -- passengers would be trapped), open doors briefly to allow evacuation, then proceed to recall. The current `move()` implementation moves one floor at a time, so this is handled naturally, but you need to suppress the normal stop logic during emergency recall.
* **Example:** The 2001 WTC evacuation revealed issues with elevator recall when fire was in the lobby. Modern codes require alternate recall floors, and many buildings now have dedicated firefighter elevators with independent power supplies and pressurized shafts.
**Red flag answer:** "Add an emergency button that sends all elevators to floor 1" -- this ignores phased recall, firefighter operation mode, the between-floors edge case, and the fire-on-lobby-floor scenario. Also a red flag: not mentioning that button presses must be ignored during recall.
**Follow-ups:**
1. How do you handle an elevator that has a mechanical fault and cannot move during fire recall -- does it affect the other elevators' behavior?
2. After the fire alarm is cleared, how do you transition back to normal operation? Can you just flip `fire_mode = False`, or are there intermediate states needed?
**Strong answer:**
* Morning rush has a distinctive traffic pattern: almost all trips originate at the lobby (floor 1) going UP, and the destination distribution depends on the building's tenant layout. This is called **up-peak traffic** and it is the hardest pattern for a naive algorithm because all elevators cluster at the lobby and compete for the same pool of passengers.
* **Zone-based partitioning:** Divide the building into zones (floors 1-13, 14-26, 27-40) and assign 2 elevators per zone. Each elevator only stops within its zone. This converts 6 elevators doing 40-floor sweeps into 3 pairs doing 13-floor sweeps -- average trip time drops roughly 3x. The trade-off is that inter-zone travel requires transferring at a sky lobby, and low-demand zones still have 2 elevators even if they only need 1.
* **Dynamic zoning:** During morning rush, assign 4 elevators to lobby express mode (they only serve the lobby for pickup and go directly to each passenger's floor) and keep 2 for inter-floor travel. After rush hour, switch to normal LOOK scheduling. This requires time-of-day awareness and smooth transitions.
* **Destination dispatch (the modern answer):** Instead of up/down buttons, passengers enter their destination floor at the lobby terminal. The controller batches passengers going to adjacent floors into the same elevator. Elevator A takes floors 8, 9, 10; elevator B takes floors 22, 23, 25. Each elevator makes 2-3 stops instead of 10-15. ThyssenKrupp claims 30% reduction in travel time with this approach.
* **The math insight:** With 6 elevators and 40 floors, the theoretical minimum average wait time during up-peak is `round_trip_time / (2 * num_elevators)`. Round trip time = travel\_time\_up + travel\_time\_down + (average\_stops \* stop\_penalty) + loading\_time. The only variables you can control are average\_stops (via destination dispatch) and partitioning (via zoning).
* **Example:** The Burj Khalifa uses a sky lobby system with zone-based partitioning. Passengers take a shuttle elevator to the sky lobby, then transfer to a local elevator for their zone. This is the only practical approach for buildings over 60 floors.
**Red flag answer:** "Just add more elevators" -- this does not address the scheduling problem and shows no understanding of the traffic pattern. Also a red flag: proposing a single algorithm without analyzing the traffic pattern first.
**Follow-ups:**
1. At 5 PM the traffic pattern reverses -- everyone goes DOWN to the lobby. Does your morning rush optimization hurt the evening rush, and how would you handle the transition?
2. What data would you collect during the first month of building operation to calibrate your partitioning, and how often would you re-calibrate?
**Strong answer:**
* Setting `elevator._state` directly from outside the class violates **encapsulation** and the **Single Responsibility Principle**. The controller is reaching into the elevator's internals and mutating private state (note the underscore prefix convention). The Elevator class should own its own state transitions and enforce valid transitions -- for example, you should not be able to go from MOVING to MAINTENANCE without first stopping.
* The proper design is a **state machine with explicit transition rules**. Define a transition table: STOPPED -> MAINTENANCE (valid), MOVING -> MAINTENANCE (invalid -- must stop first), MAINTENANCE -> STOPPED (valid, after inspection). The Elevator class exposes `enter_maintenance()` and `exit_maintenance()` methods that validate the transition internally and raise an error if the transition is not allowed.
* A full state machine for an elevator has more states than the current 3. A production model includes: IDLE, MOVING\_UP, MOVING\_DOWN, STOPPING, DOORS\_OPENING, DOORS\_OPEN, DOORS\_CLOSING, EMERGENCY\_RECALL, MAINTENANCE, OUT\_OF\_SERVICE. Each state has a defined set of valid transitions and associated actions.
* **Implementation approach:** Use the State pattern -- each state is a class with methods like `on_floor_request()`, `on_timer_tick()`, `on_door_sensor()`. The elevator holds a reference to its current state object and delegates behavior. When the state changes, you swap the state object. This eliminates the giant if/else chains that inevitably grow as you add states.
* The State pattern also makes it trivial to add the emergency mode: create an `EmergencyState` class that ignores button presses, overrides door behavior, and only transitions to `IdleState` when the emergency is cleared.
* **Example:** The State pattern is exactly how vending machines, ATMs, and traffic lights are modeled in embedded systems. Each state object knows its valid transitions and refuses invalid ones, making it impossible to reach an undefined state through a programming error.
**Red flag answer:** "Just add a setter method" -- this is better than direct access but still does not enforce valid transitions. Also a red flag: not identifying the MOVING -> MAINTENANCE transition as dangerous (the elevator would stop between floors with passengers inside).
**Follow-ups:**
1. If the elevator is currently between floors (MOVING state) and the maintenance team needs to take it offline urgently, what is the safe sequence of state transitions?
2. How would you log and audit all state transitions for regulatory compliance, and how does the State pattern make that easier than the current if/else approach?
**Strong answer:**
* `can_serve` returns True only if the elevator is idle OR if it is moving in the request's direction with the request floor ahead of it. This is too conservative and misses a common optimization case.
* **Scenario:** Elevator is on floor 8 going UP with `_up_stops = [10, 15]`. A request comes in from floor 12 going DOWN. `can_serve` returns False because the elevator is going UP and the request direction is DOWN. So the controller assigns a different elevator, possibly one much further away. But elevator 0 will *pass through floor 12* on its way to 15. It could stop at 12, pick up the passenger, and add their DOWN destination to `_down_stops` for the return trip. This is exactly what the SCAN algorithm should do, but `can_serve` prevents it.
* **The root issue** is that `can_serve` conflates two things: "can the elevator pick up this passenger?" and "can the elevator immediately serve their direction?" In SCAN, these are different. The elevator can pick up a DOWN-requesting passenger on the way up, as long as the passenger understands they will ride up to 15 first and then come back down.
* However, this introduces a UX question: do passengers accept riding past their pickup floor in the "wrong" direction? In some systems (like destination dispatch), yes. In traditional systems with hall lanterns showing direction, no -- the UP arrow is lit, and DOWN-bound passengers would not board.
* **A more nuanced `can_serve`** would return a score rather than a boolean: "this elevator can serve this request with an estimated detour of X floors." The scheduler then compares detour costs across all elevators and picks the lowest cost, even if it means a slight detour.
* **Example:** Imagine a 3-elevator building where elevator A is going UP past the request floor, elevator B is idle 20 floors away, and elevator C is in maintenance. The current `can_serve` would reject A and send B on a 20-floor trip, when A could have served the request with zero additional travel.
**Red flag answer:** "can\_serve looks correct to me" without tracing through a concrete scenario. Also a red flag: not distinguishing between picking up a passenger and serving their destination direction.
**Follow-ups:**
1. If you allow the elevator to pick up a DOWN-requesting passenger while going UP, how do you update the hall lantern (direction indicator) to avoid confusing passengers who should not board?
2. How would you modify `can_serve` to return a cost instead of a boolean, and what factors would you include in the cost function?