08 — Elevator System — Object-Oriented Design

“Design an elevator control system for a 20-floor building.”

This problem has two halves, and only one of them decides the round.

The first half is the object model: the set of classes and the relationships between them. The objects here are the easiest in the whole track. A building has cars, a car has a position and a door, a floor has two buttons. You can draw the entire object model in four minutes, and if that is all you do you fail the round.

The second half is the scheduler — the rule that picks what order one car serves its waiting passengers in. That is what the interview is actually about. A candidate who names the algorithm and then computes what it saves against the naive one is doing the thing the round is for.

By the end of this chapter you will be able to:

name the scheduling rule (it is called LOOK) and say in one sentence what it does;
work a five-call example by hand showing that LOOK travels 24 floors where the naive rule travels 58;
prove out loud that nobody waits forever under LOOK, and name the one implementation detail that proof depends on;
say precisely which of your classes exist because you expect them to change.

What goes in, and what comes out

Fix the shape of the problem before drawing a single class. The system takes exactly two kinds of request and produces exactly two kinds of answer.

The sketch below is the whole input/output contract. Read the two IN lines as the buttons a person can press, and the two OUT lines as the two separate decisions the system has to make.

IN   a hall call    someone at floor 15 pressing the DOWN button
                    -> HallCall(floor=15, direction=Direction.DOWN)
IN   a car call     someone inside car 1 pressing "6"
                    -> CarCall(floor=6)

OUT  an assignment  which car answers a given hall call
                    -> car #2
OUT  a stop order   the sequence of floors one car visits, and its cost
                    -> [3, 6, 18, 15, 11], costing 24 floors of travel

Those two outputs are produced by two different objects, and they are two different decisions.

Choosing which car answers a hall call is the dispatcher’s job. It is a policy, and policies change.

Choosing what order one car serves the calls it already holds is the car’s job. It is an algorithm, and this one does not change.

Keeping those two decisions in separate objects is the single structural choice this design rests on. Decision 3 dispatch is a strategy is where it gets defended.

Three links, offered for depth and not needed to follow this chapter. The interview method — how to spend the 45 minutes — is 02 — the object-oriented design (OOD) framework. The pattern vocabulary is 03 — object-oriented programming (OOP) fundamentals. Three patterns show up here, and each is defined again where it arrives:

Strategy — a policy in its own object, swappable without editing the caller.
State — one named situation an object can be in, together with the rules that apply while it is there.
Command — a request turned into an object you can queue, log and replay.

The next chapter, 09 — Grocery Store, is where the Strategy argument returns in its most common industrial form.

1. Clarifying questions that change the design

Ask these four. Each one flips a class in or out of the model, which is why they come before the diagram rather than after it.

Question	If yes	If no
One car or a bank?	You need a `Dispatcher` and a dispatch policy — the real problem	A single car’s queue, half the design
Destination-dispatch lobby, or up/down buttons?	Passengers declare a floor before boarding; you can group by destination, and hall calls carry a target	Hall calls carry only a direction, and the car cannot know load until the doors close
Are cars homogeneous?	One policy	Express cars, freight cars, capacity limits -> the policy must be able to refuse a car
What is being optimized?	Total travel, mean wait, and p99 wait are three different objectives that pick three different policies (Decision 3 dispatch is a strategy, and the fairness extension in Now optimize for wait time fairness instead of total travel)	If nobody says, say “mean wait, with a bounded worst case” and move on

Three terms in that table need unpacking.

Destination dispatch is the lobby arrangement where you key in your floor at a panel outside the elevators and a screen tells you which car to board, instead of pressing a plain up or down button. The controller therefore knows your destination before you are inside the car.

Mean wait is the average time a passenger stands in the hallway.

p99 wait is the 99th percentile of that same wait: the number that 99 out of 100 passengers come in under. Another way to say it is “how bad it gets for the unluckiest one percent”.

Mean wait and p99 wait genuinely conflict as objectives. A policy that improves one usually worsens the other, which is why “what is being optimized?” is a question and not a formality.

The one that changes the most is the second. Up/down buttons is the classic version and the harder scheduling problem, because the controller has strictly less information. Assume it unless told otherwise.

2. Actors and use cases

Five parties send events into this system, and the last two exist to remind you that a passenger is not the only source of input.

Actor	Action	What it produces
Passenger, in the hallway	presses UP or DOWN at floor `f`	a hall call
Passenger, inside a car	presses a destination floor	a car call
Passenger, at the doors	blocks the door, or presses open	a door state change
Maintenance technician	takes car 3 out of service	the extension in Now add a service mode that removes a car from dispatch
Fire panel	recalls every car to the lobby	a priority override

Two terms from that table carry the rest of the chapter.

A hall call is a request from outside a car: someone at a floor wanting to travel in a direction. A car call is a request from inside a car: someone already aboard wanting off at a floor.

Two request kinds, and they are not the same type. That is the first real design decision, and Decision 2 the request model and command is where it is argued.

The fire panel is worth noticing now even though the design does not build it. A recall is not a request that joins the queue; it cancels everything and drives every car to the lobby regardless of what it was doing. That is a mode, not an event, and What this class structure assumes explains why a flat set of states cannot express one cleanly.

3. Core objects, and why those

Five objects carry this design, and for each one the interesting content is not what it does but which tempting alternative it beats — the third column below is what you say out loud in the round.

Object	Responsibility	Why not the obvious alternative
`HallCall(floor, direction)`	A person waiting at a floor wanting to go a direction	The obvious model is one `Request(floor)`. It loses the direction, and direction is exactly what LOOK needs to decide whether a passing car should stop
`CarCall(floor)`	A person inside a car wanting off	Has no direction — it is implied by where the car already is
`ElevatorCar`	Position, motion, door, its own pending set	Not “Elevator + Controller + Motor” — the motor is not a domain object, it is a driver
`Dispatcher`	Assigns a hall call to a car	The alternative is “each car decides for itself”, which is a distributed-consensus problem for zero benefit
`DispatchStrategy`	The policy, swappable	Decision 3 dispatch is a strategy

The phrase distributed consensus in row four means several independent parties having to agree on one answer with no central authority, over a channel where messages can be delayed or lost — a famously hard problem, and there is nothing to gain from creating one inside a building where a single controller can simply decide.

A Floor class with a list of waiting passengers is the classic over-model. A floor has no behaviour. It is an integer plus, at most, two booleans for the lit up and down buttons.

Keep the floor as an int and track those two booleans in the dispatcher’s set of unanswered hall calls. (This chapter’s code does not build that set — see the concurrency row in What interviewers probe — but that is where it belongs.) If an interviewer wants a Floor object, adding it later touches one file.

4. Class diagram

The model fits in one diagram, but the arrowheads carry claims the boxes do not, so each line deserves to be read back as an English sentence.

