Ted Wang a master of none

OOD - Design an Elevator

This is a typical problem that one might encounter during a tech interview. The skill that the interviewer intends to test is the candidate’s ability to make object-oriented design. This means that this is an open-ended problem and has no right answer for it. Everyone has its own way of designing it. Compared with algorithm problems, this problem reflects more one’s ability to write production and maintainable code.


Object-Oriented Design Principles

Although there is no right answer, one should follow the SOLID principles to make the design. SOLID principles are a set of golden rules used by object-oriented developers. SOLID principles consist of (reference to educative.io):

  1. S: Single-responsibility principle
  2. O: Open-closed principle
  3. L: Liskov substitution principle
  4. I: Interface segregation principle
  5. D: Dependency inversion principle


Design patterns

One can also implement appropriate design patterns to enhance the functionality and code style. For this problem, I think these design pattern could be useful:

  1. Observer Design Pattern
  2. Composite Design Pattern
  3. State Design Pattern
  4. Singleton Design Pattern
  5. Maybe some others, imagination is what powers us!


Analysis

Alright, let me show you my implementation for this problem. I will try to keep it short and concise, so that it’s feasible to complete during the tech interview, which is about 45 to 60 minutes. I am sure that there are better solutions out there, but here is my approach.

First let’s identify the problem’s requirements. Usually, the basic requirements for this problem are:

  1. The elevator can go up and down in a real-world fashion.
  2. Users can send requests to the elevator from both outside and inside the elevator.

The first requirement is a bit vague, so let me break it down. A real-world elevator has the following behaviours:

  1. When elevator is going up or down, it will stop at all the floors that the users requested.
  2. If the elevator received a request of going down while it is going up, the elevator will go to the highest floor in the current requests, and then go down.
  3. Users can send requests at anytime.

After understanding the requirement, we can start with our design. From the analysis above, we know that elevator needs to sort the requests by some kind of order. It’s not by timestamp, because if elevator is at floor 1, and customer A wants to go to floor 4, and B wants to go to floor 2, the elevator should not go to floor 4 first just because A sent the request first. Instead, the elevator should stop at floor 2 and let B out, then go to floor 4 to let A out. Thus, we know that the request should be sorted by the distance from the current floor and not by timestamp.


Implementation

Let’s design the request class.

public class Request {

    int currentFloor;
    int desiredFloor;
    Direction direction;
    Location location;

    public Request(int currentFloor, int desiredFloor, Direction direction, Location location) {
        this.currentFloor = currentFloor;
        this.desiredFloor = desiredFloor;
        this.direction = direction;
        this.location = location;
    }
}
public enum Direction {
    UP,
    DOWN,
    IDLE
}
public enum Location {
    INSIDE_ELEVATOR,
    OUTSIDE_ELEVATOR
}

Assumptions

Now, in real life, the elevator will finish all up requests before starting down requests. Let’s assume that going up has more priority than going down, which means that when the elevator is in IDLE state, and has both up and down requests, it will execute up requests first.

I used a max heap to store all down requests and sort them by their desired floor. Similarly, a min heap to store all up requests and sort them by their desired floor.

When, the requester is outside of the elevator, the elevator needs to stop at the currentFloor of the requester, before going to the desiredFloor of the requester.

Here is the elevator class implementation after keeping all the above in mind.

import java.util.PriorityQueue;

public class Elevator {

    int currentFloor;
    Direction direction;
    PriorityQueue<Request> upQueue;
    PriorityQueue<Request> downQueue;

    public Elevator(int currentFloor) {
        this.currentFloor = currentFloor;

        this.direction = Direction.IDLE;

        // use default, which is a min heap
        upQueue = new PriorityQueue<>((a, b) -> a.desiredFloor - b.desiredFloor);

        // use a max heap
        downQueue =  new PriorityQueue<>((a, b) -> b.desiredFloor - a.desiredFloor);
    }

    public void sendUpRequest(Request upRequest) {
        // If the request is sent from out side of the elevator,
        // we need to stop at the current floor of the requester
        // to pick him up, and then go the the desired floor.
        if (upRequest.location == Location.OUTSIDE_ELEVATOR) {
            // Go pick up the requester who is outside of the elevator
            upQueue.offer(new Request(upRequest.currentFloor,
                upRequest.currentFloor,
                Direction.UP,
                Location.OUTSIDE_ELEVATOR));

            System.out.println("Append up request going to floor " + upRequest.currentFloor + ".");
        }

        // Go to the desired floor
        upQueue.offer(upRequest);

        System.out.println("Append up request going to floor " + upRequest.desiredFloor + ".");
    }

