Elevator design (interview)

Question

I believe interviews (~1 hour) commonly ask to code an elevator system, so this is my attempt.

I made some requirements/assumptions:

• support one or more elevators
• accept pickup requests (think of up/down buttons outside each floor) that is served by the entire elevator pool
• each elevator individually accepts destination requests (think of floor buttons in each elevator)

My code is below, I didn't include my Exception class code, as they are just bare bones. I appreciate any feedback!

Elevator interface

public interface Elevator {
    int getMinFloor();
    int getMaxFloor();
    int getCurrentFloor();
    Deque<Integer> getDestinationQueue();
    void moveUp();
    void moveDown();
    void moveNext();
    void prependDestination(int floor);
    void queueDestination(int floor);
    boolean isInPath(int floor);
    boolean isFull();
    boolean isIdle(); }

Elevator

public class ElevatorImpl implements Elevator {
    private final int minFloor;
    private final int maxFloor;
    private final int maxCapacity;

    private int currentFloor;
    private Deque<Integer> destinationQueue;

    public ElevatorImpl(int minFloor, int maxFloor, int maxCapacity) {
        this.minFloor = minFloor;
        this.maxFloor = maxFloor;
        this.maxCapacity = maxCapacity;

        currentFloor = 0;
        destinationQueue = new LinkedList<>();
    }

    @Override
    public int getMinFloor() {
        return minFloor;
    }

    @Override
    public int getMaxFloor() {
        return maxFloor;
    }

    @Override
    public int getCurrentFloor() {
        return currentFloor;
    }

    @Override
    public Deque<Integer> getDestinationQueue() {
        return destinationQueue;
    }

    @Override
    public void queueDestination(int floor) {
        //O(N)
        if (!destinationQueue.contains(floor)) {
            destinationQueue.add(floor);
        }
    }

    @Override
    public void prependDestination(int floor) {
        destinationQueue.addFirst(floor);
    }

    @Override
    public void moveNext() {
        if (destinationQueue.isEmpty()) {
            return;
        }
        int destination = destinationQueue.peek();
        if (currentFloor < destination) {
            moveUp();
        } else if (currentFloor > destination) {
            moveDown();
        }

        if (currentFloor == destination) {
            destinationQueue.poll();
        }
    }

    @Override
    public void moveUp() {
        if (currentFloor == maxFloor) {
            throw new MoveFailureException("cannot move above max currentFloor");
        }

        // if full, then takes up a tick and must check again next tick
        if (!isFull()) {
            currentFloor++;
        }
    }

    @Override
    public void moveDown() {
        if (currentFloor == minFloor) {
            throw new MoveFailureException("cannot move below minimum currentFloor");
        }

        if (!isFull()) {
            currentFloor--;
        }
    }

    @Override
    public boolean isInPath(int floor) {
        if (destinationQueue.isEmpty()) {
            return false;
        }
        int destination = destinationQueue.peek();
        return (floor >= currentFloor && floor <= destination) || (floor <= currentFloor && floor >= destination);
    }

    @Override
    public boolean isFull() {
        //would use maxCapacity here
        return false;
    }

    @Override
    public boolean isIdle() {
        return destinationQueue.isEmpty();
    }
}

Controller interface

public interface ElevatorController {
    void addPickup(int floor);
    void step() throws RunException;
}

Controller

public class GlobalElevatorController implements ElevatorController {
    private List<Elevator> elevators;

    // mainly used if no elevators are available, then need to queue into controller
    private Queue<Integer> pickupQueue;

    public GlobalElevatorController(List<Elevator> elevators) {
        this.elevators = elevators;
        pickupQueue = new LinkedList<>();
    }