Two things in the diagram are model-only and are not in the running code of Working python — the Building class and Dispatcher.step(). Section 8 implements the requests, one car’s sweep, Dispatcher.assign and the strategies, and stops there.

classDiagram
    class Building {
        +int floors
        +request(call)
    }
    class Dispatcher {
        +assign(HallCall) ElevatorCar
        +step()
    }
    class ElevatorCar {
        +int id
        +int position
        +Direction heading
        +DoorState door
        +accept(Request)
        +peek_next_stop() int
        +advance_to_next_stop() int
    }
    class Request {
        +int floor
    }
    class HallCall {
        +Direction direction
    }
    class CarCall
    class DispatchStrategy {
        <<interface>>
        +choose(cars, call) ElevatorCar
    }
    class NearestCarStrategy
    class LookCostStrategy
    class FairnessStrategy

    Building "1" *-- "1..*" ElevatorCar : owns lifetime
    Building "1" *-- "1" Dispatcher
    Dispatcher "1" o-- "1..*" ElevatorCar : schedules, does not own
    Dispatcher "1" --> "1" DispatchStrategy : delegates policy
    ElevatorCar "1" o-- "0..*" Request : pending
    Request <|-- HallCall
    Request <|-- CarCall
    DispatchStrategy <|.. NearestCarStrategy
    DispatchStrategy <|.. LookCostStrategy
    DispatchStrategy .. FairnessStrategy : wants to, but widens choose()

Reading the notation

This is a UML class diagram. UML is the Unified Modeling Language, the standard set of shapes for drawing software structure.

Each box is a class. The lines inside a box are its fields and methods, and a leading + means public. <<interface>> marks a class that is only a promise of methods, with no implementation of its own.

The quoted numbers at the ends of a line are multiplicities: how many objects sit at that end. 1 is exactly one, 1..* is one or more, 0..* is any number including none.

Six line styles appear, and they mean six different things:

*--, a filled diamond, is composition: the owner controls the part’s lifetime, and destroying the owner destroys the part.
o--, a hollow diamond, is aggregation: a “has a” that does not control lifetime, so the part can outlive the whole or be shared.
-->, a plain open arrow, is association: the class at the tail holds a reference to the class at the head, and that is all it claims.
<|--, a solid line with a hollow triangle, is inheritance: the class at the tail is a kind of the class at the head.
<|.., the same triangle on a dashed line, is realization: the class at the tail implements the interface at the head without inheriting any code from it.
.., a dashed line with no arrowhead at all, is a plain link: these two classes are related and the label says how. It is used here for exactly one thing an interface arrow would misstate.

Reading the lines back as sentences

Every line in the diagram is a claim. Here is each one in English.

Building *-- ElevatorCar, labelled owns lifetime: a building composes one or more cars. Demolish the building and the cars go with it.
Building *-- Dispatcher: a building likewise composes exactly one dispatcher.
Dispatcher o-- ElevatorCar, labelled schedules, does not own: the dispatcher aggregates those same cars, so replacing the dispatcher leaves every car running.
Dispatcher --> DispatchStrategy, labelled delegates policy: the dispatcher holds a reference to exactly one strategy. A plain association arrow, because it merely uses something it did not create.
ElevatorCar o-- Request, labelled pending: each car aggregates any number of requests as its outstanding work.
Request <|-- HallCall and Request <|-- CarCall: both call kinds are kinds of Request. That is the claim that a car can hold either one in the same pending set.
DispatchStrategy <|.. NearestCarStrategy and <|.. LookCostStrategy: each realizes the interface. That is the claim that the dispatcher can hold either one and never know which.
DispatchStrategy .. FairnessStrategy: a plain link, not a realization, and the label says why. It does the same job, but its choose takes an extra argument, so it does not satisfy the interface. Drawing a realization arrow there would be a diagram that lies about a class the chapter itself admits does not fit. The honest repair is in Now optimize for wait time fairness instead of total travel.

Note the two different arrows into ElevatorCar. The building composes its cars; the dispatcher aggregates them. Getting that pair backwards is the diagram mistake interviewers actually comment on, because it says the wrong thing about what happens when you swap a controller.

What this class structure assumes

A class diagram is a frozen bet about what will change. Every interface you draw says “I expect this to vary”. Every field you hard-code says “I expect this to hold forever”.

Naming those bets out loud is the transferable skill. The specific elevator is not going to be your job; the habit of stating your own assumptions is. The general form of the argument is What a class structure assumes, and what follows is this design’s version.

Assumed to vary — and therefore given an interface or a parameter. The third column is the one to read closely: it is the cost of having bet wrong, which is what makes each row a decision rather than a habit.

What varies	How the design absorbs it	What it would cost to have got this wrong
Which car answers a hall call	`DispatchStrategy`, an interface with one method	A `switch` inside `Dispatcher`, edited for every new policy
Which floors a car is allowed to serve	A `serves` set on the car, consulted by `can_serve`	Express cars become a special case inside every strategy
Whether a car is available at all	An `in_service` flag, consulted by the same predicate	A separate list of active cars, which drifts from reality
The number of cars and the number of floors	Constructor arguments	A twenty-floor constant compiled into the scheduler
The objective being optimised	Which strategy you install	Mean wait and worst-case wait cannot both be tuned

Assumed fixed — and therefore baked into the structure rather than into a parameter:

The largest one is deliberate and worth stating before an interviewer finds it: the per-car stop ordering is not swappable. LOOK is written directly into ElevatorCar.advance_to_next_stop, while dispatch is an interface.

That asymmetry is a claim — that dispatch policy is what a building owner argues about, and sweep order is settled engineering. It is the right bet. But it is a bet, and if it were wrong the fix is a second Strategy interface on the car.

Underneath that sit five smaller fixed bets:

One dispatcher, and it is the sole authority. Cars never negotiate with each other.
A call is assigned to exactly one car the moment it arrives, and never reassigned. That is why the pending set lives on the car and not on the dispatcher.
A car’s plan is a set of floors, not a timed schedule. Door dwell time, acceleration and passenger loading do not exist in the model.
Position is an integer floor, not a continuous height.
Every car runs in its own shaft, so two cars can never collide.

What a state machine assumes, since the car is one. A state machine is an object that is always in exactly one of a fixed set of named situations, with defined rules for moving between them. A car is described in Working python as a small one, moving between IDLE, MOVING and DOORS_OPEN.

Every state machine rests on two assumptions. Both are worth saying out loud here, because this design quietly violates them.

Assumption 1: the set of states is closed and known at design time. Naming three states claims a car is never in a fourth. It is: doors obstructed, releveling at a floor, emergency stop, and — from Actors and use cases — fire recall.

Fire recall is the instructive one, because it is not reachable by any normal event from any normal state. It preempts whatever the car was doing. A flat set of states cannot express “drop everything and do this instead” without adding an edge from every state to the new one.

