I ran into this case studying for interviews a while ago. The "maximum subarray problem"[1] is a common interview question, you are generally expected to be able to come up with the O(n) solution.
Well has a great passage about the origins of the problem and how multiple excellent algorithmists could not improve on a O(n^2) run time[2]:
> Grenander observed that the cubic time of Algorithm 1 was prohibitively slow, and derived Algorithm 2. In 1977 he described the problem to Michael Shamos of UNILOGIC, Ltd. (then of Carnegie-Mellon University) who overnight designed Algorithm 3. When Shamos showed me the problem shortly thereafter, we thought that it was probably the best possible; researchers had just shown that several similar problems require time proportional to N log N. A few days later Shamos described the problem and its history at a seminar attended by Jay Kadane (a statistician at Carnegie-Mellon University), who designed the linear-time Algorithm 4 within a minute.
The solution is elegant and seemingly "obvious" after looking at it, but good luck coming up with it yourself :)
It's much more important to explain your thought process, work through the problem, and come up with any solution than it is to come up with the optimal solution in these interviews. I think that's what people who rail on standard coding interviews don't understand.
It's not about memorizing the answer to algorithm puzzles. In fact - if a candidate seems to know a problem by heart, that interviewer's feedback will often be discarded. It's about putting the candidate in a position where they have to think through a problem critically and seeing what trade-offs they make, what constraints they assume, and how they communicate their intent.
I have recommended hires for candidates who don't find the canonical solution many times.
I've had coworkers at Google tell me that they've informed candidates verbatim "don't bother giving me the O(n^2) solution" right when they start to go down that path. Hard to get much more of their thought process when you shut them down immediately.
(Also a Googler, not GP commenter. Speaking just for me.)
Yes, I have. Generally this was a case where the candidate had a good grasp on an approach to the question by the end of the interview but wasn’t able to write it due to time constraints.
I see interviews as a dialogue between me and the candidate where I give them hints in the right direction when required. Very few candidates require 0 hints.
Counteroffer: if you know that it's being asked in an interview, it's much easier to come up with a neat and elegant answer.
The test-taker within me pattern-matches this problem to "interview question with a single-pass linear-time constant-space algorithm". Single-pass constant-space algorithms are so heavily constrained that they're much easier to find. The big hurdle for the maximum subarray problem is knowing that a single-pass constant-space algorithm exists; finding it under those conditions is not that hard. The original inventors of the algorithms you mention had a much harder job than an interview candidate does: they did not know what optimum to aim for.
I ran into this case studying for interviews a while ago. The "maximum subarray problem"[1] is a common interview question, you are generally expected to be able to come up with the O(n) solution.
Well has a great passage about the origins of the problem and how multiple excellent algorithmists could not improve on a O(n^2) run time[2]:
> Grenander observed that the cubic time of Algorithm 1 was prohibitively slow, and derived Algorithm 2. In 1977 he described the problem to Michael Shamos of UNILOGIC, Ltd. (then of Carnegie-Mellon University) who overnight designed Algorithm 3. When Shamos showed me the problem shortly thereafter, we thought that it was probably the best possible; researchers had just shown that several similar problems require time proportional to N log N. A few days later Shamos described the problem and its history at a seminar attended by Jay Kadane (a statistician at Carnegie-Mellon University), who designed the linear-time Algorithm 4 within a minute.
The solution is elegant and seemingly "obvious" after looking at it, but good luck coming up with it yourself :)
[1]: http://cricca.disi.unitn.it/montresor/wp-content/uploads/201... [2]: https://en.wikipedia.org/wiki/Maximum_subarray_problem