LLD-003 · DESIGN PRACTICE

Elevator Controller

Separate dispatch policy, movement guards and request ownership in a deterministic simulator.

Local Java 21 reference verified: 20 checks. Learner drafts are not executed. Author self-review; independent review pending.

Existing introductory lesson · Version 1

Understand the problem

Design a multi-car elevator simulation. Assign pickups, accept in-car destinations, advance cars one floor at a time, open doors at stops and reassign pickups when a car leaves service. Explain which rules are safety guards and which are replaceable scheduling choices.

Before you start

• Finite-state machines
• Ordered sets and scheduling
• Atomic state transitions
• Optimistic command versions

Scope and explicit decisions

• This is a discrete in-memory simulator, not certified elevator or real-time hardware software. It has no motor commands, evacuation protocol, travel-time physics, persistence or physical sensor validation.
• Floors are integers 0..floors-1. Each car begins at a configured floor with doors closed. One step moves at most one floor; arrival and floor movement are atomic simulator events.
• Pickup requests are directionless in this implemented slice. Up/down hall buttons, occupancy-aware grouping and hard fairness/maximum-wait guarantees are explicit extension exercises, not already supported features.
• Pickup assignment minimizes distance plus current distinct stop count, with car ID as deterministic tie-breaker. This heuristic is not claimed to minimize average wait or travel. A duplicate pending pickup for a floor returns the same car.
• Each car uses a sweep policy: continue toward pending stops in the current direction, then reverse when no stop remains ahead. An IDLE car initially prefers a higher stop if one exists. In-car and pickup stops at one floor are coalesced.
• Movement requires an in-service car, closed doors and no overload. Door close rejects obstruction or overload. An obstruction flag alone does not alter closed-door motion; it is a door-closing sensor in this model.
• step requires the current per-car version. Requests, sensor flags, service changes and door actions may advance that version, so callers must refresh a stale snapshot rather than force a command.
• Disabling a car reassigns its pending pickup requests before committing the change. Its in-car destinations remain parked for resumption. If no replacement exists, disabling with pending pickups fails atomically. No passenger evacuation behavior is implied.

Worked examples

Try before revealing

Requirements and invariants

R1 — A pending pickup has one assigned serviceable owner. requestPickup protects I1.

R2 — A discrete move cannot bypass door, overload or service guards. step protects I2.

R3 — A stale step cannot move the car twice from an old snapshot. step protects I3.

R4 — Out-of-service reassignment is planned completely before mutation. setOutOfService protects I1.

I1: Each pickup floor appears once in the assignment map and references an enabled car.

I2: The floor changes only through step after verifying closed doors, no overload and in-service status.

I3: A successful step consumes one current version; another step with the old version is rejected without movement.

Derive the design

One car with FIFO requests, then separate policy from guards

A single-car FIFO queue is easy to explain and is correct for a simple request contract, but can send the car back and forth between nearby floors. The reference keeps a sorted destination set and sweep direction, then adds a multi-car assignment map. Dispatch scoring and stop choice are explicit heuristics; door and overload guards remain hard preconditions regardless of the selected policy.

Alternative: An event loop with one writer per car can reduce shared locking, but reassignment then becomes a protocol between controller and car owners. Introduce that boundary only when its ordering and stale-command rules are designed. A strategy interface is useful after there are two real policies, not merely to inflate the class diagram.

Responsibilities and ownership

Method contracts

What, when, why and how

Each concept is attached to the requirement it protects, its implementation, an alternative and a test.

Read and run the Java reference

