Elevator System Design — A tricky technical interview question

An Elevator System Design interview question is one of the best interview questions to gauge the candidate’s grasp on the fundamentals of Computer Science. In addition, this can be extended in many different directions, making it an ideal problem to see how the candidate thinks. It’s easy to make it an object-oriented design problem. It can be used to discuss different data structures that will help in the implementation. If needed, it can be made even more complicated by adding multiple elevators serving the building, where a request button summons the most appropriate elevator. That is another nice optimization problem. But the core single elevator problem is often good enough to judge the ability of a candidate to see different trade-offs inherent in any design

Requirements:

As always when an interviewer asks this question, it is always better to first understand what he is really looking for in the candidate. The best way to find out is to collect the requirements first.

1. An elevator can move up, down or standstill.
2. An elevator can transfer passengers from one floor in a building to another floor in the minimum time possible.
3. Elevator door can only open when it is standstill in a floor (i.e. not moving).
4. Let’s first discuss the number of floors that a building can have. The tallest building in the world is Burj Khalifa and it has around 163 floors. Let’s just assume that our system has 200 floors, which is still far greater than what the tallest building has. We cannot just assume some arbitrarily large number. When we are gathering requirements, we need to make sure that we are still collecting some reasonable requirements.
5. Burj Khalifa has around 57 elevators. We can assume in our system we have around 100 elevators.
6. Then there are some requirements related to each elevator like: a. Number of passengers / Load on the elevator b. Moving speed of the elevator
7. Now fourth requirement is about what we would like to minimize. a. Do we like to minimize the wait time of the passengers? b. Or do we like to minimize the overall wait time in the system?
8. You should also discuss with the interviewer that whether he would like to have different operational zones or sectors in the elevator system. A zone is the set of floors that are covered by a set of elevators. E.g. In our case of 200 floors and 100 elevators, we can, e.g., divide all the floors into 4 zones: · From 1–50: operated by 25 elevators · From 51–100: operated by 25 elevators · From 101–150: operated by 25 elevators · From 151–200: operated by 25 elevators Another way of zoning is to divide all floors into two zones (even and odd floors, etc.). When we use multiple zones in a building along with a set of elevators assigned to a zone then we can treat each zone independently from each other. If we use the first approach of 4 zones then our elevator design problem then boils down to 50 floors and 25 elevators. On the other hand, if we use the second approach of 2 zones (i.e. odd/even zones), our elevator design problem boils down to 100 floors and 50 elevators. If we need to decide whether to use zone or not and if yes then which zoning approach to use, it all depends on the waiting time requirements and speed of the elevators. Apart from the above requirements, there are some extended requirements like:
9. Triggering emergency alarm/brake
10. VIP or utility elevators

Object and Actors:

After collecting all the requirements, it is better to identify different objects and actors in the system. These objects and actors help us to identify the classes and interfaces that we need to implement an elevator system. In an elevator system, you can easily find the following objects.

1. Passenger
2. The elevator controller
3. Elevators
4. Then each elevator can have doors, button panels inside the elevators and then buttons
5. Floors and more.

Use Cases:

After identifying the classes and interfaces and the relation between them, it is also important to discuss different use-cases. The most important use-cases include:
· Calling Elevator Car: So, when a passenger wants to go up or down to a different floor he presses the up or down button to call the elevator. This requires scheduling an elevator car to go to the passenger floor.
· Move/Stop the Elevator
· Open/Close the doors
· Indicating moving direction
· Indicating elevator position: the floor where the elevator has reached. This is important to indicate to the passenger so that the passenger can get off the elevator at his destination floor
· Triggering Emergency Breaks
· Making an Emergency call

Algorithms:

Now, at this point, you should be discussing the different algorithms that can be used by an elevator system to dispatch the elevator car to a floor to serve a passenger. Common algorithms include:

• First Come First Serve (FCFS)
• Shortest Seek Time First (SSTF)
• SCAN
• LOOK

If you are interested to know more, you can check out the below video where I am discussing the design of an elevator system in more detail. The video also discusses how different algorithms are implemented.

If you are looking for a great resource to not just improve your distributed system design skills but also to ace your distributed system design interviews and targeting level L5/L6 in companies like Facebook, Google, etc. then you should check “The Distributed System Design Interviews Bible”.