Monday, December 17, 2007

Google Interview Questions Part 2

Well here is the solution for the question from

http://j2ee-now.blogspot.com/2007/12/google-interview-questions-part-1.html

First you should pass on the list and create a new list with the summary of the numbers till now, for example if the list is:

-7 12 -5 13 -2

Then the new list would be:

-7 5 0 13 11

The subset with holds the largest sequential sum is the subset from the lowest number in the new list plus index 1 (In our case -7 (index 0) is the lowest so we start from 5 (index 1)) till the highest number in the list which is 13 (index 3) so the result is (12, -5, 13) which it's sum is 20.

Why does it work? because if we went from he lowest sum till now to the highest sum till now this is the biggest different of the numbers in the summary therefore this numbers sum would be the largest in the list.



You can find more Google Interview Questions here:

Google Interview Questions Part 3
Google Interview Questions Part 4
Google Interview Questions Part 5
Google Interview Questions Part 6
Google Interview Questions Part 7

14 comments:

Jake Voytko said...

Your solution doesn't always work. In the list (1, 3, 5, 7, 9, -2, -1), your solution would get us (3, 5, 7, 9) as the solution, when it should be (1, 3, 5, 7, 9). Edge cases are important :)

Sam said...

Hehe I wonder how google would feel about you getting an off-by-1 error :)

I think they would look the other way 'cause this is a sweet algorithm.

Anonymous said...

You can try this code:

int foundStartIndex = 0;
int foundLength = 1;
int foundMaxSum = list[0];
int currentSum = 0;
int currentIndex = 0;

for (int i = 0; i < list.length; i++) {
currentSum = currentSum + list[i];

if (currentSum > foundMaxSum) {
foundMaxSum = currentSum;
if (currentSum > list[i]) {
foundLength = i - foundStartIndex + 1;
} else {
foundLength = 1;
}
}
if (foundStartIndex != i
&& (currentSum - list[currentIndex]) > foundMaxSum) {
currentSum -= list[currentIndex];
foundMaxSum = currentSum;
foundStartIndex = ++currentIndex;
} else if (currentSum < 0) {
currentSum = list[i];
currentIndex = i;
}
}

System.out.println("foundStartIndex: " + foundStartIndex);
System.out.println("foundLength: " + foundLength);
System.out.println("foundMaxSum: " + foundMaxSum);

Ray Cromwell said...

Trivial counter example: 1million, followed by 500,000 "-1", followed by 1 million. Solution is the entire set with sum of 1.5 million, your proposal would return merely 1 million.

alider said...

Hi,
I'm an author of the code pasted above. My english isn't so good so i thought that it will be better to put the code to explain the solution, but when i'm looking on it now i think i was wrong. It needs some words.

The idea is very simply - while iterating over the list try to get the next element from the list, add to the sum and check if this new sum (currentSum) is bigger then previous (foundMaxSum). Also except the first iteration try the sum without the first element of the already found subset maybe the sum is bigger without it.

The second 'if' is independent from the first one, because there can be a case when both are true e.g.:
-5,10,5
iter = 1 (O based)

This second 'if' has a 'else' statement which is about 'currentSum'. This is the most complex part. This variable is used to keep the sum which can be part to the final solution but it doesn't have to be true, so it's the reason why i keep it separate from the current final solution (foundMaxSum) e.g. neither the next element added to the sum nor the first element removed from it doesn't make the sum bigger but it doesn't mean that the this temp subset (sum) can not be the part of the largest solution. I keep it until it goes below to zero then i reset it.

foo said...

int maxsum(int[] arr) {
_int maxsum=arr[0];
_for (int x=1; x < arr.length; x++)
__maxsum=Math.max(arr[x]+maxsum, arr[x]);
_return maxsum;
}

superq said...

Here is my solution:

We need to scan the list twice, the first time forward and the second time backward.

When scanning forward, we keep a sum of numbers we have seen so far and remember the number that gives us maximum sum. (This is exactly the same as what you propose.) At last, the number that gives us maximum sum is the right end of the sub-sequence we are looking for. (Why is this the right number? This is like buying stock, if you hold it further, there will be more damage than gains.)

So how to find left-end of the sub-squence? Easy, we just scan the list backwards, starting from the last number in the list. Similarly, we sum them up and find the number that gives us maximum sum. That would be the left end.

EIFY said...

superq, your algorithm breaks down in this counter example:

1, -9, 1
1, -8, -7 (sum from the left)
-7, -8, 1 (sum from the right)

The return of the algorithm is invalid because the right end is left to the left end.

Anonymous said...

My Algorithm:
Start with the first number, add the next number...if the number is larger
than the sum of the number and last number choose the number alone,
else add both to the sequence... continue adding until there is a decrease in the size...
stop ... skip this number and continue with the algorithm. store the index. Start with a new list beginning after the number you skipped.
Now continue adding to both the old and new lists and check if the new list is larger than the old list.
everytime we face a condition where a value drops spawn a new list.
space complexity gets higher though

Prashant Jalasutram said...

Hi,

Thanks a lot for sharing these type of questions as we programmers become dumb as mentioned by one user and we really need to update our knowledge only with these type of problems.

Thanks
Prashant Jalasutram
http://prashantjalasutram.blogspot.com/

COTOHA said...

hello all,

my coworker proposed very nice recursive solution:



std::vector <int> array;
int maxSum = INT_MIN;
unsigned posStart;
unsigned posEnd;
unsigned curPosEnd;

int getMaxSum(unsigned pos)
{
int res = 0;

if (pos >= array.size())
return 0; if (pos == (array.size() - 1))
{
res = array[pos]; curPosEnd = pos; }
else
{
res = array[pos];
int rightSum = getMaxSum(pos + 1);
if (rightSum > 0) res += rightSum;
else
curPosEnd = pos;
}

if (res > maxSum) {
maxSum = res; posEnd = curPosEnd;
posStart = pos;
}

return res;
}

int main(int argc, _TCHAR* argv[])
{

// fill in array

getMaxSum(0);

// check maxSum, posStart and posEnd
// for SUM and start and end indexes of the sequence.

return 0;
}


and the complexity is O(n) exactly.

by the way she's blonie O_o

Anonymous said...

nice collection.
You can also find google interview questions here

Anonymous said...

The solution posted by COTOHA doesn't work.

For 20, 10, -8, 9, -9 , 0 it returns 31 which is correct but for -10, 20, 10, -8, 9, -9 , 0 it returns 21 instead of 31

Anonymous said...

It works!!!

anonymous wrote:
"For 20, 10, -8, 9, -9 , 0 it returns 31 which is correct but for -10, 20, 10, -8, 9, -9 , 0 it returns 21 instead of 31"

But the algorithm calculate this new list:
-10, 10, 20, 12, 21, 12, 0
The lowest number is -10
the highest number is 21
therefore the numbers between -10 and 21 are the highest subset in which their sum is 21-(-10)=31

Links

 
RSS Feeds Submission Directory