Design a Lift System | androidinterview.com

A lift system is two decisions. Which car answers a call, and where a car goes next. Keep them apart and the design is small. Mix them together and you end up with one class that knows everything and can be changed by nobody.

The best question you can ask here is whether you are building a simulation or software that drives real hardware. The answer is always a simulation, and asking is a senior signal, because it lets you replace real time with a tick and makes the whole thing testable.

What to clarify first

Simulation or hardware. Ask this first. A simulation means a step method and no threads, which is a far better artifact for an interview.
How many cars and how many floors. Three cars and ten floors is the usual answer, and fixed is fine.
Hall calls or destination dispatch. Classic hall calls, where you press up or down in the lobby and the system picks a car, is the default. Destination dispatch, where you type your floor in the lobby, is a different and more modern problem.
Do hall calls carry a direction. They do, and this is the answer that shapes the whole model. Confirm it out loud.
Can a passenger press several floors. Yes, so a car holds a set of requests and not a single target.
What is out of scope. Weight sensors, door mechanics, emergency stop, fire service mode. Say them, because each one is a class you are not going to write.

Then say what you are optimising for. Short waits, no unnecessary reversals, and no floor left waiting forever. That sentence gives you something to judge your algorithm against later.

The classes

There are five, and each one has a job you can say in a sentence.

Direction is an enum of up, down and idle. Idle is a real value, not a null, because a parked car has no direction and you want that to be sayable.
Request is a floor plus what the caller wants to do there. It is the most important class in the design and the one most candidates get wrong.
Elevator is one car. It owns where it is, which way it is going, the set of requests it has been given, and a small inbox that new requests land in. It moves one tick at a time and never decides which car serves a call.
ElevatorSelectionStrategy picks the car for a hall call. It is the one real seam here.
ElevatorSystem is the controller and the only thing the buttons talk to. It owns the cars, the dispatch policy, and a queue of hall calls waiting to be assigned.

Why Request is a class and not an int. A car going up arrives at floor seven. Should it stop. It depends on what the person on floor seven wants. If they are waiting to go up, yes. If they are waiting to go down, no, because they would be carried the wrong way, and the car should collect them on the way back.

You cannot express that with a bare floor number. So a request carries its intent, one of waiting to go up, waiting to go down, or a destination pressed inside the car. A destination has no direction of its own, because that passenger is already inside and is happy whichever way the car is going.

There is a second benefit that comes free. A request is a value, so two people pressing the same lobby button produce the same request, and storing requests in a set means the duplicate disappears without a line of code.

Why floors stay integers. A Floor class would hold a number and nothing else. Skip it, and say you skipped it on purpose.

The controller owns the cars and routes calls, the car owns all the movement, and the request carries the direction its caller wants, which is the one arrow that makes the sweep decidable.

How the car actually moves

The algorithm is SCAN, which is the one people mean when they say the elevator algorithm. Say it in one sentence before you write any code. Keep sweeping the way you are already going, stopping at every floor that wants that direction, until nothing is left ahead, and only then turn round.

One tick does exactly four things, in this order.

If there is nothing to do, the car goes idle and stops there.
If the car is idle and something arrives, it takes the direction of the nearest request.
If this floor has a request the current sweep can serve, the doors open and every request at this floor that matches is cleared. The stop costs the tick, which is also true of a real lift.
Otherwise, if nothing is left ahead, the car reverses. If something is ahead, it moves one floor and the tick ends.

This is the whole SCAN sweep, and the reason the answer stores it as one direction field and a doors flag rather than three state classes is that the loop reads the same in both directions.

Now argue for it, because the argument is where the marks are.

First come first served sends the car back and forth across the building. It is easy to write and horrible to ride.
Nearest request first looks clever and still reverses constantly, and a distant floor can wait forever while nearby calls keep arriving.
SCAN sweeps predictably. Someone watching the indicator sees the car coming towards them and it actually arrives, and no floor starves, because every sweep eventually reaches the end.

How a call is served, end to end

Somebody on floor seven presses down. The controller turns that into a request carrying the down intent and puts it on a queue. Nothing else happens yet.

On the next tick the controller drains the queue into a list. For each waiting call it asks the strategy which car should take it, and drops the request into that car's inbox. Assignment happens once, at the top of a tick, so no car is being given work while it is moving.

Then every car steps once. A car that was given the call empties its inbox into its request set, picks a direction if it was idle, and starts sweeping. When it reaches floor seven going down, the request matches the sweep, the doors open, and the request is cleared.

