Designing an Elevator System

Problem Statement

Design an elevator system for a building with multiple elevators and floors. The system should efficiently handle passenger requests from floors (external requests) and destination selections from inside elevators (internal requests). It must manage scheduling across multiple elevators to minimize wait and travel times, handle concurrent requests safely, and incorporate safety mechanisms such as emergency stops, door sensors, and overweight detection.

This is one of the most frequently asked Low-Level Design (LLD) interview problems because it tests your understanding of state machines, scheduling algorithms, concurrency, design patterns, and real-world trade-offs - all within a single problem.

---

Requirements

Functional Requirements

1. Request Elevator (External Request) - A passenger on any floor can press an UP or DOWN button to request an elevator. The system assigns the most appropriate elevator.
2. Select Destination (Internal Request) - Once inside, a passenger selects a destination floor using the elevator panel buttons.
3. Move Between Floors - Elevators travel between floors, stopping at requested floors in an optimized order.
4. Open/Close Doors - Doors open when the elevator arrives at a requested floor and close after a configured duration or when the close button is pressed.
5. Display Current Floor - Each elevator displays its current floor both inside the cabin and on external floor displays.
6. Handle Multiple Simultaneous Requests - The system processes multiple external and internal requests concurrently across all elevators.
7. Emergency Stop - Any elevator can be stopped immediately via an emergency button, overriding all other operations.
8. Overweight Detection - The system detects when an elevator exceeds its weight capacity and prevents door closure/movement until resolved.

Non-Functional Requirements

1. Minimize Wait Time - Passengers should not wait excessively for an elevator to arrive at their floor.
2. Minimize Travel Time - Once inside, passengers should reach their destination with minimal intermediate stops.
3. Handle Concurrent Requests - The system must be thread-safe and handle race conditions when multiple requests arrive simultaneously.
4. Safety - Door sensors prevent closing on obstructions; overweight sensors prevent movement when capacity is exceeded.
5. Energy Efficiency - Idle elevators should park at strategic floors (lobby, middle floors) to reduce average response time and energy consumption.

---

Constraints & Assumptions

Assumptions:

• All elevators serve all floors (no express elevators by default).
• External buttons indicate direction (UP/DOWN), not destination.
• The system is centralized - one dispatcher coordinates all elevators.
• Elevators do not communicate directly with each other.

---

Key Entities & Relationships

---

ASCII Class Diagram

┌─────────────────────────────────────────────────────────────────────┐
│                         ElevatorSystem                               │
│─────────────────────────────────────────────────────────────────────│
│ - elevators: List<Elevator>                                         │
│ - floors: List<Floor>                                               │
│ - dispatcher: Dispatcher                                            │
│─────────────────────────────────────────────────────────────────────│
│ + requestElevator(floor, direction): void                           │
│ + selectDestination(elevatorId, floor): void                        │
│ + emergencyStop(elevatorId): void                                   │
│ + getStatus(): SystemStatus                                         │
└──────────────────────┬──────────────────────────────────────────────┘
                       │ manages
          ┌────────────┼────────────────┐
          ▼            ▼                ▼
┌──────────────┐ ┌──────────────┐ ┌──────────────────┐
│   Elevator   │ │    Floor     │ │    Dispatcher     │
│──────────────│ │──────────────│ │──────────────────│
│ - id         │ │ - floorNum   │ │ - strategy:       │
│ - currentFlr │ │ - upButton   │ │   ScheduleStrategy│
│ - direction  │ │ - downButton │ │──────────────────│
│ - state      │ │ - display    │ │ + assignElevator( │
│ - door       │ │──────────────│ │   request): Elev  │
│ - requests[] │ │ + pressUp()  │ │ + setStrategy()   │
│ - capacity   │ │ + pressDown()│ └──────────────────┘
│ - weight     │ └──────────────┘
│──────────────│          ┌──────────────────────────┐
│ + move()     │          │     «interface»           │
│ + stop()     │          │   SchedulingStrategy      │
│ + openDoor() │          │──────────────────────────│
│ + closeDoor()│          │ + selectElevator(         │
│ + addRequest()│         │   request, elevators):    │
└──────────────┘          │   Elevator                │
                          └──────────────────────────┘
       ┌──────────────────────────┐
       │       Request            │
       │──────────────────────────│
       │ - sourceFloor            │
       │ - direction              │
       │ - timestamp              │
       └─────────┬────────────────┘
                 │
       ┌─────────┴─────────┐
       ▼                   ▼
