Bird
Raised Fist0

Elevator System - Scheduling Algorithm, Multiple Lifts, Floor Queue

LLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Elevator System - Scheduling Algorithm, Multiple Lifts, Floor Queue
Design a scalable elevator system managing multiple lifts with scheduling and floor queues
mediumSystems with State MachinesFreq: high
Prerequisites:State PatternScheduling AlgorithmsConcurrency in Java
⚙️
Functional Requirements
  • Support multiple elevators operating concurrently
  • Schedule elevators to minimize wait and travel time
  • Maintain queues of floor requests per direction
  • Elevators maintain states: IDLE, MOVING_UP, MOVING_DOWN, DOOR_OPEN
  • Handle concurrent requests from multiple floors and inside elevators
  • Prevent double assignment of elevators to same request
  • Allow dynamic addition/removal of elevators
👤
Use Cases
  • Passenger requests elevator from a floor (up/down)
  • Passenger selects destination floor inside elevator
  • Elevator moves to requested floors based on scheduling
  • Elevator opens/closes doors at floors
  • System handles multiple concurrent requests efficiently
  • ElevatorController assigns elevators to floor requests
  • System queues requests if all elevators busy
🧑‍💻
Actors
  • Passenger
  • Elevator
  • ElevatorController
  • Floor
❓
Clarifying Questions to Ask
  • How many elevators and floors should the system support concurrently?
  • Are floor requests directional (up/down) or just floor numbers?
  • Should the scheduling algorithm prioritize nearest elevator or load balancing?
  • How to handle simultaneous requests from multiple passengers on same floor?
  • Is there a pricing or priority strategy for certain floors or passengers?
  • What happens if an elevator is out of service during operation?
  • Are requests cancellable or modifiable after submission?