The passenger gets in and presses floor one. That is a destination request, and the controller drops it straight into that car's inbox, because there is no decision to make. It is already the right car.

Note what the controller never does. It never moves anything and it never decides where a car goes next. It routes calls and it ticks. All the movement lives in the car.

Patterns actually used

Strategy, for dispatch, and it is the only pattern here that earns its place. Which car answers a call is genuinely a policy, and it is the thing an interviewer changes on you. Two implementations ship, and the difference between them is the ladder of answers to this problem.

Nearest car picks whichever car is fewest floors away. It is the junior answer and it is a fine starting point.
Direction aware charges a car nothing extra when it is already sweeping towards you in your direction, because it will pass your floor anyway, and charges a large penalty otherwise, because that car has to finish its sweep and come back.

The senior version of this goes one step further. Check that the car's own queue actually extends to or past your floor, so you never assign a car that is going to reverse two floors before it reaches you. Say that even if you do not write it.

State, considered and left out. Plenty of write ups give the car an idle state, a moving up state and a moving down state. It works, and here it buys very little. The behaviour is the same sweep in both directions, with the sign of one addition and the meaning of the word ahead flipped. A direction field expresses that in one line, and three classes express it in thirty.

Say you considered it and say what would change your mind. Doors opening, maintenance mode and fire service are genuinely different behaviours for the same operation, and if any of those come into scope the state classes start earning their keep.

Observer, considered and left out. The lobby indicator is the usual home for it. In a simulation the controller drives the tick, so anything that wants to draw the building can simply read the cars after each step, and a listener buys nothing.

It flips the moment the cars run on their own threads, because then there is no tick for the display to hook into and the car has to push. Naming that condition is more valuable than adding the interface.

No singleton. One building has one controller, which is true and useless. It costs you the test that runs two buildings.

The implementation

The interesting method is Elevator.step, and it is the only one worth memorising. The Kotlin version writes the same sweep as a single when over three cases, which is a fair bit shorter than the Java and reads closer to the way you would say it out loud.

Java

com.androidinterview.lift.controller.ElevatorSystem.java

package com.androidinterview.lift.controller;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

import com.androidinterview.lift.elevator.Elevator;
import com.androidinterview.lift.model.Direction;
import com.androidinterview.lift.model.Request;
import com.androidinterview.lift.strategy.ElevatorSelectionStrategy;

// The building's controller, and the only thing the buttons talk to. It owns
// the cars, the dispatch policy and the queue of hall calls waiting to be
// assigned. It owns no movement logic at all.
public final class ElevatorSystem {

    private final List<Elevator> cars;
    private final ElevatorSelectionStrategy dispatch;

    // Hall calls land here from whatever thread pressed the button, and are
    // drained at the top of a tick. A queue rather than a lock, so pressing a
    // button never waits for a car to finish moving.
    private final Queue<Request> waiting = new ConcurrentLinkedQueue<>();

    public ElevatorSystem(List<Elevator> cars, ElevatorSelectionStrategy dispatch) {
        this.cars = List.copyOf(cars);
        this.dispatch = dispatch;
    }

    // Someone in the lobby presses up or down.
    public void requestElevator(int floor, Direction direction) {
        if (direction == Direction.IDLE) {
            throw new IllegalArgumentException("a hall call has to have a direction");
        }
        Request.Type type = direction == Direction.UP ? Request.Type.PICKUP_UP : Request.Type.PICKUP_DOWN;
        waiting.add(new Request(floor, type));
    }

    // Someone inside a car presses a floor. No dispatch decision to make, the
    // passenger is already in that car, so it goes straight into that car's
    // inbox. The inbox is concurrent and the car folds it into its request set
    // at the top of its own step, so a button thread never touches the set the
    // sweep is iterating.
    public void selectFloor(int carId, int floor) {
        car(carId).add(new Request(floor, Request.Type.DESTINATION));
    }

    // One tick of the building. Assign everything that came in since the last
    // tick, then move every car once.
    //
    // Drain into a local list first. Re-adding an unassigned call to the queue
    // while polling that same queue would hand it straight back to poll, and
    // the loop would never end.
    public void step() {
        List<Request> unassigned = new ArrayList<>();
        Request request;
        while ((request = waiting.poll()) != null) {
            Request call = request;
            dispatch.select(cars, call).ifPresentOrElse(car -> car.add(call), () -> unassigned.add(call));
        }
        waiting.addAll(unassigned); // every car was busy, so these wait for the next tick
        cars.forEach(Elevator::step);
    }