The honest structures are therefore either a hierarchical state machine, where a high-priority parent mode overrides its children, or a separate mode flag consulted before the state machine runs at all. What breaks if you ignore it: the recall arrives while the car is in DOORS_OPEN, no transition is defined, and the car finishes its trip during a fire.

Assumption 2: transitions are total — every combination of state and event has a defined outcome, none left undefined.

This design does not achieve that, and pretending otherwise would be the lie. advance_to_next_stop() and arrive() never inspect the car’s state at all. arrive sets the door to OPEN unconditionally, nothing ever closes it, and door is written but never read.

The code in Working python is a scheduler, not a door controller. That is a scope decision rather than an oversight — but you should be the one to say so. The contrast with a machine that gets this right is 07 — Vending Machine, where every undefined combination inherits an explicit refusal instead of quietly doing something.

What a different assumption would have produced. Four rewrites of the problem statement, and what each one does to the class model.

If the lobby used destination dispatch, HallCall and CarCall collapse into one request type carrying an origin and a destination, the direction filter that LOOK depends on becomes unnecessary, and the dispatcher can group passengers going to the same floor into the same car — a different and easier optimisation problem.
If assignments could be revoked, the pending set could not live on the car, because the dispatcher would need to move calls between cars as conditions change. Ownership of every unserved call would migrate to the dispatcher and each car would be handed only its next stop. That is what real high-traffic controllers do, and it costs you the clean per-car queue that makes this design testable.
If two cars shared one shaft — which exists, in tall buildings — the independence assumption dies completely. Each car’s plan constrains its neighbour’s, cars can deadlock by needing to pass each other, and per-car LOOK is no longer even well defined.
If the objective were p99 wait rather than total travel, LookCostStrategy is the wrong default and the fairness policy in Now optimize for wait time fairness instead of total travel is the right one. Same classes, different installed policy — which is the return on having made dispatch an interface.

5. Decision 1 — LOOK, not FCFS, and here is the number

The scheduling rule deserves a name and a number: name the algorithm, work one concrete burst of calls through both it and the naive alternative, and the number that justifies the choice falls out.

The two rules

FCFS, first-come first-served, is the naive rule: serve requests in the order they were pressed.

LOOK is the good rule. The car sweeps in one direction as far as the furthest request that way, serving everything on the path, then reverses and does the same going back.

It is called LOOK because before reversing, the car looks ahead to see whether anything is still pending in the current direction. Contrast SCAN, its cruder relative, which always runs to the physical top or bottom of the building before turning around and therefore wastes the empty end of every sweep. Both names come from disk-drive head scheduling, where the identical problem is ordering reads across a spinning platter.

Working one burst by hand

Take a 20-floor building, one car parked at floor 1, and a burst of five hall calls arriving in this order:

#1  floor 15  DOWN
#2  floor  3  UP
#3  floor 18  UP
#4  floor  6  UP
#5  floor 11  DOWN

FCFS serves them in arrival order. The path is 1 -> 15 -> 3 -> 18 -> 6 -> 11, and its cost is the sum of the distances between consecutive stops:

|15 -  1|   = 14
| 3 - 15|   = 12
|18 -  3|   = 15
| 6 - 18|   = 12
|11 -  6|   = 5
14 + 12 + 15 + 12 + 5    = 58

LOOK sweeps up as far as the highest pending request, serving every UP call on the way, then reverses and serves the DOWN calls descending. Path 1 -> 3 -> 6 -> 18 -> 15 -> 11. Because the path never doubles back, its cost is just the length of the two sweeps:

up-sweep    18 - 1     = 17
down-sweep  18 - 11    = 7
17 + 7                 = 24

Comparing the two:

58 - 24        = 34
34 / 58        = 0.586

58 floors versus 24 — the same five passengers, 59% less travel, from nothing but service order. Say that number out loud; it is the whole reason the algorithm exists.

Why the gap widens with load

One example is an anecdote. It becomes a rule once you ask what each policy costs per request as the building gets busier.

FCFS travel per request does not depend on how many requests are pending, because it always flies from wherever it is to wherever the next-pressed button happens to be. If two floors are drawn independently and uniformly at random from 1..n — uniformly meaning every floor is equally likely — then the expected distance between them is the following. The notation E|X - Y| reads “the expected, or long-run average, value of the absolute distance between two random floors X and Y”:

E|X - Y| = (n^2 - 1) / (3n)
(400 - 1) / 60    = 6.65

So FCFS costs 6.65 floors per request, forever. A full LOOK sweep costs 2(n-1) floors — up the building and back down — and serves every pending request in one pass:

2 x 19    = 38

With m requests pending, LOOK costs 38 / m per request. The two policies break even where those per-request costs meet:

38 / 6.65    = 5.71

Above about 6 concurrent requests LOOK wins, and its per-request cost keeps falling while FCFS’s stays flat. The busier the building, the worse FCFS is — which is precisely the regime you built an elevator for.

One honesty note on that crossover. The comparison is deliberately unfair to LOOK: 6.65 is FCFS’s expected cost, while 38 is LOOK’s worst case, since a sweep that turns around below the top floor is shorter than the full 2(n-1). The real crossover is therefore below 5.71, and 5.71 is the conservative number to quote.

The starvation is in the other naive policy

Candidates reliably get one claim wrong here. To starve a request is to leave it unserved indefinitely while newer requests keep overtaking it, and it is worth being precise about which policy actually does that, because the sloppy version of the claim gets challenged.

FCFS is first-in, first-out, so it does not starve anyone. It is merely slow.

The policy that starves is the greedy one candidates reach for instead: nearest-request-first, known in the disk-scheduling literature as SSTF, for shortest seek time first. Here is the sequence that kills it — a call at the top of the building that never gets picked, because a nearer one always arrives first.

car idle at floor 1, one pending call at floor 20
lobby traffic arrives at floors 2, 3, 4 every few seconds
nearest-first picks a lobby floor every single time
floor 20 waits forever

LOOK is what fixes that, and the fix is provable: a request is served within one full sweep, so worst-case wait is bounded by 2(n-1) = 38 floors of travel plus the door time of the stops in between. SSTF has no such bound. That sentence is the answer to “is your scheduler fair?”

The proof has a precondition, and it is the precondition implementations get wrong. A sweep is bounded only if the set of calls it will serve is fixed when the sweep begins.

Recompute the furthest pending stop on every step instead — which is the natural way to write it — and a steady stream of requests in the current direction extends the sweep forever. At that point the far end starves exactly the way SSTF does, and the bound is not a bound at all.

That is what the frozen sweep_target field in Working python exists for, and the 500-tick assertion beside it is the proof executed rather than claimed.

What LOOK costs. It is worse than SSTF for a single request on an idle car — a call one floor behind the car waits for the sweep to turn around instead of being picked up immediately. Real controllers cheat here: if the car is idle with an empty queue, take the nearest call and start the sweep from there. Say that; it shows you know the algorithm has a bad case.

