Interview question int array

[Jehan Jaleel]

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]

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]

Backtracking maybe?

[fred rosenberger]

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.

[Alexander Sales]

please illustrate your problem.

[Mike Simmons]

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]

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]

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]

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]

If anyone is interested, this is how I would do it for any old array:

static int[] getHighestSumming(int[] values) {
  if (values.length == 0)
    return new int[] {};

  int first = 0;
  int last  = 0;

  int start   = 0;
  int current = 0;
  int highest = Integer.MIN_VALUE;

  for (int i = 0; i < values.length; i++) {
    current += values[i];

    if (current > highest) {
      first = start;
      last = i;
      highest = current;
    }

    if (current < 0) {
      start = i+1;
      current = 0;
    }
  }

  return Arrays.copyOfRange(values, first, last+1);
}