Interview question ranking FizzBuzz (1), implementing malloc (10)

Question

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.

Answer 1

That really depends on the developer.

If malloc was 10 then I would rate this problem as 20. But then again I have done malloc before and could probably do it again.

Somebody that has done this problem or knows the appropriate algorithm of the top of their head will make it a 5 and malloc() a 10.

The problem with this type of question is that if you have done them before they are easy and this is really a test of whether you have seen this algorithm before. Thus I do not like them for interviews.

Now for tests where you give the developer a couple of days it is a perfectly good test because if they do not know the algorithm you then give them the chance to do the research and get up-to speed and it is a test of not only your knowledge but your ability to gain new knowledge.

Answer 2

I guess, the rating should be two-dimensional, at least. FizzBuzz-malloc describes the range on one axis, I would call it "technological complexity". But this single dimension is certainly not enough to describe the problem. To solve the problem in question, the developer should think more than code, while implementing malloc requires more of coding discipline than of creating complex algorithms.

So here's how I'd arrange these problems:

To illustrate my point, I added to parallel merge sort to the plot, as, I guess, it is a good example of both technologically and algorithmically sophisticated task.

Answer 3

I think it's considerably more difficult than FizzBuzz or HoppityHop--those two are nothing more than a simple if-else or switch-case in a loop.

The maximum sub-array will require deeper analysis of the underlying problem--it's not something you would expect to see in a beginner programming class as it requires higher mathematical skills than a FizzBuzz-type problem. This problem has a similar feel to the shortest path problem, which is solved by Dijkstra's algorithm--perhaps it's a specialization of the longest path problem.

On your scale of 1 to 10 I'd probably rate it between 3 and 5.

*While the server was down I found that the maximum subarray problem has its own page on wikipedia.

Answer 4

I give it a 3. Beyond most of the programmers I have interviewed, but an easy problem for those I recommended for hire.