6. Decision 2 — the request model, and Command

Two questions hang over the request model: why the two request kinds are separate types, and what turning requests into objects at all buys and costs.

Why two request types instead of one

HallCall and CarCall are separate types because the sweep filter treats them differently.

On an up-sweep a car stops for every CarCall on its path. Someone aboard wants off, and there is no direction to check. It stops for a HallCall only when that call’s direction is UP, because a down-bound passenger who boards an up-going car rides the wrong way.

Collapse both into a single Request(floor) and you are forced into a direction: Optional[Direction] field — Optional[T] being the type “either a T or nothing” — plus a None check at every stop decision. That is the same two-case split, with worse names.

Requests as Command objects

A request object is also the natural Command. The Command pattern turns a request into an object carrying everything needed to service it, which makes it queueable, loggable and replayable.

Two things fall out of that.

The first is an audit log: a durable record of what was asked and what was done, so you can answer “why did car 2 skip floor 9 at 09:14?”

The second is deterministic replay, which is what makes the simulator in Working python testable. Replaying the same recorded requests must produce the same stops every time.

The cost is real, and it is memory. A press(5) call now allocates an object, and the queue holds objects rather than an int bitmask — a single integer whose individual bits stand for floors, so a 200-floor building’s entire pending set fits in 200 bits.

Put numbers on that at 200 floors. Two set[int] objects holding a few dozen ints cost a few kilobytes; two 200-bit masks cost 50 bytes. Each Command object costs an allocation and a few dozen bytes, per press.

In a real controller you would keep the bitmask for scheduling and keep the Command objects only in the log.

7. Decision 3 — dispatch is a Strategy

The design’s one interface has to earn its place — by what it makes cheap, what it makes worse, and where you stop applying the same trick.

With one car there is no dispatch. With a bank of six, choosing which car answers a hall call is a separate policy from how each car orders its own stops, and it is the one product managers change.

The diagram below is Class diagram’s strategy corner on its own. The label on each line names the quantity that implementation minimises, and the fact that there are three different quantities is the whole argument for the interface.

classDiagram
    class Dispatcher
    class DispatchStrategy {
        <<interface>>
        +choose(cars, call)
    }
    Dispatcher --> DispatchStrategy
    DispatchStrategy <|.. NearestCarStrategy : min distance
    DispatchStrategy <|.. LookCostStrategy : min added sweep
    DispatchStrategy .. FairnessStrategy : min max-wait, wider signature

Read that diagram back using the notation from Class diagram. The dispatcher holds a reference to one DispatchStrategy and calls choose on it. Two classes realize that interface and a third would like to:

NearestCarStrategy minimises distance — the car with the smallest gap between its position and the calling floor.
LookCostStrategy minimises added sweep — the car whose route grows least when this call is added to it. The implementation in Working python approximates that as distance + penalty x stops already queued rather than re-simulating each car’s sweep, which is cheaper and good enough.
FairnessStrategy minimises the max wait — the assignment producing the smallest worst wait rather than the smallest average. It hangs off a plain link instead of a realization arrow because its choose takes one extra argument, so it does not fit the interface.

A pattern is worth its cost when you can name the second and third implementation, and here they are named on the diagram.

What Strategy makes cheap: the three extensions in Extension scenarios are each one new class and zero edits to Dispatcher or ElevatorCar.

What it costs: you can no longer read the dispatch decision by reading Dispatcher. The flow now goes Dispatcher -> DispatchStrategy -> concrete class, three files for what a switch would say in twelve lines. That is a real readability tax, and it is worth paying only because dispatch policy is the thing that provably changes.

Do not also make the door timing a Strategy. Nobody has ever asked for a second door-timing policy.

8. Working Python

Now the design as running code, in three parts:

The request types and the two travel costs — the 58-versus-24 arithmetic from Decision 1 look not fcfs and here is the number, as executable assertions.
One car’s LOOK sweep — ElevatorCar, and the two details that separate real LOOK from something that resembles it.
The dispatcher and its swappable policy — Dispatcher plus two strategies that give different answers to the same call.

Every block runs on its own, and the blocks also run in sequence, so you can paste any one of them into a file and execute it.

Part 1 — the request types and the two travel costs

This first block defines the two call types and two plain functions that price a set of calls, one per scheduling rule. The three assertions at the bottom are the hand calculation from §5, checked by the interpreter.

from __future__ import annotations

from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from enum import Enum
from typing import List, Optional, Sequence, Set, Union


class Direction(Enum):
    UP = 1
    DOWN = -1
    IDLE = 0


@dataclass(frozen=True)
class HallCall:
    """Someone waiting at a floor. Carries the direction they want to go."""
    floor: int
    direction: Direction


@dataclass(frozen=True)
class CarCall:
    """Someone inside a car. Direction is implied by where the car is."""
    floor: int


Request = Union[HallCall, CarCall]


def fcfs_travel(start: int, reqs: Sequence[Request]) -> int:
    pos, dist = start, 0
    for r in reqs:
        dist += abs(r.floor - pos)
        pos = r.floor
    return dist


def look_travel(start: int, reqs: Sequence[Request]) -> int:
    """Sweep up serving UP + car calls, reverse, serve DOWN calls descending."""
    up = sorted({r.floor for r in reqs
                 if isinstance(r, CarCall) or r.direction is Direction.UP})
    down = sorted({r.floor for r in reqs
                   if isinstance(r, HallCall) and r.direction is Direction.DOWN},
                  reverse=True)
    pos, dist = start, 0
    for f in [f for f in up if f >= start] + down + [f for f in up if f < start]:
        dist += abs(f - pos)
        pos = f
    return dist


BURST: List[Request] = [
    HallCall(15, Direction.DOWN),
    HallCall(3, Direction.UP),
    HallCall(18, Direction.UP),
    HallCall(6, Direction.UP),
    HallCall(11, Direction.DOWN),
]

assert fcfs_travel(1, BURST) == 58
assert look_travel(1, BURST) == 24
assert fcfs_travel(1, BURST) - look_travel(1, BURST) == 34

# A CarCall has no direction, so it rides whichever sweep reaches it. One at
# floor 9 is free here: the up-sweep already passes through 9 on its way to 18.
assert look_travel(1, BURST + [CarCall(9)]) == 24
# FCFS pays for it, because it flies back down to 9 after finishing at 11.
assert fcfs_travel(1, BURST + [CarCall(9)]) == 60

Four Python idioms are doing work in that block.