    /**
     * Represents pick up (origin floor).  Attempt to delegate request immediately, but if no elevators presently
     * available, then add to controller's queue, and attempt again during step().
     *
     * @param floor assumption: the same pickup floor will not be requested while it's being processed.  Logic should
     *             be handled by hypothetical button class.
     */
    @Override
    public void addPickup(int floor) {
        if (!pickupQueue.isEmpty()) {
            pickupQueue.add(floor);
        } else {
            // immediately put into idle or in-path elevators
            for (Elevator elevator : elevators) {
                if (elevator.isIdle()) {
                    elevator.queueDestination(floor);
                    return;
                } else if (elevator.isInPath(floor)) {
                    elevator.queueDestination(floor);
                }
            }
        }
    }

    /**
     * Move elevators.
     *
     * TODO: extend Thread, so this runs autonomously.  For now, call step() manually.
     */
    @Override
    public void step() {
        for (Elevator elevator : elevators) {
            if (elevator.isIdle()) {
                if (!pickupQueue.isEmpty()) {
                    elevator.queueDestination(pickupQueue.poll());
                }
            } else {
                elevator.moveNext();
            }
        }
    } }

Answer 1

As an interviewer, I would consider this to be a failed attempt. Simply put, it's conceptually wrong. No elevator that I have ever encountered acts as a queue. In a single-elevator system, it should go up, stopping at all requested floors on the way, until there are no more pending requests for higher floors, then it should service all of the down requests in descending order. The order in which the requests are submitted does not matter; the timing does matter, though.

In an interview, you should usually submit the simplest solution that works (then ask for feedback, and refine the solution as necessary). I see that you wrote an interface and an implementation, so I would challenge you to explain why you felt that an interface was needed. Are you anticipating the need for multiple implementations? One such justification might be to implement a multi-elevator system in the future. But in that case, your interface would not be sophisticated enough. With multiple elevators, you would need to distinguish between external and internal requests: external requests (consisting of a floor and desired direction) may be served by any elevator, but internal requests (consisting of a destination) must be served by a specific elevator. Furthermore, you would probably want to model the system using a controller that directs the elevators' movements. With multiple elevators, the algorithms for deciding which elevator to dispatch to handle an external request could get quite sophisticated. If you are planning for growth (which doesn't look like the case here), a // TODO comment would be helpful.

One minor observation: you have a maxCapacity field. What is it for? "Max" capacity sounds redundant — why not just "capacity"? Are you talking about limiting the load that the elevator is carrying (which you haven't modeled), or limiting the number of requests (which makes no sense)? In any case, I'd avoid leaving unexplained dead code when submitting a solution.

Answer 2

The interview reason for this task, is the intelligence in coordinating several elevators. As a normal user the behavior of an elevator is simple. But as house owner buying an elevator system, you want specs on the intelligence: what elevators do coordinated: no two elevators waiting on the same floor, going waiting at the first floor, secondarily at the top floor.

So I would have made the individual elevator behave consistently: up-going pressing a lower floor deferred handled after all up-floors are dealt with; downwards the reversed. Doors openable. In short: let everyone survive a ride.

Then with closed doors, with no buttons pressed for say 10 seconds, request the common intelligence/coordinator whether to go somewhere. It has to know where every elevator is, in which direction, with how much buttons pressed internally. It has to know which floor buttons in which direction are pressed. That is the most interesting class. As time might not suffice, add comments on your ideas ("might do statistics, learning when rush hours are"). But the basics: if a floor button is pressed an elevator will pass the floor, decide whether to halt, or not (already many other floors pressed, an other elevator free).

Typically minimism is the best strategy. The states, the data model, states like direction and actors like buttons.

Even if you did not present an entirely satisfying piece of software, that would be much more interesting, do you not think too?

• You can do the above, without the technical object implementation.
• Use-case specification: controller.floorButtonPressed(floor, direction); physical: which floor buttons there are.
• In Model-View-Controller sense: what data you need to know of the elevators and floors, to determine what elevator to call in the controller.

Queues will automatically come to bear, when assuring that a pressed floor button will be served in reasonable time (no starvation).