┌──────────────┐  ┌───────────────┐
│ExternalRequest│  │InternalRequest│
│──────────────│  │───────────────│
│ - direction  │  │ - destFloor   │
│ - srcFloor   │  │ - elevatorId  │
└──────────────┘  └───────────────┘

---

Scheduling Algorithms

1. FCFS (First Come, First Served)

The simplest approach - requests are served in the order they arrive. The elevator completes one request fully before moving to the next.

How it works: Maintain a FIFO queue. Dequeue the next request, travel to that floor, then dequeue again.

Drawback: An elevator on floor 1 going to floor 10 will ignore a request on floor 2 if it arrived later. Extremely inefficient for multi-request scenarios.

2. SSTF (Shortest Seek Time First)

Always serve the nearest pending request from the elevator's current position.

How it works: From the current floor, calculate the distance to all pending requests and pick the closest one.

Drawback: Starvation - requests far from the elevator's operating zone may never be served if closer requests keep arriving.

3. SCAN (Elevator Algorithm)

The elevator moves in one direction, serving all requests in that direction, then reverses and serves requests in the opposite direction. It travels to the extreme end of the building before reversing.

How it works: Move UP serving all UP requests, reach the top floor, reverse to DOWN, serve all DOWN requests, reach the bottom, reverse again.

Drawback: Travels to building extremes even if no requests exist there, wasting time and energy.

4. LOOK (Improved SCAN)

Like SCAN, but the elevator reverses direction at the last request in the current direction rather than traveling to the building's extreme floor.

How it works: Move UP serving requests. When no more requests exist above, reverse immediately. Same for DOWN.

Advantage: More efficient than SCAN - avoids unnecessary travel to empty extremes. This is the most commonly used algorithm in real elevators.

5. Destination Dispatch

Passengers enter their destination floor before boarding (at a kiosk on the floor). The system groups passengers going to similar floors into the same elevator.

How it works: External panels accept destination input. The dispatcher assigns passengers to elevators that are already heading to nearby destinations, minimizing stops per trip.

Advantage: Dramatically reduces travel time in high-rise buildings. Used in modern skyscrapers.

Comparison Table

---

State Machine

                    ┌─────────────────────────────┐
                    │                             │
                    ▼                             │
              ┌──────────┐                       │
              │   IDLE   │◄──────────────────┐   │
              └────┬─────┘                   │   │
                   │ request received         │   │
          ┌────────┴────────┐                │   │
          ▼                 ▼                │   │
   ┌────────────┐   ┌─────────────┐         │   │
   │ MOVING_UP  │   │ MOVING_DOWN │         │   │
   └─────┬──────┘   └──────┬──────┘         │   │
         │                  │                │   │
         │ arrived at       │ arrived at     │   │
         │ target floor     │ target floor   │   │
         ▼                  ▼                │   │
   ┌─────────────────────────────┐           │   │
   │          STOPPED            │           │   │
   └──────────────┬──────────────┘           │   │
                  │ open doors               │   │
                  ▼                          │   │
   ┌─────────────────────────────┐           │   │
   │         DOOR_OPEN           │           │   │
   │  (timer / sensor active)    │           │   │
   └──────────────┬──────────────┘           │   │
                  │ timeout / close pressed  │   │
                  ▼                          │   │
   ┌─────────────────────────────┐           │   │
   │        DOOR_CLOSED          │───────────┘   │
   └──────────────┬──────────────┘               │
                  │ no more requests              │
                  └──────────────────────────────►┘

   ════════════════════════════════════════════════
   EMERGENCY (can be triggered from ANY state)
   ════════════════════════════════════════════════

         ┌──────────────┐
    ──── │  EMERGENCY   │ ◄── emergency button from any state
         │  (all stop)  │
         └──────┬───────┘
                │ reset by maintenance
                ▼
         ┌──────────────┐
         │ MAINTENANCE  │ ──► manual inspection ──► IDLE
         └──────────────┘