class Direction(Enum) defines an enumeration: a closed set of named constant values. Direction.UP is a distinct object you compare with is, rather than a bare string somebody can typo. Giving UP the value 1 and DOWN the value -1 is not decoration — it means the direction doubles as the sign of the car’s motion.
@dataclass(frozen=True) generates the constructor, the printable representation and equality for a class defined by its fields. frozen=True additionally makes instances immutable (their fields cannot be reassigned after construction) and therefore hashable, so a call can be put in a set and deduplicated. This chapter’s car does not do that: it stores bare floor numbers in up_stops/down_stops rather than call objects. Storing the call objects is what the audit log of Decision 2 the request model and command would need.
Request = Union[HallCall, CarCall] names a type that is either of the two. It is the type-level statement of “two request kinds, one pending queue”.
from __future__ import annotations stores annotations as text instead of evaluating them, so newer type syntax runs on older interpreters.

The first three assertions at the end are Decision 1 look not fcfs and here is the number’s numbers, executed rather than claimed. The last two add a CarCall at floor 9 to the same burst and show the gap widening on its own: LOOK still costs 24, because its up-sweep already passes floor 9, while FCFS climbs to 60 because it flies back down to 9 after finishing at 11.

One thing to be clear about before moving on: look_travel is a costing function, not the car. It prices a whole batch of calls in one shot to produce the 24, and it is deliberately the shortest code that does so. The real per-call, step-by-step LOOK that a car runs is Part 2, and it has to handle cases this function does not — an idle car with no heading, calls arriving mid-sweep, and the reversal itself.

Part 2 — one car’s LOOK sweep

The car is a small State machine — IDLE -> MOVING -> DOORS_OPEN -> IDLE — but it is described, not implemented. The code has no state field at all, only heading and door. As What this class structure assumes says plainly, this code tracks the door but never acts on it. It is the scheduler, not the door controller.

The block opens by repeating Direction, HallCall and CarCall so it runs standalone. Skip past that to ElevatorCar. Four things there are worth your attention as you read:

the two stop sets, up_stops and down_stops, which are what make the direction filter trivial;
sweep_target, frozen at the start of a sweep and never recomputed mid-sweep;
the split between peek_next_stop (pure) and advance_to_next_stop (mutating);
the driver loop and five assertion groups at the bottom, which exercise the sweep, car calls, purity, the starvation bound, and floor validation in that order.

from __future__ import annotations

from dataclasses import dataclass, field
from enum import Enum
from typing import List, Optional, Set, Tuple, Union

# Repeated from the block above so this one runs on its own.
class Direction(Enum):
    UP = 1
    DOWN = -1
    IDLE = 0

@dataclass(frozen=True)
class HallCall:
    floor: int
    direction: Direction

@dataclass(frozen=True)
class CarCall:
    floor: int

Request = Union[HallCall, CarCall]

class DoorState(Enum):
    CLOSED = "closed"
    OPEN = "open"

@dataclass
class ElevatorCar:
    id: int
    top_floor: int
    position: int = 1
    heading: Direction = Direction.IDLE
    door: DoorState = DoorState.CLOSED
    up_stops: Set[int] = field(default_factory=set)     # serve while heading UP
    down_stops: Set[int] = field(default_factory=set)   # serve while heading DOWN
    sweep_target: Optional[int] = None                  # frozen when a sweep starts

    def accept(self, req: Request) -> None:
        if not 1 <= req.floor <= self.top_floor:
            raise ValueError(f"floor {req.floor} outside 1..{self.top_floor}")
        if isinstance(req, CarCall):
            # a car call has no direction: it rides whichever sweep reaches it
            (self.up_stops if req.floor >= self.position
             else self.down_stops).add(req.floor)
        else:
            (self.up_stops if req.direction is Direction.UP
             else self.down_stops).add(req.floor)

    def _begin_sweep(self, direction: Direction) -> None:
        """LOOK: finish the current sweep, then reverse. `sweep_target` is fixed
        when the sweep starts. Recomputing the furthest pending stop on every
        call is what lets a stream of calls ahead of the car extend a sweep
        forever and starve the far end.
        """
        self.heading = direction
        pending = self.up_stops | self.down_stops
        ahead = [f for f in pending
                 if (f >= self.position if direction is Direction.UP
                     else f <= self.position)]
        if not ahead:
            self.sweep_target = None
        else:
            self.sweep_target = (max(ahead) if direction is Direction.UP
                                 else min(ahead))

    def peek_next_stop(self) -> Optional[int]:
        """The next stop of the sweep in progress. Pure: it changes nothing.

        `None` means *this sweep* is finished, not that the car has no work.
        """
        t = self.sweep_target
        if t is None:
            return None
        if self.heading is Direction.UP:
            ahead = [f for f in self.up_stops if self.position <= f <= t]
            return min(ahead) if ahead else (t if t > self.position else None)
        if self.heading is Direction.DOWN:
            ahead = [f for f in self.down_stops if t <= f <= self.position]
            return max(ahead) if ahead else (t if t < self.position else None)
        return None

    def _sweep_order(self) -> Tuple[Direction, ...]:
        """Reverse first. From idle, head towards the nearest call -- §5's cheat."""
        if self.heading is Direction.UP:
            return (Direction.DOWN, Direction.UP)
        if self.heading is Direction.DOWN:
            return (Direction.UP, Direction.DOWN)
        rest = self.up_stops | self.down_stops
        if not rest:
            return ()
        near = min(rest, key=lambda f: abs(f - self.position))
        return ((Direction.UP, Direction.DOWN) if near >= self.position
                else (Direction.DOWN, Direction.UP))

    def advance_to_next_stop(self) -> Optional[int]:
        """The next stop, starting or reversing a sweep when the current one ends.

        MUTATES: it can flip `heading` and freeze a new `sweep_target`, which
        is why the pure `peek_next_stop` exists beside it -- a dispatcher
        scoring a car must not change the car it is scoring.
        """
        stop = self.peek_next_stop()
        if stop is not None:
            return stop
        for direction in self._sweep_order():
            self._begin_sweep(direction)
            stop = self.peek_next_stop()
            if stop is not None:
                return stop
        self.heading, self.sweep_target = Direction.IDLE, None
        return None

    def arrive(self, floor: int) -> None:
        self.position = floor
        self.up_stops.discard(floor)
        self.down_stops.discard(floor)
        self.door = DoorState.OPEN
        if floor == self.sweep_target:
            self.sweep_target = None        # the frozen sweep is complete


# Drive the same five calls from §5 through the real car and check the
# stop order and the travel cost against the hand calculation.
car = ElevatorCar(id=1, top_floor=20)
for req in [HallCall(15, Direction.DOWN), HallCall(3, Direction.UP),
            HallCall(18, Direction.UP), HallCall(6, Direction.UP),
            HallCall(11, Direction.DOWN)]:
    car.accept(req)

visited, travel = [], 0
while True:
    nxt = car.advance_to_next_stop()
    if nxt is None:
        break
    travel += abs(nxt - car.position)
    car.arrive(nxt)
    visited.append(nxt)

