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
40 min · medium
medium

Design an elevator system for a building with 5 floors and 4 elevators. The system must handle multiple concurrent requests from floors and inside elevators, schedule elevators efficiently to minimize wait time, and maintain queues per floor. Elevators can move up or down, stop at requested floors, and handle door open/close states.

Given Info
  • Building has 5 floors numbered 1 to 5.
  • There are 4 elevators serving all floors.
  • Each floor maintains a queue of up/down requests.
  • Elevators have states: MOVING_UP, MOVING_DOWN, IDLE, DOOR_OPEN.
  • Scheduling algorithm should assign elevators to requests minimizing wait time.
  • Concurrent requests can come from multiple floors and inside elevators.
📋
Guided Steps
1/5
Step 1
Define Elevator and Floor Entities with States
Design Elevator and Floor classes capturing their states and behaviors. Consider how to represent elevator direction and door states using Java enums.
💡 Hint
Use Java enums for elevator direction and door state to ensure type safety and exhaustive switch-case handling.
Key Decision
Use enum ElevatorDirection {UP, DOWN, IDLE} and enum DoorState {OPEN, CLOSED} for elevator states - enums provide compile-time safety and prevent invalid states unlike Strings.
Interviewer Expectation
Mid: Defines enums for direction and door state. Senior: Explains how enums enable exhaustive switch-case and prevent invalid states at compile time.
⚠️Common Wrong Answer
Using String constants for direction and door state leads to runtime bugs due to typos and no compile-time checks.
Step 2
Design Floor Queues and Request Handling
Model floor queues to hold up/down requests. Decide how to represent requests and how floors enqueue them. Consider thread safety for concurrent requests.
💡 Hint
Use thread-safe concurrent collections like ConcurrentLinkedQueue for floor queues to handle concurrent enqueues without explicit synchronization.
Key Decision
Use ConcurrentLinkedQueue<Request> for floor queues - avoids explicit synchronization and prevents race conditions when multiple threads add requests concurrently.
Interviewer Expectation
Mid: Uses thread-safe queue for floor requests. Senior: Explains how ConcurrentLinkedQueue avoids race conditions without blocking, allowing high concurrency.
⚠️Common Wrong Answer
Using non-thread-safe collections like LinkedList for queues causes race conditions and data corruption under concurrent access.
Step 3
Implement Elevator Scheduling Algorithm
Design a scheduling component that assigns elevators to floor requests. Consider how to synchronize assignment to avoid double booking elevators.
💡 Hint
Use synchronized methods or locks to atomically check elevator availability and assign requests, preventing race conditions in multi-threaded environment.
Key Decision
Use synchronized boolean assignRequest(Request r) in Elevator class to atomically check and set elevator state to BUSY - prevents two threads assigning same elevator simultaneously.
Interviewer Expectation
Mid: Uses synchronized method for assignment. Senior: Traces thread interleaving where without synchronized, two threads read elevator as IDLE and both assign it, causing double booking.
⚠️Common Wrong Answer
Not synchronizing assignment leads to race conditions where multiple threads assign the same elevator concurrently, causing inconsistent states.
Step 4
Manage Elevator Movement and State Transitions
Model elevator movement between floors and door operations. Decide how to represent state transitions and ensure thread-safe updates.
💡 Hint
Use volatile for elevator currentFloor and state fields to ensure visibility across threads; use synchronized methods for state transitions to avoid inconsistent states.
Key Decision
Declare volatile int currentFloor and volatile ElevatorState state in Elevator class - ensures visibility of updates across threads; use synchronized methods for state transitions to maintain atomicity.
Interviewer Expectation
Mid: Uses volatile for shared fields. Senior: Explains how without volatile, thread may see stale currentFloor causing incorrect scheduling decisions.
⚠️Common Wrong Answer
Not using volatile causes threads to see stale elevator state or floor, leading to incorrect scheduling or movement decisions.
Step 5
Design Extensible Elevator and Request Hierarchy
Consider future extensions like different elevator types or request priorities. Decide between abstract classes and interfaces for Elevator and Request abstractions.
💡 Hint
Use abstract class Elevator with instance fields for shared state; interfaces cannot hold state in Java. Use interface Request for extensibility of request types.
Key Decision
abstract class Elevator holds shared instance state (currentFloor, state) - interface cannot hold fields in Java; interface Request allows multiple request types with different implementations.
Interviewer Expectation
Mid: Uses abstract class Elevator and interface Request. Senior: Explains why abstract class needed for shared state and interface for flexible request types.
⚠️Common Wrong Answer
Using interface Elevator leads to duplicated state fields in subclasses and violates DRY principle.
🔌
API Design Challenge
Design APIs for the elevator system to handle request submission from floors and inside elevators, elevator status updates, and scheduling decisions. Consider concurrency and thread safety in your API design.
Hints
  • Use thread-safe data structures and synchronization in API methods to handle concurrent requests.
  • Design clear method signatures for submitting requests and querying elevator states.
  • Separate scheduling logic from elevator movement and state update APIs to maintain single responsibility.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of enums for elevator direction and door state
  • Thread-safe floor queues using ConcurrentLinkedQueue
  • Synchronized elevator assignment method to prevent race conditions
  • Volatile fields for elevator currentFloor and state
  • abstract class Elevator for shared instance state
