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):
- S: Single-responsibility principle
- O: Open-closed principle
- L: Liskov substitution principle
- I: Interface segregation principle
- 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:
- Observer Design Pattern
- Composite Design Pattern
- State Design Pattern
- Singleton Design Pattern
- 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:
- The elevator can go up and down in a real-world fashion.
- 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:
- When elevator is going up or down, it will stop at all the floors that the users requested.
- 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.
- 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!
Written on May 29th, 2021 by Ted Wang