    // For the display and for tests. The cars are live objects, so this is a
    // simulation hook and not something a button handler should hold.
    public List<Elevator> cars() {
        return cars;
    }

    private Elevator car(int id) {
        return cars.stream()
                .filter(car -> car.id() == id)
                .findFirst()
                .orElseThrow(() -> new IllegalArgumentException("no car " + id));
    }
}

com.androidinterview.lift.elevator.Elevator.java

package com.androidinterview.lift.elevator;

import java.util.Comparator;
import java.util.LinkedHashSet;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ConcurrentLinkedQueue;

import com.androidinterview.lift.model.Direction;
import com.androidinterview.lift.model.Request;

// One car. It owns where it is, which way it is going, and the requests it has
// been given. It does not choose which car serves a hall call, that is the
// controller's job with a strategy.
//
// There are no threads here. The car moves when someone calls step, which
// makes the whole simulation deterministic and testable. Say that you would
// give each car its own thread only if you were driving real hardware.
public final class Elevator {

    private final int id;

    // Requests arrive from whatever thread pressed the button and land in the
    // inbox. Only step touches the request set, so the sweep never iterates a
    // set another thread is writing to.
    private final Queue<Request> inbox = new ConcurrentLinkedQueue<>();
    private final Set<Request> requests = new LinkedHashSet<>();

    private int currentFloor;
    private Direction direction = Direction.IDLE;
    private boolean doorsOpen;

    public Elevator(int id, int currentFloor) {
        this.id = id;
        this.currentFloor = currentFloor;
    }

    public int id() {
        return id;
    }

    public int currentFloor() {
        return currentFloor;
    }

    public Direction direction() {
        return direction;
    }

    public boolean doorsOpen() {
        return doorsOpen;
    }

    // Safe from any thread. The request is folded into the set at the top of
    // the next step, and the set dedupes the same hall call pressed twice.
    public void add(Request request) {
        inbox.add(request);
    }

    // One tick of the SCAN algorithm, and the only method in this problem
    // worth memorising.
    //
    // Keep sweeping the way we are already going, stopping at every floor that
    // wants this direction, until there is nothing left ahead. Then turn
    // round. That is what makes a lift predictable, someone watching the
    // indicator sees it coming towards them and it actually arrives.
    public void step() {
        drainInbox();
        doorsOpen = false;
        if (requests.isEmpty()) {
            direction = Direction.IDLE;
            return;
        }
        if (direction == Direction.IDLE) {
            direction = directionOfNextRequest();
        }
        if (shouldStopHere()) {
            serveHere();
            return;
        }
        if (!hasWorkAhead()) {
            // Nothing left this way, so turn round. The turn costs a tick,
            // which is also true of a real lift.
            direction = direction.opposite();
            return;
        }
        currentFloor += direction == Direction.UP ? 1 : -1;
    }

    private void drainInbox() {
        Request request;
        while ((request = inbox.poll()) != null) {
            requests.add(request);
        }
    }

    // Stop only for requests this sweep can serve. A destination always
    // counts, a hall call only if it wants to go the way we are going.
    private boolean shouldStopHere() {
        return requests.stream().anyMatch(this::servedBySweep);
    }

    private void serveHere() {
        requests.removeIf(this::servedBySweep);
        doorsOpen = true;
    }

    private boolean servedBySweep(Request request) {
        return request.floor() == currentFloor
                && (request.type() == Request.Type.DESTINATION || request.type().travel == direction);
    }

    private boolean hasWorkAhead() {
        return requests.stream()
                .anyMatch(request -> direction == Direction.UP
                        ? request.floor() > currentFloor
                        : request.floor() < currentFloor);
    }

    // Only decides which way to leave idle. Nearest is a tie break here and
    // nothing more, because once the car is moving the sweep runs to the end
    // and every request in that direction gets served on the way.
    private Direction directionOfNextRequest() {
        Request next = requests.stream()
                .min(Comparator.comparingInt(request -> Math.abs(request.floor() - currentFloor)))
                .orElseThrow();
        if (next.floor() > currentFloor) {
            return Direction.UP;
        }
        if (next.floor() < currentFloor) {
            return Direction.DOWN;
        }
        // Someone is waiting on the floor we are parked on, so take their
        // direction and open the doors on the next tick.
        return next.type().travel == Direction.IDLE ? Direction.UP : next.type().travel;
    }
}

com.androidinterview.lift.model.Direction.java

package com.androidinterview.lift.model;

public enum Direction {
    UP,
    DOWN,
    IDLE;

