my dog learned polymorphism*
The moose likes Java in General and the fly likes Interview question int array Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Interview question int array" Watch "Interview question int array" New topic
Author

Interview question int array

Jehan Jaleel
Ranch Hand

Joined: Apr 30, 2002
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
Ranch Hand

Joined: Nov 19, 2001
Posts: 174

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

Joined: Mar 10, 2008
Posts: 1761
    
    7

Backtracking maybe?


Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11256
    
  16

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?

I would immediately start asking questions about the array given.

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.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Alexander Sales
Ranch Hand

Joined: Feb 21, 2011
Posts: 89

please illustrate your problem.


OCPJP 6, OCEWCD Java EE 6
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3012
    
  10
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

Joined: Oct 02, 2003
Posts: 11256
    
  16

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

Joined: Mar 05, 2008
Posts: 3012
    
  10
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

Joined: Apr 30, 2002
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

Joined: Sep 20, 2010
Posts: 3615
    
  14

If anyone is interested, this is how I would do it for any old array:
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Interview question int array