    public void sendDownRequest(Request downRequest) {
        // Similar to the sendUpRequest logic
        if (downRequest.location == Location.OUTSIDE_ELEVATOR) {
            downQueue.offer(new Request(downRequest.currentFloor,
                downRequest.currentFloor,
                Direction.DOWN,
                Location.OUTSIDE_ELEVATOR));

            System.out.println("Append down request going to floor " + downRequest.currentFloor + ".");
        }

        // Go to the desired floor
        downQueue.offer(downRequest);

        System.out.println("Append down request going to floor " + downRequest.desiredFloor + ".");
    }

    public void run() {
        while (!upQueue.isEmpty() || !downQueue.isEmpty()) {
            processRequests();
        }

        System.out.println("Finished all requests.");
        this.direction = Direction.IDLE;
    }

    private void processRequests() {
        if (this.direction == Direction.UP || this.direction == Direction.IDLE) {
            processUpRequest();
            processDownRequest();
        } else {
            processDownRequest();
            processUpRequest();
        }
    }

    private void processUpRequest() {
        while (!upQueue.isEmpty()) {
            Request upRequest = upQueue.poll();
            // Communicate with hardware
            this.currentFloor = upRequest.desiredFloor;
            System.out.println("Processing up requests. Elevator stopped at floor " + this.currentFloor + ".");
        }
        if (!downQueue.isEmpty()) {
            this.direction = Direction.DOWN;
        } else {
            this.direction = Direction.IDLE;
        }
    }

    private void processDownRequest() {
        while (!downQueue.isEmpty()) {
            Request downRequest = downQueue.poll();
            // Communicate with hardware
            this.currentFloor = downRequest.desiredFloor;
            System.out.println("Processing down requests. Elevator stopped at floor " + this.currentFloor + ".");
        }
        if (!upQueue.isEmpty()) {
            this.direction = Direction.UP;
        } else {
            this.direction = Direction.IDLE;
        }
    }


    public static void main(String[] args) {
        Elevator elevator = new Elevator(0);

        Request upRequest1 = new Request(elevator.currentFloor, 5, Direction.UP, Location.INSIDE_ELEVATOR);
        Request upRequest2 = new Request(elevator.currentFloor, 3, Direction.UP, Location.INSIDE_ELEVATOR);

        Request downRequest1 = new Request(elevator.currentFloor, 1, Direction.DOWN, Location.INSIDE_ELEVATOR);
        Request downRequest2 = new Request(elevator.currentFloor, 2, Direction.DOWN, Location.INSIDE_ELEVATOR);
        Request downRequest3 = new Request(4, 0, Direction.DOWN, Location.OUTSIDE_ELEVATOR);

        // Two people inside of the elevator pressed button to go up to floor 5 and 3.
        elevator.sendUpRequest(upRequest1);
        elevator.sendUpRequest(upRequest2);

        // One person outside of the elevator at floor 4 pressed button to go down to floor 0
        elevator.sendDownRequest(downRequest3);

        // Two person inside of the elevator pressed button to go down to floor 1 and 2.
        elevator.sendDownRequest(downRequest1);
        elevator.sendDownRequest(downRequest2);


        elevator.run();
    }

}


Validation

As shown above, I have giving one example run of my code. In the example, there are two people inside of the elevator that want to go to floor 5 and 3. A person outside the elevator at floor 4 wants to go to floor 0. And two people inside of the elevator want to go to floor 1 and 2.

We expect the elevator up first and stop at floor 3 and 5. Then, the elevator to go down and stop at floor 4 to pick up the person outside the elevator. Then, the elevator should keep going down and stop at floor 2, 1, and 0 respectively.

Let’s see the output message to verify if the elevator’s behaviour aligns with our expectation.

Append up request going to floor 5.
Append up request going to floor 3.
Append down request going to floor 4.
Append down request going to floor 0.
Append down request going to floor 1.
Append down request going to floor 2.

Processing up requests. Elevator stopped at floor 3.
Processing up requests. Elevator stopped at floor 5.
Processing down requests. Elevator stopped at floor 4.
Processing down requests. Elevator stopped at floor 2.
Processing down requests. Elevator stopped at floor 1.
Processing down requests. Elevator stopped at floor 0.
Finished all requests.

Process finished with exit code 0

As the above log shows, it is exactly what we expected.


Time and Space Complexity

The main structure that we use in this design is heap. It has a time complexity of O(nlogn). The space complexity is O(n).


Conclusion

This is a simple design that can be completed within an interview. There are many more things to consider in a production code, but for a temp solution, I think this suffices. This is just my solution, and the link to the code is here -> Elevator. I am sure that there are many better designs out there. I hope this helps with your interview preparation!