programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# 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
Saloon Keeper
Posts: 3328
46
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: 12565
49
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: 12565
49
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
Saloon Keeper
Posts: 7993
143
If anyone is interested, this is how I would do it for any old array:

 It is sorta covered in the JavaRanch Style Guide.