1import java.util.*;
2/** Discrete simulator, not a hardware safety controller. Pickup requests are directionless. */
3public final class Solution {
4    private Solution() {}
5    public enum Direction { IDLE, UP, DOWN }
6    public record View(String id,int floor,Direction direction,boolean doorsOpen,boolean overloaded,
7                       boolean obstructed,boolean outOfService,long version,List<Integer> stops) {
8        public View { stops=List.copyOf(stops); }
9    }
10    private static final class Car {
11        final String id;
12        int floor;
13        Direction direction=Direction.IDLE;
14        boolean doors,overloaded,obstructed,disabled;
15        long version;
16        final TreeSet<Integer> destinations=new TreeSet<>();
17        Car(String id,int floor){this.id=id;this.floor=floor;}
18    }
19    public static final class Controller {
20        private final int floors;
21        private final Map<String,Car> cars=new TreeMap<>();
22        private final Map<Integer,String> pickups=new TreeMap<>();
23        public Controller(int floors,Map<String,Integer> initial){
24            if(floors<2||initial.isEmpty())throw new IllegalArgumentException("configuration");this.floors=floors;
25            initial.forEach((id,f)->{if(id==null||id.isBlank()||f<0||f>=floors)throw new IllegalArgumentException("car");cars.put(id,new Car(id,f));});
26        }
27        private void floor(int f){if(f<0||f>=floors)throw new IllegalArgumentException("floor");}
28        private Car car(String id){var c=cars.get(id);if(c==null)throw new IllegalArgumentException("car");return c;}
29        private TreeSet<Integer> stops(Car c){var result=new TreeSet<>(c.destinations);pickups.forEach((f,id)->{if(id.equals(c.id))result.add(f);});return result;}
30        private Car choose(int floor,String excluding){
31            return cars.values().stream().filter(c->!c.disabled&&!c.id.equals(excluding)).min(Comparator.comparingLong((Car c)->Math.abs((long)c.floor-floor)+stops(c).size()).thenComparing(c->c.id)).orElseThrow(()->new IllegalStateException("no available car"));
32        }
33        public synchronized String requestPickup(int floor){
34            floor(floor);if(pickups.containsKey(floor))return pickups.get(floor);
35            var c=choose(floor,"");pickups.put(floor,c.id);c.version++;return c.id;
36        }
37        public synchronized void selectFloor(String id,int floor){floor(floor);var c=car(id);if(c.disabled)throw new IllegalStateException("out of service");if(c.destinations.add(floor))c.version++;}
38        public synchronized View step(String id,long expectedVersion){
39            var c=car(id);if(c.version!=expectedVersion)throw new IllegalStateException("stale command");
40            if(c.disabled||c.doors||c.overloaded)throw new IllegalStateException("movement blocked");
41            var pending=stops(c);if(pending.isEmpty()){c.direction=Direction.IDLE;c.version++;return view(c);}
42            Integer target;
43            if(pending.contains(c.floor))target=c.floor;
44            else if(c.direction==Direction.DOWN){target=pending.lower(c.floor);if(target==null)target=pending.higher(c.floor);}
45            else {target=pending.higher(c.floor);if(target==null)target=pending.lower(c.floor);}
46            if(target>c.floor){c.direction=Direction.UP;c.floor++;}
47            else if(target<c.floor){c.direction=Direction.DOWN;c.floor--;}
48            if(pending.contains(c.floor)){
49                c.destinations.remove(c.floor);pickups.remove(c.floor,c.id);c.doors=true;
50                if(stops(c).isEmpty())c.direction=Direction.IDLE;
51            }
52            c.version++;return view(c);
53        }
54        public synchronized void closeDoors(String id){var c=car(id);if(c.obstructed||c.overloaded)throw new IllegalStateException("door blocked");if(c.doors){c.doors=false;c.version++;}}
55        public synchronized void setObstructed(String id,boolean value){var c=car(id);c.obstructed=value;c.version++;}
56        public synchronized void setOverloaded(String id,boolean value){var c=car(id);c.overloaded=value;c.version++;}
57        public synchronized void setOutOfService(String id,boolean value){
58            var c=car(id);if(c.disabled==value)return;
59            if(value){
60                // Plan every reassignment before committing, so failure leaves all assignments intact.
61                var replacement=new TreeMap<Integer,String>();
62                pickups.forEach((f,owner)->{if(owner.equals(id))replacement.put(f,choose(f,id).id);});
63                c.disabled=true;c.direction=Direction.IDLE;
64                replacement.forEach((f,owner)->{pickups.put(f,owner);cars.get(owner).version++;});
65            }else c.disabled=false;
66            c.version++;
67        }
68        public synchronized View snapshot(String id){return view(car(id));}
69        public synchronized String assignedCar(int floor){floor(floor);return pickups.get(floor);}
70        private View view(Car c){return new View(c.id,c.floor,c.direction,c.doors,c.overloaded,c.obstructed,c.disabled,c.version,new ArrayList<>(stops(c)));}
71    }
72}
73

Complexity and limits

• With C cars, P pickup requests and D internal destinations per car, choose recomputes stop sets for candidates. A conservative bound is O(C×(P+D log D)); snapshot/step also derive a stop set.
• TreeSet neighbor queries are O(log S) for S distinct stops after constructing that set. Do not label the whole step O(log S) while ignoring derivation work.
• State uses O(C+Dtotal+P); served requests are removed. Version and direction snapshots use O(S) copied stop values.
• One monitor serializes all cars. Indexed per-car pickup sets or event loops require new invariant/ownership tests before performance claims.

Walk through the actual reference

These walkthrough fixtures are emitted only after the Java harness verifies their operations and expected state. Concurrency tests additionally exercise competing callers.

Mistakes and counterexamples

Engineer → Senior → Staff

Return to the lesson →

Provenance and scope of evidence

Original teaching material. The local contract is implemented by Solution.java and tested by Test.java on Java 21. Distributed persistence, real provider/device adapters and deployment are not claimed.

Reference verification is not independent editorial review, production deployment verification or a claim that distributed adapters are implemented.