Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
12  
The difficulty here being that integers can be negative? (otherwise the entire array is always the largest subarray, hence O(1) :-P ) –  Macke Feb 26 '11 at 23:24
4  
The problem should say "Find the contiguous subarray..." –  v64 Feb 27 '11 at 1:01
6  
I wouldn't make "in O(n)" a requirement in an interview. You can start with a naive solution and then refine it if you want, but I wouldn't expect someone to be able to derive an O(n) solution in a 1 hour interview without previous exposure to this algorithm. –  Dean Harding Feb 27 '11 at 4:51
2  
Right. This is an easy problem if you allow O(n²) solutions. –  dan04 Feb 27 '11 at 20:20
    
@Dean, I would hope they would be able to move a running aveerage type sum from location j to j+1 in O(1). Perhaps to be fair, that can be provided as a hint. (I am assuming the length of the subarray has been prespecified) –  Omega Centauri Feb 27 '11 at 23:24
show 1 more comment

4 Answers 4

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:

enter image description here

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.

share|improve this answer
add comment

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.

share|improve this answer
    
weather --> whether in fourth paragraph (and sorry for the noise, I don't have the rep to make typo edits...) –  Matthieu M. Feb 27 '11 at 9:53
    
Martin, I think it depends on the type of application you are interviewing people for. For systems types malloc is pretty simple. For me -I'm stuck, [I presume the stack address and length etc. have been deliberately hidden from me] with malloc, but the subarray problem is almost trivial. The key is matching the questions to the needs of the job. –  Omega Centauri Feb 27 '11 at 23:28
add comment

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.

share|improve this answer
    
Can someone explain why the algorithm described on wikipedia is needed, when the following conceptually much simpler algorithm works for me: In a single pass, calculate the cumulative sum, finding the minimum and maximum in the usual way. The maximal sum consecutive subsequence starts after the minimum cumsum index, and extends up to and including the maximum cumsum index. –  Ben Voigt Feb 27 '11 at 5:57
2  
@Ben Voigt: try the sequence {+2, -4, +1}, or {+1, +1, -1, -1, -1, -1, +1}. Actually, the Kadane method is very simple - it only scans the array once and keeps three variables updated in the style of dyanmic programming. –  rwong Feb 27 '11 at 7:28
    
@rwong: ah ok, Kadane is needed in the case when the minimum comes after the maximum. And I count 5 variables, not 3, plus the loop index. –  Ben Voigt Feb 27 '11 at 16:59
    
@Ben: you're right, it's 5 variables plus the loop index. –  rwong Feb 28 '11 at 6:12
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.