Java LLD: Designing a High-Concurrency Elevator System

#java #systemdesign #interview #concurrency

Java LLD: Designing a High-Concurrency Elevator System

Designing an elevator system is a classic "Machine Coding" round favorite because it tests concurrency, state management, and algorithmic efficiency simultaneously. At companies like Apple or Amazon, interviewers aren't just looking for a working loop; they are looking for thread safety and optimal scheduling.

The Mistake Most Candidates Make

Using a simple Queue<Integer>: This leads to inefficient "ping-ponging" where the elevator moves from floor 1 to 10, then back to 2, then up to 9.
Over-locking: Using a global lock on the entire ElevatorSystem which kills performance in multi-elevator scenarios.
Ignoring Visibility: Forgetting that the ElevatorController needs the most recent currentFloor from the Elevator thread to make dispatching decisions.

The Right Approach

Core mental model: Treat each elevator as an autonomous actor using the SCAN Algorithm (Elevator Algorithm) to process requests in its current path before reversing.
Key entities: ElevatorSystem, Elevator, InternalButtonPanel, ExternalButtonPanel, and DispatchStrategy.
Why it beats the naive approach: It minimizes travel distance and power consumption while preventing passenger starvation.

Shameless plug: javalld.com has full LLD implementations with step-by-step execution traces — free to use while prepping.

The Key Insight (Code)

The secret to an efficient elevator is managing two separate heaps to track requests based on the current direction.

public class Elevator implements Runnable {
    private volatile int currentFloor = 0; // Visibility for the Controller
    private Direction direction = Direction.IDLE;
    private final PriorityQueue<Integer> upMinHeap = new PriorityQueue<>();
    private final PriorityQueue<Integer> downMaxHeap = new PriorityQueue<>(Collections.reverseOrder());

    public void run() {
        while (true) {
            PriorityQueue<Integer> currentQueue = (direction == Direction.UP) ? upMinHeap : downMaxHeap;
            while (!currentQueue.isEmpty()) {
                this.currentFloor = currentQueue.poll();
                processArrival(currentFloor);
            }
            this.direction = Direction.IDLE;
        }
    }
}

Key Takeaways

Thread Confinement: Each Elevator should run in its own thread. This isolates the movement logic and prevents a single stuck elevator from freezing the entire system.
The SCAN Strategy: Use a Min-Heap for upward requests and a Max-Heap for downward requests. This ensures the elevator picks up everyone on the way before switching directions.
Volatile for State: Mark currentFloor and direction as volatile. This ensures the ElevatorController sees real-time updates when deciding which elevator is closest to a new request.