Low-Level Design: Elevator System in Java: State Pattern, LOOK Scheduling and Multi-Car Dispatching
Design an elevator system in Java from scratch: a State-pattern car, the LOOK rule that makes a lift skip your floor, why SSTF starves a request, and three dispatchers (round robin, nearest car, ETA by cloning the car) measured on 120 simulated people. Every number is quoted from a committed transcript.
You press DOWN on the third floor. A lift arrives, full of people, going up, and it sails past you. You press the button again, as if that would help. Eventually it comes back, and it was never broken: it was doing exactly what it was designed to do. “Design an elevator system” is a favourite low-level design interview question because it hides three real problems: how do you model a machine that behaves differently when it is moving, when its doors are open and when it is out of service, how does a car decide which floor to visit next, and when there are several cars, which one answers a button press.
This post builds a small elevator simulator in Java that answers all three, and measures the answers. It is written so that someone meeting the problem for the first time can read it straight through; the collapsible “going deeper” panels hold the intermediate and reference-level material, so open them on a second read. Every number and console line is quoted from a file in the companion module (regenerate them all with ./scripts/run-all.sh, script here), and every code block and output block links to the file it came from. For the same style of walk-through on other classic questions, see Parking Lot System, BookMyShow Seat Booking, Rate Limiter and Splitwise.
Versions this was built and run against. JDK 25.0.5+8 (Temurin, LTS; the java -version banner reads 2026-10-20), JUnit 6.1.3 (the latest GA on Maven Central, taken from maven-metadata.xml for junit-bom; 6.2.0-M1 is a milestone, and the <release> element in that file points at it) and Maven 3.9.11. No frameworks and no runtime dependencies: everything in src/main is plain Java. Time in the simulation is counted in ticks: one tick is one floor of travel, and the doors stay open for three ticks.
A lift is a machine that keeps promises, not one that answers buttons
Start with the two kinds of button. Outside the lift, on a floor, there is a hall button with a direction: UP or DOWN. Inside the car there is a car button for each floor. Every press becomes a stop: a promise that the car will visit that floor. A hall stop remembers its direction, because the person waiting wants to go that way; a car stop does not, because anybody inside is already on board and will get off when the car arrives.
The whole design follows from one idea: a car is a list of promises, and each tick it works on keeping them. The building hands promises to cars; a car decides the order in which to keep them. Here is the shape of the solution before the details.
Read the picture from the top. The Simulation pushes people into the Building and calls tick(). When a person presses a button, the Building asks the Dispatcher which car should answer, and the chosen car gets a new stop. The cars never talk to each other: all they know about the outside world is the narrow Lobby interface that tells them who is waiting on a floor. Each car hands every tick to whichever state it is currently in, which is the subject of the next section.
A stop is the smallest class in the module. It is a floor and a direction, where NONE means “a car button, either way” (from Stop.java):
public record Stop(int floor, Direction dir) {
@Override
public String toString() {
return dir == Direction.NONE ? String.valueOf(floor) : floor + dir.name().substring(0, 1).toLowerCase();
}
}
toString() prints a car stop as a bare floor and a hall stop with a letter, so 3d means “someone on floor 3 pressed DOWN”. You will see that notation in every trace below.
Going deeper: what each class is for, and what this model leaves out
Class
Role
Car
floor, heading, stops and riders; delegates each tick to its state; owns the LOOK rule and the forecast
CarState and four implementations
idle, moving, doors open, maintenance: one class per behaviour
Building
the cars, the people waiting on each floor, the dispatcher; one tick() advances everything
Lobby
what a car may know about the building; also a do-nothing version used when a car is cloned to predict its future
Dispatcher and three implementations
round robin, nearest car, and one that asks each car for a forecast
Traffic, Simulation, Report
seeded streams of people, the run loop, and the summary figures
Left out on purpose: acceleration and door-close delays, a person holding the doors, weight sensors, an emergency stop, fire service, and a parking policy for idle cars. The model also ignores destination dispatch, where people enter their floor at the lobby and the system assigns a car before anyone steps in; that is a different design, not a tweak to this one. Everything here is a single-threaded simulation, so there are no locks; the rate limiter and BookMyShow posts are the place to look for concurrency.
Going deeper
Building.java — the world that holds the cars and the queues
Lobby.java — the narrow view a car has of the building
A car is four behaviours, and the State pattern gives each one a class
A car does one of four things at any moment. It sits idle with its doors closed. It moves up or down. It stands at a floor with its doors open. Or it is out of service for maintenance. What the car should do on the next tick depends entirely on which of these it is doing now, and that is the situation the State pattern exists for: instead of one huge method full of if (state == ...), each behaviour becomes a small class with one method, and the car simply calls the current one.
The diagram shows every legal move between states. A car that is IDLE starts moving when a stop appears above or below it; a moving car opens its doors when it arrives at a floor it must serve; an open-door car closes up after three ticks and either carries on or goes back to idle; and only an idle, empty car with a service request is allowed to enter MAINTENANCE. Those restrictions are the point: no code path takes a moving car straight into MAINTENANCE, so a planned service request cannot strand riders between floors.
The interface is two methods. A state is told what to do on this tick, and it can copy itself, which matters in section 5 (from CarState.java):
interface CarState {
String name();
void tick(Car car, Lobby lobby);
/** A copy with the same internal counters, so a cloned car can be run forward without touching the real one. */
CarState copy();
}
The moving state is the simplest real one. It steps one floor, then asks the car whether this floor is one it must serve; if so it hands over to the doors-open logic (from MovingState.java):
final class MovingState implements CarState {
private final Direction direction;
MovingState(Direction direction) { this.direction = direction; }
@Override public String name() { return "MOVING_" + direction; }
@Override
public void tick(Car car, Lobby lobby) {
car.step(direction);
Set<Stop> served = car.servedHere(direction);
if (!served.isEmpty()) {
DoorsOpenState.open(car, lobby, served);
}
}
@Override public CarState copy() { return new MovingState(direction); }
}
The doors-open state counts down three ticks. When the count reaches zero, the car asks itself where to go next and becomes either idle or moving (from DoorsOpenState.java):
@Override
public void tick(Car car, Lobby lobby) {
if (--remaining > 0) return;
Direction next = car.nextHeading();
car.setHeading(next);
car.setState(next == Direction.NONE ? new IdleState() : new MovingState(next));
}
The first five ticks of the trace in the next section show it working. Doors open for three lines, the car is MOVING_UP but still on floor 0 for one more, and then it climbs (from 01-single-car-trace.txt):
Going deeper: why a class per state, and what adding “maintenance” costWhy not an enum and a switch? For four states it would work, and for a toy it is fine. The trouble comes with change. In an enum design, adding a fifth state means finding every switch over the enum and deciding what the new case does in each, and the compiler will only help if you left out the default. With a class per state, a new behaviour is a new file, and the existing behaviours stay as they were.
You can see how small the cost is, because maintenance is the last state in the module. It is one tiny class (from MaintenanceState.java):
final class MaintenanceState implements CarState {
@Override public String name() { return "MAINTENANCE"; }
@Override public void tick(Car car, Lobby lobby) { }
@Override public CarState copy() { return new MaintenanceState(); }
}
The only existing state that had to change is IdleState, which decides when to enter it (from IdleState.java):
if (car.maintenanceRequested() && car.riderCount() == 0 && car.stops().isEmpty()) {
car.setHeading(Direction.NONE);
car.setState(new MaintenanceState());
lobby.log("car" + car.id() + " out of service at floor " + car.floor());
return;
}
Beyond that, Car carries a flag and an accepting() method so the building knows not to hand a car in maintenance any new work. Neither MovingState nor DoorsOpenState mentions maintenance at all. So the whole feature touches three places: the new class, one branch in IdleState, and the accepting() check the building uses.
Where should transitions live? Here each state decides its own successor (DoorsOpenState creates a MovingState or an IdleState). The alternative is a central transition table. A table is easier to print and to verify against a diagram, but it moves the knowledge of “what happens next” away from the code that knows why. For four states that stay together in one package, letting each state name its successor is the lighter choice.
Going deeper
IdleState.java — the only state that can start a trip or enter maintenance
DoorsOpenState.java — people getting off, people getting on, and the doors timer
The car skips your floor on purpose: the LOOK rule
Now the second question: given a car with several promises, which floor does it visit next? The rule below matches how most lifts you have ridden behave, and it is worth saying out loud. Keep going in the direction you are travelling while there is anything ahead; stop at a floor if someone there wants to go your way; turn round only when nothing is left ahead. This is called the LOOK rule (a cousin of the disk-scheduling “elevator algorithm”, named after the lift it imitates).
The code needs three questions, all in Car. Is there a stop strictly ahead? Which stops on this floor should I serve, travelling this way? And, when I close the doors, which way do I go (from Car.java):
/** Is there a stop strictly ahead of the car when travelling in direction h? */
boolean aheadOf(Direction h) {
for (Stop s : stops) {
if ((h == Direction.UP && s.floor() > floor) || (h == Direction.DOWN && s.floor() < floor)) return true;
}
return false;
}
Set<Stop> stopsHere() {
Set<Stop> here = new LinkedHashSet<>();
for (Stop s : stops) {
if (s.floor() == floor) here.add(s);
}
return here;
}
/**
* The stops at this floor that a car travelling in direction h should serve now: stops going
* the same way, car calls, and (only at the turning point) stops going the other way.
*/
Set<Stop> servedHere(Direction h) {
Set<Stop> here = stopsHere();
Set<Stop> served = new LinkedHashSet<>();
for (Stop s : here) {
if (s.dir() == h || s.dir() == Direction.NONE) served.add(s);
}
boolean sameDirectionHall = served.stream().anyMatch(s -> s.dir() == h);
if (!aheadOf(h) && !sameDirectionHall) {
for (Stop s : here) {
if (s.dir() == h.opposite()) served.add(s);
}
}
return served;
}
The servedHere method holds the part that surprises people. A car travelling UP serves car stops and UP hall stops on a floor, and it serves a DOWN hall stop only at the turning point: when there is nothing ahead and no UP stop on the same floor. Choosing the next direction is short (also from Car.java):
/** Keep going while there is something ahead, turn round when there is only something behind, else stop. */
Direction nextHeading() {
if (heading != Direction.NONE) {
if (aheadOf(heading)) return heading;
if (aheadOf(heading.opposite())) return heading.opposite();
return Direction.NONE;
}
int best = Integer.MAX_VALUE;
Direction dir = Direction.NONE;
for (Stop s : stops) {
if (s.floor() == floor) continue;
int d = Math.abs(s.floor() - floor);
Direction towards = Direction.between(floor, s.floor());
if (d < best || (d == best && towards == Direction.UP)) {
best = d;
dir = towards;
}
}
return dir;
}
Now watch it run. One car sits at floor 0 of a ten-floor building. Three people press buttons at the same moment: p0 on floor 0 wants floor 6 (UP), p1 on floor 4 wants floor 8 (UP), and p2 on floor 3 wants floor 1 (DOWN). The chart plots the car’s floor against time, with a green dot wherever the doors open (the data comes from 01-single-car-trace.txt).
The line climbs from floor 0 to 8, opening at 4, 6 and 8, then falls back to open at 3 and 1. The red dashed line is p2, who pressed DOWN at floor 3 at time zero: the car passed that floor at t=6 on its way up, and did not stop, because it was carrying people up and had stops further ahead. Here are the door openings and each person’s wait, copied from 01-single-car-trace.txt:
Door openings (from the building log):
t=0 car0 opens at 0 heading UP off=[] on=[p0(0->6)]
t=7 car0 opens at 4 heading UP off=[] on=[p1(4->8)]
t=12 car0 opens at 6 heading UP off=[p0(0->6)] on=[]
t=17 car0 opens at 8 heading UP off=[p1(4->8)] on=[]
t=25 car0 opens at 3 heading DOWN off=[] on=[p2(3->1)]
t=30 car0 opens at 1 heading DOWN off=[p2(3->1)] on=[]
Per person (ticks): wait = button to boarding, ride = boarding to arrival
p0 p0(0->6) wait 0 ride 12 total 12
p1 p1(4->8) wait 7 ride 10 total 17
p2 p2(3->1) wait 25 ride 5 total 30
The fingerprint of “the lift skipped my floor”. p0 waited 0 ticks, p1 waited 7, and p2 waited 25 — for a floor the car was passing at t=6. Nothing is broken: a DOWN stop is kept for the way back. If you see a lift ignore your button while it travels the other way, this is why, and a car that stopped for you would make everyone already on board sit through an extra stop for someone going the other way.
Going deeper: the turning point, and a stop on the floor the car is standing onThe turning point. When the car reaches floor 8 at t=17 it opens its doors for p1 with p2’s DOWN stop still pending below. It stays heading UP while the doors are open and flips only when the doors close and nextHeading() finds nothing ahead. If the person at the top floor had pressed DOWN, servedHere would have served that stop at the turn and flipped the heading before boarding, so the right passengers get on. That flip is the else if branch in DoorsOpenState.open that compares the heading with the direction of the stops being served.
A stop on the floor the car is standing on. Stops at the current floor are neither “ahead” nor “behind”. A moving car ignores them until it comes back round; an idle car opens its doors for them at once. This avoids a loop that would be easy to write (I did not build that version, so this is design reasoning, not an observed bug): a full car that re-queues a left-behind passenger at its own floor and re-opens its doors forever. The cost is a limitation worth knowing: a button pressed on the floor where a car has its doors open does not extend the doors-open time. If the car has nothing else to do it simply opens again after closing; otherwise the person waits for its next visit, or for a different car.
Two stops, same floor, opposite directions. The car serves one direction and the other person triggers a second door cycle after the car has closed up. It costs a few ticks and keeps the rule simple.
Going deeper
Car.java — aheadOf, servedHere and nextHeading in one place
TraceTest.java — the test that wrote the trace above and asserts the door openings and waits
It is the first idea everyone has, and it is worth testing rather than dismissing. Take one car at floor 5 with six requests: floors 8, 2, 9, 1, 6 and 3, in that order. FCFS (first come, first served) visits them in arrival order. SSTF (shortest seek time first) always goes to the nearest remaining floor. LOOK sweeps up through everything above, then down through everything below. Here is the total distance each makes the car travel (from 02-policies.txt):
requests in arrival order: [8, 2, 9, 1, 6, 3]
FCFS order [8, 2, 9, 1, 6, 3] distance 32
SSTF order [6, 8, 9, 3, 2, 1] distance 12
LOOK order [6, 8, 9, 3, 2, 1] distance 12
FCFS travels 32 floors where the other two travel 12, because it ping-pongs between the ends of the shaft. SSTF and LOOK tie on this list, and honesty requires saying so: if distance were the only thing that mattered, SSTF would do. It is not, because SSTF has a failure that a list of floors cannot show. Put one request at floor 0, the car at floor 5, and a steady trickle of new requests at floors 6 and 7. The car moves one floor per tick, and the trickle lasts 40 ticks (from 02b-starvation.txt):
The stream of new requests lasts 40 ticks. The car moves one floor per tick.
SSTF far request served at tick 46
LOOK far request served at tick 9
Under SSTF the person at floor 0 is served at tick 46, six ticks after the trickle ended, because there is always something nearer. Under LOOK they are served at tick 9: the car finishes its sweep, turns, and the new requests are now behind it. That is the real reason lifts sweep: not to save distance but to put an upper bound on how long anyone can wait.
SSTF is not wrong, it is unbounded. On ordinary traffic it behaves well and on a list of floors it ties with LOOK. What it lacks is a promise: there is always a scenario in which the next-nearest request is never the far one. A scheduler that carries people should be able to say how long the worst case is, and a sweep can.
Going deeper: SCAN, LOOK and C-LOOK, and what LOOK does not guarantee
Wikipedia’s “Elevator algorithm” page distinguishes these as follows. SCAN runs to the end of the track before turning back. LOOK turns at the last pending request instead, which is what the car in this module does. C-SCAN and C-LOOK serve in one direction only and then jump back to the start, which makes sense for a disk arm and not for a lift cabin that people ride in both directions.
What the tests do not prove. In a shaft of ten floors a LOOK sweep must end at the top floor at the latest, so a request waits at most roughly one trip up and one trip down plus door time. That argument is short, but the module does not assert it. What it does assert, over 900 randomised runs, is that everyone is delivered within 3,000 ticks (section 8).
A warning about the SSTF demonstration. The trickle is deliberately chosen to be adversarial: new requests land on floors 6 and 7 every tick. Real traffic is rarely that unkind, and SSTF is not unusable. The point is that it has no upper bound on waiting, and LOOK does.
Going deeper
With several cars, someone has to decide who answers the button
One car decides its own order. With three cars in one building there is a different decision: when someone presses UP on floor 6, which car gets the stop? That is the dispatcher’s job, and it is a small interface so the strategy can be swapped (from Dispatcher.java):
public interface Dispatcher {
String name();
Car choose(List<Car> candidates, int floor, Direction dir);
}
Three implementations, from naive to careful. Round robin takes the cars in turn and looks at nothing (from RoundRobinDispatcher.java):
@Override
public Car choose(List<Car> candidates, int floor, Direction dir) {
return candidates.get(next++ % candidates.size());
}
Nearest car is the obvious idea and the one most interview answers stop at: pick the car whose floor is closest to the button (from NearestCarDispatcher.java):
@Override
public Car choose(List<Car> candidates, int floor, Direction dir) {
return candidates.stream()
.min(Comparator.comparingInt((Car c) -> Math.abs(c.floor() - floor)).thenComparingInt(Car::id))
.orElseThrow();
}
ETA asks every car how long it would take to open its doors at that floor, and picks the smallest answer (from EtaDispatcher.java):
@Override
public Car choose(List<Car> candidates, int floor, Direction dir) {
return candidates.stream()
.min(Comparator.comparingInt((Car c) -> c.eta(floor, dir))
.thenComparingInt(c -> c.stops().size())
.thenComparingInt(Car::id))
.orElseThrow();
}
The interesting part is how a car answers “how long?”. It does not use a formula. It clones itself and runs the real state machine forward with a lobby where nobody ever boards, counting ticks until the new stop is served (from Car.java):
/**
* Ticks until this car would open its doors for a new hall call, found by cloning the car
* and running the real state machine forward. Nobody boards in the clone, so the figure
* ignores stops the car will pick up on the way: an estimate, not a promise.
*/
public int eta(int callFloor, Direction callDir) {
Car copy = new Car(id, minFloor, maxFloor, floor, capacity);
copy.heading = heading;
copy.state = state.copy();
copy.stops.addAll(stops);
copy.riders.addAll(riders);
Stop wanted = new Stop(callFloor, callDir);
copy.stops.add(wanted);
for (int t = 1; t <= 1000; t++) {
copy.tick(Lobby.FORECAST);
if (!copy.stops.contains(wanted)) return t;
}
return Integer.MAX_VALUE;
}
Because the forecast is the same code as the real thing, it cannot drift away from it the way a separate formula could. The test for that is the smallest one in the module: an idle car at floor 0 and a call at floor 7 (from 03b-eta-forecast.txt):
predicted: 7 ticks
actual: 7 ticks
Now the comparison. The same 120 people, from the same seeded random streams, go through all three dispatchers in a twelve-floor building with three cars. One stream is a morning up-peak where 70% of people start at the lobby; the other is people travelling between random floors. The chart shows the average wait from button press to boarding.
On the up-peak, nearest-car is by far the worst, at 91.9 ticks of average wait against 13.7 for ETA, and the full figures show why it is worth measuring more than one number (from 03-dispatchers.txt):
Up-peak (70% start at the lobby), seed 42, arrivals spread over 240 ticks
round-robin delivered 120/120 wait avg 18.5 max 57 total avg 32.7 max 79 floors 363 door cycles 134 ticks 299
hall calls per car (car0, car1, car2): [15, 15, 15]
nearest-car delivered 120/120 wait avg 91.9 max 248 total avg 106.4 max 258 floors 317 door cycles 129 ticks 481
hall calls per car (car0, car1, car2): [23, 15, 4]
eta delivered 120/120 wait avg 13.7 max 43 total avg 27.6 max 63 floors 338 door cycles 136 ticks 273
hall calls per car (car0, car1, car2): [18, 15, 14]
Between floors (uniform origin and destination), seed 7, arrivals spread over 360 ticks
round-robin delivered 120/120 wait avg 13.3 max 45 total avg 22.6 max 69 floors 564 door cycles 181 ticks 400
hall calls per car (car0, car1, car2): [30, 30, 29]
nearest-car delivered 120/120 wait avg 16.5 max 66 total avg 26.5 max 86 floors 428 door cycles 177 ticks 398
hall calls per car (car0, car1, car2): [36, 25, 26]
eta delivered 120/120 wait avg 9.9 max 43 total avg 19.6 max 61 floors 489 door cycles 190 ticks 378
hall calls per car (car0, car1, car2): [37, 28, 33]
Two things in that output are easy to miss. First, nearest-car gave car 2 only 4 of the morning’s 42 hall calls while car 0 got 23, more than half of them. Second, ETA is not best on every column: nearest-car travelled fewer floors in total (317 against 338) and used fewer door cycles (129 against 136). ETA wins on waiting, which is what passengers feel, and pays for it in movement. These are two seeded streams, not a law of nature; change the seeds in DispatcherTest.java and the numbers move, though in these two runs the order of the dispatchers by average wait did not change.
Going deeper: what the forecast ignores, and the bug that taught me where to take the cloneWhat it ignores. Nobody boards in the clone, so the forecast cannot know about people the car will pick up on the way, and each of those adds a door cycle. It is an estimate, not a promise. It also costs a short simulation per car for every hall call, capped at 1,000 ticks as a guard against a car that can never reach the stop.
The bug. The first full run of the tests crashed with a message of the form “car1 left the shaft at -1”. The cause was an ordering mistake I made. When a car arrives and opens its doors it may need to re-issue a hall call for people it could not fit in (section 6), and that call reaches the dispatcher, which asks this same car for a forecast. At that instant the car had already arrived but still reported itself as MOVING, so the clone kept driving downwards with nothing to stop for. The fix is one line: switch to the doors-open state before anything that might ask for a forecast (from DoorsOpenState.java):
// Switch state before anything below can ask the dispatcher for a forecast of this car:
// a clone taken while the car still says MOVING would drive off the end of the shaft.
car.setState(new DoorsOpenState(Car.DWELL_TICKS));
Nothing is committed that reproduces the original crash, so treat that account as mine rather than as a transcript. What is committed is the check that would catch it again: the 900-run test in section 8 calls the forecast thousands of times and throws if any car leaves the shaft.
What real systems add. Idle cars are parked in useful places (for example back at the lobby before the morning peak), cars are assigned zones, and some buildings use destination dispatch. This module does none of that. I did not isolate why nearest-car does so badly on the up-peak run: the lopsided calls per car are the visible symptom, and the small trap in section 7 shows the mechanism at toy scale (the closest car is not always the car that gets there first).
Going deeper
So far the car has been a magic box. Real cars hold a limited number of people, and sometimes have to be taken out of service. Both are small additions because of how the pieces were cut.
A hall button is lit once, however many people press it. The building only dispatches a call when no car already holds that stop. That one rule is why five people at one floor cost one dispatch (section 7) and why a car that leaves people behind has to ask again.
Capacity. When the doors open, people get off first, then waiting people whose direction matches the car’s heading get on, until it is full. Anyone left behind has pressed a button that has just been answered, so the car re-issues the call. The code is short (from DoorsOpenState.java):
for (Direction d : new Direction[] {Direction.UP, Direction.DOWN}) {
boolean left = queue.stream().anyMatch(p -> p.direction() == d);
if (left && !lobby.hallStopPending(floor, d)) lobby.callHall(floor, d);
}
Notice the hallStopPending check. If another car already holds that stop, nothing new is dispatched: it is the same lit button, however many people are waiting. The next trace shows capacity 2 and five people at the lobby, all going up (from 05-capacity.txt):
hall calls dispatched after five button presses: 1
t=0 hall 0u -> car0 (at 0 IDLE)
t=0 hall 0u -> car0 (at 0 DOORS_OPEN)
t=0 car0 opens at 0 heading UP off=[] on=[p0(0->2), p1(0->3)]
t=5 car0 opens at 2 heading UP off=[p0(0->2)] on=[]
t=9 car0 opens at 3 heading UP off=[p1(0->3)] on=[]
t=15 hall 0u -> car0 (at 0 DOORS_OPEN)
t=15 car0 opens at 0 heading UP off=[] on=[p2(0->4), p3(0->5)]
t=22 car0 opens at 4 heading UP off=[p2(0->4)] on=[]
t=26 car0 opens at 5 heading UP off=[p3(0->5)] on=[]
t=34 car0 opens at 0 heading UP off=[] on=[p4(0->6)]
t=43 car0 opens at 6 heading UP off=[p4(0->6)] on=[]
p0(0->2) wait 0 ride 5
p1(0->3) wait 0 ride 9
p2(0->4) wait 15 ride 7
p3(0->5) wait 15 ride 11
p4(0->6) wait 34 ride 9
The first two take the car at tick 0, the next two wait 15 ticks for it to come back, and the last waits 34. Notice also that the log shows one hall call at tick 0 for five presses and a second one, for the people left behind, the moment the doors open.
Maintenance. Asking a car to go out of service does not stop it on the spot: it finishes what it is carrying first. In this scenario car 0 is carrying passenger a to floor 5 when maintenance is requested at tick 5, and a new person b presses UP on floor 2 straight after. Car 0 is closer, but it no longer accepts work, so the call goes to car 1. The last two ticks of the trace, where the car goes idle and then out of service, and the outcome (from 04-maintenance.txt):
If every car is out of service, a hall call has nowhere to go. The building keeps it in an unassigned list and retries each tick (from 04b-all-cars-out.txt):
after 10 ticks: delivered=0 waiting=1
car1 returned to service: delivered after 11 more ticks
Bad input. The building refuses requests that cannot be real, with a message that names the problem (from 06-validation.txt):
origin above the top floor -> origin floor 12 is outside 0..9
origin below the ground floor -> origin floor -1 is outside 0..9
destination above the top floor -> destination floor 10 is outside 0..9
destination below the ground floor -> destination floor -4 is outside 0..9
same origin and destination -> origin and destination are both floor 5
people waiting afterwards: 0, hall calls dispatched: 0
Going deeper: what maintenance and capacity deliberately leave outMaintenance is a polite request, not a fault. A real fault happens with people aboard, between floors, and the right response is a safety procedure, not a state transition. This module models the planned case only: the car finishes its riders, then stops. It does not model riders trapped in a failed car, a fire-service recall, or a car that stops answering.
Capacity is a head count. Real cars typically use a weight sensor rather than counting people. Here the car simply stops boarding at the limit and re-issues the call; the people left behind wait for the next visit, which with a full car can be a whole sweep away.
A hall call is shared. Five people pressing the same button make one stop, and when one car serves a stop, every other car drops its copy of it (hallServed). Without that, two cars could be promised the same floor and the second would arrive to find nobody there.
Going deeper
Dispatching on distance alone. The nearest car may be the one moving away from you. The next transcript sets it up directly: car 0 is at floor 4 about to go DOWN to floor 0, car 1 is parked at floor 9, and someone on floor 3 presses UP.
Stopping for every hall button regardless of direction. A lift that stopped for a DOWN call while going UP would add an extra stop for everyone already on board. The LOOK rule exists to prevent exactly this (section 3).
Treating five presses as five calls. The button is lit once. The second transcript below shows five people at floor 6 producing one dispatched call.
Asking a car for a forecast in the middle of changing its state. The bug described in section 5. A clone is only as trustworthy as the state it copies.
Letting a car walk off the end of the shaft.Car.step throws if a car ever leaves its floors, so a logic error fails loudly instead of printing floor -1.
The first trap, run under the nearest-car dispatcher and the ETA dispatcher (from 08-nearest-car-trap.txt):
nearest-car: after 4 ticks car0 floor 4 MOVING_DOWN DOWN stops [0] riders [rider(4->0)]
nearest-car: t=4 hall 3u -> car0 (at 4 MOVING_DOWN)
eta: after 4 ticks car0 floor 4 MOVING_DOWN DOWN stops [0] riders [rider(4->0)]
eta: t=4 hall 3u -> car1 (at 9 IDLE)
wait for the person at floor 3, in ticks:
nearest-car 9
eta 5
Nearest-car gives the call to car 0, which is one floor away and moving down; the car must go all the way to floor 0, turn round and come back. ETA gives it to car 1, which is six floors away but has nothing else to do. The person waits 9 ticks in one case and 5 in the other. The second trap (from 08b-same-button.txt):
hall calls dispatched: 1
door cycles used to serve all five: 2
A simulation can look right and still be wrong in a way you only meet on the thousandth run. So the tests do two jobs. The first is the one you have seen all through this post: each test writes a transcript and asserts the same numbers it prints, so a figure in this article that stops being true fails the build. The second is a randomised check. After every single tick of 900 runs (150 seeds, three dispatchers, two kinds of traffic), a function checks four rules (from InvariantsTest.java):
/** Rules that must hold after every single tick of every run. */
private static void check(Building b) {
for (Car c : b.cars()) {
if (c.floor() < 0 || c.floor() >= b.floors()) throw new AssertionError(c + " is outside the shaft");
if (c.riderCount() > c.capacity()) throw new AssertionError(c + " is over capacity");
for (Passenger p : c.riders()) {
if (p.destination() != c.floor() && !c.stops().contains(new Stop(p.destination(), Direction.NONE))) {
throw new AssertionError(c + " carries " + p + " but has no stop for them");
}
}
if (c.stateName().equals("DOORS_OPEN") && c.heading() == Direction.NONE && c.riderCount() > 0 && c.stops().isEmpty()) {
throw new AssertionError(c + " is stuck with riders and no stops");
}
}
}
That is 36,000 trips and 137,430 ticks with no car outside its shaft, over capacity, carrying someone it has no stop for, or stuck. Every run also had to deliver every passenger within 3,000 ticks.
Going deeper: what these checks do not cover, and how to present this in 45 minutesNot covered. The invariants say nothing about fairness or efficiency: a dispatcher that sends every call to one car passes all four, and so does a car that takes the longest route. Wait-time figures are measured, not constrained. There is no test of two people pressing a button in the same tick from different threads, because the simulation is single-threaded by design.
In an interview, a good order is: requirements and the idea that a car is a list of promises (five minutes), the class diagram and the state diagram (ten), the LOOK rule and why not FCFS (ten), several cars and the dispatcher (ten), then capacity, maintenance and what you would test (ten). Interviewers tend to push on exactly three places: why does the lift skip my floor, what if two cars are both close, and how would you add a new mode, such as maintenance or fire service, without touching everything. Sections 3, 5 and 2 are those three answers.
Going deeper
README.md — versions, quickstart and an index of all thirteen transcripts
Should you build it this way?
For learning and for interviews, yes; for a real building, never. The simulation is the right thing to draw on a whiteboard and to test the rules against: promises, the State pattern, the LOOK sweep and the dispatching decision. It is the wrong thing to put in charge of a lift. A real controller is safety-critical embedded software that works with hardware interlocks for doors, speed and overload, and it is built and certified for that purpose; none of that exists here. If you are writing an interview answer, the point to land is not the code but the three ideas: model behaviour as states, bound the wait with a sweep, and choose a car by time to arrive rather than distance.
Further reading
elevator module in asmhatre/java-interview-lab — every file referenced above, and all thirteen transcripts in output/
Parking Lot System — another low-level design walk-through, from requirements to class diagram to tests
BookMyShow Seat Booking — concurrency in a booking system: naive, pessimistic and optimistic
Rate Limiter in Java — another interview classic, with the same transcript-driven approach
No Comments yet!