Out of Scope
✗ Detailed UI design
✗ Elevator maintenance and fault tolerance
✗ Energy optimization
✗ Emergency handling (fire, power failure)
⚡
QPS Calculation
write qps100
read qps1000
peak qps1500
🖥️
Server Estimate
elevator controller servers3
scheduler servers2
database servers3
🔢
Enumerations
enum ElevatorState
IDLE | MOVING_UP | MOVING_DOWN | DOOR_OPEN
Defines finite states of an elevator for state machine implementation; using enum prevents invalid states and enables exhaustive switch-case handling.
enum Direction
UP | DOWN | NONE
Represents direction of elevator movement or floor request; NONE used for idle or no direction. Enum avoids string typos and clarifies logic.
enum DoorState
OPEN | CLOSED | OPENING | CLOSING
Models door lifecycle states for elevator doors; enum ensures consistent door state transitions.
📦
Elevator
7 fields
private final int idprivate volatile ElevatorState stateprivate volatile int currentFloorprivate final TreeSet<Integer> upStopsprivate final TreeSet<Integer> downStopsprivate volatile DoorState doorStateprivate final Object lock
Maintain elevator state machine, track current floor and stops, manage door state, and execute movement commands.
Why thisJava synchronized methods and volatile variables ensure thread-safe state updates and visibility in concurrent environments.
Why notUsing lock-free or reactive frameworks adds complexity and overhead; synchronized methods provide simpler, reliable concurrency control.
Key Methods
public synchronized void moveOneFloor()Moves elevator one floor in current direction atomically, updates currentFloor and state.
public synchronized void addStop(int floor)Adds a floor to the appropriate stop queue (upStops or downStops) based on current direction.
public synchronized void openDoor()Transitions doorState to OPEN if currently CLOSED or CLOSING.
public synchronized void closeDoor()Transitions doorState to CLOSED if currently OPEN or OPENING.
public ElevatorState getState()Returns current elevator state with volatile visibility guarantees.
📦
FloorRequest
2 fields
private final int floorNumberprivate final Direction direction
Represents a passenger request from a floor with direction (up/down).
Why thisImmutable object with final fields ensures thread safety and consistency.
Why notMutable request objects risk inconsistent state in concurrent scenarios.
Key Methods
public int getFloorNumber()Returns the floor number of the request.
public Direction getDirection()Returns the direction of the request.
📦
ElevatorController
4 fields
private final List<Elevator> elevatorsprivate final Map<Integer, Queue<FloorRequest>> upFloorQueuesprivate final Map<Integer, Queue<FloorRequest>> downFloorQueuesprivate final Object schedulingLock
Central controller that schedules elevators to floor requests, manages floor queues, and dispatches commands.
Why thisSynchronized methods and explicit locks ensure consistent scheduling decisions in concurrent environment.
Why notEvent-driven or actor models add complexity; synchronized approach is straightforward for interview context.
Key Methods
public synchronized void requestElevator(FloorRequest request)Adds floor request to queue and triggers scheduling.
private synchronized Elevator assignElevator(FloorRequest request)Selects the best elevator for the request based on scheduling algorithm.
public synchronized void step()Advances system state by moving elevators and processing stops.
📦
Floor
3 fields
private final int floorNumberprivate final Queue<FloorRequest> upQueueprivate final Queue<FloorRequest> downQueue
Represents a floor with queues for up and down requests.
Why thisSynchronized methods protect queue integrity during concurrent access.
Why notLock-free queues could be used but add complexity; synchronized is simpler for this scale.
Key Methods
public synchronized void addRequest(Direction direction)Adds a floor request to the appropriate queue.
public synchronized FloorRequest pollRequest(Direction direction)Removes and returns the next request in the queue for the given direction.
📦
Scheduler
1 fields
private final ElevatorController controller
Implements scheduling algorithm to assign elevators to floor requests efficiently.
Why thisCentralizing scheduling logic improves maintainability and allows algorithm swapping.
Why notDistributing scheduling to elevators complicates coordination and consistency.
Key Methods
public synchronized Elevator schedule(FloorRequest request, List<Elevator> elevators)Returns the best elevator to serve the given floor request.
🔗
Relationships
ElevatorController◇──►Elevator[1..*]
aggregationElevators exist independently; controller manages references
ElevatorController──►FloorRequest[0..*]
associationFloorRequests created by passengers, managed temporarily by controller
Floor◆──►FloorRequest[0..*]
compositionFloor owns requests in queues; requests destroyed when served
🗄️
ElevatorStatus
PK: elevatorId
elevatorId INTtimestamp TIMESTAMPcurrentFloor INTstate VARCHARdoorState VARCHAR
Stores real-time status updates of each elevator.
🗄️
FloorRequests
PK: floorNumber
floorNumber INTrequestTime TIMESTAMPdirection VARCHARrequestId UUID
Stores floor requests queued by direction and time.
🔌
POST
RequestElevator
Request
{
  "floorNumber": "int",
  "direction": "string (UP or DOWN)"
}
Response
{
  "status": "string",
  "assignedElevatorId": "int"
}
Allows passengers to request an elevator from a floor.
🔌
POST
SelectDestination
Request
{
  "elevatorId": "int",
  "destinationFloor": "int"
}
Response
{
  "status": "string"
}
Passenger selects destination floor inside elevator.
🔌
GET
GetElevatorStatus
Request
{}
Response
{
  "currentFloor": "int",
  "state": "string",
  "doorState": "string"
}
Fetches current status of specified elevator.

Practice

(1/5)
1. In a vehicle rental system, should Vehicle be designed as an abstract class or an interface if it needs to hold common state like licensePlate and rentalStatus? Why?
easy
A. Abstract class, because it forces all subclasses to implement all methods explicitly.
B. Interface, because it allows multiple inheritance and enforces method signatures without state.
C. Interface, because Java interfaces can now have default methods and fields for state.
D. Abstract class, because it can hold shared state and provide default behavior for subclasses.

Solution

  1. Step 1: Analyze state requirements

    Vehicle needs to hold common mutable state like licensePlate and rentalStatus, which interfaces cannot hold as fields.

  2. Step 2: Choose correct OOP construct

    Abstract classes can have instance variables and default method implementations, making them suitable for shared state. Interfaces cannot hold instance state, only constants.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Shared mutable state -> abstract class, not interface [check]
