androidinterview.com

Low Level Design (LLD) Interview Questions

Design a Lift System

Tier: EssentialDifficulty: MediumAsked of: Mid, SeniorAsked at: Amazon, Microsoft, Uber, Google, Adobe, Lyft

Design the controller for a lift that receives destination floors and stops at those floors to let passengers out.

The problem

A lift starts on floor 0. Passengers request floors 3 and 5. It moves up, stops at 3, continues to 5 and then becomes idle. Duplicate requests for floor 3 should create only one stop.

Start with one lift and destination requests. Each simulation step moves at most one floor. Door timing, passenger limits, hall call directions and choosing among several lifts are follow-ups.

How to explain the design

“I store the current floor, direction and a sorted set of requested stops. The lift continues in its current direction while there are requests ahead. When there are none, it reverses. Reaching a requested floor removes that request and reports a stop.”

Lift owns these three pieces of state. The sorted set removes duplicates and lets us find whether there is a request above or below the current floor.

Walk through a trip

  1. Add floors 3 and 5 to the stop set.
  2. Call step until the lift reaches 3. That step returns 3 and removes the request.
  3. Continue stepping. The lift reaches and reports floor 5.
  4. With no requests left, later steps leave it where it is.
  5. If floor 1 is requested, it reverses and travels down.

Interview implementation

A null result means the step did not stop at a requested floor. Keep requests and stepping on one controller thread.

Java

Lift.java

package interview.lift;

import java.util.TreeSet;

public class Lift {
    private final int topFloor;
    private int floor;
    private int direction = 1;
    private final TreeSet<Integer> stops = new TreeSet<>();

    public Lift(int topFloor) {
        if (topFloor < 0) throw new IllegalArgumentException("Invalid top floor");
        this.topFloor = topFloor;
    }

    public int floor() { return floor; }

    public void request(int destination) {
        if (destination < 0 || destination > topFloor) throw new IllegalArgumentException("Invalid floor");
        stops.add(destination);
    }

    // Move one floor. Return a floor only when we stop there.
    public Integer step() {
        if (stops.remove(floor)) return floor;
        if (stops.isEmpty()) return null;
        if (direction == 1 && stops.higher(floor) == null) direction = -1;
        if (direction == -1 && stops.lower(floor) == null) direction = 1;
        floor += direction;
        return stops.remove(floor) ? floor : null;
    }
}

package interview.lift;

import java.util.TreeSet;

public class Lift {
    private final int topFloor;
    private int floor;
    private int direction = 1;
    private final TreeSet<Integer> stops = new TreeSet<>();

    public Lift(int topFloor) {
        if (topFloor < 0) throw new IllegalArgumentException("Invalid top floor");
        this.topFloor = topFloor;
    }

    public int floor() { return floor; }

    public void request(int destination) {
        if (destination < 0 || destination > topFloor) throw new IllegalArgumentException("Invalid floor");
        stops.add(destination);
    }

    public Integer step() {
        if (stops.remove(floor)) return floor;
        if (stops.isEmpty()) return null;
        if (direction == 1 && stops.higher(floor) == null) direction = -1;
        if (direction == -1 && stops.lower(floor) == null) direction = 1;
        floor += direction;
        return stops.remove(floor) ? floor : null;
    }
}

Kotlin

Lift.kt

package interview.lift

import java.util.TreeSet

class Lift(private val topFloor: Int) {
    var floor = 0
        private set
    private var direction = 1
    private val stops = TreeSet<Int>()

    init { require(topFloor >= 0) }

    fun request(destination: Int) {
        require(destination in 0..topFloor)
        stops.add(destination)
    }

    // Move one floor. Return a floor only when we stop there.
    fun step(): Int? {
        if (stops.remove(floor)) return floor
        if (stops.isEmpty()) return null
        if (direction == 1 && stops.higher(floor) == null) direction = -1
        if (direction == -1 && stops.lower(floor) == null) direction = 1
        floor += direction
        return if (stops.remove(floor)) floor else null
    }
}

package interview.lift

import java.util.TreeSet

class Lift(private val topFloor: Int) {
    var floor = 0
        private set
    private var direction = 1
    private val stops = TreeSet<Int>()

    init { require(topFloor >= 0) }

    fun request(destination: Int) {
        require(destination in 0..topFloor)
        stops.add(destination)
    }

    fun step(): Int? {
        if (stops.remove(floor)) return floor
        if (stops.isEmpty()) return null
        if (direction == 1 && stops.higher(floor) == null) direction = -1
        if (direction == -1 && stops.lower(floor) == null) direction = 1
        floor += direction
        return if (stops.remove(floor)) floor else null
    }
}

Follow-up questions

Request for the current floor?