assert visited == [3, 6, 18, 15, 11], visited
assert travel == 24, travel

# A CarCall carries no direction: it joins whichever sweep reaches it.
rider = ElevatorCar(id=2, top_floor=20, position=8)
rider.accept(CarCall(12))
rider.accept(CarCall(4))
assert rider.up_stops == {12} and rider.down_stops == {4}

# `peek` is pure: six calls, one answer, and nothing moved.
peeker = ElevatorCar(id=3, top_floor=20)
peeker.accept(HallCall(3, Direction.UP))
peeker.accept(HallCall(10, Direction.DOWN))
assert peeker.advance_to_next_stop() == 3
peeker.arrive(3)
before = (peeker.heading, peeker.position, peeker.sweep_target)
assert {peeker.peek_next_stop() for _ in range(6)} == {10}
assert (peeker.heading, peeker.position, peeker.sweep_target) == before

# The freeze is what makes the one-sweep bound true. A fresh call ahead of the
# car on every single tick cannot push the frozen turnaround further away.
starved = ElevatorCar(id=4, top_floor=20, position=1)
starved.accept(HallCall(2, Direction.DOWN))          # the victim
for tick in range(500):
    starved.accept(HallCall(20, Direction.UP))       # a new top-floor call, forever
    stop = starved.advance_to_next_stop()
    starved.arrive(stop)
    if stop == 2:
        break
assert tick == 1 and 2 not in starved.down_stops, (tick, starved.down_stops)

# The floor range is checked, so a typo cannot land in a stop set.
for bad in (HallCall(9999, Direction.UP), HallCall(-5, Direction.DOWN)):
    try:
        starved.accept(bad)
        raise AssertionError(f"{bad} accepted on a 20-floor building")
    except ValueError:
        pass

Two more Python idioms

field(default_factory=set) gives each car its own empty set. Writing = set() instead does not silently share one — dataclasses raises ValueError: mutable default … is not allowed at class-definition time. That is the language having learned from the classic def f(x=[]) trap and closed it here.

Optional[int] as the return type of advance_to_next_stop says the honest thing: sometimes there is no next stop. The caller’s if nxt is None: break is where the sweep ends.

Where LOOK actually lives

Keeping two separate sets, up_stops and down_stops, is what makes the direction filter from Decision 2 the request model and command trivial. While heading up, the only candidates are stops in up_stops at or above the car, and the nearest of those is next.

When nothing in up_stops remains ahead, the car still runs on to sweep_target — the turnaround floor, which may itself be a down-call. That is the case the purity assertion exercises: peeker is heading UP with an empty up_stops and a sweep_target of 10, and peek_next_stop() returns 10, the floor where the DOWN call is waiting. After that the heading flips and the far end of the other set becomes the new target. Looking ahead before reversing is what the algorithm is named for.

_sweep_order covers the idle case by starting towards the nearest pending stop in either set, which is exactly the cheat described at the end of The starvation is in the other naive policy.

The first two assertions reproduce the same 24 floors and the same stop order the hand calculation produced.

The two details that separate LOOK from a lookalike

Detail one: sweep_target is frozen. _begin_sweep sets it once, and only arrive clears it, when the car actually reaches it. The set of floors this sweep will serve is therefore decided at the start of the sweep.

Recompute the furthest pending stop on every call — the version almost everyone writes — and a sweep never has a fixed end. A steady stream of calls in the current direction extends it indefinitely while the far end waits forever.

The starved loop is that scenario run 500 times, and it terminates on the second tick. Trace it: the car starts at floor 1 holding one DOWN call at floor 2 (the victim). On tick 0 a call at floor 20 arrives, the idle car heads UP with sweep_target frozen at 20, and it runs to 20. On tick 1 another floor-20 call arrives, but it cannot move a target that has already been reached and cleared; the car reverses, freezes sweep_target at 2, and serves the victim. Hence assert tick == 1. That is why the bound in The starvation is in the other naive policy is a claim about this code rather than about the algorithm in the abstract.

Detail two: peek_next_stop is pure and advance_to_next_stop is not. A method named like a query that quietly flips the car’s heading is a trap for exactly the caller Decision 3 dispatch is a strategy invites. A dispatcher that scores a car by looking at where it is going next must be able to look without changing the answer. The peeker assertions call peek_next_stop() six times and check that heading, position and sweep_target all come out unchanged.

Two smaller choices in `accept`

accept never touches heading. Only two places write it: _begin_sweep, from the direction the car is actually about to move, and the last line of advance_to_next_stop, which sets IDLE once there is no work left anywhere. So heading cannot say UP while the car descends — which is what happens if you derive it from floor >= self.position at the moment a call arrives.

That heading is not the same thing as the direction on the hall call. A car at floor 10 answering HallCall(5, Direction.UP) descends to 5 and then sweeps up: its heading is DOWN for the first leg while the hall indicator correctly reads UP.

accept validates the floor against top_floor. Without that check, accept(HallCall(9999, ...)) drops 9999 into a stop set and the car spends the rest of its life sweeping towards a floor that does not exist. The last loop in the block asserts both an over-range and a negative floor are rejected.

Part 3 — the dispatcher and its swappable policy

This last block is the Strategy pattern from Decision 3 dispatch is a strategy as code. Read it for one thing: Dispatcher.assign contains no policy at all, it just forwards to whatever strategy object it holds.

Note that Car here is a deliberately smaller stand-in for ElevatorCar, and that this block passes the direction as the plain string "up" rather than a Direction — both points are explained under the block.

from __future__ import annotations

from abc import ABC, abstractmethod
from typing import List, Optional, Sequence

class DispatchStrategy(ABC):
    """Returns the car that should answer a hall call, or None to defer."""

    @abstractmethod
    def choose(self, cars: Sequence["Car"], floor: int,
               direction: str) -> Optional["Car"]:
        ...

class Car:                       # stand-in; the real one is above
    def __init__(self, id: int, position: int, pending: int = 0,
                 in_service: bool = True, serves=range(1, 21),
                 oldest_since: float = 0.0):
        self.id, self.position, self._pending = id, position, pending
        self.in_service, self.serves = in_service, serves
        self._oldest_since = oldest_since

    def pending(self) -> int:
        return self._pending

    def oldest_waiting_since(self) -> Optional[float]:
        """When the oldest call this car already holds was made, or None."""
        return self._oldest_since if self._pending else None

    def can_serve(self, floor: int) -> bool:
        return self.in_service and floor in self.serves

class NearestCarStrategy(DispatchStrategy):
    """Minimize distance. Simple, and starves the far end under lobby load."""

    def choose(self, cars, floor, direction):
        ok = [c for c in cars if c.can_serve(floor)]
        return min(ok, key=lambda c: abs(c.position - floor)) if ok else None

