9.7.28 — Elevator

"Design an elevator system: N floors, M cars, buttons in the lobby and buttons inside."

Someone on floor 3 presses "up". Someone on floor 9 presses "down". A car is sitting on floor 6. Which one does it go to, and why?

There is no correct answer to that question — there are only policies, and the difference between a passable design and a good one is whether you noticed that. The state machine for a single car is the easy half of this problem and takes ten minutes. The scheduling policy is the interview, and the first thing to establish is that the two are separate, because that separation is what lets a building change its policy without touching anything that moves.

1. Two kinds of button, and they are not the same request

The most common mistake is treating every press as "a request for floor N". They are different in three ways, and every one of them matters later.

interface HallCall {                        // (1)
  floor: Floor;
  direction: "up" | "down";                 // (2)
  pressedAt: Instant;
  assignedCar: CarId | null;                // (3)
}

interface CarCall {                         // (4)
  carId: CarId;
  floor: Floor;
  pressedAt: Instant;
}

(1) A hall call comes from a button in the corridor. It belongs to the building, not to any car, which is why it is a separate entity with its own life.

(2) It carries a direction, and this is the field people forget. Somebody pressing "down" on floor 9 does not want a car that is going up. Sending them one wastes a stop for everybody and produces the experience where a lift arrives, opens, and everybody stands still.

(3) A hall call is assigned to a car by the dispatcher, and it can be reassigned before it is served. That mutability is deliberate: a car that becomes unavailable must be able to hand its calls back.

(4) A car call comes from a button inside a specific car. It has no direction — you are already in the lift, and you have named where you want to get out — and it can never be reassigned to a different car, because you are physically inside this one.

The consequences of the split show up immediately:

Capacity behaves differently for each. A full car must stop refusing hall calls, because nobody else can get in. It must keep serving its car calls, because the people inside need to get out. A design with one kind of request cannot express that distinction, and the resulting lift either strands its passengers or stops on every floor to open its doors at people who cannot board.

Only hall calls need a dispatcher. Car calls go straight into their own car's stop list, with no decision to make. So the whole scheduling problem in section 4 is about hall calls only, which is a much smaller problem than it first looks.

The lights work differently. A hall call's light goes out when any car serves that floor in that direction. A car call's light goes out only when that car stops there.

2. The car: doors and motion are one state machine

type CarState =
  | { kind: "idle"; floor: Floor }                                   // (1)
  | { kind: "moving"; from: Floor; to: Floor; direction: Direction } // (2)
  | { kind: "doorsOpening"; floor: Floor }
  | { kind: "doorsOpen"; floor: Floor; closesAt: Instant }           // (3)
  | { kind: "doorsClosing"; floor: Floor }                           // (4)
  | { kind: "outOfService"; floor: Floor; reason: string };

(1) Idle means stopped, doors shut, no committed stops. It carries the floor, because a dispatcher choosing a car needs to know where the idle ones are.

(2) Moving carries a direction as well as a destination, because the direction is what the sweep policy in section 3 commits to, and because a hall call in that direction can be picked up on the way.

(3) Doors open carries the time they will close. The timer is in the state, so "how long have the doors been open" is answerable from the state itself rather than from a variable beside it.

(4) Closing is a real state and not an instant, because a person putting a hand in the doors during it sends the car back to doorsOpening. A design that treats closing as instantaneous cannot express the most common thing that happens in a lift.

The reason this is a state machine rather than a set of flags is one sentence: "moving with the doors open" must be impossible to represent. With a direction field and an isDoorOpen boolean beside it, that combination exists in the type and is prevented only by everyone remembering to check. With a union, there is no moving case containing a door state, so the dangerous combination cannot be written down. Making the unsafe state unrepresentable is stronger than checking for it, and this is the clearest example of that idea in the whole chapter.

The stop list is separate from the state, because it survives every transition:

class Car {
  private state: CarState;
  private stops = new Set<Floor>();          // (1)

  addStop(f: Floor): void { this.stops.add(f); }   // (2)

