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
Monday, December 17, 2007
Google Interview Questions Part 2
Subscribe to:
Post Comments (Atom)
14 comments:
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 :)
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.
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);
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.
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.
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;
}
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.
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.
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
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/
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
nice collection.
You can also find google interview questions here
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
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
Post a Comment