Elevator system
Design an elevator system in a machine-coding interview: hall and car calls, LOOK scheduling per car, a swappable dispatch strategy, full Java and Python code, and thread safety.
On this page
- The problem: one queue, first come first served
- 1. Clarify the requirements
- 2. Find the entities
- 3. How one car orders its stops: SCAN and LOOK
- 4. Which car goes: the dispatch strategy
- 5. The class design
- 6. The code
- 7. Concurrency
- 8. Extensions the interviewer will ask for
- When not to over-design
- In the interview
- Quiz
The problem: one queue, first come first served
"Design an elevator system" sounds like a simulation, but the interviewer wants to see two separate decisions made well: which car answers a call, and in what order a car visits its floors. The first attempt usually merges both into one queue:
class Elevator {
Queue<Integer> requests = new LinkedList<>();
void request(int floor) { requests.add(floor); }
void run() {
while (!requests.isEmpty()) moveTo(requests.poll()); // first come, first served
}
}
Requests for floors 9, 1, 8, 2 arrive in that order, and the car goes 9 → 1 → 8 → 2: 9 + 8 + 7 + 6 = 30 floors of travel, passing floors where people are waiting. It also ignores direction: someone on floor 5 who pressed "down" gets picked up by a car on its way up. And with several cars, who decides which one goes?
Serving the same four floors in sweeps (up to 9 stopping at 8, then down stopping at 2 and 1) from floor 0 is 9 + 8 = 17 floors of travel instead of 30.
1. Clarify the requirements
Clarify the building and the two kinds of button
- “Design an elevator system.” First, clarify. How many elevators and floors? People press an up or down button on a floor, called a hall call, or a floor number inside the car. A controller decides which elevator answers each call.
The interviewer says "Design an elevator system for an office building." Write 5–6 questions you would ask, then the requirements you would agree on and what's out of scope.
Compare with our answer
Questions worth asking: How many cars and floors? Do all cars serve all floors? Hall buttons with up/down, or destination keypads in the lobby? Is there a capacity or weight limit? What happens in an emergency or fire? Is the goal shortest wait, shortest trip, or energy? Do we simulate time or drive real motors?
A strong answer mentions: the difference between hall calls (floor + direction) and car calls (floor) · several cars and a dispatcher · direction-aware stopping · a swappable dispatch rule · emergency stop and maintenance mode · a simulated clock (ticks) for testability.
The agreed list for this page:
| Functional | Detail |
|---|---|
| Building | N cars, F floors (0 = lobby); every car serves every floor |
| Hall call | A button on a floor: (floor, UP or DOWN). The controller assigns it to one car |
| Car call | A floor button inside a car; goes to that car only |
| Movement | Each car visits its stops in sweeps: keep going one way while there are stops ahead, then turn |
| Direction | A car stops for a hall call only when travelling in the direction the caller wants |
| Time | A simulated tick: each tick a car either moves one floor or opens its doors |
Out of scope: weight sensors, door obstruction, fire service mode, energy optimisation, destination-dispatch keypads. Mention them as extensions.
2. Find the entities
Controller, elevators, requests and a dispatch strategy
- The main classes: an ElevatorController, the Elevators it manages, a Request for each button press, and a Direction enum. Which elevator to send is a rule likely to change, so it’s a DispatchStrategy.
- Nouns → classes:
ElevatorController,Elevator(a car),Direction, and requests. In the code a hall call is passed as(floor, direction)rather than a separateRequestobject; add the class when requests gain more data (timestamp, priority). - Verbs → methods: press a hall button →
controller.hallCall(floor, dir); press a car button →elevator.pressFloor(f); move →elevator.step(); choose a car →DispatchStrategy.choose(...).
The two decisions map onto two different classes, and that separation is the core of the design:
| Decision | Who makes it | Changes how often |
|---|---|---|
| Which car answers a hall call | DispatchStrategy, called by the controller | Often: rush hour, zoning, VIP floors, energy saving |
| In what order a car visits its stops | The Elevator itself (LOOK) | Rarely: it is a well-known algorithm |
3. How one car orders its stops: SCAN and LOOK
The classic elevator algorithm comes from disk scheduling, where a disk head moves across tracks the way a car moves across floors.
Keep going while there are stops ahead, then turn round
- Each elevator follows the classic elevator algorithm: keep moving in the current direction, stopping at every requested floor on the way, and only turn around when there are no more stops ahead.
| Algorithm | How it works | Good at | Weak at |
|---|---|---|---|
| FCFS (first come, first served) | Visit requests in arrival order | Simple, obviously fair | Zig-zags; long travel |
| SSTF (shortest seek first) | Always go to the nearest request | Short average travel | Starvation: a far floor can wait for ever while near requests keep coming |
| SCAN | Sweep to the top floor, then to the bottom, serving requests on the way | Bounded wait; no starvation | Travels to the end even when nobody is there |
| LOOK (used here) | Like SCAN, but turn round at the last request in each direction | Bounded wait, less travel | Slightly more bookkeeping |
Why LOOK can't starve a floor: a car serves every stop ahead before it turns, and it can't go past the top or bottom floor, so any request is served within at most about two sweeps of the building, however many new requests arrive.
Direction-aware stops
A single set of stops (as in the figure below) stops at a floor whenever the car passes it. That picks up a "down" caller on the way up, who then rides to the top and back. The full code keeps two sets:
upStops: floors to stop at while going up (car calls above the car, hall calls for UP).downStops: floors to stop at while going down.
Each tick, a car does one of three things:
- If the current floor is in the stop set for its direction, open the doors and remove it.
- Otherwise, if there's any stop ahead (in either set), move one floor that way.
- Otherwise turn round, and check step 1 again (a "down" call at the topmost stop is served here).
When both sets are empty the car is IDLE; the next call sets its direction towards the nearest stop.
step(): open the doors, move one floor, or turn round
- In code, an elevator’s step() moves one floor toward its next stop, opens the doors when it arrives, and turns around or goes idle when there’s nothing left ahead.
4. Which car goes: the dispatch strategy
Dispatch: pick the best car for each hall call
- The controller’s job is dispatching: pick the best elevator for each hall call. “Nearest idle car” is a fine start. In the morning rush, a smarter rule spreads cars across the lobby. Because the rule is a strategy, swapping it doesn’t touch anything else.
"Nearest car" is the usual starting point, but plain distance is wrong for moving cars: a car two floors away heading the other way may take longer than an idle car six floors away. The strategy in the code estimates a cost per car:
| Car's situation | Cost estimate |
|---|---|
| Idle | Distance to the call |
| Moving towards the call, in the caller's direction | Distance, plus one for each stop on the way |
| Anything else (moving away, or wrong direction) | Distance to the end of its current sweep, back to the call, plus its number of stops |
Other strategies the interviewer may ask about, each a new class behind the same interface:
- Least busy: the car with the fewest stops; balances wear, ignores distance.
- Zoning: in tall buildings, cars A–B serve floors 0–20 and C–D serve 0 and 21–40; morning rush sends idle cars back to the lobby.
- Destination dispatch: passengers enter their destination in the lobby and are grouped by destination, so a car makes fewer stops. Many modern high-rises use this; the input changes from (floor, direction) to (floor, destination).
5. The class design
| Class / type | Kind | Responsibility |
|---|---|---|
Direction | enum | UP, DOWN, IDLE |
Elevator | entity | Floor, direction, upStops and downStops; pressFloor, assign, step, costTo |
DispatchStrategy | interface | choose(cars, floor, direction) |
DirectionAwareNearest | strategy | The cost rule above |
ElevatorController | facade | Owns the cars; hallCall asks the strategy and assigns; tick advances every car |
Why each pattern is there: Strategy for dispatch, because it's the rule most likely to change and to be tuned per building; Facade for the controller, because buttons, a building-management screen and tests all call two methods; and the car's own movement could become a State pattern (Idle, MovingUp, MovingDown, DoorsOpen, OutOfService) once doors, overload and maintenance are in scope. With three directions and one rule, an enum is simpler for now.
6. The code
Time is a tick, not a wall clock, so the demo is deterministic and testable. In a building each car would run its own loop calling step() every second or so.
import java.util.*;
import java.util.concurrent.*;
// ---------- Demo (first, so `java ElevatorDemo.java` finds main) ----------
public class ElevatorDemo {
public static void main(String[] args) throws Exception {
ElevatorController c = new ElevatorController(3, 10, new DirectionAwareNearest());
c.car(1).moveTo(5); c.car(2).moveTo(9); // start positions: A at 0, B at 5, C at 9
Elevator chosen = c.hallCall(4, Direction.DOWN); // someone on floor 4 wants to go down
System.out.println("hall call 4 DOWN -> car " + chosen.name);
c.runUntilIdle(true);
chosen.pressFloor(0); // passenger gets in, presses 0
c.runUntilIdle(true);
// One car, mixed calls: going up from 2 with car calls 4 and 7, and a hall call DOWN at 3
ElevatorController one = new ElevatorController(1, 10, new DirectionAwareNearest());
Elevator a = one.car(0);
a.moveTo(2); a.pressFloor(4); a.pressFloor(7);
one.hallCall(3, Direction.DOWN);
one.hallCall(5, Direction.UP);
one.runUntilIdle(true); // LOOK: up 4, 5, 7, then down to 3
// Concurrency: 8 threads press 50 random buttons each while the cars run
ElevatorController busy = new ElevatorController(3, 20, new DirectionAwareNearest());
ExecutorService pool = Executors.newFixedThreadPool(8);
List<Future<?>> fs = new ArrayList<>();
for (int t = 0; t < 8; t++) {
final long seed = t;
fs.add(pool.submit(() -> {
Random r = new Random(seed);
for (int i = 0; i < 50; i++) {
int f = 1 + r.nextInt(18);
busy.hallCall(f, r.nextBoolean() ? Direction.UP : Direction.DOWN);
busy.tick();
}
}));
}
for (Future<?> f : fs) f.get();
pool.shutdown();
busy.runUntilIdle(false); // throws if any stop is never served
System.out.println("400 calls from 8 threads: every stop served");
}
}
// ---------- Values ----------
enum Direction { UP, DOWN, IDLE }
// ---------- One car ----------
final class Elevator {
final String name; final int topFloor;
private int floor = 0;
private Direction dir = Direction.IDLE;
private final TreeSet<Integer> upStops = new TreeSet<>(); // stop here while going up
private final TreeSet<Integer> downStops = new TreeSet<>(); // stop here while going down
Elevator(String name, int topFloor) { this.name = name; this.topFloor = topFloor; }
synchronized int floor() { return floor; }
synchronized Direction direction() { return dir; }
synchronized boolean idle() { return upStops.isEmpty() && downStops.isEmpty(); }
synchronized void moveTo(int f) { floor = f; } // test setup only
/** Button inside the car: the direction follows from where the car is now. */
synchronized void pressFloor(int f) {
check(f);
if (f > floor) upStops.add(f);
else if (f < floor) downStops.add(f);
else (dir == Direction.DOWN ? downStops : upStops).add(f); // same floor: reopen doors
}
/** A hall call assigned to this car by the controller. */
synchronized void assign(int f, Direction wanted) {
check(f);
(wanted == Direction.UP ? upStops : downStops).add(f);
}
/** One tick: open doors here, or move one floor. LOOK: turn round only when nothing is ahead. */
synchronized String step() {
if (idle()) { dir = Direction.IDLE; return null; }
if (dir == Direction.IDLE) dir = nearestStop() >= floor ? Direction.UP : Direction.DOWN;
if (serveHere()) return name + " opens at " + floor + " (" + dir + ")";
if (!anythingAhead(dir)) {
dir = (dir == Direction.UP) ? Direction.DOWN : Direction.UP;
if (serveHere()) return name + " opens at " + floor + " (" + dir + ")";
}
floor += (dir == Direction.UP) ? 1 : -1;
return null;
}
/** Rough time to reach floor f, used by dispatch. Counts floors travelled, plus 1 per stop on the way. */
synchronized int costTo(int f, Direction wanted) {
if (idle()) return Math.abs(floor - f);
boolean ahead = dir == Direction.UP ? f >= floor : f <= floor;
if (ahead && dir == wanted) return Math.abs(floor - f) + stopsBetween(floor, f);
int end = dir == Direction.UP ? Math.max(maxStop(), floor) : Math.min(minStop(), floor);
return Math.abs(floor - end) + Math.abs(end - f) + upStops.size() + downStops.size();
}
private boolean serveHere() { return (dir == Direction.UP ? upStops : downStops).remove(floor); }
private boolean anythingAhead(Direction d) {
return d == Direction.UP ? upStops.higher(floor) != null || downStops.higher(floor) != null
: upStops.lower(floor) != null || downStops.lower(floor) != null;
}
private int nearestStop() {
int best = -1;
for (TreeSet<Integer> s : List.of(upStops, downStops))
for (int f : s) if (best < 0 || Math.abs(f - floor) < Math.abs(best - floor)) best = f;
return best;
}
private int maxStop() { return Math.max(upStops.isEmpty() ? 0 : upStops.last(), downStops.isEmpty() ? 0 : downStops.last()); }
private int minStop() { return Math.min(upStops.isEmpty() ? topFloor : upStops.first(), downStops.isEmpty() ? topFloor : downStops.first()); }
private int stopsBetween(int a, int b) {
TreeSet<Integer> s = dir == Direction.UP ? upStops : downStops;
return s.subSet(Math.min(a, b), false, Math.max(a, b), false).size();
}
private void check(int f) { if (f < 0 || f > topFloor) throw new IllegalArgumentException("no floor " + f); }
}
// ---------- What varies: which car answers a hall call ----------
interface DispatchStrategy {
Elevator choose(List<Elevator> cars, int floor, Direction wanted);
}
/** Cheapest car: idle cars by distance; moving cars only cheap if already heading there the right way. */
final class DirectionAwareNearest implements DispatchStrategy {
public Elevator choose(List<Elevator> cars, int floor, Direction wanted) {
Elevator best = null; int bestCost = Integer.MAX_VALUE;
for (Elevator e : cars) {
int cost = e.costTo(floor, wanted);
if (cost < bestCost) { best = e; bestCost = cost; }
}
return best;
}
}
// ---------- The controller ----------
final class ElevatorController {
private final List<Elevator> cars = new ArrayList<>();
private volatile DispatchStrategy strategy;
ElevatorController(int count, int floors, DispatchStrategy strategy) {
for (int i = 0; i < count; i++) cars.add(new Elevator(String.valueOf((char) ('A' + i)), floors - 1));
this.strategy = strategy;
}
Elevator car(int i) { return cars.get(i); }
void setStrategy(DispatchStrategy s) { strategy = s; }
/** Called from any thread when a hall button is pressed. */
Elevator hallCall(int floor, Direction wanted) {
Elevator e = strategy.choose(cars, floor, wanted); // reads a snapshot; a slightly stale one is fine
e.assign(floor, wanted);
return e;
}
/** In a real building each car runs its own loop; here one tick advances every car. */
void tick(boolean log) {
for (Elevator e : cars) { String event = e.step(); if (log && event != null) System.out.println(" " + event); }
}
void tick() { tick(false); }
int runUntilIdle(boolean log) {
int n = 0;
while (cars.stream().anyMatch(e -> !e.idle())) {
tick(log);
if (++n > 10_000) throw new IllegalStateException("cars never went idle");
}
return n;
}
}import random
import threading
from abc import ABC, abstractmethod
from concurrent.futures import ThreadPoolExecutor
from enum import Enum
class Direction(Enum):
UP = "UP"
DOWN = "DOWN"
IDLE = "IDLE"
# ---------- One car ----------
class Elevator:
def __init__(self, name: str, top_floor: int):
self.name, self.top_floor = name, top_floor
self.floor = 0
self.dir = Direction.IDLE
self.up_stops: set[int] = set() # stop here while going up
self.down_stops: set[int] = set() # stop here while going down
self._lock = threading.RLock() # buttons and the car's own loop run on different threads
def idle(self) -> bool:
with self._lock:
return not self.up_stops and not self.down_stops
def press_floor(self, f: int):
"""Button inside the car: the direction follows from where the car is now."""
self._check(f)
with self._lock:
if f > self.floor:
self.up_stops.add(f)
elif f < self.floor:
self.down_stops.add(f)
else: # same floor: reopen doors
(self.down_stops if self.dir == Direction.DOWN else self.up_stops).add(f)
def assign(self, f: int, wanted: Direction):
"""A hall call assigned to this car by the controller."""
self._check(f)
with self._lock:
(self.up_stops if wanted == Direction.UP else self.down_stops).add(f)
def step(self):
"""One tick: open doors here, or move one floor. LOOK: turn round only when nothing is ahead."""
with self._lock:
if self.idle():
self.dir = Direction.IDLE
return None
if self.dir == Direction.IDLE:
self.dir = Direction.UP if self._nearest_stop() >= self.floor else Direction.DOWN
if self._serve_here():
return f"{self.name} opens at {self.floor} ({self.dir.value})"
if not self._anything_ahead(self.dir):
self.dir = Direction.DOWN if self.dir == Direction.UP else Direction.UP
if self._serve_here():
return f"{self.name} opens at {self.floor} ({self.dir.value})"
self.floor += 1 if self.dir == Direction.UP else -1
return None
def cost_to(self, f: int, wanted: Direction) -> int:
"""Rough time to reach floor f: floors travelled, plus 1 per stop on the way."""
with self._lock:
if self.idle():
return abs(self.floor - f)
ahead = f >= self.floor if self.dir == Direction.UP else f <= self.floor
stops = self.up_stops | self.down_stops
if ahead and self.dir == wanted:
lo, hi = sorted((self.floor, f))
same = self.up_stops if self.dir == Direction.UP else self.down_stops
return abs(self.floor - f) + sum(1 for s in same if lo < s < hi)
end = max(max(stops), self.floor) if self.dir == Direction.UP else min(min(stops), self.floor)
return abs(self.floor - end) + abs(end - f) + len(self.up_stops) + len(self.down_stops)
def _serve_here(self) -> bool:
stops = self.up_stops if self.dir == Direction.UP else self.down_stops
if self.floor in stops:
stops.remove(self.floor)
return True
return False
def _anything_ahead(self, d: Direction) -> bool:
stops = self.up_stops | self.down_stops
if d == Direction.UP:
return any(s > self.floor for s in stops)
return any(s < self.floor for s in stops)
def _nearest_stop(self) -> int:
return min(self.up_stops | self.down_stops, key=lambda s: abs(s - self.floor))
def _check(self, f):
if not 0 <= f <= self.top_floor:
raise ValueError(f"no floor {f}")
# ---------- What varies: which car answers a hall call ----------
class DispatchStrategy(ABC):
@abstractmethod
def choose(self, cars: list, floor: int, wanted: Direction) -> Elevator: ...
class DirectionAwareNearest(DispatchStrategy):
"""Cheapest car: idle cars by distance; moving cars only cheap if already heading there the right way."""
def choose(self, cars, floor, wanted):
return min(cars, key=lambda e: e.cost_to(floor, wanted))
# ---------- The controller ----------
class ElevatorController:
def __init__(self, count: int, floors: int, strategy: DispatchStrategy):
self.cars = [Elevator(chr(ord("A") + i), floors - 1) for i in range(count)]
self.strategy = strategy
def hall_call(self, floor: int, wanted: Direction) -> Elevator:
"""Called from any thread when a hall button is pressed."""
car = self.strategy.choose(self.cars, floor, wanted) # a slightly stale snapshot is fine
car.assign(floor, wanted)
return car
def tick(self, log=False):
"""In a real building each car runs its own loop; here one tick advances every car."""
for car in self.cars:
event = car.step()
if log and event:
print(" " + event)
def run_until_idle(self, log=False) -> int:
n = 0
while any(not c.idle() for c in self.cars):
self.tick(log)
n += 1
if n > 10_000:
raise RuntimeError("cars never went idle")
return n
# ---------- Demo ----------
if __name__ == "__main__":
c = ElevatorController(3, 10, DirectionAwareNearest())
c.cars[1].floor, c.cars[2].floor = 5, 9 # A at 0, B at 5, C at 9
chosen = c.hall_call(4, Direction.DOWN) # someone on floor 4 wants to go down
print("hall call 4 DOWN -> car", chosen.name)
c.run_until_idle(log=True)
chosen.press_floor(0) # passenger gets in, presses 0
c.run_until_idle(log=True)
# One car, mixed calls: going up from 2 with car calls 4 and 7, and hall calls 3 DOWN, 5 UP
one = ElevatorController(1, 10, DirectionAwareNearest())
a = one.cars[0]
a.floor = 2
a.press_floor(4); a.press_floor(7)
one.hall_call(3, Direction.DOWN)
one.hall_call(5, Direction.UP)
one.run_until_idle(log=True) # LOOK: up 4, 5, 7, then down to 3
# Concurrency: 8 threads press 50 random hall buttons each while the cars run
busy = ElevatorController(3, 20, DirectionAwareNearest())
def presser(seed):
r = random.Random(seed)
for _ in range(50):
busy.hall_call(r.randint(1, 18), r.choice([Direction.UP, Direction.DOWN]))
busy.tick()
with ThreadPoolExecutor(max_workers=8) as pool:
list(pool.map(presser, range(8)))
busy.run_until_idle() # raises if any stop is never served
print("400 calls from 8 threads: every stop served")Both print:
hall call 4 DOWN -> car B
B opens at 4 (DOWN)
B opens at 0 (DOWN)
A opens at 4 (UP)
A opens at 5 (UP)
A opens at 7 (UP)
A opens at 3 (DOWN)
400 calls from 8 threads: every stop served
In the first scenario car B is idle at floor 5, one floor away, so it wins over A (at 0) and C (at 9). In the second, car A is at floor 2 going up with car calls 4 and 7, a hall call for UP at 5 and one for DOWN at 3. It doesn't stop at 3 on the way up, because that caller wants to go down; it serves 4, 5 and 7, turns, and collects the floor-3 caller on the way down.
7. Concurrency
Buttons are pressed on many threads, and each car runs its own loop. The races:
| Race | What goes wrong | Fix in the code above |
|---|---|---|
A button press while the car is mid-step() | A stop is added to a set being read; TreeSet and Python set are not thread-safe, so the set can be corrupted or the stop lost | Every method on Elevator is synchronized (an RLock in Python): one car's state changes one call at a time |
| Dispatch reads car positions that change immediately after | The chosen car has moved one floor; the cost estimate is slightly stale | Accepted on purpose: dispatch is a heuristic, and LOOK still serves the stop. Never hold every car's lock while choosing |
| Two people press the same hall button | Two assignments | The stop sets are sets, so a duplicate is ignored; a real controller also lights the button once |
| Controller locks car A then car B, while another thread locks B then A | Deadlock | The controller never holds two car locks at once: costTo locks and releases each car in turn |
Two standard structures, worth naming:
- Lock per car (used here): simple, and cars never block each other.
- Command queue per car: buttons put commands on a
BlockingQueue(Java) orqueue.Queue(Python), and the car's loop is the only thread that touches its state. No locks on the car's fields at all; this is the actor style many real controllers use.
8. Extensions the interviewer will ask for
- Maintenance mode: an
outOfServiceflag (or state) that makescostToreturn infinity, so dispatch never picks the car; its assigned hall calls are reassigned. - Destination dispatch:
hallCall(floor, destination); the strategy groups passengers going to nearby floors into the same car. - VIP or freight priority: a priority on requests and a strategy that serves priority calls first, with a cap so others aren't starved.
- Display panels: Observer: each car publishes floor and direction changes; hall displays and the building-management screen subscribe.
- Express zones: a
servedFloorsset per car, checked by the strategy and bypressFloor(a button for an unserved floor is not lit).
When not to over-design
- One car, a few floors: skip the dispatch strategy entirely; the controller is the car.
- If the interviewer cares about scheduling, spend time on LOOK, the direction-aware sets and fairness, and keep dispatch to one sentence.
- Don't model motors, acceleration or door timing unless asked; a tick that moves one floor is the right level of detail.
In the interview
A candidate's car keeps one sorted set of stops and this step(). Find at least three problems.
void step() {
if (stops.isEmpty()) return;
int target = stops.first(); // lowest requested floor
if (floor == target) { stops.remove(target); openDoors(); return; }
floor += (target > floor) ? 1 : -1;
}Compare with our answer
The problems: (1) it always heads for the lowest stop, so a car at floor 8 with stops 9 and 1 goes down to 1 first, then back up to 9; with new low requests arriving, floor 9 can wait for ever (starvation). (2) It ignores direction: it opens at floors it is merely passing only if they happen to be the lowest, and it can't tell an UP hall call from a DOWN one. (3) The direction field is never updated, so dispatch can't estimate cost. (4) Nothing is synchronised, and a TreeSet modified by a button thread during step() is a data race.
synchronized String step() {
if (idle()) { dir = Direction.IDLE; return null; }
if (dir == Direction.IDLE) dir = nearestStop() >= floor ? Direction.UP : Direction.DOWN;
if (serveHere()) return name + " opens at " + floor; // stop set for the current direction
if (!anythingAhead(dir)) { // LOOK: turn only when nothing is ahead
dir = (dir == Direction.UP) ? Direction.DOWN : Direction.UP;
if (serveHere()) return name + " opens at " + floor;
}
floor += (dir == Direction.UP) ? 1 : -1;
return null;
}def step(self):
with self._lock:
if self.idle():
self.dir = Direction.IDLE
return None
if self.dir == Direction.IDLE:
self.dir = Direction.UP if self._nearest_stop() >= self.floor else Direction.DOWN
if self._serve_here(): # stop set for the current direction
return f"{self.name} opens at {self.floor}"
if not self._anything_ahead(self.dir): # LOOK: turn only when nothing is ahead
self.dir = Direction.DOWN if self.dir == Direction.UP else Direction.UP
if self._serve_here():
return f"{self.name} opens at {self.floor}"
self.floor += 1 if self.dir == Direction.UP else -1
return NoneA strong answer mentions: lowest-first is not an elevator algorithm and can starve floors · keep a direction and continue while stops remain ahead (LOOK) · separate up and down stops for hall-call direction · the direction is needed by dispatch · locking the car's state against button threads.
The building owner adds a rule: between 8:00 and 9:30, at least one idle car must always wait at the lobby, and cars C and D should only answer calls above floor 10. What changes, and what stays the same?
Compare with our answer
A strong answer mentions:
- A new dispatch strategy (
MorningRush) that applies the zoning rule (C and D only for floors above 10, plus the lobby) and otherwise delegates toDirectionAwareNearest. - A scheduler that swaps the strategy at 8:00 and 9:30 (or a
TimeOfDayStrategythat picks per call, given the time). - Lobby parking: when a car goes idle and no car is at or heading to the lobby, the controller assigns it a stop at floor 0. That's a controller policy run on each tick, not part of LOOK.
Elevatorand its LOOK logic don't change; nor does the button code.- Testing it with a simulated clock: a scenario at 8:15 checks C never takes floor 4, and that a car returns to the lobby.
- Two decisions: which car (a
DispatchStrategy) and the order of stops (LOOK, inside each car). - Buttons: hall call = (floor, direction), assigned by the controller; car call = floor, for that car.
- Stops: separate
upStopsanddownStops; stop only for callers going your way. - LOOK: serve what's ahead, turn when nothing is; bounded wait. SSTF can starve; FCFS zig-zags; SCAN goes to the end needlessly.
- Dispatch cost: idle → distance; heading there the right way → distance + stops between; otherwise via the end of the sweep.
- Time as ticks for deterministic tests; each car's loop calls
step(). - Concurrency: lock per car (or a command queue per car); dispatch reads a slightly stale snapshot; never hold two car locks.
- Real-world: reassign calls from broken cars, re-dispatch, capacity, emergency mode, morning-rush lobby parking and zoning.
1. Car A is idle at floor 9. Car B is at floor 6 moving up to floor 12. A hall call arrives: floor 4, going DOWN. With the direction-aware cost rule, which car should be sent?
B's cost is (12 − 6) + (12 − 4) plus its stops = at least 14, while idle A's is 9 − 4 = 5. Raw distance picks B and makes the caller wait much longer.
2. Why do production elevators use a SCAN or LOOK style algorithm instead of always going to the nearest requested floor?
Shortest-seek-first is greedy and unfair: a stream of nearby requests can keep the car away from floor 30 indefinitely. LOOK bounds the wait to about two sweeps; it does not always minimise distance.
3. A car going up from floor 2 has a hall call at floor 5 for DOWN, and a car call for floor 8. What should happen at floor 5 on the way up?
The caller wants to go down. Stopping on the way up would take them to floor 8 first. Separate up and down stop sets let the car pick them up on the downward sweep.
4. Buttons are pressed on several threads while each car's loop calls step(). The controller's hallCall computes a cost for every car, then assigns the call. Which locking approach is safest?
Holding several car locks risks deadlock and stalls every car during dispatch. The cost read is allowed to be slightly stale. Unlocked access is a data race, since button threads add stops; a controller lock doesn't cover the cars' own loops.
5. Car C breaks down and is switched to maintenance while three hall calls are assigned to it. What should the design do?
The controller must track unserved hall calls and re-dispatch them using the normal strategy. Waiting for a repair or expecting people to press again leaves them stranded; ignoring position makes waits long.
6. During the morning rush all four cars end up on upper floors and the lobby queue grows. Which change fits the design best?
Where idle cars wait is a dispatch policy that changes by time of day, so it belongs in a swappable strategy or controller policy. Changing LOOK in every car mixes policy into the per-car algorithm.
7. Why does the design advance time in ticks instead of using Thread.sleep and the wall clock inside Elevator?
A simulated clock makes the behaviour repeatable and fast to test. In production, each car's loop calls step() on a timer, and the logic stays the same.
Score 60% or more and the lesson is marked complete.