class LookCostStrategy(DispatchStrategy):
    """Minimize distance plus a penalty per stop already queued on that car."""

    def __init__(self, stop_penalty: int = 2):
        self.stop_penalty = stop_penalty

    def choose(self, cars, floor, direction):
        ok = [c for c in cars if c.can_serve(floor)]
        if not ok:
            return None
        return min(ok, key=lambda c: abs(c.position - floor)
                   + self.stop_penalty * c.pending())

class Dispatcher:
    def __init__(self, cars: List[Car], strategy: DispatchStrategy):
        self.cars, self.strategy = cars, strategy

    def assign(self, floor: int, direction: str) -> Optional[Car]:
        return self.strategy.choose(self.cars, floor, direction)


fleet = [Car(1, position=2, pending=6), Car(2, position=9, pending=0)]
d = Dispatcher(fleet, NearestCarStrategy())
assert d.assign(4, "up").id == 1              # car 1 is closer...

d.strategy = LookCostStrategy(stop_penalty=2)
# cost = distance + 2 * already-queued stops
# car 1:   2 + 2 * 6 = 14
# car 2:   5 + 2 * 0 = 5
assert d.assign(4, "up").id == 2              # ...but car 2 is sooner

# ABC is enforced, not documentation: the bare interface cannot be built.
try:
    DispatchStrategy()
    raise AssertionError("an abstract strategy was instantiated")
except TypeError:
    pass

# `can_serve` is the eligibility gate §9's express cars are built on, and it
# is asked BEFORE any car is scored -- so a fleet with no eligible car
# returns None rather than a bad assignment.
express = Car(3, position=20, serves=range(20, 21))
assert express.can_serve(20) and not express.can_serve(4)
assert NearestCarStrategy().choose([express], 4, "up") is None

DispatchStrategy(ABC) inherits from ABC, short for abstract base class: a class Python refuses to instantiate directly. DispatchStrategy() raises TypeError instead of silently producing a policy that decides nothing, which the try/except block above demonstrates. @abstractmethod marks choose as the method every subclass is obliged to supply, and the ... in its body is the literal Ellipsis object standing in for “no implementation here”.

The Car in this block is a deliberate stand-in for ElevatorCar. A dispatch policy needs only four facts about a car: where it is, how much work it already has, how long the oldest of that work has been waiting, and whether it may serve this floor. Writing the smaller class makes that list visible. Its serves=range(1, 21) default is the twenty floors of the building, and can_serve is the eligibility predicate that the express-car extension in Now add express cars that only serve floors 20 and above is built on.

The direction is a plain "up" string here, not Direction.UP. Neither strategy in this block reads it — every one of them decides on position and load alone — so the block keeps the parameter in the signature and does not import the enum. In a real controller you would pass the Direction, or better, pass the whole HallCall object, which is exactly the repair Now optimize for wait time fairness instead of total travel needs for a different reason.

Follow the two assertions that flip. Car 1 sits at floor 2 with six stops already queued. Car 2 sits at floor 9 with none.

NearestCarStrategy compares only distance, so car 1 wins: a gap of 2 against 5.

LookCostStrategy adds two floors of penalty per queued stop. Car 1 now costs 2 + 2 * 6 = 14 against car 2’s 5 + 2 * 0 = 5, and the answer flips.

That assertion pair is the chapter in two lines: the same call, two policies, two answers, and Dispatcher never changed.

9. Extension scenarios

Three follow-ups, each stated the way an interviewer states it. For each one the useful answer has the same four parts: what changes, what does not, why the design absorbed it, and what it still costs.

“Now add express cars that only serve floors 20 and above”

What changes. One field on the car — serves, the set of floors it is allowed to answer — and one filter in the strategy. Both already exist in Working python as Car.serves and Car.can_serve, with a worked express car at the end of that block: Car(3, position=20, serves=range(20, 21)) is rejected for a floor-4 call and choose returns None. Nothing changes in ElevatorCar.advance_to_next_stop, because LOOK does not care why a floor is not in its set.

What does not change. The request model, the dispatcher and the car state machine are all untouched.

Why the design absorbed it. Dispatch already asks each car whether it can take a call before scoring it. Eligibility and preference were kept as two separate questions. If eligibility had been folded into the cost function as “return infinity”, every new strategy would have to remember to re-implement the express rule.

The catch worth volunteering: a hall call at floor 25 going DOWN and a hall call at floor 5 going UP are now served by disjoint car sets, so the building has two independent queues and the fairness bound is per-set, not global. If every express car is busy, a floor-25 passenger waits behind express traffic no matter how idle the local cars are.

“Now add a service mode that removes a car from dispatch”

What changes. One boolean is flipped, already present as in_service, plus the door interlock — the safety circuit that refuses to let a car move while its doors are open — so a technician can hold the doors without the car being scheduled.

What does not change. Nothing in scheduling moves at all. can_serve returns False and the car is invisible to every strategy at once.

Why the design absorbed it. The car’s availability lives on the car and is consulted by the policy, rather than the dispatcher keeping its own list of active cars. The list-of-active-cars version is the design that breaks: now there are two sources of truth and they drift the first time a car goes out of service while holding pending calls.

The real question that follows is what happens to the calls already queued on that car. Two honest answers: drain them first (in_service=False blocks new assignments only), or reassign them immediately. Say which you picked. Draining is right for maintenance, immediate reassignment is right for a fault.

“Now optimize for wait-time fairness instead of total travel”

What changes. You write one new FairnessStrategy, and the requests need to carry an arrival timestamp. The HallCall dataclass in Working python does not have one yet, but adding a field to a Command object is a one-line change — which is part of what modelling requests as objects bought you in Decision 2 the request model and command.

What does not change. ElevatorCar, Dispatcher and the diagram all stay exactly as they are.

The block below is the new policy plus three assertion groups: the aging term flipping the answer, the same class with the weight set to zero reverting to nearest-car, and — at the bottom — a demonstration that the tempting version of aging does nothing at all. That last one is the point of the block.

from typing import Optional, Sequence


class FairnessStrategy:
    """Score by the worst wait the assignment creates, not the mean.

    Minimizing total travel is a utilitarian objective: it will happily make
    one passenger wait 4 minutes to save six passengers 20 seconds each.

    Aging cannot live in the per-car score as a function of THIS call: `age`
    is the same number for every candidate car, and subtracting a constant
    from every score cannot change the argmin. It has to weight the CALL
    against other calls, or weight each car by the age of the work it is
    already carrying. This class does the second.
    """

    def __init__(self, now: float, aging_weight: float = 3.0):
        self.now, self.aging_weight = now, aging_weight

    def _staleness(self, car) -> float:
        since = car.oldest_waiting_since()
        return 0.0 if since is None else self.now - since

    def choose(self, cars, floor: int, direction: str, waiting_since: float):
        ok = [c for c in cars if c.can_serve(floor)]
        if not ok:
            return None
        # Penalise a car by how long ITS oldest pending call has waited, so a
        # car already carrying a stale request stops accumulating new ones.
        return min(ok, key=lambda c: abs(c.position - floor)
                   + self.aging_weight * self._staleness(c))