Hint: Shared state needs abstract class, interfaces only define behavior [check]
Common Mistakes:
2. In the brokerage system, should the Order entity be designed as an abstract class or an interface? Consider that orders have common state fields like orderId and timestamp, but different types of orders have distinct execution logic.
easy
A. Abstract class, because it can hold shared state and provide default implementations for common behavior.
B. Interface, because Java 8+ interfaces can have default methods and fields for state.
C. Interface, because it allows multiple inheritance and enforces method signatures without state.
D. Abstract class, because it forces all subclasses to implement all methods explicitly.

Solution

  1. Step 1: Analyze state vs behavior requirements

    Orders share common state fields like orderId and timestamp, which require storage and possibly shared methods.

  2. Step 2: Why abstract class fits better

    Abstract classes can hold state and provide default method implementations, reducing code duplication. Interfaces cannot hold instance state.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Shared state + default behavior -> abstract class [check]
Hint: Stateful base class -> abstract class, not interface [check]
Common Mistakes:
3. Adding a WeekendFeeStrategy to calculate weekend parking fees requires which minimum change to the current design that uses a FeeStrategy interface?
medium
A. Modify the existing FeeStrategy interface to add a isWeekend() method and update all implementations.
B. Create a new WeekendFeeStrategy class implementing FeeStrategy and inject it where needed without modifying existing classes.
C. Create a subclass of FeeStrategy that overrides all methods and duplicates existing logic.
D. Add a boolean flag isWeekend to the ParkingLot class and modify fee calculation logic accordingly.

Solution

  1. Step 1: Identify SOLID principle involved

    The Open-Closed Principle (OCP) requires that new functionality be added by extending, not modifying, existing code.

  2. Step 2: Evaluate options against OCP

    Create a new WeekendFeeStrategy class implementing FeeStrategy and inject it where needed without modifying existing classes. respects OCP by adding a new class implementing the interface without changing existing code. Add a boolean flag isWeekend to the ParkingLot class and modify fee calculation logic accordingly. modifies ParkingLot, violating OCP. Options A and D modify or duplicate existing code, violating OCP or causing complexity.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    New strategy class + no existing code change -> OCP compliance [check]
Hint: OCP: extend with new class, don't modify existing code [check]
Common Mistakes:
4. ElectricCar pieces require special ChargingSpot compatibility in the Jigsaw Puzzle System. What is the minimum design change to support ElectricCar and ChargingSpot without modifying existing classes?
hard
A. Add ELECTRIC_CAR to PieceType enum, CHARGING to SpotType enum, create ElectricCarPiece subclass, and update compatibility map externally.
B. Modify existing Piece and Spot classes to include electric-specific fields and logic.
C. Create a new ElectricCarPiece class implementing a new interface and modify Board to handle it specially.
D. Add a god-class CompatibilityManager that hardcodes all compatibility rules including electric cars.

Solution

  1. Step 1: Identify extensibility requirements

    New piece and spot types must be added without modifying existing classes to respect OCP.

  2. Step 2: Evaluate minimal change approach

    Adding new enum values and subclass for ElectricCarPiece plus updating compatibility map externally allows extension without modifying existing code.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    New enums and subclass extend system without changing existing classes [check]
Hint: Add enums + subclass + external map update = minimal invasive extension [check]
Common Mistakes:
5. ElectricCar requires ChargingSpots in the parking system using Prototype pattern. What is the minimum change to support this without modifying existing classes?
hard
A. Modify Vehicle base class to include charging logic and add ChargingSpot as a subclass of Spot
B. Add charging logic inside Vehicle clone() and modify SpotCompatibility map inside existing classes
C. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map externally
D. Create a god-class that handles both ElectricCar and ChargingSpot logic to avoid modifying existing classes

Solution

  1. Step 1: Identify extensibility requirements

    Adding ElectricCar and ChargingSpot must avoid modifying existing classes to respect OCP.

  2. Step 2: Evaluate options for minimal invasive change

    Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map externally adds new enum values and subclasses externally, updating compatibility map without changing existing code. Options B and C modify base classes, violating OCP. Create a god-class that handles both ElectricCar and ChargingSpot logic to avoid modifying existing classes creates god-class, violating SRP and maintainability.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    New enums + subclass + external map update -> minimal change, OCP respected [check]
Hint: New enums + subclass + external map -> minimal invasive change [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard