These are the notes for Low-Level Design (LLD) episode 62, the second half of the elevator machine-coding problem. Part 1 (episode 61) built the model: states, the door, a state machine, internal and external requests, and a first-come-first-served queue that zigzagged 18 floors where 6 would do. Now we fix the order with elevator scheduling (FCFS, shortest seek time first, the SCAN algorithm and the LOOK algorithm), meet starvation, add multiple elevators with a dispatcher (ElevatorController) and a choosing-an-elevator strategy, run the cars with a simulation loop or a thread per elevator, and show extensibility for VIP or service modes.
How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. The threads program prints a time in milliseconds that changes from run to run; three real runs are shown. The office building is made up for teaching.
1. The problem: Monday, 9:55 a.m., three lifts
| What people see | What went wrong | Fixed by |
|---|---|---|
| The car goes up, down, up, down | Calls served in pressed order (FCFS) | A scheduling strategy: LOOK |
| Ravi waits at the ground floor while the lift serves floors 4 and 6 again and again | "Nearest call first" (SSTF) never picks him | SCAN / LOOK: no starvation |
| Asha (floor 4, DOWN) gets car A, the nearest, which first goes up to 9 | "Nearest car" ignores direction | A direction-aware cost in the dispatcher |
| A car being cleaned takes passengers | Mode ignored | Modes: the dispatcher filters by Mode |
2. Scheduling: in which order?
Elevator scheduling means choosing the order in which a car serves its requests. Goals: less travel, less waiting, and nobody waits forever.
One word borrowed from hard disks, which had the same problem with their read/write arm moving across the disk: seek = the distance the car moves to reach a floor. "Seek time" is how long that takes; with one floor per tick, it's the number of floors.
There are several orders, so the order becomes a strategy (episode 34, Strategy pattern): an interface SchedulingStrategy with one method, path(start, requests), returning the floors in visit order. The car doesn't care which strategy it has.
The four classic orders:
| Strategy | Rule | Real-life picture |
|---|---|---|
| FCFS (first come, first served) | In the order pressed | The token counter at a bank: token 1, 2, 3 |
| SSTF (shortest seek time first) | Always go to the nearest waiting request | A waiter who always serves the nearest table: the corner table waits all evening |
| SCAN | Keep going one way, serving everything on the way, to the end of the shaft; then turn | A local train: runs to the last station, then back |
| LOOK | Like SCAN, but turn at the last request in that direction, not at the end | A school bus: turns at the last child's stop |
SCAN is also known in disk scheduling as the elevator algorithm, because it's how lifts naturally move.
3. FCFS vs SSTF vs SCAN vs LOOK, on the same requests
Test: the car is at floor 4, going up; requests 8, 1, 6, 2; the shaft's top floor is 9.
import java.util.*;
interface SchedulingStrategy { List<Integer> path(int start, List<Integer> requests); } // visit order
class Fcfs implements SchedulingStrategy { // first come, first served: as pressed
public List<Integer> path(int s, List<Integer> r) { return r; } }
class Sstf implements SchedulingStrategy { // shortest seek time first: nearest next
public List<Integer> path(int s, List<Integer> r) {
List<Integer> left = new ArrayList<>(r), out = new ArrayList<>();
while (!left.isEmpty()) {
final int at = s;
int next = Collections.min(left, Comparator.comparingInt(f -> Math.abs(f - at)));
left.remove(Integer.valueOf(next)); out.add(next); s = next; }
return out; } }
class Look implements SchedulingStrategy { // up to the LAST request, then turn
public List<Integer> path(int s, List<Integer> r) { return sweep(s, r, -1); }
static List<Integer> sweep(int s, List<Integer> r, int end) { // the car starts going UP
List<Integer> out = new ArrayList<>(r.stream().filter(f -> f >= s).sorted().toList());
if (end >= 0 && !out.contains(end)) out.add(end); // SCAN rides on to the end floor
r.stream().filter(f -> f < s).sorted(Comparator.reverseOrder()).forEach(out::add);
return out; } }
class Scan implements SchedulingStrategy { private final int top; Scan(int top) { this.top = top; }
public List<Integer> path(int s, List<Integer> r) { return Look.sweep(s, r, top); } }
public class Main { public static void main(String[] args) {
List<Integer> req = List.of(8, 1, 6, 2); // the car is at 4, going up
for (SchedulingStrategy st : List.of(new Fcfs(), new Sstf(), new Scan(9), new Look())) {
List<Integer> p = st.path(4, req); int moved = 0, at = 4;
for (int f : p) { moved += Math.abs(f - at); at = f; }
System.out.println(st.getClass().getSimpleName() + " " + p + " moved " + moved + " floors"); }
}}
Output:
Fcfs [8, 1, 6, 2] moved 20 floors
Sstf [6, 8, 2, 1] moved 11 floors
Scan [6, 8, 9, 2, 1] moved 13 floors
Look [6, 8, 2, 1] moved 11 floors
How each path is made:
- Fcfs:
[8, 1, 6, 2]as pressed: 4→8 (4) →1 (7) →6 (5) →2 (4) = 20. - Sstf: from 4, the nearest of {8, 1, 6, 2} is 6 (distance 2; 2 is also distance 2, and
Collections.minkeeps the first minimum it meets, which is 6). Then from 6: 8. From 8: 2. From 2: 1. Total 11. - Scan: up from 4: 6, 8, then on to the end 9 (nobody asked), then down: 2, 1. Total 5 + 8 = 13.
- Look: up: 6, 8, turn at 8 (the last request up), down: 2, 1. Total 4 + 7 = 11.
Tools used: Collections.min(list, comparator) returns the smallest element by that comparator; Comparator.comparingInt(f -> Math.abs(f - at)) compares floors by distance from at. Inside a lambda you may only use effectively final local variables (never reassigned), which is why Sstf copies s into final int at each round. stream().filter(...).sorted().toList() (episode 5) keeps the matching floors and sorts them; Comparator.reverseOrder() sorts downwards.
So SSTF ties with LOOK. It looks just as good. Is it?
4. The hidden trap: starvation
The test above was fixed: four requests, then done. In a real building new calls arrive all the time. Car at 5, Ravi waiting at 0, and floors 4 and 6 calling again on every tick:
import java.util.*;
public class Main { // SSTF while new calls keep arriving
public static void main(String[] args) {
List<Integer> waiting = new ArrayList<>(List.of(0)); // Ravi on floor 0 is waiting
int car = 5, served = 0;
for (int tick = 1; tick <= 20; tick++) {
waiting.add(tick % 2 == 0 ? 4 : 6); // the busy floors keep calling
final int at = car;
int next = Collections.min(waiting, Comparator.comparingInt(f -> Math.abs(f - at)));
waiting.remove(Integer.valueOf(next)); car = next; served++;
if (next == 0) { System.out.println("floor 0 served at tick " + tick); return; }
}
System.out.println(served + " calls served in 20 ticks. Floor 0 still waiting: " + waiting.contains(0));
}
}
Output:
20 calls served in 20 ticks. Floor 0 still waiting: true
The car worked every tick, and Ravi was never served: there was always a call nearer than floor 0. A request that can wait forever because others keep jumping ahead of it suffers starvation.
Why SCAN and LOOK are fair
SCAN and LOOK only turn around after finishing a direction. New calls at 4 and 6 can't keep the car near them forever: once it's going up it must later come down, and on the way down it reaches 0. So every request is served within about one round trip (a bounded wait). LOOK does the same with less waste (no empty ride to the end). That's why LOOK is our default, and why it's a strategy: a building can swap it without touching the car.
| Strategy | Total travel | Worst-case wait | Starvation? |
|---|---|---|---|
| FCFS | high (zigzag) | bounded | no |
| SSTF | low | unbounded | yes |
| SCAN | medium (empty ride to the end) | about one round trip | no |
| LOOK | low | about one round trip | no |
5. Many elevators: a dispatcher
With three cars, someone must decide which car answers a hall call. A dispatcher is whoever sends each job to a worker, like the person at a taxi stand. Ours is the ElevatorController: one per building, it owns all the cars.
- A hall call (external request) goes to the controller, which picks one car and adds the floor to that car's stops.
- A car call (internal request) goes straight into that car's own stops: no choice needed.
How to choose? A choosing-an-elevator strategy, ElevatorSelectionStrategy, gives each car a cost (lower = better); the controller takes the lowest. The obvious cost is the distance: "send the nearest car".
The smarter direction-aware cost:
| Car situation | Cost |
|---|---|
| Idle | distance to the floor |
| Moving in the wanted direction and hasn't passed the floor yet ("on the way") | distance to the floor |
| Anything else (moving away, or moving the other way) | finish its trip to its target, then come back: |target − floor_car| + |target − floor_call| |
import java.util.*;
enum Direction { UP, DOWN, IDLE } enum Mode { NORMAL, VIP, SERVICE }
record Car(String id, int floor, int target, Mode mode) { // target: where it is heading now
Direction dir() { return target > floor ? Direction.UP : target < floor ? Direction.DOWN : Direction.IDLE; } }
interface ElevatorSelectionStrategy { int cost(Car c, int floor, Direction want); } // lower = better
class Nearest implements ElevatorSelectionStrategy { // the obvious way
public int cost(Car c, int floor, Direction want) { return Math.abs(c.floor() - floor); } }
class DirectionAware implements ElevatorSelectionStrategy {
public int cost(Car c, int floor, Direction want) {
boolean onTheWay = c.dir() == want && (want == Direction.UP ? c.floor() <= floor : c.floor() >= floor);
if (c.dir() == Direction.IDLE || onTheWay) return Math.abs(c.floor() - floor);
return Math.abs(c.target() - c.floor()) + Math.abs(c.target() - floor); // finish the trip, come back
} }
class ElevatorController { // the dispatcher
final List<Car> cars; ElevatorSelectionStrategy strategy;
ElevatorController(List<Car> cars, ElevatorSelectionStrategy s) { this.cars = cars; strategy = s; }
Car assign(int floor, Direction want) {
return cars.stream().filter(c -> c.mode() == Mode.NORMAL) // VIP and SERVICE cars skip hall calls
.min(Comparator.comparingInt(c -> strategy.cost(c, floor, want))).orElseThrow(); } }
public class Main { public static void main(String[] args) {
List<Car> cars = List.of(new Car("A", 5, 9, Mode.NORMAL), new Car("B", 0, 0, Mode.NORMAL),
new Car("C", 4, 4, Mode.SERVICE)); // C is being cleaned
ElevatorController ctl = new ElevatorController(cars, new Nearest());
System.out.println("Asha on 4 wants DOWN. Nearest picks " + ctl.assign(4, Direction.DOWN));
ctl.strategy = new DirectionAware();
System.out.println("DirectionAware picks " + ctl.assign(4, Direction.DOWN));
for (Car x : cars) System.out.println(" cost of " + x.id() + " = " + ctl.strategy.cost(x, 4, Direction.DOWN));
}}
Output:
Asha on 4 wants DOWN. Nearest picks Car[id=A, floor=5, target=9, mode=NORMAL]
DirectionAware picks Car[id=B, floor=0, target=0, mode=NORMAL]
cost of A = 9
cost of B = 4
cost of C = 0
Car A is at 5 heading up to 9; B is idle at 0; C is idle at 4 but in SERVICE mode. Asha on 4 wants DOWN.
- Nearest picks A (1 floor away), the car that first goes up to 9.
- DirectionAware picks B: A's cost is (9 − 5) + (9 − 4) = 9; B's cost is 4. C's cost is 0, but
assignfilters it out because it isn'tNORMAL.
Car is a record here (episode 3): id, floor, target, mode, plus a computed dir(). ctl.strategy = new DirectionAware() swaps the strategy at runtime: the controller code doesn't change.
6. Running the cars: simulation loop vs thread per elevator
Every car runs a simulation loop: again and again, take the next target, move there floor by floor, open the door. Two ways to run several cars:
| One simulation loop for all cars | Thread per elevator | |
|---|---|---|
| How | One loop calls step() on every car each tick |
Each car runs its own loop in its own thread (episode 46) |
| Output | The same every run (deterministic) | Order and timing vary between runs |
| Testing | Easy: call tick() n times |
Harder: needs waiting, timeouts |
| Real concurrency | No | Yes: cars really move at the same time |
| Best for | Interviews, tests, simulations | A real controller talking to real motors |
For thread per elevator, each car takes its targets from a BlockingQueue (episode 49): take() makes the thread sleep, using no CPU, until a target arrives. To stop a thread cleanly we send a poison pill: a special value (here -1) meaning "shut down". join() makes main wait until a thread has finished.
import java.util.*;
import java.util.concurrent.*;
class ElevatorCar implements Runnable { // one thread per elevator
final String id; int floor; final List<String> log = new ArrayList<>();
final BlockingQueue<Integer> targets = new LinkedBlockingQueue<>();
ElevatorCar(String id, int floor) { this.id = id; this.floor = floor; }
public void run() { // the car's own simulation loop
try {
while (true) {
int t = targets.take(); // sleeps until there is work
if (t < 0) break; // -1 means: shut down
while (floor != t) { Thread.sleep(20); floor += t > floor ? 1 : -1; } // 20 ms a floor
log.add(id + " opens at " + floor);
}
} catch (InterruptedException e) { Thread.currentThread().interrupt(); }
} }
public class Main { public static void main(String[] args) throws Exception {
ElevatorCar a = new ElevatorCar("A", 0), b = new ElevatorCar("B", 9);
Thread ta = new Thread(a), tb = new Thread(b);
long t0 = System.nanoTime(); ta.start(); tb.start();
a.targets.put(3); a.targets.put(7); // A: 0 -> 3 -> 7, 7 floors
b.targets.put(6); b.targets.put(1); // B: 9 -> 6 -> 1, 8 floors
a.targets.put(-1); b.targets.put(-1); ta.join(); tb.join();
System.out.println(a.log + " " + b.log);
long ms = (System.nanoTime() - t0) / 1_000_000;
System.out.println("took " + ms + " ms; one car after the other needs at least " + (7 + 8) * 20 + " ms");
}}
Three real runs:
[A opens at 3, A opens at 7] [B opens at 6, B opens at 1]
took 190 ms; one car after the other needs at least 300 ms
[A opens at 3, A opens at 7] [B opens at 6, B opens at 1]
took 202 ms; one car after the other needs at least 300 ms
[A opens at 3, A opens at 7] [B opens at 6, B opens at 1]
took 197 ms; one car after the other needs at least 300 ms
A moves 7 floors and B 8, at 20 ms a floor: one after the other that's at least (7 + 8) × 20 = 300 ms. Both together take about as long as the slower car (B: 160 ms) plus thread start-up, and the number changes every run.
Why no lock on log? Each log is written only by its own car's thread, and main reads it only after join(). join() creates a happens-before relationship (episode 47): everything the thread did before ending is visible to the thread that joined it. So this code is correct without synchronized. If main read a.log while car A was still running, you would need a thread-safe list.
InterruptedException: take() and sleep() throw it when another thread interrupts this one (asks it to stop). Catching it and calling Thread.currentThread().interrupt() keeps the "interrupted" flag set, the standard polite way to handle it.
7. Extensibility: VIP, service and other modes
Interviewers love "now add a VIP mode". With enum Mode { NORMAL, VIP, SERVICE } it's already there:
- SERVICE: the car is being cleaned or repaired: no passengers, no hall calls.
- VIP: one key-holder (a hospital stretcher, a chairman) rides nonstop to their floor: no hall calls while in VIP mode.
- The dispatcher filters by mode: one line in
assign. No new classes, no change to the cars.
More modes, the same way:
| Need | Where it goes |
|---|---|
| Morning up-peak (everyone goes up from the lobby) | an up-peak scheduling strategy that sends idle cars back to the lobby |
| Fire alarm | a FIRE mode: every car to the ground floor, doors open, hall calls refused (practice 3) |
| Car full | cost = infinity until people get out (practice 1) |
| Odd and even floors | a selection strategy that only allows some floors per car |
8. The class diagram
ElevatorController (the dispatcher, one per building)
├─uses──▶ ElevatorSelectionStrategy ── Nearest · DirectionAware
├─has───▶ ElevatorCar ×3 each: floor, Direction, Mode, its own thread
│ └─uses──▶ SchedulingStrategy ── Fcfs · Sstf · Scan · Look
└─skips─▶ cars whose Mode is VIP or SERVICE for hall calls
Hall call → controller.assign(floor, direction) → one car's queue
Car button → straight into that car's queue
Two strategies, two levels: the selection strategy decides which car; each car's scheduling strategy decides in which order it serves its stops.
9. Interview follow-ups
| Follow-up | Answer |
|---|---|
| The car is full | Its cost becomes infinite (Integer.MAX_VALUE) until people get out |
| Some cars serve only odd or even floors | A selection strategy that allows only some floors per car |
| Destination dispatch (type your floor in the lobby; the screen says which car) | The controller knows destinations up front and can group people going to nearby floors |
| A thread-safe controller | assign reads every car's floor and direction: lock the cars, or read an immutable snapshot of each |
| How do you test it? | The single simulation loop with an injected clock: no sleep, the same output every run |
| Which strategy is best? | Don't guess: simulate a morning and measure the average and worst wait (practice 4) |
10. Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Serving in pressed order (FCFS) | Fcfs [8, 1, 6, 2] moved 20 floors |
Zigzag | LOOK: sweep, then turn |
| Always the nearest request (SSTF) | 20 calls served in 20 ticks. Floor 0 still waiting: true |
Starvation | SCAN or LOOK |
| SCAN when LOOK would do | Scan [6, 8, 9, 2, 1] moved 13 floors |
Empty ride to the end | LOOK turns at the last request |
| Nearest car, ignoring direction | Nearest picks Car[id=A, floor=5, target=9, mode=NORMAL] |
Distance isn't the whole cost | Direction-aware cost |
| Hall calls to a car in SERVICE | a car being cleaned takes people | Mode ignored | Filter by Mode in assign() |
| No car available | IllegalStateException: no car available for floor 6 (practice 3) |
Every car filtered out | orElseThrow with a clear message, or queue the call until a car is free |
A busy loop instead of take() |
a thread burns a whole CPU core while idle | Polling an empty queue | BlockingQueue.take() sleeps until work arrives |
| Using a variable that changes inside a lambda | error: local variables referenced from a lambda expression must be final or effectively final |
Lambdas capture values, not variables | Copy it into a final local first |
Reading another thread's data before join() |
stale or partial results | No happens-before | join() first, or a thread-safe collection |
The lambda error is real: replace final int at = s; in Sstf with nothing and use s inside the lambda, and javac 21 prints Main.java:9: error: local variables referenced from a lambda expression must be final or effectively final.
Mini project: a building with two cars, one simulation loop
A controller with a direction-aware selection strategy, two cars that each keep their stops in a TreeSet and sweep through them LOOK-style, and one deterministic loop that ticks every car. Ravi (3, UP) and Asha (7, DOWN) call; then each presses a destination inside.
import java.util.*;
enum Direction { UP, DOWN, IDLE }
enum Mode { NORMAL, VIP, SERVICE }
class ElevatorCar {
final String id;
int floor;
Direction dir = Direction.IDLE;
Mode mode = Mode.NORMAL;
final TreeSet<Integer> stops = new TreeSet<>(); // LOOK: sorted stops, sweep through them
ElevatorCar(String id, int floor) { this.id = id; this.floor = floor; }
void addStop(int f) { stops.add(f); }
int targetAhead() { // next stop in the current direction, or null-like -1
Integer t = dir == Direction.DOWN ? stops.floor(floor) : stops.ceiling(floor);
return t == null ? -1 : t;
}
void step() { // one tick of the simulation loop
if (stops.isEmpty()) { dir = Direction.IDLE; return; }
if (stops.remove(floor)) { System.out.println(" " + id + " opens at " + floor); return; }
if (dir == Direction.IDLE) dir = stops.ceiling(floor) != null ? Direction.UP : Direction.DOWN;
if (targetAhead() < 0) dir = dir == Direction.UP ? Direction.DOWN : Direction.UP; // LOOK: turn at the last stop
floor += dir == Direction.UP ? 1 : -1;
}
int target() { return stops.isEmpty() ? floor : dir == Direction.DOWN ? stops.first() : stops.last(); }
public String toString() { return id + "@" + floor + (dir == Direction.IDLE ? "" : dir == Direction.UP ? "^" : "v"); }
}
interface ElevatorSelectionStrategy { int cost(ElevatorCar c, int floor, Direction want); }
class DirectionAware implements ElevatorSelectionStrategy {
public int cost(ElevatorCar c, int floor, Direction want) {
boolean onTheWay = c.dir == want && (want == Direction.UP ? c.floor <= floor : c.floor >= floor);
if (c.dir == Direction.IDLE || onTheWay) return Math.abs(c.floor - floor);
return Math.abs(c.target() - c.floor) + Math.abs(c.target() - floor);
}
}
class ElevatorController { // the dispatcher
private final List<ElevatorCar> cars;
private final ElevatorSelectionStrategy strategy;
ElevatorController(List<ElevatorCar> cars, ElevatorSelectionStrategy s) { this.cars = cars; strategy = s; }
void hallCall(int floor, Direction want) {
ElevatorCar best = cars.stream().filter(c -> c.mode == Mode.NORMAL)
.min(Comparator.comparingInt(c -> strategy.cost(c, floor, want))).orElseThrow();
best.addStop(floor);
System.out.println(" hall call " + floor + " " + want + " -> " + best.id);
}
void carCall(ElevatorCar c, int floor) { c.addStop(floor); System.out.println(" inside " + c.id + ": " + floor); }
void tick(int t) { // the simulation loop body: every car, one step
for (ElevatorCar c : cars) c.step();
System.out.println("t=" + t + " " + cars);
}
}
public class Main {
public static void main(String[] args) {
ElevatorCar a = new ElevatorCar("A", 0), b = new ElevatorCar("B", 9);
ElevatorController ctl = new ElevatorController(List.of(a, b), new DirectionAware());
ctl.hallCall(3, Direction.UP); // Ravi on 3 wants up
ctl.hallCall(7, Direction.DOWN); // Asha on 7 wants down
for (int t = 1; t <= 4; t++) ctl.tick(t);
ctl.carCall(a, 6); // Ravi got in A, pressed 6
ctl.carCall(b, 1); // Asha got in B, pressed 1
for (int t = 5; t <= 11; t++) ctl.tick(t);
}
}
Output:
hall call 3 UP -> A
hall call 7 DOWN -> B
t=1 [A@1^, B@8v]
t=2 [A@2^, B@7v]
B opens at 7
t=3 [A@3^, B@7v]
A opens at 3
t=4 [A@3^, B@7]
inside A: 6
inside B: 1
t=5 [A@4^, B@6v]
t=6 [A@5^, B@5v]
t=7 [A@6^, B@4v]
A opens at 6
t=8 [A@6^, B@3v]
t=9 [A@6, B@2v]
t=10 [A@6, B@1v]
B opens at 1
t=11 [A@6, B@1v]
How LOOK works here: stops is a TreeSet (always sorted). Going up, stops.ceiling(floor) is the next stop at or above the car; going down, stops.floor(floor) is the next at or below. When there's nothing ahead, the car turns. Each car's step() does one thing per tick, so the run is the same every time: a great shape for an interview, and easy to test.
Practice
1. Make a full car never get chosen: give Car a number of people and a capacity, and make the cost Integer.MAX_VALUE when it's full.
Answer
import java.util.*;
enum Direction { UP, DOWN, IDLE }
record Car(String id, int floor, int target, int people, int capacity) {
Direction dir() { return target > floor ? Direction.UP : target < floor ? Direction.DOWN : Direction.IDLE; }
boolean full() { return people >= capacity; }
}
interface ElevatorSelectionStrategy { int cost(Car c, int floor, Direction want); }
class DirectionAware implements ElevatorSelectionStrategy {
public int cost(Car c, int floor, Direction want) {
if (c.full()) return Integer.MAX_VALUE; // can't take anyone: never choose it
boolean onTheWay = c.dir() == want && (want == Direction.UP ? c.floor() <= floor : c.floor() >= floor);
if (c.dir() == Direction.IDLE || onTheWay) return Math.abs(c.floor() - floor);
return Math.abs(c.target() - c.floor()) + Math.abs(c.target() - floor);
}
}
public class Main {
public static void main(String[] args) {
List<Car> cars = List.of(new Car("A", 3, 0, 8, 8), new Car("B", 9, 9, 0, 8));
ElevatorSelectionStrategy s = new DirectionAware();
for (Car c : cars) System.out.println(c.id() + " cost " + (s.cost(c, 2, Direction.DOWN) == Integer.MAX_VALUE ? "FULL" : s.cost(c, 2, Direction.DOWN)));
Car best = cars.stream().min(Comparator.comparingInt(c -> s.cost(c, 2, Direction.DOWN))).orElseThrow();
System.out.println("call on 2, DOWN -> car " + best.id());
}
}
Output:
A cost FULL
B cost 7
call on 2, DOWN -> car B
Car A is nearer and even heading down, but it's full (8 of 8), so B gets the call.
2. Our LOOK assumed the car starts going up. Write a LOOK that works for a car going up or down.
Answer
import java.util.*;
public class Main {
// LOOK for a car going in either direction: first the requests ahead, then turn
static List<Integer> look(int start, boolean goingUp, List<Integer> r) {
List<Integer> up = r.stream().filter(f -> f >= start).sorted().toList();
List<Integer> down = r.stream().filter(f -> f < start).sorted(Comparator.reverseOrder()).toList();
List<Integer> out = new ArrayList<>(goingUp ? up : down);
out.addAll(goingUp ? down : up);
return out;
}
static int moved(int s, List<Integer> path) { int m = 0; for (int f : path) { m += Math.abs(f - s); s = f; } return m; }
public static void main(String[] args) {
List<Integer> req = List.of(8, 1, 6, 2);
for (boolean up : new boolean[] { true, false }) {
List<Integer> p = look(4, up, req);
System.out.println("car at 4 going " + (up ? "UP " : "DOWN") + ": " + p + ", moved " + moved(4, p));
}
}
}
Output:
car at 4 going UP : [6, 8, 2, 1], moved 11
car at 4 going DOWN: [2, 1, 6, 8], moved 10
3. Add a FIRE mode: on an alarm every car goes to the ground floor, and hall calls are refused with a clear message.
Answer
import java.util.*;
enum Mode { NORMAL, VIP, SERVICE, FIRE }
class Car {
final String id; int floor; Mode mode = Mode.NORMAL;
Car(String id, int floor) { this.id = id; this.floor = floor; }
public String toString() { return id + "@" + floor + " " + mode; }
}
class ElevatorController {
final List<Car> cars;
ElevatorController(List<Car> cars) { this.cars = cars; }
void fireAlarm() { // every car: straight to the ground floor, doors open
for (Car c : cars) { c.mode = Mode.FIRE; c.floor = 0; }
System.out.println("FIRE: " + cars);
}
Car assign(int floor) {
return cars.stream().filter(c -> c.mode == Mode.NORMAL)
.min(Comparator.comparingInt(c -> Math.abs(c.floor - floor)))
.orElseThrow(() -> new IllegalStateException("no car available for floor " + floor));
}
}
public class Main {
public static void main(String[] args) {
ElevatorController ctl = new ElevatorController(List.of(new Car("A", 5), new Car("B", 8)));
System.out.println("call on 6 -> " + ctl.assign(6));
ctl.fireAlarm();
ctl.assign(6);
}
}
Output:
call on 6 -> A@5 NORMAL
FIRE: [A@0 FIRE, B@0 FIRE]
Exception in thread "main" java.lang.IllegalStateException: no car available for floor 6
at ElevatorController.lambda$assign$2(Main.java:18)
at java.base/java.util.Optional.orElseThrow(Optional.java:403)
at ElevatorController.assign(Main.java:18)
at Main.main(Main.java:26)
orElseThrow(() -> new IllegalStateException(...)) turns "no car matched the filter" into a clear exception instead of NoSuchElementException: No value present.
4. Don't guess which strategy is best: simulate 50 batches of 5 random calls (fixed seed, so the run is repeatable) in a 20-floor building and compare the average floors moved.
Answer
import java.util.*;
public class Main {
interface Strategy { List<Integer> path(int start, List<Integer> r); }
static int moved(int s, List<Integer> path) { int m = 0; for (int f : path) { m += Math.abs(f - s); s = f; } return m; }
public static void main(String[] args) {
Strategy fcfs = (s, r) -> r;
Strategy sstf = (s, r) -> {
List<Integer> left = new ArrayList<>(r), out = new ArrayList<>(); int at = s;
while (!left.isEmpty()) { final int a = at; int n = Collections.min(left, Comparator.comparingInt(f -> Math.abs(f - a)));
left.remove(Integer.valueOf(n)); out.add(n); at = n; }
return out; };
Strategy look = (s, r) -> {
List<Integer> out = new ArrayList<>(r.stream().filter(f -> f >= s).sorted().toList());
r.stream().filter(f -> f < s).sorted(Comparator.reverseOrder()).forEach(out::add); return out; };
Random rnd = new Random(42); // fixed seed: the same "random" calls every run
long[] total = new long[3];
for (int batch = 0; batch < 50; batch++) { // 50 batches of 5 calls in a 20-floor building
int start = rnd.nextInt(20); List<Integer> calls = new ArrayList<>();
for (int i = 0; i < 5; i++) calls.add(rnd.nextInt(20));
Strategy[] all = { fcfs, sstf, look };
for (int k = 0; k < 3; k++) total[k] += moved(start, all[k].path(start, calls));
}
System.out.printf("average floors per batch: FCFS %.1f, SSTF %.1f, LOOK %.1f%n", total[0] / 50.0, total[1] / 50.0, total[2] / 50.0);
}
}
Output:
average floors per batch: FCFS 34.0, SSTF 18.3, LOOK 19.9
On distance alone, SSTF edges out LOOK, and both beat FCFS by far. But this simulation has no new calls arriving during a batch, so it can't show starvation (section 4). A real comparison also measures the worst wait, where SSTF loses. Measure what matters to the building.
5. (Thinking) Why are there two strategies, one in the controller and one in each car?
Answer
They answer different questions. The selection strategy (controller) answers which car takes this hall call? The scheduling strategy (car) answers in which order does this car serve its stops? They change for different reasons (a new building policy vs a new sweep rule), so by the Single Responsibility Principle (episode 12) they are separate.
Quick quiz
The car is at floor 4, going UP. Requests: 7, 2, 9. Strategy: LOOK. In which order are they served? (a) 2, 7, 9 (b) 7, 9, 2 (c) 9, 7, 2 (d) 7, 2, 9
Answer
(b) 7, 9, 2. LOOK keeps going up while there are requests above: 7, then 9; 9 is the last request up, so it turns and comes down for 2. That's 3 + 2 + 7 = 12 floors. (SSTF would go to 2 first, the nearest, for 2 + 5 + 2 = 9 floors here, but it can starve someone when calls keep arriving.)
Interview questions
- What scheduling algorithms do you know for elevators? FCFS (pressed order), SSTF (nearest next), SCAN (sweep to the end, turn), LOOK (sweep to the last request, turn). LOOK is the usual default.
- Why not SSTF, if it moves the least? Starvation: with calls arriving all the time, a far request may never be the nearest. SCAN/LOOK bound the wait to about one round trip.
- SCAN vs LOOK? SCAN always rides to the end of the shaft; LOOK turns at the last request, saving the empty ride.
- How do you pick which elevator answers a hall call? A dispatcher (
ElevatorController) with a pluggableElevatorSelectionStrategy: compute a cost per car (idle or on the way: distance; otherwise finish the trip and come back) and take the lowest, skipping cars that are full or in special modes. - Internal requests: does the controller choose? No: a car button belongs to that car; it goes straight into its stops.
- How do you run several cars? One deterministic simulation loop ticking every car (best for interviews and tests), or a thread per elevator with a
BlockingQueueof targets (real concurrency). - How do you stop a car's thread cleanly? A poison pill (a special value like
-1) in its queue, orinterrupt(); thenjoin(). - How would you add VIP, service or fire modes? A
Modeenum; the dispatcher filters by mode; mode-specific behaviour (nonstop, go to ground) goes in the car or in a strategy. No change to other classes. - Is your controller thread-safe? In the threaded version
assignreads all cars, so it must lock them or read immutable snapshots; each car's queue is already thread-safe (LinkedBlockingQueue). - How would you prove one strategy is better? Simulate realistic traffic with a fixed random seed, and measure average and worst-case waiting time and total travel.
Glossary
| Term | Meaning, with an example |
|---|---|
| Elevator scheduling | Choosing the order in which a car serves its requests |
| Seek / seek time | The distance (or time) the car moves to reach a floor; borrowed from disk scheduling |
| FCFS | First come, first served: requests in the order pressed; [8, 1, 6, 2] → 20 floors |
| SSTF | Shortest seek time first: always the nearest waiting request next |
| SCAN algorithm | Sweep one way to the end of the shaft, serving requests on the way, then turn; also called the "elevator algorithm" |
| LOOK algorithm | Like SCAN, but turn at the last request in the current direction |
| Starvation | A request that can wait forever because others keep jumping ahead: Ravi on floor 0 under SSTF |
| Bounded wait | A guarantee that every request is served within some limit, like one round trip |
| Strategy pattern | Putting an algorithm behind an interface so it can be swapped: SchedulingStrategy |
| SchedulingStrategy | Our interface for the order: path(start, requests) |
| Dispatcher | Whoever sends each job to a worker; for lifts, the part that picks a car for a hall call |
| ElevatorController | Our dispatcher: owns all cars, assigns hall calls |
| Choosing an elevator strategy | The rule for which car answers a call; our ElevatorSelectionStrategy |
| Cost function | A number per car (lower = better) used to choose: distance, or "finish the trip and come back" |
| Direction-aware cost | A cost that counts a car moving away as far away, even if it's near now |
| Hall call / car call | External request from a floor / internal request from inside a car |
| Mode | A car's special condition: NORMAL, VIP, SERVICE (and FIRE) |
| VIP mode | One key-holder rides nonstop; no hall calls |
| Service mode | Cleaning or repair; no passengers |
| Simulation loop | A loop that advances the model one step at a time: for each tick: every car steps |
| Tick | One step of simulated time |
| Deterministic | The same input always gives the same output (the single loop) |
| Thread | A path of execution that runs at the same time as others (episode 46) |
| Thread per elevator | Each car runs its own simulation loop in its own thread |
| Runnable | An interface with one method run(): the work a thread does |
| BlockingQueue | A thread-safe queue whose take() waits (sleeps) until an element is available |
| LinkedBlockingQueue | A common BlockingQueue implementation, backed by linked nodes |
| take() | Remove the head of a BlockingQueue, waiting if it's empty |
| Poison pill | A special value meaning "stop": -1 in our queue |
| join() | Wait until a thread finishes |
| Happens-before | Java's rule for when one thread's writes are visible to another; join() creates one |
| InterruptedException | Thrown by sleep() / take() when the thread is asked to stop |
| Busy loop (polling) | Checking again and again in a loop; wastes CPU; use take() instead |
| Effectively final | A local variable never reassigned; only those may be used inside a lambda |
| Collections.min | Returns the smallest element by a comparator |
| TreeSet ceiling / floor | The smallest element ≥ x / the largest element ≤ x |
| Record | A short class that just holds values: record Car(String id, int floor, int target, Mode mode) |
| Destination dispatch | You enter your floor in the lobby; the system tells you which car to take |
| Up-peak | The morning rush when most people go up from the lobby |
Summary
- Scheduling decides the order. On the same requests: FCFS 20 floors, SSTF 11, SCAN 13, LOOK 11.
- SSTF moves little but starves:
20 calls served in 20 ticks. Floor 0 still waiting: true. SCAN/LOOK sweep, so every request is served within a round trip; LOOK is the default. It's a strategy, so it's swappable. - An ElevatorController (dispatcher) picks a car for each hall call with a pluggable selection strategy. Nearest picked car A going up to 9; a direction-aware cost (A 9, B 4) picked idle car B. Car calls go straight to their car.
- Cars run in one simulation loop (deterministic, testable) or a thread per elevator with a BlockingQueue, a poison pill and join().
- Modes (VIP, SERVICE, FIRE) are a filter in the dispatcher plus small rules in the car: extension without rewrites.
Next episode: Design a Vending Machine: products, inventory, coins and notes, states, change and refunds.