Questions like this are great because they test so many things | Coding interview preparation
Questions like this are great because they test so many things at the same time:
The candidate's general competence with algorithms, space/time complexity, etc. The candidate's ability to respond to different constraints and handle various trade-offs. This is something engineers deal with all of the time, and it's a critical skill to have. The candidate's creativity. Each constraint forces a person to start from scratch and think of a completely new approach -- a great test of creativity. The candidate's attitude toward complexity. Some candidates get permanently stuck because they start off by trying to come up with the O(n*log n) time / O(1) space solution. They assume that using a hash or comparing all elements of the list to all other elements is not what you're looking for, and so they don't mention the easy solutions (but also can't figure out the harder solutions). This is a yellow flag that the candidate tends to overcomplicate things (I'll typically ask subsequent interviewers to watch out for this tendency). The candidate's passion for learning and challenges. Some people get excited when you throw in harder and harder constraints, others get dejected and/or lazy.
** To give credit where credit is due, I was asked this question during an interview at Microsoft. I thought it was a great question and have been using it myself ever since. Quora seems like a good place to retire the question and force myself to think of something more original =).