    public Direction opposite() {
        return this == UP ? DOWN : this == DOWN ? UP : IDLE;
    }
}

com.androidinterview.lift.model.Request.java

package com.androidinterview.lift.model;

// A floor and what the caller wants to do there. Storing the intent as well as
// the number is the modelling decision that makes the whole thing work.
//
// A car going up that reaches floor seven stops for someone waiting to go up
// and for anyone whose destination is seven. It drives past someone waiting to
// go down, and comes back for them on the way. With a bare int you cannot tell
// those apart, and you pick up passengers travelling the wrong way.
//
// It is a record, so two identical hall calls are equal, and a Set of requests
// dedupes two people pressing the same button for free.
public record Request(int floor, Type type) {

    public enum Type {
        PICKUP_UP(Direction.UP),
        PICKUP_DOWN(Direction.DOWN),
        // Pressed inside the car. It has no direction of its own, the car
        // stops for it whichever way it happens to be going.
        DESTINATION(Direction.IDLE);

        public final Direction travel;

        Type(Direction travel) {
            this.travel = travel;
        }
    }
}

com.androidinterview.lift.strategy.ElevatorSelectionStrategy.java

package com.androidinterview.lift.strategy;

import java.util.Comparator;
import java.util.List;
import java.util.Optional;

import com.androidinterview.lift.elevator.Elevator;
import com.androidinterview.lift.model.Direction;
import com.androidinterview.lift.model.Request;

// Which car answers a hall call. This is the rule buildings actually change,
// for rush hour, for express cars, for saving power overnight, and it is the
// rule the interviewer will ask you to change. So it is the one real seam in
// the design.
public interface ElevatorSelectionStrategy {

    Optional<Elevator> select(List<Elevator> cars, Request request);

    // The naive answer, and a fine place to start. Whichever car is fewest
    // floors away, ignoring which way it is going.
    static ElevatorSelectionStrategy nearestCar() {
        return (cars, request) -> cars.stream()
                .min(Comparator.comparingInt(car -> Math.abs(car.currentFloor() - request.floor())));
    }

    // The better answer. A car already sweeping towards you in your direction
    // will pass your floor anyway, so it is nearly free. Any other car has to
    // finish its sweep and come back, so it is charged a penalty larger than
    // any building is tall.
    static ElevatorSelectionStrategy directionAware() {
        return (cars, request) -> cars.stream().min(Comparator.comparingInt(car -> cost(car, request)));
    }

    private static int cost(Elevator car, Request request) {
        int distance = Math.abs(car.currentFloor() - request.floor());
        if (car.direction() == Direction.IDLE) {
            return distance;
        }
        boolean onTheWay = car.direction() == Direction.UP
                ? request.floor() >= car.currentFloor()
                : request.floor() <= car.currentFloor();
        boolean sameWay = request.type().travel == car.direction();
        return onTheWay && sameWay ? distance : distance + 1000;
    }
}

Kotlin

com.androidinterview.lift.controller.ElevatorSystem.kt

package com.androidinterview.lift.controller

import java.util.concurrent.ConcurrentLinkedQueue

import com.androidinterview.lift.elevator.Elevator
import com.androidinterview.lift.model.Direction
import com.androidinterview.lift.model.Request
import com.androidinterview.lift.model.RequestType
import com.androidinterview.lift.strategy.ElevatorSelectionStrategy

// The building's controller, and the only thing the buttons talk to. It owns
// the cars, the dispatch policy and the hall calls waiting to be assigned. It
// owns no movement logic at all.
//
// cars is public for the display and for tests. They are live objects, so it
// is a simulation hook and not something a button handler should hold.
class ElevatorSystem(
    val cars: List<Elevator>,
    private val dispatch: ElevatorSelectionStrategy,
) {
    // Hall calls land here from whatever thread pressed the button and are
    // drained at the top of a tick. A queue rather than a lock, so pressing a
    // button never waits for a car to finish moving.
    private val waiting = ConcurrentLinkedQueue<Request>()

    // Someone in the lobby presses up or down.
    fun requestElevator(floor: Int, direction: Direction) {
        require(direction != Direction.IDLE) { "a hall call has to have a direction" }
        val type = if (direction == Direction.UP) RequestType.PICKUP_UP else RequestType.PICKUP_DOWN
        waiting += Request(floor, type)
    }

    // Someone inside a car presses a floor. There is no dispatch decision to
    // make, the passenger is already in that car, so it goes straight into that
    // car's inbox. The inbox is concurrent and the car folds it into its
    // request set at the top of its own step, so a button thread never touches
    // the set the sweep is iterating.
    fun selectFloor(carId: Int, floor: Int) {
        car(carId).add(Request(floor, RequestType.DESTINATION))
    }

    // One tick of the building. Assign everything that arrived since the last
    // tick, then move every car once.
    //
    // Drain into a list first. Re-adding an unassigned call to the queue while
    // polling that same queue would hand it straight back to poll, and the
    // loop would never end.
    fun step() {
        val arrived = generateSequence { waiting.poll() }.toList()
        for (request in arrived) {
            val car = dispatch.select(cars, request)
            if (car != null) car.add(request) else waiting += request // every car busy, try next tick
        }
        cars.forEach(Elevator::step)
    }

    private fun car(id: Int) = cars.first { it.id == id }
}