now = 10.0
fleet2 = [Car(1, position=2, pending=6, oldest_since=0.0),   # holding a 10s-old call
          Car(2, position=9, pending=0)]                     # idle, nothing stale

assert NearestCarStrategy().choose(fleet2, 4, "up").id == 1          # closest wins
assert FairnessStrategy(now).choose(fleet2, 4, "up", waiting_since=now).id == 2
# car 1:  2 + 3.0 * 10 = 32        car 2:  5 + 3.0 * 0 = 5

# ...and the aging term is what flipped it: at weight 0 it is nearest-car again.
assert FairnessStrategy(now, aging_weight=0.0).choose(
    fleet2, 4, "up", waiting_since=now).id == 1

# Why the tempting version does nothing. `age` is one number for the whole
# call, so subtracting it moves every candidate's score by the same amount.
age = now - 0.0
plain = [abs(c.position - 4) for c in fleet2]
aged = [s - 1_000_000.0 * age for s in plain]
assert min(range(2), key=plain.__getitem__) == min(range(2), key=aged.__getitem__)

Utilitarian in that docstring means an objective that maximises the total across everyone and is indifferent to how that total is distributed. That is exactly the property that lets a policy sacrifice one passenger for six.

How the working version ages. aging_weight penalises a car in proportion to how long its own oldest pending call has waited. A car already carrying a stale request therefore stops accumulating new ones. That is what flips the answer to car 2 in the first assertion, and setting the weight to zero in the second assertion flips it back to car 1.

Why the tempting version does nothing. The natural instinct is to subtract aging_weight * age from every car’s score, where age is this call’s own age. But age is one number for the whole call, so it is the same constant on every candidate, and subtracting a constant from every score cannot change which car wins.

The last assertion in the block is that non-fix executed: a weight of a million against an age of ten seconds shifts both scores and leaves the argmin exactly where it was. An aging term that only ever moves every score by the same amount is a comment, not a policy. It is the shape of bug that survives review because the sentence describing it is persuasive. Aging can bite when you choose which call to serve next; it cannot bite when you choose which car serves one given call.

One honest wrinkle to volunteer before an interviewer spots it. choose here takes an extra waiting_since argument, so this class does not actually satisfy the DispatchStrategy signature from Working python — and note that it does not subclass DispatchStrategy in the code either, which is the same fact stated by the interpreter.

The two clean repairs are to put the arrival timestamp on the call object and pass the call rather than a bare floor, or to widen the interface for every strategy. Adding a parameter for one implementation is the classic way an interface starts to rot, and naming it is worth more than quietly ignoring it.

Why this is the honest version: the objective genuinely conflicts. Total travel and p99 wait cannot both be minimized; the aging term deliberately makes the fleet travel further so the oldest call gets picked up. State the trade instead of pretending a policy is strictly better — that is what the question is testing.

10. What interviewers probe

These are the seven follow-ups this problem reliably produces, with the answer that ends each one rather than extends it. Two rows admit something is missing from the code rather than claiming it is there — that is the tone to copy.

Probe	Answer that lands
“Why not just FCFS?”	58 floors versus 24 on the burst in Decision 1 look not fcfs and here is the number, and the gap grows with load: FCFS costs a flat 6.65 floors/request while LOOK costs 38/m
“Does your scheduler starve anyone?”	Not LOOK: served within one sweep, so worst case is 38 floors. Nearest-first does starve, and here is the sequence
“Where does the direction on a hall call matter?”	The stop filter on the sweep. Without it a down-bound car stops for up-bound passengers who then ride the wrong way
“Make the dispatcher a Singleton?”	No. A Singleton is a class rigged so only one instance can ever exist. One dispatcher per building is a deployment fact, not a language-level constraint. Construct it once in `main` and inject it — hand it in as an argument rather than letting callers reach for a global. A Singleton makes a two-building test process impossible and hides the dependency from every call site (chapter 03)
“Where is the concurrency?”	Two hall calls for the same floor+direction must collapse to one, and assignment must be atomic — indivisible, so no other thread can observe a half-done assignment — or two cars answer the same call. Put the pending-call set behind one lock in the dispatcher; the car’s own queue is touched only by its control loop, so it needs no lock. Neither exists in this chapter’s code — there is no dispatcher-side pending set and no lock, because every block here is single-threaded. Say it as the next thing you would build, not as something you already did
“What if a car’s position sensor lies?”	Position is an observation, not state you own. The controller reconciles against floor sensors and enters a fault mode on disagreement -> `in_service = False`, which the service-mode extension already built
“Capacity?”	A car at capacity should stop for `CarCall`s but skip `HallCall`s. That is one predicate in the sweep filter, not a new class

11. Cheat sheet

One line per claim you should be able to make without notes. If you can reproduce this table from memory, you can redraw the class model and defend it.


Two request types	`HallCall(floor, direction)` and `CarCall(floor)`. The direction is what makes LOOK work
Per-car algorithm	LOOK: finish the current direction, then reverse. Never wrap to the bottom (that is SCAN, and it wastes a full traverse)
The number	FCFS 58 floors vs LOOK 24 on five calls. FCFS is 6.65 floors/request at any load; LOOK is 38/m and improves with load
Fairness	LOOK bounds wait at one sweep = 38 floors. SSTF has no bound and starves the far end
Fleet dispatch	Strategy. Cost = distance + penalty x queued stops. Eligibility (`can_serve`) is a separate question from preference
State	Car is described as a state machine — IDLE / MOVING / DOORS_OPEN — and the code has no state field, only `heading` and `door`
What it assumes	The state set is closed and known, and every (state, event) pair is defined. Fire recall breaks the first; the shown car code never checks its own state, which breaks the second
The asymmetry	Dispatch policy is an interface because it changes; per-car sweep order is hard-coded because it does not. That is a bet, and you should say so
Command	Requests as objects buy the audit log and deterministic replay; cost is allocation per press
Do not	Model `Floor` as a class, make `Dispatcher` a Singleton, or make door timing a Strategy
Concurrency	Future work, not shipped here: dedupe hall calls and assign under one lock. The per-car queue is single-threaded by construction

Related: 02 — The OOD Framework is the six-step method, and its section on the five assumptions generalises What this class structure assumes here. 03 — OOP Fundamentals treats Strategy, State and “what a class structure assumes” as topics in their own right. 07 — Vending Machine is the state machine done strictly, with every undefined transition refused by construction — the discipline this chapter’s car deliberately skips.

Next: 09 — Grocery Store System, where the swappable-policy argument returns as pricing rules and the ordering between them turns out to be worth a dollar a cart.

08 — Elevator System