Good to Have - 30%
  • Synchronized methods for elevator state transitions
  • Clear composition and aggregation relationships with lifecycle ownership
  • Separation of scheduling logic from elevator movement
  • Use of interface for extensible request types
  • Explanation of SOLID principles applied
Bonus - 10%
  • Detailed concurrency scenario tracing thread interleaving
  • Use of Java concurrent utilities beyond basic synchronization
  • Extensibility for future elevator types or request priorities
Anti-patterns to Avoid
Using String constants for elevator states leads to runtime bugs due to typos and lack of compile-time checks, causing invalid states to propagate unnoticed.
Using non-thread-safe collections for floor queues causes race conditions and data corruption under concurrent access, leading to inconsistent request handling.
Not synchronizing elevator assignment leads to race conditions where multiple threads assign the same elevator concurrently, causing inconsistent states and double booking.
✅
Model Answer
▼ Reveal

Key Decisions
    • Use enum ElevatorDirection and DoorState for elevator states to ensure compile-time safety.
    • Use ConcurrentLinkedQueue<Request> for floor queues to handle concurrent requests without explicit synchronization.
    • Synchronize elevator assignment method to atomically check and assign requests, preventing double booking.
    • Declare elevator currentFloor and state as volatile to guarantee visibility across threads.
    • Use synchronized methods for elevator state transitions to maintain atomicity and consistency.
    • abstract class Elevator holds shared instance state; interface Request enables extensible request types.
    • Floor maintains aggregation relationship with queue of requests; requests exist independently of floors.
    • Elevator system manages composition of elevators; elevators cannot exist independently of system.
    • Scheduling algorithm enforces Single Responsibility Principle by separating assignment logic from elevator movement.
    • Use of enums and abstract classes enforces Open/Closed Principle by allowing extension without modification.

    Practice

    (1/5)
    1. A class provides a createIterator() method that returns an object allowing traversal over its elements without exposing its internal data structure. Which design pattern is being applied and why is this the correct choice?
    easy
    A. Factory Method pattern, because it encapsulates object creation logic.
    B. Decorator pattern, because it adds traversal behavior dynamically.
    C. Iterator pattern, because it separates traversal logic from the collection's internal structure.
    D. Composite pattern, because it treats individual and composite objects uniformly.

    Solution

    1. Step 1: Identify the role of createIterator()

      This method returns an object that allows clients to traverse elements without exposing the collection's internal representation, which is the core intent of the Iterator pattern.

    2. Step 2: Eliminate other patterns

      Factory Method focuses on object creation, Decorator adds responsibilities dynamically, and Composite manages tree structures. None focus on traversal abstraction.

    3. Final Answer:

      Option C -> Option C

    4. Quick Check:

      Iterator separates traversal from collection internals [check]
    Hint: Iterator hides structure, exposes traversal [check]
    Common Mistakes:
    2. A class has a private constructor and a static synchronized getInstance() method returning the single instance. Which pattern is applied and why is this the CORRECT use case?
    easy
    A. Singleton pattern, because it ensures only one instance exists and controls concurrent access.
    B. Factory Method pattern, because it controls object creation with a static method.
    C. Builder pattern, because it constructs complex objects step-by-step.
    D. Prototype pattern, because it clones existing instances to avoid new construction.

    Solution

    1. Step 1: Identify Singleton pattern characteristics

      The private constructor prevents external instantiation, and the static synchronized getInstance() method ensures a single instance with thread-safe lazy initialization.

    2. Step 2: Eliminate other creational patterns

      Factory Method controls subclass instantiation, Builder separates construction from representation, and Prototype clones objects; none enforce single instance or thread safety.

    3. Final Answer:

      Option A -> Option A

    4. Quick Check:

      Private constructor + synchronized static getInstance() -> Singleton pattern [check]
    Hint: Private constructor + synchronized getInstance() -> Singleton [check]
    Common Mistakes:
    3. The system needs to support ElectricCar vehicles that require ChargingSpots. What is the minimum change to the current design to add this feature without modifying existing classes?
    hard
    A. Add charging logic inside Vehicle class and extend FareCalculator to include charging fees.
    B. Modify Vehicle class to include a boolean isElectric field and add charging logic inside existing methods.
    C. Create a new ElectricCar class and modify ParkingLot to handle charging spots explicitly.
    D. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map externally.

    Solution

    1. Step 1: Identify extensibility without modifying existing classes

      Adding new enums and subclasses externally allows extension without changing existing code, preserving OCP.

    2. Step 2: Update SpotCompatibility map externally

      Maintaining compatibility mapping outside existing classes avoids class explosion or god-class logic.

    3. Final Answer:

      Option D -> Option D

    4. Quick Check:

      New enums + subclass + external compatibility update -> minimal change [check]
    Hint: Add enums + subclass + external map update, no existing class edits [check]
    Common Mistakes:
    4. To add an ElectricPlayer who requires ChargingSpot in the Snake and Ladder game, what is the minimum change to the current design to maintain extensibility without modifying existing classes?
    hard
    A. Add ELECTRIC_PLAYER to PlayerType enum, add CHARGING to SpotType enum, create ElectricPlayer extends Player, update SpotCompatibility map.
    B. Modify Player class to include charging logic and add ChargingSpot as a new field.
    C. Create a new ElectricPlayer class and modify Board to handle ChargingSpots explicitly.
    D. Add charging behavior directly inside Player class and update all existing player types.

    Solution

    1. Step 1: Identify extensibility without modifying existing classes

      Adding new enum values and new subclass preserves existing class code unchanged.

    2. Step 2: Update compatibility map for new player and spot types

      SpotCompatibility map extension allows new rules without changing existing logic.

    3. Final Answer:

      Option A -> Option A

    4. Quick Check:

      New enums + subclass + compatibility map extension -> minimal existing code change [check]
    Hint: New enums + subclass + map update = extensible addition [check]
    Common Mistakes:
    5. You need to add support for ElectricCar and ChargingSpot in the existing Template Method-based parking lot design. What is the minimum change to support this without modifying existing classes?
    hard
    A. Modify existing Vehicle and ParkingSpot classes to handle electric-specific logic with flags.
    B. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType, create ElectricCar subclass, and update compatibility map externally.
    C. Create a new parallel class hierarchy for electric vehicles and spots, duplicating existing logic.
    D. Add charging logic inside the base template method, using instanceof checks for electric cars.

    Solution

    1. Step 1: Extend enums without modifying existing classes

      Adding new enum values for vehicle and spot types allows new categories without changing existing code.

    2. Step 2: Create new subclass and update compatibility externally

      Implementing ElectricCar subclass and updating compatibility map outside existing classes respects OCP and avoids class explosion.

    3. Final Answer:

      Option B -> Option B

    4. Quick Check:

      New types and subclass added; existing classes unchanged [check]
    Hint: Add enums and subclass; keep existing classes intact [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