com.androidinterview.lift.elevator.Elevator.kt

package com.androidinterview.lift.elevator

import java.util.concurrent.ConcurrentLinkedQueue
import kotlin.math.abs

import com.androidinterview.lift.model.Direction
import com.androidinterview.lift.model.Request
import com.androidinterview.lift.model.RequestType

// One car. It owns where it is, which way it is going and the requests it was
// given. It never chooses which car answers a hall call, the controller does
// that with a strategy.
//
// No threads. The car moves when someone calls step, which makes the whole
// simulation deterministic and easy to test. Threads per car belong in the
// version that drives real hardware.
class Elevator(val id: Int, startFloor: Int = 0) {

    // Requests arrive from whatever thread pressed the button and land in the
    // inbox. Only step touches the request set, so the sweep never iterates a
    // set another thread is writing to.
    private val inbox = ConcurrentLinkedQueue<Request>()
    private val requests = linkedSetOf<Request>()

    var currentFloor: Int = startFloor
        private set
    var direction: Direction = Direction.IDLE
        private set
    var doorsOpen: Boolean = false
        private set

    // Safe from any thread. The request is folded into the set at the top of
    // the next step, and the set dedupes the same hall call pressed twice.
    fun add(request: Request) {
        inbox += request
    }

    // One tick of the SCAN algorithm, and the only method in this problem
    // worth memorising.
    //
    // Keep sweeping the way we are already going, stopping at every floor that
    // wants this direction, until nothing is left ahead. Then turn round. That
    // is what makes a lift predictable, someone watching the indicator sees it
    // coming towards them and it actually arrives.
    fun step() {
        requests += generateSequence { inbox.poll() }
        doorsOpen = false
        if (requests.isEmpty()) {
            direction = Direction.IDLE
            return
        }
        if (direction == Direction.IDLE) direction = directionOfNextRequest()

        when {
            requests.any { it.servedBySweep() } -> {
                requests.removeAll { it.servedBySweep() }
                doorsOpen = true
            }
            // Nothing left this way, so turn round. The turn costs a tick,
            // which is also true of a real lift.
            !hasWorkAhead() -> direction = direction.opposite
            else -> currentFloor += if (direction == Direction.UP) 1 else -1
        }
    }

    // Stop only for what this sweep can serve. A destination always counts, a
    // hall call only when it wants to go the way we are going.
    private fun Request.servedBySweep() =
        floor == currentFloor && (type == RequestType.DESTINATION || type.travel == direction)

    private fun hasWorkAhead() = requests.any {
        if (direction == Direction.UP) it.floor > currentFloor else it.floor < currentFloor
    }

    // Only decides which way to leave idle. Nearest is a tie break here and
    // nothing more, because once the car is moving the sweep runs to the end
    // and every request in that direction gets served on the way.
    private fun directionOfNextRequest(): Direction {
        val next = requests.minBy { abs(it.floor - currentFloor) }
        return when {
            next.floor > currentFloor -> Direction.UP
            next.floor < currentFloor -> Direction.DOWN
            // Someone is waiting on the floor we are parked on, so take their
            // direction and open the doors on the next tick.
            next.type.travel == Direction.IDLE -> Direction.UP
            else -> next.type.travel
        }
    }
}

com.androidinterview.lift.model.Direction.kt

package com.androidinterview.lift.model

// Idle is a real value and not a null, because a parked car has no direction
// and that needs to be sayable.
enum class Direction {
    UP,
    DOWN,
    IDLE;

    val opposite: Direction
        get() = when (this) {
            UP -> DOWN
            DOWN -> UP
            IDLE -> IDLE
        }
}

com.androidinterview.lift.model.Request.kt