  tick(now: Instant): CarState {                    // (3)
    this.state = this.next(this.state, now);
    return this.state;
  }
}

(1) A set, not a queue. The order the buttons were pressed does not decide the order of stops — the sweep does — so storing arrival order would be storing something the design deliberately ignores.

(2) Both dispatched hall calls and internal car calls arrive here. By this point the difference between them has already been used, and the car only needs to know which floors it must visit.

(3) One tick, one transition. The car does not sleep, block or wait for hardware; it is driven by ticks and events, which is what makes section 8's replay possible.

3. Which stop next: the sweep

Serving requests in the order the buttons were pressed makes the car cross itself. Take a car at floor 1 with stops at 3, 9, 2 and 8, pressed in that order:

First-come: 1→3 is 2 floors, 3→9 is 6, 9→2 is 7, 2→8 is 6. Twenty-one floors travelled, and the person who pressed 2 waited while the car went past them to 9 and back.

Sweeping upwards: 1→2→3→8→9. Eight floors, and everybody's wait is shorter than their worst case under the first-come order.

So the rule is: keep going the way you are going, stop at every committed floor on the way, and only turn round when there is nothing left ahead.

function nextTarget(current: Floor, dir: Direction, stops: Set<Floor>): Floor | null {
  const ahead = [...stops].filter(f =>                              // (1)
    dir === "up" ? f > current : f < current);

  if (ahead.length > 0)                                             // (2)
    return dir === "up" ? Math.min(...ahead) : Math.max(...ahead);

  const behind = [...stops].filter(f =>                             // (3)
    dir === "up" ? f < current : f > current);

  if (behind.length > 0)                                            // (4)
    return dir === "up" ? Math.max(...behind) : Math.min(...behind);

  return null;                                                      // (5)
}

(1) Split the stops into the ones ahead in the current direction and the ones behind.

(2) The nearest one ahead is next. Going up means the smallest floor above us; going down means the largest below. This is the line that produces the whole sweeping behaviour.

(3) and (4) With nothing ahead, turn round and take the furthest one behind — because after turning, that is the far end of the new sweep and everything between will be picked up on the way.

(5) Nothing at all: the car becomes idle.

This is the same algorithm as the disk head scheduler in 2.7, which is called the elevator algorithm because it was named after this. Saying so is worth a moment in an interview: it shows the same problem recognised in a different domain, and it is a genuine connection rather than a decoration — both are a physical head that is expensive to reverse, serving requests scattered along one axis.

One rule the sweep needs and that is easy to miss: a car going up should only pick up hall calls whose direction is up. A "down" call on floor 5 is not served by a car passing floor 5 on its way to 9. It is served on the way back, and the direction field from section 1 is what makes that expressible.

The sweep can starve someone, and it must be said before being asked. In a building with heavy upward traffic, a single "down" call on a low floor can wait a very long time, because there is always another up call to serve first. The fix is aging: a call's priority rises with its wait, and past a threshold it is served next regardless of direction. This is the same starvation problem and the same cure as process scheduling in 2.3, and the practical form is a hard cap — "no call waits more than 90 seconds" — because that is a promise a building manager can understand and check.

4. Which car: dispatch is a policy, and the cost function is the design

With several cars, somebody has to decide who takes each hall call. This is the only genuinely open question in the problem, so it gets its own interface and lives behind it.

Figure 2 — Scoring three cars against one call. The physically nearest car is the worst choice because it is travelling the wrong way. Everything interesting about dispatch is in what the cost function charges for.

interface DispatchPolicy {                                          // (1)
  assign(call: HallCall, cars: readonly CarSnapshot[]): CarId | null;
}

class NearestCarGoingTheRightWay implements DispatchPolicy {
  assign(call: HallCall, cars: readonly CarSnapshot[]): CarId | null {
    const eligible = cars.filter(c => c.available && !c.full);      // (2)
    if (eligible.length === 0) return null;                         // (3)

    return eligible
      .map(c => ({ id: c.id, cost: this.cost(call, c) }))
      .sort((a, b) => a.cost - b.cost)[0].id;                       // (4)
  }