“I would serve it before moving, since the lift is already there.” The interview implementation removes the current floor from its pending stops and returns that floor immediately. Repeating the same request before it is served still produces only one stop because requests are stored in a set.

Kotlin

val lift = Lift(5)
lift.request(0)
lift.request(0)
println(lift.step()) // 0
println(lift.step()) // null
println(lift.floor) // 0

Java

var lift = new Lift(5);
lift.request(0);
lift.request(0);
System.out.println(lift.step()); // 0
System.out.println(lift.step()); // null
System.out.println(lift.floor()); // 0

More than one lift?

“I would add a controller that assigns each pickup to one lift.” Start by choosing the nearest idle lift. If all are busy, choose a lift already moving toward the pickup or keep the request waiting. The controller must assign a request once, while each lift keeps its own pending stops and movement logic.

Doors or emergency stop?

“I would add explicit states such as idle, moving, doors open and emergency stopped.” Movement is allowed only with the doors closed and no emergency stop. Reaching a requested floor changes to doors open, and closing the doors allows scheduling to continue. An emergency state blocks movement until a separate reset, rather than being cleared by another floor request.

What should I test?

“With no requests, a step should leave the floor unchanged.” Duplicate requests should create one stop. A request for the current floor should be served immediately. With requests ahead and behind, the lift should finish the stops ahead before reversing. A floor outside the building should be rejected without changing pending stops.

Extended implementation and optional features

This reference explores a larger scope. Use it after you can explain and write the interview version. Its extra types and features are not required for the scope above.

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));
    }
}

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;

public final class ElevatorSystem {

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

    private final Queue<Request> waiting = new ConcurrentLinkedQueue<>();

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

    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));
    }

    public void selectFloor(int carId, int floor) {
        car(carId).add(new Request(floor, Request.Type.DESTINATION));
    }

    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);
        cars.forEach(Elevator::step);
    }

    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;
    }
}

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;

public final class Elevator {

    private final int id;

    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;
    }

    public void add(Request request) {
        inbox.add(request);
    }

    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()) {
            direction = direction.opposite();
            return;
        }
        currentFloor += direction == Direction.UP ? 1 : -1;
    }

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

    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);
    }

    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;
        }
        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;
    }
}

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;
        }
    }
}

package com.androidinterview.lift.model;

public record Request(int floor, Type type) {

    public enum Type {
        PICKUP_UP(Direction.UP),
        PICKUP_DOWN(Direction.DOWN),
        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;
    }
}

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;

public interface ElevatorSelectionStrategy {

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

    static ElevatorSelectionStrategy nearestCar() {
        return (cars, request) -> cars.stream()
                .min(Comparator.comparingInt(car -> Math.abs(car.currentFloor() - request.floor())));
    }

    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 }
}

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

class ElevatorSystem(
    val cars: List<Elevator>,
    private val dispatch: ElevatorSelectionStrategy,
) {
    private val waiting = ConcurrentLinkedQueue<Request>()

    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)
    }

    fun selectFloor(carId: Int, floor: Int) {
        car(carId).add(Request(floor, RequestType.DESTINATION))
    }

    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
        }
        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
        }
    }
}

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

class Elevator(val id: Int, startFloor: Int = 0) {

    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

    fun add(request: Request) {
        inbox += request
    }

    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
            }
            !hasWorkAhead() -> direction = direction.opposite
            else -> currentFloor += if (direction == Direction.UP) 1 else -1
        }
    }

    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
    }

    private fun directionOfNextRequest(): Direction {
        val next = requests.minBy { abs(it.floor - currentFloor) }
        return when {
            next.floor > currentFloor -> Direction.UP
            next.floor < currentFloor -> Direction.DOWN
            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
        }
}

package com.androidinterview.lift.model

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)

package com.androidinterview.lift.model

enum class RequestType(val travel: Direction) {
    PICKUP_UP(Direction.UP),
    PICKUP_DOWN(Direction.DOWN),
    DESTINATION(Direction.IDLE),
}

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
    }
}

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

fun interface ElevatorSelectionStrategy {
    fun select(cars: List<Elevator>, request: Request): Elevator?
}

val nearestCar = ElevatorSelectionStrategy { cars, request ->
    cars.minByOrNull { abs(it.currentFloor - request.floor) }
}

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
    }
}

Watch

8. Elevator System, Low Level Design (Hindi) | SDE LLD interview question | Design Elevator System (opens in a new tab)Concept && Coding - by Shrayansh
Low-Level Design Interview: Design an Elevator w/ a Ex-Meta Staff Engineer (opens in a new tab)Hello Interview
Low Level Design of Elevator with @gkcs - Mock System Design Interview (opens in a new tab)Keerti Purswani