package com.androidinterview.lift.model

// A hall call carries the way the caller wants to travel. A cabin button does
// not, because the passenger is already inside and the car stops whichever way
// it is going.
enum class RequestType(val travel: Direction) {
    PICKUP_UP(Direction.UP),
    PICKUP_DOWN(Direction.DOWN),
    DESTINATION(Direction.IDLE),
}

// A floor and what the caller wants to do there. Storing the intent as well as
// the number is the modelling decision that makes the whole thing work.
//
// A car going up that reaches floor seven stops for someone waiting to go up
// and for anyone whose destination is seven. It drives past someone waiting to
// go down and comes back for them. A bare Int cannot tell those apart.
//
// A data class, so two identical hall calls are equal and a Set dedupes two
// people pressing the same button for nothing.
data class Request(val floor: Int, val type: RequestType)

com.androidinterview.lift.strategy.Dispatch.kt

package com.androidinterview.lift.strategy

import kotlin.math.abs

import com.androidinterview.lift.elevator.Elevator
import com.androidinterview.lift.model.Direction
import com.androidinterview.lift.model.Request

// Which car answers a hall call. This is the rule buildings really change, for
// rush hour, for express cars, for saving power overnight, and it is the rule
// the interviewer will ask you to change. One method, so a fun interface.
fun interface ElevatorSelectionStrategy {
    fun select(cars: List<Elevator>, request: Request): Elevator?
}

// The naive answer, and a fine place to start. Fewest floors away, ignoring
// which way each car is going.
val nearestCar = ElevatorSelectionStrategy { cars, request ->
    cars.minByOrNull { abs(it.currentFloor - request.floor) }
}

// The better answer. A car already sweeping towards you in your direction will
// pass your floor anyway, so it is nearly free. Any other car has to finish
// its sweep and come back, so it pays a penalty larger than any building is
// tall.
val directionAware = ElevatorSelectionStrategy { cars, request ->
    cars.minByOrNull { car ->
        val distance = abs(car.currentFloor - request.floor)
        if (car.direction == Direction.IDLE) return@minByOrNull distance
        val onTheWay = if (car.direction == Direction.UP) {
            request.floor >= car.currentFloor
        } else {
            request.floor <= car.currentFloor
        }
        val sameWay = request.type.travel == car.direction
        if (onTheWay && sameWay) distance else distance + 1_000
    }
}

Concurrency and edge cases

Simultaneous lift requests. Two people press buttons on different floors at the same moment, from two different threads, while a car is halfway through moving. If the button handler reaches into the car directly, you have two threads writing the same request set, and one of the calls can be lost.

There are two honest answers, and you should name both.

One lock around the tick and the button. Correct, easy to explain, and it makes pressing a button wait for a car to finish moving. Under load the lobby buttons feel sticky.
A concurrent queue that buttons write to and the tick drains. No lock is taken by a button press, assignment happens at one known point in the cycle, and the whole thing stays deterministic. This is what the implementation does, twice. Hall calls go on the controller's queue, and cabin buttons go into the car's own inbox, which the car empties into its request set at the top of its step. No button thread ever touches the set the sweep is iterating.

Then say the deeper reason the queue is better. It gives assignment a single moment in time, so a car cannot be given a new request halfway through deciding where to go. Correctness by scheduling beats correctness by locking whenever you can arrange it.

The same call pressed twice. Two people on floor four both press up. Requests are values and a car holds a set, so the duplicate disappears. That is the second reason the request is a class.

The same call assigned to two cars. This is the one to watch. If the request is still in the queue and gets assigned again on the next tick, two cars come for one person. Draining the queue and assigning in one pass, before any car moves, is what prevents it.

Other cases worth a sentence each.

A call for the floor the car is parked on. The car takes that request's direction and opens the doors on the next tick rather than moving away and coming back.
An invalid floor. Reject at the controller. Nothing invalid should ever reach a car.
Every car busy. Queue the call, never drop it. The implementation drains the queue into a list, assigns what it can, and puts the rest back on the queue for the next tick. Draining into a list first matters, because putting a call back on the queue you are still polling hands it straight back to you and the loop never ends.
A full car. It must skip pickups and still honour the destinations of the people inside it. That is a filter on which requests the sweep can serve, not a new state.
A car taken out of service mid trip. Reassign its hall calls to other cars, but not its destinations. Those passengers are inside that car and are going where it goes.
Starvation during rush hour. SCAN protects you here, because a sweep always runs to the end. A nearest first algorithm does not, and that is the strongest argument against it.