  private cost(call: HallCall, c: CarSnapshot): number {
    const distance = Math.abs(c.floor - call.floor);                // (5)
    const wrongWay = c.direction !== null && c.direction !== call.direction
                   && this.wouldPass(c, call);
    const stopsOnTheWay = c.stopsBetween(c.floor, call.floor);      // (6)

    return distance
         + (wrongWay ? REVERSAL_PENALTY : 0)                        // (7)
         + stopsOnTheWay * STOP_PENALTY                             // (8)
         + (c.load / c.capacity) * LOAD_PENALTY;                    // (9)
  }
}

(1) One method, one decision. Everything a building wants to change about how lifts behave is behind this interface, and nothing about the cars changes when it does — the plug point from 9.3.6.

(2) Cars that are out of service or full are removed before anything is scored, because they are not choices.

(3) No eligible car is a real outcome, not an error. The call stays unassigned and is offered again on the next pass, which is what happens in a busy building for a few seconds at a time.

(4) Score every car, take the cheapest. The whole policy is in cost.

(5) Distance is the obvious term and it is the least important one.

(6) Stops already committed between here and the call, because each one costs a door cycle — typically five to ten seconds, which is far more than travelling one floor.

(7) The reversal penalty is what makes this policy better than "nearest car". A car one floor away going the other way will arrive later than a car four floors away coming towards you, and charging for the reversal is what expresses that.

(8) Every intervening stop is charged, which is why a heavily loaded car is passed over even when it is close.

(9) A nearly full car is penalised, because it may not be able to take the passenger at all, and arriving unable to help is worse than arriving late.

The numbers are tuning knobs, and they belong in configuration. A REVERSAL_PENALTY of 10 in an office tower and 4 in a small block are both right, and the only way to know is to measure. Section 8 is about making that measurable.

Then the twists land as new policies, with nothing else changing:

Morning rush. Everybody enters at the lobby and goes up. Idle cars return to the ground floor instead of waiting where they were, and the cost function weights lobby calls heavily. That is one new class.

Evening rush. The opposite, and it is not simply the morning policy reversed — people leave from many floors to one, so cars spread out rather than gathering.

Zoning. In a tall building, cars are assigned floor ranges so they sweep shorter distances. Again a policy, and it also makes the sweep in section 3 shorter without changing it.

And one twist that is honestly not a policy. Firefighter mode — recall every car to the ground floor, open the doors, ignore all calls — is a change to the car's state machine, because it is a state with different physics that outranks everything. Saying "this one restructures, and here is why it must" is a better answer than pretending every requirement fits an existing seam.

5. Capacity, and the rule most designs get wrong

A car has a weight limit, and the sensor under the floor is what knows.

A full car stops accepting hall calls and keeps serving car calls. Those are different rules for the same car at the same moment, and they are the reason section 1 insisted the two kinds of request are different entities.

Hall calls: nobody can get in, so stopping is a wasted door cycle for everyone including the people already inside. The call goes back to the dispatcher and another car takes it. If the car was the only one assigned, the call is simply re-offered — which is also why assignment has to be reversible.

Car calls: the people inside asked to get out. Refusing those is not a capacity optimisation, it is trapping people.

The re-offer must not be a loop. A call handed back by a full car, re-assigned to the same car because it is nearest, handed back again, is livelock — busy, and making no progress (9.5.3). The cure is that the dispatcher excludes a car from a call it has just declined, for a short period. One line, and it removes a failure that is very confusing to watch.

6. What must hold when the software is wrong

Everything above is about service. This section is about the part that is not negotiable, and it belongs in any answer that wants to sound like it has been near a real building.

The safety chain is not software. Door interlocks, overspeed governors and the brakes are electromechanical, wired in series, and they stop the car whether or not any program agrees. Software cannot open the doors between floors because the interlock physically prevents it, not because a function checks. Say this plainly, because a candidate who puts the safety of a lift in a if (doorsClosed) has not understood what kind of machine this is.

What software owes the safety chain is honesty about state. The car reports what it believes; an independent monitor compares that with the sensors; a disagreement takes the car out of service rather than trying to reconcile it. outOfService is a state in section 2's union for exactly this reason — it is not an error path bolted on, it is a normal condition a car can be in, and the dispatcher already excludes such cars because they are not available.

Degraded but working beats stopped. A car with a failed door sensor is removed from service, and the building keeps running on the others, more slowly. A dispatcher that fails entirely should fall back to something simple — every car serves every call, sweeping — rather than stopping. This is the same reasoning as the traffic controller's flashing mode in 9.7.15: the fallback is worse and is still a working building.

7. Concurrency: one mailbox per car

Hall calls arrive from every floor while cars are moving, and the dispatcher is reading car positions while they change.

Each car processes one event at a time from its own mailbox — ticks, stop assignments, door events, sensor reports — which is the actor shape from 9.5.4. There is one writer for each car's state and stop list, so there is no lock anywhere in the car.

The dispatcher works from snapshots. It reads each car's position, direction, load and stop count as a copy, scores them, and sends an assignment. It never reaches into a car and mutates anything. The consequence to say out loud is that a snapshot can be slightly stale — a car may have moved a floor since it was taken — and that this is harmless, because the assignment is a hint about which car should take a call, and being one floor out changes the quality of the decision rather than its correctness.

That tolerance is what makes the design simple. If dispatch had to be exactly right, it would need to freeze the cars while it decided, and a system that stops all the lifts to think is worse than one that occasionally picks the second-best car.

8. Making the policy measurable

The reason the dispatcher is behind an interface is not tidiness. It is so that two policies can be compared on the same day's traffic.

For that to work, the whole system must be drivable by a recorded list of events — every button press, with its time — which requires three things the design already has, plus one it must be given:

Everything arrives as an event. No blocking calls into hardware, so a day of presses replays in seconds.

Time is injected. The cars take now as a parameter rather than reading a clock, so a replay can run at any speed.

Cars are actors with no hidden shared state, so a replay produces the same result every time.

And any randomness must be seeded, so two policies are compared on identical traffic rather than on two similar days.

Then the question "should we use the up-peak policy from 08:00 to 09:30?" stops being an opinion. Replay yesterday's traffic under both policies and compare the numbers that matter: the median wait, the 95th percentile wait — which is what people actually complain about, since nobody notices an average — the number of calls waiting over 60 seconds, and the total distance travelled, which is the energy bill.

This is the same idea as the exchange's replay in 9.7.25, arriving for a different reason. There, determinism exists so a trade can be proved. Here, it exists so a policy can be argued about with data. In both cases it is the same discipline that buys it: events in, pure step function, no hidden clock.

9. What the interviewer will push on

"A car is on floor 6. Floor 3 presses up, floor 9 presses down. Which one?" There is no correct answer, only a policy — and noticing that is the answer. Then give a cost function rather than a rule: distance, plus a penalty for reversing direction, plus a penalty per committed stop in between, plus a penalty for load. The common wrong answer is "the nearest car", which reliably picks a car travelling the wrong way.

"Why not serve requests in the order they were pressed?" Because the car crosses itself. Give the numbers: stops at 3, 9, 2, 8 from floor 1 is 21 floors in press order and 8 floors swept. Then name the algorithm and the connection — this is the same sweep as a disk head scheduler, which is called the elevator algorithm after this exact problem.

"Why are doors part of the state machine?" So that "moving with the doors open" cannot be represented. With a direction field and an isDoorOpen boolean, that combination exists in the type and is prevented only by everybody remembering to check. Making an unsafe state unrepresentable is stronger than checking for it.

"The car is full." It stops accepting hall calls and keeps serving car calls — different rules for the same car in the same moment, which is why the two kinds of request are different entities. Then volunteer the failure this creates: a declined call reassigned to the same car is livelock, so the dispatcher excludes a car from a call it just declined for a short period.

"Can a call wait forever?" Yes, under a pure sweep, in a building with sustained traffic in one direction. The fix is aging — priority rising with wait, with a hard cap such as 90 seconds — which is the same starvation problem and the same cure as process scheduling. A candidate who says the sweep is optimal without naming this has not thought about a busy morning.

"What happens if your software is wrong?" Nothing dangerous, because the safety chain is electromechanical and stops the car regardless. What software owes it is honest reporting: a car whose reported state disagrees with its sensors goes outOfService, which is a normal state in the union rather than an error path, and the building keeps running on the other cars.

The thing to volunteer that nobody asks for: that the dispatcher sits behind an interface so that two policies can be replayed against yesterday's recorded traffic and compared on the 95th percentile wait rather than the average. Candidates present a policy as a good idea. Presenting the mechanism for deciding whether it was a good idea is what shows you have shipped something that had to be tuned after it was built.

Recall

• Hall calls and car calls are different entities. Hall calls carry a direction and are assigned by a dispatcher; car calls have no direction and can never be reassigned.
• A full car refuses hall calls and keeps serving car calls — the rule that needs the two entities.
• Doors and motion are one state machine, so "moving with the doors open" is unrepresentable rather than merely checked.
• Closing is a real state, because a hand in the doors sends the car back to opening.
• The stop list is a set, not a queue — press order is deliberately ignored.
• Sweep, do not serve in press order. Stops at 3, 9, 2, 8 from floor 1: 21 floors in press order, 8 swept. Same algorithm as the disk-head scheduler named after it.
• A car going up serves up hall calls only; the down call is picked up on the way back.
• The sweep can starve a call. Fix with aging and a hard cap — the same cure as process scheduling.
• Dispatch is a policy behind an interface. The cost function is the design: distance, plus reversal penalty, plus committed stops between, plus load.
• "Nearest car" is the answer that sounds right and is wrong — it picks cars travelling the wrong way.
• Morning rush, evening rush and zoning are new policies; firefighter recall is an honest change to the car's state machine.
• A declined call reassigned to the same car is livelock — exclude a car from a call it just declined.
• The safety chain is electromechanical, not software. Software owes it honest state, and a disagreement means outOfService.
• One mailbox per car; the dispatcher works from snapshots. A slightly stale snapshot degrades the choice, never the correctness.
• Events in, injected time, seeded randomness — so two policies can be replayed on the same recorded day and compared on the 95th percentile wait.

Self-test: Why are hall and car calls different types? What does a full car do with each? Why must doors live in the state? What does a press-order design cost in floors? Which term makes the cost function better than distance? Which twist genuinely changes the state machine?

Quiz Bank

FoundationalModel a single car. Say why the doors belong in the state machine and why the stop list does not.

The states:

type CarState =
  | { kind: "idle"; floor: Floor }
  | { kind: "moving"; from: Floor; to: Floor; direction: Direction }
  | { kind: "doorsOpening"; floor: Floor }
  | { kind: "doorsOpen"; floor: Floor; closesAt: Instant }
  | { kind: "doorsClosing"; floor: Floor }
  | { kind: "outOfService"; floor: Floor; reason: string };

Why the doors are in here rather than beside it. The alternative is a direction field with an isDoorOpen boolean next to it. That representation contains the combination "moving, doors open" — it is a valid value of the type — and the only thing preventing it is that every piece of code remembers to check. In this union there is no moving case that holds a door state, so the dangerous combination cannot be written down at all.

Making an unsafe state unrepresentable is stronger than checking for it, and this is the clearest instance of that idea in the whole chapter. A check can be forgotten by the next person; a type cannot.

doorsClosing is a state rather than an instant because it is where the most common event in a lift happens: someone puts a hand in the doors. From doorsClosing, a sensor event returns the car to doorsOpening. A design that treats closing as instantaneous has nowhere to put that event, and the usual result is a boolean flag that recreates exactly the problem the union was chosen to avoid.

doorsOpen carries closesAt rather than a separate timer, so "how long have the doors been open" is answered from the state itself. The alternative — a timer variable that must be started and cleared alongside transitions — is two things that must agree, and they will eventually not.

outOfService is in the union rather than being an error path, because it is a normal condition. A car can be out of service for maintenance, for a fault, or because its reported state disagreed with a sensor, and it is important that the dispatcher can see this as an ordinary property to filter on rather than as an exception to catch.

Now the stop list, which is deliberately outside the state:

class Car {
  private state: CarState;
  private stops = new Set<Floor>();
}

The stops survive every transition. A car moving, opening its doors, closing them and moving again has the same commitments throughout, minus the floor it just served. Putting them inside the state would mean copying the set into every new state value on every transition, for no benefit, and it would blur the distinction between what the car is doing and what it has promised to do.

It is a Set rather than a queue, and that is a design statement. The order the buttons were pressed does not determine the order of stops — the sweep does — so keeping arrival order would be storing information the design has decided to ignore, which invites somebody later to use it.

And the car is driven by ticks, not by waiting. tick(now) performs one transition and returns. Nothing blocks on hardware, nothing sleeps, and time arrives as a parameter. That is what makes the whole system replayable from a recorded list of events, which is the property section 8 turns into a way of choosing policies.

AppliedA car at floor 1 has stops at 3, 9, 2 and 8, pressed in that order. Compare press order with sweeping, then implement the sweep.

Press order, floor by floor. 1→3 is 2 floors. 3→9 is 6. 9→2 is 7. 2→8 is 6. Twenty-one floors.

Sweeping upwards. 1→2→3→8→9. Eight floors.

But the total distance is not the main point. Look at the person who pressed 2. Under press order they watch the car pass floor 2 on its way to 9, then come back — the worst possible experience, and one that makes people press the button repeatedly and then complain that the lift is broken. Under the sweep they are served second. Press order does not merely travel further; it produces waits that are unpredictable and visibly unfair, and the visible unfairness is what generates complaints.

The sweep in code:

function nextTarget(current: Floor, dir: Direction, stops: Set<Floor>): Floor | null {
  const ahead = [...stops].filter(f => dir === "up" ? f > current : f < current);
  if (ahead.length > 0)
    return dir === "up" ? Math.min(...ahead) : Math.max(...ahead);

  const behind = [...stops].filter(f => dir === "up" ? f < current : f > current);
  if (behind.length > 0)
    return dir === "up" ? Math.max(...behind) : Math.min(...behind);

  return null;
}

The nearest floor ahead is next. Going up, that is the smallest floor above the car; going down, the largest below. Those two lines produce the entire sweeping behaviour, and there is no separate notion of a "route" anywhere in the design.

When nothing is ahead, take the furthest floor behind. That looks backwards for a moment and is right: after reversing, the furthest one is the far end of the new sweep, and everything between it and here will be collected on the way. Taking the nearest one behind would mean reversing again almost immediately, which is exactly the thrashing the sweep exists to remove.

One rule the code above does not show and the design needs. A car travelling up should only pick up hall calls whose direction is up. A "down" press on floor 5 is not served by a car passing 5 on its way to 9 — those passengers want to go down, and stopping for them wastes a door cycle for everybody. It is served on the way back. The direction on the hall call is what makes this expressible, which is why the two kinds of request had to be separate entities.

This is the disk-head scheduling algorithm from 2.7, which is literally called the elevator algorithm because it was named after this problem. The connection is real rather than cute: both are a physical head that is expensive to reverse, serving requests scattered along a single axis, and both discover that committing to a direction beats optimising each request individually.

And the sweep's weakness, which should be said unprompted. In a building with sustained upward traffic, a lone "down" call on a low floor can wait a very long time, because there is always another up call ahead of it. Pure sweeping has no mechanism to stop that. The fix is aging — a call's priority rises with its wait, and past a threshold it is served next regardless of direction — and the practical form is a hard cap such as "no call waits more than 90 seconds", because that is a promise a building manager can check. This is the same starvation problem and the same cure as process scheduling in 2.3, and the vocabulary transfers exactly.

InterviewFour cars, one hall call on floor 3 going up. Car A is on 1 going up, car B is idle on 4, car C is on 2 going down to the basement, car D is full on 7. Which do you send, and what is the general rule?

Take the cars in turn, because the reasoning is the answer.

Car D is removed before any scoring. It is full, so it cannot take the passenger. Sending it produces a lift that arrives, opens, and helps nobody, while the people inside lose ten seconds. Eligibility is a filter, not a penalty.

Car C is one floor away and is the worst remaining choice. It is going down and committed to the basement, so it must finish that trip and reverse before it can reach floor 3. Physical distance says C; arrival time says C is last. This car is why "nearest" is the wrong rule.

Car B is idle on floor 4, one floor above. It can start immediately, but it must come down to floor 3 and then go up, which means a direction change and a passenger who watches the lift approach from the wrong side.

Car A is on floor 1 going up, two floors away, already heading the right way. It will pass floor 3 anyway. Picking it up costs one extra stop, and the passenger boards a car already travelling in the direction they want.

Send car A, unless it has several committed stops between 1 and 3, in which case B becomes competitive — and that "unless" is exactly why this is a cost function rather than a rule.

private cost(call: HallCall, c: CarSnapshot): number {
  const distance = Math.abs(c.floor - call.floor);
  const wrongWay = c.direction !== null && c.direction !== call.direction
                 && this.wouldPass(c, call);
  return distance
       + (wrongWay ? REVERSAL_PENALTY : 0)
       + c.stopsBetween(c.floor, call.floor) * STOP_PENALTY
       + (c.load / c.capacity) * LOAD_PENALTY;
}

Each term earns its place.

Distance is the obvious term and the least important. One floor takes a couple of seconds.

The reversal penalty is what makes this better than "nearest". A car going the wrong way must finish its current commitments first, and that is usually far more expensive than a few floors of travel. This single term is the difference between the naive answer and a working one.

Stops in between matter more than distance, because a door cycle is five to ten seconds and a floor of travel is two. A close car with three intervening stops arrives later than a distant car with none.

Load penalises a nearly full car, because it might not be able to take the passenger at all, and arriving unable to help is worse than arriving late.

The general rule, stated as the answer: dispatch minimises expected time until this passenger is inside a car going where they want, and every term in the cost function is an estimate of part of that time. Distance estimates travel; the reversal penalty estimates the remaining commitments; the stop penalty estimates door cycles; the load penalty estimates the risk of arriving useless.

The constants belong in configuration, not in the code, because a REVERSAL_PENALTY of 10 is right for an office tower and 4 for a small block, and no amount of reasoning settles which. That is what section 8 exists for: replay a recorded day under both values and look at the 95th percentile wait.

One failure this creates, worth naming unprompted. If car A becomes full before reaching floor 3, it hands the call back. If the dispatcher then reassigns it to A because A is still nearest, and A declines again, the call bounces forever — busy and making no progress, which is livelock (9.5.3). The cure is one line: a car is excluded from a call it has just declined, for a short period. It is easy to add and very confusing to watch when it is missing.

StaffThe building manager wants a morning rush mode, energy saving at night, and proof that either is actually better. What do you build, and what do you refuse to guess?

Start by separating the two kinds of request, because only one of them is a design change. Morning rush and energy saving are policies, and the design already has a place for them. "Proof that either is better" is a capability the system does not have yet, and it is the most valuable thing in the question.

Morning rush mode is one class.

class UpPeakPolicy implements DispatchPolicy { /* … */ }

Two behaviours change and neither touches a car. Idle cars return to the lobby instead of waiting where they last stopped, because in the morning the next call is almost certainly from the ground floor and a car already there answers instantly. And lobby calls are weighted heavily in the cost function, so a car will accept a longer trip to serve the lobby. Nothing about the sweep, the doors or the state machine is involved.

Evening rush is not the morning policy reversed, and saying so is worth a moment. In the morning everybody boards at one floor and scatters; in the evening they board at many floors and converge. So the morning policy gathers cars at the lobby and the evening policy spreads them across the building. Two different classes, both behind the same interface.

Energy saving at night is a third policy plus one small system rule. Fewer cars are kept in service, so the others are genuinely parked rather than repositioned; idle cars stop returning anywhere; and the dispatcher tolerates longer waits because a thirty-second wait at 3am costs nothing and repositioning empty cars all night costs real money. The system rule is that a parked car must rejoin service instantly when a call arrives, which means "parked" is a dispatcher-level availability decision rather than a new car state — the car is simply idle and not being chosen.

Switching between them is itself a policy, chosen by time of day, and it is worth making that explicit rather than hard-coding times: a selector reads a schedule and swaps the active policy. A building manager changing the morning window from 08:00 to 07:30 should be editing configuration, not waiting for a release.

Now the part that matters, which is what I would refuse to guess. Whether up-peak mode is better is an empirical question, and answering it by intuition is how buildings end up with a mode that makes things worse and that nobody dares turn off. So the system must be able to replay a recorded day of traffic under a different policy.

Four properties make that possible, and three are already in the design:

Everything arrives as an event. No blocking calls into hardware, so a day's presses replay in seconds.

Time is injected. tick(now) takes the time rather than reading a clock, so a replay runs at any speed.

Cars are actors with no shared hidden state, so the same input produces the same output.

And any randomness must be seeded — the one thing to add — so two policies are compared on identical traffic rather than on two similar days.

Then the question becomes a measurement, and the metrics have to be chosen carefully. The median wait is nearly useless, because nobody notices a good average. The numbers that matter are the 95th percentile wait, which is what people complain about; the count of calls waiting more than 60 seconds, which is the complaint threshold in most buildings; the total distance travelled by all cars, which is the energy bill; and the number of times a call was reassigned, which reveals a policy fighting itself.

This is the same discipline as the exchange in 9.7.25 — events in, a pure step function, no hidden clock — arriving for a completely different reason. There it exists so a trade can be proved to a regulator; here so a policy can be argued about with data instead of opinions. The engineering habit is identical, and pointing that out is a stronger answer than describing either case alone.

One requirement I would push back on if it appeared: firefighter recall as "just another mode". It is not a policy. It is a state with different physics that outranks everything — every car goes to the ground floor, opens its doors and ignores all calls — and it belongs in the car's state machine rather than in the dispatcher, because it changes what the car does rather than which car is chosen. It is also almost always governed by regulation rather than by the building manager's preferences. Being able to say "this one restructures the safety-critical part, and here is why it must" is more valuable than claiming every requirement fits a seam, because a design whose seams absorb everything usually has seams in the wrong places.

What I would monitor once it is running. The 95th percentile wait per hour, which shows immediately whether the morning window is set correctly; calls waiting over 60 seconds, which should be near zero outside peaks; cars out of service and for how long, since one car down changes every number above; and reassignment counts, because a rise means cars are declining calls and the load penalty needs tuning.

Flashcards

FlashTwo kinds of button

Hall calls carry a direction and are assigned by a dispatcher; car calls have no direction and can never be reassigned. A full car refuses hall calls and keeps serving car calls — the rule that needs both entities to exist.

FlashWhy doors live in the state

So "moving with the doors open" is unrepresentable rather than merely checked. And doorsClosing is a real state, because a hand in the doors has to send the car back to opening.

FlashPress order versus sweeping

Stops at 3, 9, 2, 8 from floor 1: 21 floors in press order, 8 swept. Keep going one way, serve everything en route, reverse only when nothing is ahead. Same algorithm as the disk-head scheduler named after it.

FlashWhy nearest car is wrong

It picks the car travelling the other way. The cost function charges for distance, a reversal penalty, committed stops in between, and load — and the reversal penalty is what makes it better than distance alone.

FlashThe sweep can starve

Sustained traffic one way leaves a lone opposite call waiting. Fix with aging and a hard cap — 90 seconds — the same starvation problem and cure as process scheduling.

FlashReplay is how you choose a policy

Events in, injected time, seeded randomness. Then two policies run against yesterday's recorded traffic and are compared on the 95th percentile wait, not the average — because nobody notices a good average.

Next: 9.7.4 — the parking lot, where choosing a space and winning one turn out to be two different operations.