Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Interview question int array

Jehan Jaleel
Ranch Hand
Posts: 196
Hi all,

I recently took an interview and got a challenging question on integer arrays. Basically if you have an int array of both positive and negative and you want get a sub array where the total is the largest sum possible, how would you do this? The interviewer said he needed the beginning and ending indecies from the original array.

Any suggestions on how this could be coded?

Carey Brown
Bartender
Posts: 1756
22
Is the input array in sorted order. That would be the simplest problem to solve. Else you would probably need to try all combinations of sums of some starting point to some ending point and make note of the one with the greatest sum.

Jelle Klap
Bartender
Posts: 1952
7
Backtracking maybe?

fred rosenberger
lowercase baba
Bartender
Posts: 12235
36
Questions like this are usually less about giving a solution than seeing how you approach the problem. Are you making assumptions? do you dive in with writing actual code?

is it sorted?
what are the possible ranges of values?
Is speed more important that memory consumption?
Will I need to do this once, for one specific array, or will this be used over and over for many different inputs?
What is the expected size of the input array?

I wouldn't even try to write a single line of code until i had those questions answered.

Alexander Sales
Ranch Hand
Posts: 89

Mike Simmons
Ranch Hand
Posts: 3090
14
I expect the answer to "is it sorted?" would be "no". That would have made the problem too simple.

There is a way to solve this with a single loop that reads each value in the array exactly once.

fred rosenberger
lowercase baba
Bartender
Posts: 12235
36
Mike Simmons wrote:I expect the answer to "is it sorted?" would be "no". That would have made the problem too simple.

agree, but it is still a valid question to ask.

Mike Simmons wrote:There is a way to solve this with a single loop that reads each value in the array exactly once.

now you've given me something to think about during my lunch break.

Mike Simmons
Ranch Hand
Posts: 3090
14
fred rosenberger wrote:
Mike Simmons wrote:I expect the answer to "is it sorted?" would be "no". That would have made the problem too simple.

agree, but it is still a valid question to ask.

Oh, absolutely - particularly in an interview. Same with the other questions suggested by you and others.

Jehan Jaleel
Ranch Hand
Posts: 196
Thanks all for your valuable advice. I think you are right in that the question was more about the approach then the actual solution. Actually they asked me this during a phone screen which is more of a reason to think that.

My face to face interview is next week. Any further tips you can offer on how to prepare and for the actual interview itself would be great appreciated.

Thanks again.

Stephan van Hulst
Bartender
Posts: 6486
83
If anyone is interested, this is how I would do it for any old array: