Elevator / Lift system

import java.util.*;

enum Direction { UP, DOWN, IDLE }
enum CarState { IDLE, MOVING_UP, MOVING_DOWN, DOORS_OPEN }

/**
 * TWO kinds of request, and they are NOT the same thing.
 *   HallCall : pressed outside. Knows a floor AND a direction, but no destination.
 *   CarCall  : pressed inside.  Knows a destination, but carries no direction.
 * Collapsing both into "a floor number" is what makes correct scheduling impossible.
 */
sealed interface Request permits HallCall, CarCall { int floor(); }
record HallCall(int floor, Direction direction) implements Request {}
record CarCall(int floor) implements Request {}

class ElevatorCar {
    private final int id;
    private int floor;
    private Direction direction = Direction.IDLE;
    private CarState state = CarState.IDLE;
    private int floorsTravelled = 0;

    // Two sorted sets. The whole algorithm is "drain the one matching my direction, then flip".
    private final NavigableSet<Integer> upRequests   = new TreeSet<>();
    private final NavigableSet<Integer> downRequests = new TreeSet<>(Comparator.reverseOrder());
    private final Object queueLock = new Object();          // guards the two sets, nothing else

    ElevatorCar(int id, int startFloor) { this.id = id; this.floor = startFloor; }

    int id()              { return id; }
    int floor()           { return floor; }
    Direction direction() { return direction; }
    CarState state()      { return state; }
    int floorsTravelled() { return floorsTravelled; }

    int pending()  { synchronized (queueLock) { return upRequests.size() + downRequests.size(); } }
    boolean busy() { return pending() > 0 || state == CarState.DOORS_OPEN; }

    /** Hall calls arrive from many floors at once — this is the only shared state. */
    void addRequest(Request r) {
        synchronized (queueLock) {
            if (r instanceof HallCall h) {
                if (h.direction() == Direction.UP) upRequests.add(h.floor());
                else                               downRequests.add(h.floor());
            } else {                                        // a CarCall: direction comes from where we are
                if (r.floor() > floor)      upRequests.add(r.floor());
                else if (r.floor() < floor) downRequests.add(r.floor());
                else                        state = CarState.DOORS_OPEN;    // already standing here
            }
        }
    }

    /** ONE floor of movement. Time is driven from outside — never sleep in here. */
    void step() {
        if (state == CarState.DOORS_OPEN) { state = resume(); return; }     // doors take one tick
        if (!busy()) { direction = Direction.IDLE; state = CarState.IDLE; return; }

        if (direction == Direction.IDLE) direction = towardsNearest();
        if (serveHere()) { state = CarState.DOORS_OPEN; return; }

        if (!workAhead(direction)) direction = opposite(direction);         // nothing left this way
        if (serveHere()) { state = CarState.DOORS_OPEN; return; }

        floor += (direction == Direction.UP) ? 1 : -1;
        floorsTravelled++;
        state = (direction == Direction.UP) ? CarState.MOVING_UP : CarState.MOVING_DOWN;
        if (serveHere()) state = CarState.DOORS_OPEN;                       // stop for it on the way
    }

    /** Remove a request at this floor IF it matches where we are going. */
    private boolean serveHere() {
        synchronized (queueLock) {
            if (direction == Direction.UP) {
                if (upRequests.remove(floor)) return true;
                if (!anyAbove() && downRequests.remove(floor)) return true;   // turnaround point
            } else {
                if (downRequests.remove(floor)) return true;
                if (!anyBelow() && upRequests.remove(floor)) return true;
            }
            return false;
        }
    }

    private CarState resume() {
        if (pending() == 0) { direction = Direction.IDLE; return CarState.IDLE; }
        return direction == Direction.UP ? CarState.MOVING_UP : CarState.MOVING_DOWN;
    }

    private Direction towardsNearest() {
        int best = Integer.MAX_VALUE, target = floor;
        for (int f : allRequests())
            if (Math.abs(f - floor) < best) { best = Math.abs(f - floor); target = f; }
        return target >= floor ? Direction.UP : Direction.DOWN;
    }

    private boolean workAhead(Direction d) { return d == Direction.UP ? anyAbove() : anyBelow(); }
    private boolean anyAbove() { for (int f : allRequests()) if (f > floor) return true; return false; }
    private boolean anyBelow() { for (int f : allRequests()) if (f < floor) return true; return false; }

    private List<Integer> allRequests() {
        synchronized (queueLock) {
            List<Integer> out = new ArrayList<>(upRequests);
            out.addAll(downRequests);
            return out;
        }
    }

    private static Direction opposite(Direction d) { return d == Direction.UP ? Direction.DOWN : Direction.UP; }

    String describe() {
        synchronized (queueLock) {
            return "car#" + id + " floor " + floor + "  " + pad(state.name()) + " up" + upRequests + "  down" + downRequests;
        }
    }
    private static String pad(String s) { return (s + "           ").substring(0, 11); }
}

/** WHICH car takes a hall call. The one decision the interviewer will ask you to change. */
interface SchedulingStrategy {
    ElevatorCar pick(List<ElevatorCar> cars, HallCall call);
}

class NearestCarStrategy implements SchedulingStrategy {
    private static final int DETOUR = 100;      // big enough that a wrong-way car only wins if nothing else is close

    public ElevatorCar pick(List<ElevatorCar> cars, HallCall call) {
        ElevatorCar best = null;
        int bestCost = Integer.MAX_VALUE;
        for (ElevatorCar c : cars) {
            int cost = cost(c, call);
            if (cost < bestCost) { bestCost = cost; best = c; }
        }
        return best;
    }

    static int cost(ElevatorCar c, HallCall call) {
        int distance = Math.abs(c.floor() - call.floor());
        if (c.direction() == Direction.IDLE) return distance;               // idle: just the walk
        boolean towards = (c.direction() == Direction.UP   && call.floor() >= c.floor())
                       || (c.direction() == Direction.DOWN && call.floor() <= c.floor());
        if (towards && c.direction() == call.direction()) return distance;  // it passes you anyway
        return distance + DETOUR;                                          // it must finish its run first
    }
}

class LeastLoadStrategy implements SchedulingStrategy {
    public ElevatorCar pick(List<ElevatorCar> cars, HallCall call) {
        ElevatorCar best = null;
        int bestCost = Integer.MAX_VALUE;
        for (ElevatorCar c : cars) {
            int cost = c.pending() * 100 + Math.abs(c.floor() - call.floor());
            if (cost < bestCost) { bestCost = cost; best = c; }
        }
        return best;
    }
}

class ElevatorSystem {
    private final List<ElevatorCar> cars;
    private SchedulingStrategy strategy;

    ElevatorSystem(List<ElevatorCar> cars, SchedulingStrategy strategy) {
        this.cars = List.copyOf(cars);
        this.strategy = strategy;
    }

    /** Open for a new policy, closed for modification — request() below never changes. */
    void setStrategy(SchedulingStrategy s) { this.strategy = s; }

    ElevatorCar request(HallCall call) {
        ElevatorCar car = strategy.pick(cars, call);    // WHICH car — pluggable
        car.addRequest(call);                           // WHEN to serve it — the car's own LOOK
        return car;
    }

    ElevatorCar car(int id) {
        for (ElevatorCar c : cars) if (c.id() == id) return c;
        throw new NoSuchElementException("no car " + id);
    }

    /** Time comes from OUTSIDE: a main loop, a test, or a hardware timer. */
    void tick() { for (ElevatorCar c : cars) c.step(); }

    boolean busy() { for (ElevatorCar c : cars) if (c.busy()) return true; return false; }
    int floorsTravelled() { int t = 0; for (ElevatorCar c : cars) t += c.floorsTravelled(); return t; }
    List<ElevatorCar> cars() { return cars; }
}

public class Main {
    /** What FIFO would have cost: walk to each request in arrival order. */
    static int fifoFloors(int start, List<Integer> arrivalOrder) {
        int total = 0, at = start;
        for (int f : arrivalOrder) { total += Math.abs(f - at); at = f; }
        return total;
    }

    public static void main(String[] args) {
        System.out.println("=== one car, four hall calls: 5 up, 2 up, 8 up, 3 up ===");
        ElevatorSystem one = new ElevatorSystem(List.of(new ElevatorCar(1, 1)), new NearestCarStrategy());
        for (int f : new int[] { 5, 2, 8, 3 }) one.request(new HallCall(f, Direction.UP));

        int t = 0;
        while (one.busy() && t < 200) {                 // the caller owns time
            one.tick();
            t++;
            System.out.println("t=" + (t < 10 ? "0" : "") + t + "  " + one.car(1).describe());
        }
        System.out.println("LOOK floors travelled: " + one.floorsTravelled());
        System.out.println("FIFO floors travelled: " + fifoFloors(1, List.of(5, 2, 8, 3)) + "   (1 -> 5 -> 2 -> 8 -> 3)");

        System.out.println();
        System.out.println("=== two cars, dispatch is a separate decision ===");
        ElevatorSystem bank = new ElevatorSystem(
                List.of(new ElevatorCar(1, 1), new ElevatorCar(2, 9)), new NearestCarStrategy());

        for (int f : new int[] { 8, 7, 6 })
            System.out.println("hall call " + f + " DOWN -> car #" + bank.request(new HallCall(f, Direction.DOWN)).id());

        bank.setStrategy(new LeastLoadStrategy());      // the ONLY line that changes
        System.out.println("swapped strategy to LeastLoad — request() did not change");
        System.out.println("hall call 5 DOWN -> car #" + bank.request(new HallCall(5, Direction.DOWN)).id());
    }
}

/* expected output
=== one car, four hall calls: 5 up, 2 up, 8 up, 3 up ===
t=01  car#1 floor 2  DOORS_OPEN  up[3, 5, 8]  down[]
t=02  car#1 floor 2  MOVING_UP   up[3, 5, 8]  down[]
t=03  car#1 floor 3  DOORS_OPEN  up[5, 8]  down[]
t=04  car#1 floor 3  MOVING_UP   up[5, 8]  down[]
t=05  car#1 floor 4  MOVING_UP   up[5, 8]  down[]
t=06  car#1 floor 5  DOORS_OPEN  up[8]  down[]
t=07  car#1 floor 5  MOVING_UP   up[8]  down[]
t=08  car#1 floor 6  MOVING_UP   up[8]  down[]
t=09  car#1 floor 7  MOVING_UP   up[8]  down[]
t=10  car#1 floor 8  DOORS_OPEN  up[]  down[]
t=11  car#1 floor 8  IDLE        up[]  down[]
LOOK floors travelled: 7
FIFO floors travelled: 18   (1 -> 5 -> 2 -> 8 -> 3)

=== two cars, dispatch is a separate decision ===
hall call 8 DOWN -> car #2
hall call 7 DOWN -> car #2
hall call 6 DOWN -> car #2
swapped strategy to LeastLoad — request() did not change
hall call 5 DOWN -> car #1
*/