State Transitions:

• IDLE → MOVING_UP/DOWN: New request assigned to this elevator
• MOVING → STOPPED: Arrived at a floor with a pending request
• STOPPED → DOOR_OPEN: Doors open for passenger entry/exit
• DOOR_OPEN → DOOR_CLOSED: Timer expires or close button pressed (no obstruction)
• DOOR_CLOSED → MOVING_UP/DOWN: More requests pending in queue
• DOOR_CLOSED → IDLE: No more requests; elevator parks
• ANY → EMERGENCY: Emergency button pressed; immediate halt
• EMERGENCY → MAINTENANCE: System reset initiated
• MAINTENANCE → IDLE: Technician clears the elevator for service

---

Design Decisions & Trade-offs

1. Single vs. Multiple Dispatchers

Recommendation: Start with a single dispatcher. For buildings with 6+ elevators, consider zone-based dispatching (e.g., elevators 1-3 serve floors 1-15, elevators 4-6 serve floors 15-30).

2. Request Assignment Strategy

• Nearest Elevator: Assign to the closest idle or same-direction elevator. Simple and effective for low-rise buildings.
• Least Loaded: Assign to the elevator with the fewest pending requests. Balances load but may increase wait time.
• Zone-Based: Partition floors into zones; each zone has dedicated elevators. Reduces travel distance but underutilizes elevators during off-peak hours.

Recommendation: Use a weighted scoring system combining distance, current load, and direction alignment.

3. Direction Priority

• Continue in Current Direction: Serve all requests in the current direction before reversing (LOOK algorithm). Reduces direction changes and mechanical wear.
• Nearest Request: Always go to the closest request regardless of direction. Lower average wait time but more direction changes.

Recommendation: Continue in current direction (LOOK) for general use. Switch to nearest-request for low-traffic periods.

4. Door Timing

• Fixed Timer: Doors stay open for a fixed duration (e.g., 4 seconds). Predictable but may close on passengers.
• Sensor-Based: Doors remain open while sensors detect movement in the doorway. Safer but can delay departure if passengers linger.

Recommendation: Hybrid - fixed timer with sensor override. Doors attempt to close after the timer but reopen if the sensor is triggered (with a maximum retry count to prevent indefinite blocking).

5. Emergency Handling

• Dedicated Emergency Elevator: One elevator is always reserved for emergencies. Wastes capacity during normal operation.
• All Stop: All elevators stop and open doors at the nearest floor. Disrupts all passengers.
• Selective Response: Only the affected elevator stops; others continue. Balanced approach.

Recommendation: Selective response for mechanical issues. All-stop with nearest-floor evacuation for fire alarms (per building codes).

---

Design Patterns Used

Why These Patterns Matter in Interviews

The Strategy pattern is the most critical here - interviewers want to see that you can decouple the scheduling algorithm from the system. This allows A/B testing different algorithms, time-of-day switching (LOOK during peak, SSTF during off-peak), and easy extensibility.

The State pattern eliminates the "state explosion" problem. Without it, you'd have nested conditionals checking if (moving && doorOpen && emergencyPressed) - unmaintainable and error-prone.

---

Edge Cases

1. All Elevators Busy - Queue the request. Assign to the first elevator that becomes available or the one that will arrive soonest based on current trajectory.

2. Simultaneous Requests from Same Floor (UP + DOWN) - Treat as two separate requests. Assign to different elevators if possible. If only one elevator is available, serve the request matching its current direction first.

