Why this matters: elevator implementations live or die on transition discipline — every event handler must leave a car in a state the invariants allow, and interviewers read your handlers the way they'd read a state-machine table. The walkthrough below builds the car first (it's self-contained), then the dispatcher on top, in the order you'd write them live.
The vocabulary types
enum Direction { UP, DOWN }
enum CarState { IDLE, MOVING_UP, MOVING_DOWN, DOORS_OPEN }
record HallCall(int floor, Direction direction) {}
// a car call is just a destination — it arrives already bound to a carKeeping HallCall a value object matters later: the dispatcher tracks them, and value semantics make "this exact call" unambiguous.
The car: state + two stop sets
class Car {
final int id;
int floor; // updated only by arrived()
CarState state = CarState.IDLE;
Direction committed = null; // direction of the current sweep
NavigableSet<Integer> stopsAbove = new TreeSet<>(); // ascending
NavigableSet<Integer> stopsBelow = new TreeSet<>(Comparator.reverseOrder()); // descending
void addStop(int target) {
if (target > floor) stopsAbove.add(target);
else if (target < floor) stopsBelow.add(target);
else /* already here */ openDoors();
if (state == CarState.IDLE) startMoving();
}
}Narrate the invariant as you type it: a stop goes into the set that matches its position relative to the car right now — stopsAbove is strictly above, stopsBelow strictly below. That placement rule is the whole reason nextStop() will be one line.
The sweep, as code
Integer nextStop() {
if (committed == Direction.UP) return stopsAbove.isEmpty() ? null : stopsAbove.first();
if (committed == Direction.DOWN) return stopsBelow.isEmpty() ? null : stopsBelow.first();
return null;
}
void startMoving() {
// commit to whichever side has work; prefer continuing the last direction
if (!stopsAbove.isEmpty()) { committed = Direction.UP; state = CarState.MOVING_UP; emit(MOVE_UP); }
else if (!stopsBelow.isEmpty()) { committed = Direction.DOWN; state = CarState.MOVING_DOWN; emit(MOVE_DOWN); }
else { committed = null; state = CarState.IDLE; }
}nextStop() being a first() on an ordered set is the LOOK sweep — the data structure carries the algorithm. Say that out loud; it's the implementation matching the design's words.
Event handlers: where transitions live
void onArrived(int newFloor) { // hardware event
floor = newFloor;
boolean stopHere = (committed == Direction.UP && !stopsAbove.isEmpty() && stopsAbove.first() == newFloor)
|| (committed == Direction.DOWN && !stopsBelow.isEmpty() && stopsBelow.first() == newFloor);
if (stopHere) {
removeStop(newFloor);
state = CarState.DOORS_OPEN;
emit(STOP_NEXT); emit(OPEN_DOORS);
}
// otherwise keep moving; no command needed
}
void onDoorsClosed() { // hardware event
// sweep rule: continue in the committed direction while work remains ahead,
// else reverse, else idle
if (committed == Direction.UP && !stopsAbove.isEmpty()) { state = CarState.MOVING_UP; emit(MOVE_UP); }
else if (committed == Direction.DOWN && !stopsBelow.isEmpty()) { state = CarState.MOVING_DOWN; emit(MOVE_DOWN); }
else startMoving(); // may reverse or go idle
}Two handlers, and every legal transition from lesson 02's diagram appears in exactly one of them. This is the checkable claim: events mutate state, commands are emitted outputs — there's no sleep(), no timer, no physics. A test injects onArrived(7) and asserts OPEN_DOORS was emitted; no clock anywhere.
The dispatcher
interface DispatchStrategy {
Car choose(HallCall call, List<Car> cars);
}
class NearestInDirection implements DispatchStrategy {
public Car choose(HallCall call, List<Car> cars) {
// pass 1: nearest car already sweeping toward the call, call on its path
// pass 2: nearest idle car
// pass 3: nearest car regardless (it'll get there after its sweep)
return best(cars, call); // linear scan, scored
}
}
class Dispatcher {
final List<Car> cars;
final DispatchStrategy strategy;
void onHallCall(HallCall call) {
Car chosen = strategy.choose(call, cars);
chosen.addStop(call.floor()); // assignment recorded — exactly one owner
}
void onCarCall(int carId, int destination) {
car(carId).addStop(destination); // no choosing: the rider chose already
}
}The three-pass scoring narrates well: cars already heading the right way are cheapest (the rider joins a sweep), idle cars are next, and worst case someone finishes a sweep first. And the structural point from lesson 02 is now visible in the code: Dispatcher.onHallCall is the only place a hall call meets a car, and onCarCall demonstrates why the two request types stayed separate — one routes through a decision, the other doesn't.
What you'd say about complexity
Hall-call assignment is O(cars) per call — four cars, and the honest engineering statement is that no index could pay for itself here. Stop insertion and nextStop() are O(log s) and O(1) on the ordered sets, with s bounded by 20 floors. State transitions are O(1) per event. This problem's complexity story is deliberately boring, and saying so plainly is the complexity-honesty points.
Key takeaway
The implementation is the state machine made checkable: two ordered stop sets whose placement rule makes nextStop() a one-liner, two event handlers that own every legal transition, and a dispatcher whose onHallCall is the single point where calls meet cars — all clock-free, so the whole controller tests by injecting events and asserting commands.