For many years now, puzzle like questions have been very commonly asked during an interview for a Software Engineering job. If my memory serves me right, these were called the Microsoft Interview Questions during the 1990s. These days, they are more commonly referred to as Google Interview Questions.
Not everyone agrees with the strategy of asking these seemingly non-technical questions. For example, a famous question used to be about 4 people who walk at different speeds, and need to cross a bridge at night. The constraints being, there is only one flashlight available, and the bridge can safely take the weight of only two people. The task was to find the sequence that transports all of them in the shortest time, given the need that the flashlight has to be brought back once a pair uses it to cross the bridge. I liked that question, but I also understand, that it is only indirectly related to scheduling algorithms.
On the other hand, the “Elevator Algorithm”, as it is often called, is a much broader problem, and it is absolutely related to actual day to day coding tasks.
Let’s start with the simplest version. There is a very tall building, with one elevator to transport people. It’s just a regular elevator. On the inside there are command buttons corresponding to every floor, and every floor has request buttons for up and down. We have to design an algorithm to respond to the command buttons pressed by people inside the elevator, and the request buttons on the floors.
I am not giving a solution here, because the candidate has to treat it as a design problem, and more importantly as an “optimization problem”. There are different strategies available, and they optimize on different parameters.
The simplest strategy is of course, FCFS, First Come First Served. The elevator would respond to the first request button, go to that floor, drop the person to the requested floor and then move on to the next person. At first glance, it’s clear that this will generate excessive up and down movement of the elevator. It also will not be the most time efficient. But it’s not all bad. It’s very fair in terms of serving, if fairness means relative wait time. Choosing the next request would be very fast, based on a simple queue data structure.
A completely different strategy would be SSF, Shortest Seek First. Whenever the elevator drops a person to the desired floor, it can look at all the requests, and pick the request that’s originating at the nearest floor. It will minimize the distance that elevator has to travel to start serving another request. Clearly, there is a possibility that requests keep coming from a region of nearby floors, and the elevator doesn’t get a chance to serve older requests from floors that are far away. This can lead to starvation for some requests, as there is no upper bound on the wait time. Note that a slightly more complex structure than a queue, would be needed to store the requests, so that they can be searched quickly to find out the next best request. That would be another side question.
The two strategies above try to optimize different goals - fairness and the distance our elevator has to travel. These goals are in conflict of each other. A candidate can be expected to observe this conflict, and realize that this is an optimization problem, and not a simple coding exercise.
There can be other considerations as well, which will matter in more sophisticated strategies. For example the travel time once the person is on board, and the cost of stopping/restarting the elevator for picking up a person.
It’s easy to see the relation of this problem to Computer Science. This is an old and very well known problem of Disk Arm Scheduling. The cost of seek as measured in time, and the movement of disk arm, both need to be minimized. A very similar problem exists for sorting items that are on tape, and is addressed by Knuth in his book.
The elevator problem, itself has been described on the
Wikipedia page. It’s possible to tweak FCFS and SSF to add other considerations. For example, adding an upper bound on wait time in SSF, so that a request waiting over that bound gets priority over the nearest request etc. But the most widely used compromise relies on moving the elevator in one direction, serving as many requests as possible, and then changing the direction to serve requests in that direction, and so on. That's what is actually known as the Elevator Algorithm.
More fundamentally, the core of the problem is sequential access. In my opinion, that realization is more important than knowing an implementation of Elevator Algorithm. The idea behind this problem will appear in one form or another whenever you are restricted to sequential access. For example, the data in memory could in a very big doubly linked list. Today, in the world of Big Data, sequential read is the most common access pattern, and a variation of this problem will confront you, whether you do map-reduce or some other implementation.
Hence, in my opinion, this is one of the best interview questions to gauge the candidate’s grasp on the fundamentals of Computer Science. In addition, this one 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.
As a side note, the original elevator analogy for sequential access and/or processing is not as straightforward anymore. Real life elevators have other complex considerations, such as time of day, special floors etc. Some have more complex floor controls, where people can also express where they intend to go. And so on. It’s a topic in itself, as can be seen by a rather large tome named
Elevator Traffic Handbook. You can preview that book on Google Books if you want to dig deeper on this topic. :-)