3. Elevator at Capacity - Skip the floor for external requests (don't open doors for new passengers). Continue serving internal requests. Signal the dispatcher to assign another elevator to the waiting floor.

4. Power Failure - Engage electromagnetic brakes immediately. Switch to battery backup for emergency lighting and communication. Move to nearest floor on generator power and open doors.

5. Stuck Between Floors - Trigger EMERGENCY state. Activate intercom. Do not attempt to move. Wait for maintenance. Reassign all pending requests to other elevators.

6. Maintenance Mode - Remove elevator from dispatcher's available pool. Complete current trip (deliver existing passengers) then park at ground floor. Redistribute its pending requests.

7. VIP/Express Elevator - Assign highest priority. Preempt non-express requests. Can skip intermediate floors. Implement as a priority queue with VIP requests at the front.

8. Door Sensor Repeated Triggers - After N consecutive sensor triggers (e.g., 5), sound an alarm and hold doors open indefinitely until manual intervention. Prevents infinite open-close loops.

9. Rapid Button Pressing - Debounce button inputs. Ignore duplicate requests for the same floor within a short window.

10. Conflicting Internal Requests - If passengers select floors in opposite directions, serve in the current direction first (LOOK behavior).

---

Extensibility Points

1. Express Elevators - Configure certain elevators to skip floors (e.g., serve only lobby and floors 20-40). Modify the dispatcher to route requests accordingly.

2. Zone-Based Assignment - Partition the building into zones. Low-zone elevators serve floors 1-15, high-zone serve 15-30. Reduces average travel time in tall buildings.

3. Destination Dispatch - Replace floor buttons with destination kiosks. Requires UI changes and a more sophisticated grouping algorithm in the dispatcher.

4. Energy-Saving Mode - During off-peak hours, park idle elevators at strategic floors (lobby, middle). Reduce the number of active elevators and consolidate requests.

5. Predictive Scheduling (ML-Based) - Learn traffic patterns (morning rush = lobby→upper floors, evening = upper→lobby). Pre-position elevators before demand spikes.

6. Accessibility Features - Extended door open time for accessibility-flagged requests. Audio announcements. Braille buttons. Priority service for accessibility requests.

7. Multi-Building Integration - Sky lobbies connecting towers. Transfer floors where passengers switch between local and express elevators.

8. Real-Time Monitoring Dashboard - WebSocket-based live view of all elevator positions, states, and queue depths for building management.

---

Interview Follow-ups

Q1: How would you optimize for a 50-floor building with 8 elevators?

Answer: Use a combination of zone-based assignment and destination dispatch. Divide into zones: elevators 1-3 serve floors 1-20 (local), elevators 4-6 serve floors 20-40 (express from lobby), elevators 7-8 serve floors 40-50 (express from lobby). Implement destination dispatch at the lobby - passengers enter their floor at a kiosk, and the system groups them into elevators heading to nearby floors. During peak hours (morning arrival, evening departure), bias elevator parking positions toward the lobby. Use predictive positioning based on historical traffic data to pre-stage elevators before rush periods.

Q2: How do you prevent starvation?

Answer: Implement an aging mechanism. Each pending request has a timestamp. If a request has been waiting longer than a threshold (e.g., 60 seconds), its priority increases. The dispatcher periodically scans for aged requests and forces assignment even if it's suboptimal. Additionally, the LOOK algorithm inherently prevents starvation because it guarantees every floor in the current direction will be served before reversal - no request waits more than one full sweep cycle. For SSTF, add a maximum wait time after which the farthest request gets promoted to highest priority.

Q3: How would you handle the morning rush hour when everyone arrives at the lobby?

Answer: Implement "up-peak" mode detection. When the system detects a high volume of requests from the lobby (e.g., >70% of requests originate from floor 1), switch to up-peak strategy: all idle elevators return to the lobby immediately. Use destination dispatch to group passengers by destination floor, minimizing stops per trip. Temporarily disable down-calls from upper floors (or assign only one elevator to down-service). This maximizes throughput from the lobby during peak ingress.

Hint-Only Follow-ups

Q4: How would you design the system to handle a fire alarm?

• Hint: Think about building codes - elevators must go to a designated floor (usually lobby or fire floor +1). Consider: which elevators stop? Do doors open? What about passengers mid-transit? How does the fire floor affect routing?

Q5: How would you implement fair load balancing across elevators to prevent uneven wear?

• Hint: Consider tracking cumulative trips, distance traveled, and door cycles per elevator. Factor "wear score" into the dispatcher's assignment algorithm. Think about periodic rotation of primary/secondary assignments and maintenance scheduling based on usage metrics.

---

Counter Questions to Ask Interviewer

Before diving into design, clarify scope with these questions:

1. How many floors and elevators? - This determines whether you need zone-based dispatching or a simple single-dispatcher approach.

2. Is this a commercial building, residential, or hospital? - Traffic patterns differ dramatically. Hospitals need priority elevators for emergencies. Residential has predictable morning/evening peaks.

3. Do we need destination dispatch or traditional UP/DOWN buttons? - This fundamentally changes the external request model and dispatcher complexity.

4. Should all elevators serve all floors? - Express elevators and zone restrictions significantly alter the design.

5. What's the expected peak traffic? - Determines queue sizing, number of active elevators, and whether predictive scheduling is needed.

6. Are there accessibility or regulatory requirements? - Affects door timing, audio systems, and priority handling.

7. Should we handle power failures and emergency scenarios? - Determines whether we need state persistence, battery backup logic, and evacuation protocols.

8. Is this a real-time system with hard latency requirements, or is best-effort acceptable? - Affects threading model and whether we need real-time OS considerations.

---

References

1. Elevator Scheduling Algorithms - The LOOK algorithm is the industry standard for most commercial elevators. It's directly analogous to the LOOK disk scheduling algorithm in operating systems, where the disk head moves in one direction serving requests, then reverses at the last request rather than the disk edge.

2. SCAN/LOOK Disk Scheduling Analogy - Understanding disk scheduling (from OS courses) maps directly to elevator scheduling. The "disk head" is the elevator, "tracks" are floors, and "I/O requests" are passenger requests. This analogy is useful for explaining trade-offs in interviews.

3. Destination Dispatch Systems - Implemented by Schindler (PORT), ThyssenKrupp (AGILE), and KONE (Polaris). These systems report 30% reduction in travel time for buildings over 30 floors.

4. Design Patterns: Elements of Reusable Object-Oriented Software (Gang of Four) - Strategy, State, Observer, and Command patterns as applied to real-time control systems.

5. Real-World Constraints - ASME A17.1 (Safety Code for Elevators) governs door timing, emergency protocols, and capacity limits. EN 81 is the European equivalent.

6. Traffic Analysis - Uppeak, downpeak, interfloor, and balanced traffic patterns. Each requires different dispatcher strategies for optimal performance.

---

Summary

The Elevator System design problem tests multiple dimensions of software engineering:

• State management - Complex state machine with safety-critical transitions
• Algorithm design - Scheduling optimization with real-world constraints
• Concurrency - Multiple elevators handling simultaneous requests
• Extensibility - Clean separation of concerns enabling future enhancements
• Trade-off analysis - No single "correct" answer; every choice has consequences

The key insight interviewers look for: separate the scheduling policy from the mechanism. The elevator knows how to move and open doors (mechanism). The dispatcher decides which elevator serves which request (policy). This separation - implemented via the Strategy pattern - is what makes the system maintainable and extensible.

Start your interview answer with the requirements, draw the class diagram, explain the LOOK algorithm as your default scheduling strategy, walk through the state machine, and then discuss trade-offs. This demonstrates both breadth and depth - exactly what interviewers want to see.

Related Topics

• Strategy Pattern
• State Pattern
• Observer Pattern
• Command Pattern
• Thread Safety and Synchronization