I'd like to have your opinion on the difficulty of the following interview question:
Find the contiguous subarray with maximum sum in an array of integers in O(n) time.
This trivial sounding problem was made famous by Jon Bentley in his Programming Pearls where he uses it to demonstrate algorithm design techniques.
On a scale of 1-10, 1 being the FizzBuzz (or HoppityHop) test and 10 being implement the C stdlib function malloc(), how would you rank the above problem?
I think the people who can best answer this question are those who have read Programming Pearls and have tried to solve this problem on their own. To motivate those who haven't, 'Programming Pearls' gets featured many times in the 'Top 10 programming books' list.
A couple of comments might help get a better rating:
Implementing malloc() is not as formidable as it seems. See K&R's C Programming Language for example. It sometimes gets asked at Microsoft.
CLRS observation on problem solving: it is often more difficult to solve a problem from scratch than to verify a clearly presented solution, especially when working under time constraints.