5 ms·
Probably should have checked before posting...this was discussed 4 years ago: https://news.ycombinator.com/item?id=2062889 https://news.ycombinator.com/item?id=
by danso 12y ago
Probably should have checked before posting...this was discussed 4 years ago: https://news.ycombinator.com/item?id=2062889 https://news.ycombinator.com/item?id=2062889 (so I guess it's eligible for re-discussion)
I stumbled across it doing a Google search for "interview question elevator design"...I haven't been asked in a technical interview about how I would implement the logic for an elevator controller, but I heard about the question second-hand at a college job fair...and since then, I still think about that question. In fact, I think I've thought about it almost every time I've ever waited for an elevator in New York (that, and the story of the poor woman who was crushed while stepping into an upward-shooting elevator in Midtown a few years ago)...so...4 times a day, times 6 years...and I still haven't come up with enough optimal algorithms to cover all the edge cases and scenarios that I come across :)
The Monopoly question that the OP mentions is good, but I think is a bit problematic since not everyone has played Monopoly. And not everyone is familiar even with the standard rules. But everyone's been in an elevator before, and virtually no one thinks about how complicated an elevator's operation might be: it's one of those incredible, life-changing inventions that you take for granted after the first time you've pressed a button. So I think it's great material for an open-ended technical question.
The single-elevator logic is convoluted enough: If the elevator is going from bottom floor to 10th floor, obviously it should stop if someone on the 5th floor signals their intention to go up. But what if, after the 1st floor door closes and the elevator starts moving, a 2nd-floor person wants to go up? What's the cutoff in last-second button pushes to prevent the elevator from too abruptly stopping?
And of course, the more complicated logic is if someone on the 5th floor press Down while the elevator is heading up. Then you have to implement a queue system. But simple FIFO may not be efficient...if the elevator is moving up, and someone on the 5th floor presses Down, and then, someone on the 7th floor also presses Down...it would seem that the elevator should stop at the 7th floor first, on its way down.
And then things get really complicated with even just one more elevator, particularly with race conditions. If both elevators are moving up, and a 5th floor signal for "Down" is followed by a 7th floor signal for "Down"...ideally, the first elevator to finish its Up job will take the 7th floor...Should it also take the 5th floor Down job? Or let the other elevator handle that? And should that decision change if the 7th floor person signals their intention to go to the 4th floor, whereas the 5th floor person most likely just wants to go to the bottom floor?
Beyond the interruption/queuing logic, there's a lot of interesting discussion about how the elevators should be positioned during idle time. Presumably, they should return to ground floor in the mornings, and stay near the top (or at least midway) during the beginning of lunch, and the end of the day.
What I like about the elevator question is that elevator algorithms are their own science. But a lot of the complexity can be realized just by taking the time to think about all the scenarios you've encountered as an elevator user. And so given the typical technical interview situation, it's a good test of the candidate's reflection, ability to ask questions of the requirements, the ability to apply heuristics for good non-optimal solutions, and the ability to not let edge-cases dominate the thinking.
- grogers 12y agoThis seems roughly the same as the monopoly question. Both are seemingly more about enumerating all the edge cases than anything to do with software design or implementation. In 20-30 minutes what do you generally expect to get out of asking this? The benefit to me of elevator over monopoly is that there are inherent issues of safety that dovetail nicely into fault avoidance and recovery and into broader system design and testing.
- ant6n 12y agoI lived in a building (6 floors) where the elevator appeared to be always in one of four states: Door opened, going to floor n, waiting for input inside elevator, waiting for input from anybody. It only remembers a single floor - where it's going now. Once it goes into the input state, it's a race among everybody who wants to take the elevator to push the buttons. I was never quite sure whether the 'waiting for input inside elevator' actually existed, because every once in a while the elevator would get summoned by someone else before I could give it a destination when inside. I guess this is a bit off-topic, it's just to say that even very simple logic can solve the problem, in a possibly infuriating way. ;)
- justizin 12y agoYeah I'm pretty sure the elevator, at least that old one, doesn't know if you're in it, though more modern ones will open the door as you walk up.
- im3w1l 12y agoMaybe everyone has been in an elevator, but not everyone has daily experience with them. And not all elevators have lots of contention. I'd say it was several years ago I last waited for an occupied elevator.
- Someone 12y ago"What I like about the elevator question is that elevator algorithms are their own science." Are they? I think they have analogies in task schedulers. You have things like fairness guarantees (maximizing number of trips made or people moved is not ideal, as that could keep someone waiting for an elevator for weeks), livelock (elevators being stuck on short trips between floors 1 and 2 with people waiting forever on floor 55), elevator/CPU affinity (if we know it is highly likely that the person on floor 14 wants to go to floor 7, we might not let the elevator going past it to floor 3 stop at 14, but schedule the elevator now a few floors higher that we knew will stop at 7 stop there instead, but if we are fairly sure he wants to go to floor 6, where the elevator is going anyways, we might want the first elevator to stop there) For the "ground floor in the morning" thing, task schedulers can switch behavior, too, for example by detecting the difference between batch-like and GUI-like programs. Extreme example (probably far-fetched): in embedded systems, the task scheduler could even know, say, when Wall Street opens, and make sure the cron task that should run then is paged in when it does.