Google Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
3
of 3 vote

Kadane algorithm , taking into account negative cases

- EPavlova February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Kadane algorithm gives sum of the largest continuous subarray , task is to find elements of that largest subarray as @zr.roman bro already commented above

- abhay0609 February 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

actually, Kadane is a correct approach, but the algorithm should be modified to keep track of the starting and ending indices of the maximum subarray.

- zr.roman February 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ zr.roman yup, Kadane is correct approach in modified way, thats how i solved the problem but didnot mention algo name in my code, so i want to know is it necessary to tell name of the algo to interviewer, as i am preparing for my tech interviews or implementation is enough??

- abhay0609 February 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

actually, I don't know. Well, by default, the more you tell the better.
As I understand the interviewer when he gives such a task, he wants to know the approach.
For example, this task can be solved with 3 approaches:
1) brute force O(n^2),
2) divide'n'conquer O(n log n)
3) DP O(n).
I think, that is the basis.
Moreover, in CLRS textbook the DP approach is described but not mentioned that it is Kadane.

- zr.roman February 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ zr.roman I got the point...thanks

- abhay0609 February 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static ArrayList findConsecutiveMaxSum(int[] nums){

        if(nums.length<1) return null;

        ArrayList<Integer> res = new ArrayList<>();

        int maxSofar, currMax,startIndx =0,endIndx =0;

        maxSofar = currMax = nums[0];

        for (int i = 1 ; i< nums.length ;i++){

            if(currMax + nums[i] < nums[i]) startIndx = i;

            currMax = Math.max(nums[i],currMax+nums[i]);

            if(maxSofar<currMax) endIndx = i;

            maxSofar = Math.max(maxSofar,currMax);

        }

        for (int i = startIndx ; i<=endIndx ;i++) res.add(nums[i]);
        
    if(endIndx<startIndx) res.add(nums[endIndx]);
       
        return res;
    }

- abhay0609 February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please correct me if i miss anything.

- abhay0609 February 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The below code will give you max Sum in O(N).
We just have to get the startIndex and endIndex(when you make tempSum 0) and get the values in-between them.

public static int maxSum(int[] numbers)
	{
		/*
		 *  Handle Edge cases
		 *  1. is input Array is NULL
		 *  2. If input Array has only one element
		 */
		if(numbers == null)
		{
			return -1;
		}
		int maxSum = 0;
		int tempSum = 0;
		// int numbers[] = { 1 , 3 , -5 , 3 , 2 , 1 , -3 , 4 , 2 , -12 , 2 , 3}	
		// Iterating through the array 0...N
		for(int i=0; i< numbers.length; i++)
		{
			// Adding it to temp Sum
			tempSum = tempSum + numbers[i];
			if(maxSum < tempSum)
			{
				maxSum = tempSum;
			}
			// If temp Sum is less than 0, making it to Zero.
			// Ex: 1 + 3 + -5 = -1. In this case, making tempSum to Zero, so that -1 doesnt affect the sum of the next sequence
			else if(tempSum < 0)
			{
					tempSum = 0;
			}		
		}
		return maxSum;
	}

- PS February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You need to add special condition for array with only negative numbers.
{-1,-2,-3}

- Anonymous February 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you need to handle use case where array contains only negative numbers
eg) {-1,-2,-3}

- Coder February 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the task is to return the subarray, not the maxSum.

- zr.roman February 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will not work for -3, 1, -2,1, -2

- Debabrata February 10, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will not work for -3, 1, -2,1, -2

- Debabrata February 10, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you explain more about interview - is it phone call or site.

- EPavlova February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

modified Kadane.
c#

private static int[] Kadane( int[] arr ) {

    var coords = new int[2] { 0, 0 };
    int maxByNow = arr[ 0 ], greatest = arr[ 0 ];

    for (int i = 1; i < arr.Length; i++) {
        if ( maxByNow < 0 ) { coords[ 0 ] = i; }
        maxByNow = Math.Max( arr[ i ], maxByNow + arr[ i ] );
        var tmp = Math.Max( greatest, maxByNow );
        if ( tmp > greatest ) { coords[ 1 ] = i; }
        greatest = tmp;
    }
    int[] res = new int[ coords[ 1 ] > coords[ 0 ] ? coords[ 1 ] - coords[ 0 ] + 1 : 1 ];
    res[ 0 ] = arr[ coords[ 1 ] ];
    for ( int i = coords[ 0 ]; i <= coords[ 1 ]; i++ ) {
        res[ i - coords[ 0 ] ] = arr[ i ];
    }
    return res;
}

- zr.roman February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
int main(){
int n=0,i=0;
int max_end=0;
int max_far=0;
scanf("%d",&n);
int array[n];
while(i<n){
scanf("%d",&array[i]);
i++;
}
for(i=0;i<n;i++){
max_end=max_end+array[i];
if(max_end<0){
max_end=0;
}
if(max_far<max_end){
max_far=max_end;
}
}
printf("%d",max_far);
}

- pardeep February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) solution in Python
returns a list of consecutive numbers with the biggest sum

def findConsecutiveIntegerBiggestSum(l):
    
    if type(l) != list:
        raise Exception('input is not a list')
    if len(l) == 0:
        raise Exception('list is empty')
    
    accum_li = [0] * len(l)
    accum = 0
    ct_pos = 0
    for i, v in enumerate(l):
        accum += v
        accum_li[i] = accum
        if v > 0:
            ct_pos += 1

    if ct_pos < 2:
        return [max(l)]
    
    best_sum = accum_li[-1]
    best_low = 0
    best_high = len(l) - 1
    
    curr_low = 0
    curr_high = len(l) - 1
    
    while(curr_high - curr_low > 1):
        
        curr_sum = accum_li[curr_high] - accum_li[curr_low]

        if curr_sum > best_sum:            
            best_sum = curr_sum
            best_low = curr_low + 1
            best_high = curr_high
            
        if l[curr_low] > l[curr_high]:
            curr_high -= 1
        else:
            curr_low += 1
            
    return l[best_low : best_high + 1]

- NH February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Python
- O(N)
- needs two pass over entire list
- returns a list containing consecutive numbers which give the max sum

def findConsecutiveMaxSum(l):
    
    if type(l) != list:
        raise Exception('input is not a list')
    if len(l) == 0:
        raise Exception('list is empty')
    
    accum_li = [0] * len(l)
    accum = 0
    ct_pos = 0
	
    #first pass: integrate over list
    for i, v in enumerate(l):
        accum += v
        accum_li[i] = accum
        if v > 0:
            ct_pos += 1

    if ct_pos < 2:
        return [max(l)]
    
    best_sum = accum_li[-1]
    best_low = 0
    best_high = len(l) - 1
    
    curr_low = 0
    curr_high = len(l) - 1
    
    #second pass: try to improve sum
    while(curr_high - curr_low > 1):
        
        curr_sum = accum_li[curr_high] - accum_li[curr_low]

        if curr_sum > best_sum:            
            best_sum = curr_sum
            best_low = curr_low + 1
            best_high = curr_high
            
        if l[curr_low] > l[curr_high]:
            curr_high -= 1
        else:
            curr_low += 1
            
    return l[best_low : best_high + 1]

- n_h February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Kadane algorithm in Java

private static void kadaneAlgo(int[] input){
        int max_curr=input[0];
        int curr_start=0;
        int curr_end=0;
        int max_ref=Integer.MIN_VALUE;
        int max_start=0;
        int max_end=0;
        for(int i=0;i<input.length;i++){
            if(input[i] > max_curr+input[i]){
                max_curr=input[i];
                curr_start=i;
                curr_end=i;
            }else{
                max_curr+=input[i];
                curr_end=i;
            }
            if(max_curr>max_ref){
                max_ref=max_curr;
                max_start=curr_start;
                max_end=curr_end;
            }
        }
        System.out.println("Max sum of subarray --> "+max_ref+" with index start "+max_start+" index end "+max_end);
    }

- t@_@n February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm preparing to apply for tech companies next months and wanted to ask you guys. How on earth am I supposed to know there is an algorithm called "Kadane algorithm" would solve this problem? Do you learn that at school? (I'm from a different country)

My thinking of tech interviews was that it measures how someone could find a solution for a given problem in a short period of time, not memorize unknown algorithms and write them down at the time of interview. So frustrating.

- JK February 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's such a bullshit. It's all about how much you know now. Because of all the people sitting down and memorizing all the algorithms and questions, interviews have become all about how much you know.

- nope February 13, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This code returns a list of the elements that gives the max sum, the code uses dynamic programming

public List<int> FindMaxSum(int[] values)
{
    int sum = values[0];
    int index = 0;
    int maxSum = values[0];
    int maxIndex = 0;
    int minIndex = 0;

    for (int i = 1; i < values.Length; i++)
    {
        if (sum + values[i] > values[i])
        {
            sum += values[i];
        }
        else
        {
            sum = values[i];
            index = i;
        }

        if (sum > maxSum)
        {
            maxSum = sum;
            maxIndex = i;
            minIndex = index;
        }
    }

    var result = new List<int>();
    for (int i = minIndex; i <= maxIndex; i++)
        result.Add(values[i]);

    return result;
}

- hnatsu February 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Prints the largest sum, and the start/end indices (indices begin from 0). Change array vars and length if needed.

#include <stdio.h>

main()
{
    int nums[100] = {-2,1,-3,4,-1,2,1,-5,4}, length = 9, i = 0, j = 0;
    int largestSum = 0, largestSumBegin = 0, largestSumEnd = 0; 
    int tempSum = 0, tempSumBegin = 0;

    for (i = 0; i < length; i++) {
         if (i == 0) {
             largestSum = tempSum = nums[i];
         }
         tempSum += nums[i];
         if (tempSum > largestSum) {
             largestSum = tempSum;
             largestSumBegin = tempSumBegin;
             largestSumEnd = i;
         }
         if (tempSum < 0) {
             tempSum = 0;
             tempSumBegin = i+1;
         }
    }

    printf("\nlargest sum = %d, start idx = %d, end idx = %d", largestSum, largestSumBegin, largestSumEnd);

}

- SK February 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

main()
{
    int nums[100] = {-2,1,-3,4,-1,2,1,-5,4}, length = 9, i = 0, j = 0;
    int largestSum = 0, largestSumBegin = 0, largestSumEnd = 0; 
    int tempSum = 0, tempSumBegin = 0, tempSumEnd = 0;

    for (i = 0; i < length; i++) {
         if (i == 0) {
             largestSum = tempSum = nums[i];
         }
         tempSum += nums[i];
         if (tempSum > largestSum) {
             largestSum = tempSum;
             largestSumBegin = tempSumBegin;
             largestSumEnd = i;
         }
         if (tempSum < 0) {
             tempSum = 0;
             tempSumBegin = i+1;
         }
    }

    printf("\nlargest sum = %d, start idx = %d, end idx = %d", largestSum, largestSumBegin, largestSumEnd);

}

- SK February 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void max_sum_cons(const int* arr, const int n)
{

    int starting_pt[n];
    int sums[n];
    
    sums[0] = arr[0];
    starting_pt[0] = 0;
    
    int max_sum = sums[0];
    int max_loc = 0;
    
    for(int i = 1; i < n; ++i)
    {
        if(sums[i-1] > 0)
        {
            sums[i] = sums[i-1] + arr[i];
            starting_pt[i] = starting_pt[i-1];
            
            if(max_sum <= sums[i])
            {
                max_sum = sums[i];
                max_loc = i;
            }
        }
        else
        {
            sums[i] = arr[i];
            starting_pt[i] = i;
            
            if(max_sum <= sums[i])
            {
                max_sum = sums[i];
                max_loc = i;
            }
        }
    }
    
    for(int i = starting_pt[max_loc]; i <= max_loc; ++i)
        std::cout << arr[i] << " ";
        
    std::cout << std::endl;
}

- badcoder February 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void max_sum_cons(const int* arr, const int n)
{

    int starting_pt[n];
    int sums[n];
    
    sums[0] = arr[0];
    starting_pt[0] = 0;
    
    int max_sum = sums[0];
    int max_loc = 0;
    
    for(int i = 1; i < n; ++i)
    {
        if(sums[i-1] > 0)
        {
            sums[i] = sums[i-1] + arr[i];
            starting_pt[i] = starting_pt[i-1];
            
            if(max_sum <= sums[i])
            {
                max_sum = sums[i];
                max_loc = i;
            }
        }
        else
        {
            sums[i] = arr[i];
            starting_pt[i] = i;
            
            if(max_sum <= sums[i])
            {
                max_sum = sums[i];
                max_loc = i;
            }
        }
    }
    
    for(int i = starting_pt[max_loc]; i <= max_loc; ++i)
        std::cout << arr[i] << " ";
        
    std::cout << std::endl;
}

- bad_coder February 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findHighestSum(int[] arr){
        int temp = 0;
        int max = Integer.MIN_VALUE;
        for(int num : arr){
            if(max < 0){
                if(num>max){
                    max = num;
                    temp = max;
                }else{
                    temp+=num;
                }
            }else{
                if(num+temp>max){
                    max = num+temp;
                    temp = max;
                }else{
                    temp+=num;
                }
            }
        }
        return max;
    }

- ricardo.mogg February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My version in Python, O(n):

from sys import maxint

def max_subarray(A):
    max_ending_here = max_so_far = 0
    index_low = index_high = 0
    negative_case = -maxint

    for x in A:
    	if max_ending_here + x > 0:
    		max_ending_here += x
    	else:
    		max_ending_here = 0
    		index_low = A.index(x) + 1

    	if max_ending_here > max_so_far:
    		max_so_far = max_ending_here
    		index_high = A.index(x)

    	if x > negative_case:
    		negative_case = x

    if sum(A[index_low:index_high]) == 0:
    	return negative_case
    return max_so_far,index_low,index_high,A[index_low:index_high + 1]

A = [-2,-7,-6,-4,-1,-5,-8,-1,-7]
print max_subarray(A)

- tulians February 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My version in Python, O(n)

from sys import maxint

def max_subarray(A):
    max_ending_here = max_so_far = 0
    index_low = index_high = 0
    negative_case = -maxint

    for x in A:
    	if max_ending_here + x > 0:
    		max_ending_here += x
    	else:
    		max_ending_here = 0
    		index_low = A.index(x) + 1

    	if max_ending_here > max_so_far:
    		max_so_far = max_ending_here
    		index_high = A.index(x)

    	if x > negative_case:
    		negative_case = x

    if sum(A[index_low:index_high]) == 0:
    	return negative_case
    return max_so_far,index_low,index_high,A[index_low:index_high + 1]

A = [-2,-7,-6,-4,-1,-5,-8,-1,-7]
print max_subarray(A)

- tulians February 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
int arr[5]={-2,5,-1,7,-3};
int i,j,k,counter,sum,l,m,temp;
temp=0;
int n;
for(i=0;i<5;i++)
{
counter=-1;
for(j=0;j<=i;j++)
{
counter++;
k=counter;
sum=0;
for(l=0;l<5-i;l++)
{
sum=sum+arr[k];
k=k+1;
}
printf("%d",sum);
if(sum>temp)
{
temp=sum;
}
}
}


printf(" biggest sum from give array:=>%d",temp);
return 0;
}

- mithleshtechno February 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

long ConsecutiveLargestSum(vector<long>& data, vector<long>& result)
{
	long max_ending_here = 0, max_so_far = 0;
	vector<long>::iterator start, end;
	for (vector<long>::iterator it = data.begin(); it != data.end(); it++) {
		max_ending_here += *it;
		if (max_ending_here < 0) {
			max_ending_here = 0;
			start = end = data.begin();
		}
		if (max_so_far < max_ending_here) {
			max_so_far = max_ending_here;
			if (start == data.begin())
				start = it;
			end = it;
		}
	}
	result.assign(start, end + 1);
	return max_so_far;
}

- funcoolgeek February 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

slick python solution

def max_list(arr):
	i,j,s,mi,mj,ms = 0,0,0,0,0,0
	for i in xrange(len(arr)):
		s += arr[i]
		if s <= 0:
			j = i+1
			s = 0
		if s > ms:
			ms = s
			mi,mj = i,j
	return arr[mj:mi+1]
print max_list([-2,5,-1,7,-3])

- eric February 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def max_list(arr):
	i,j,s,mi,mj,ms = 0,0,0,0,0,0
	for i in xrange(len(arr)):
		s += arr[i]
		if s <= 0:
			j = i+1
			s = 0
		if s > ms:
			ms = s
			mi,mj = i,j
	return arr[mj:mi+1]
print max_list([-2,5,-1,7,-3])

- eric03 February 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can first sort the list and can take the last two integers ....

- Bibhu February 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive Approach:

from sys import maxint

def max_subarray(A):
    if not A:
        return -maxint

    max_sub = A[0]
    sum_subarray = 0

    for i in range(len(A)):
        sum_subarray += A[i]
        if sum_subarray < 0:
            break
        if max_sub < sum_subarray:
            max_sub = sum_subarray


    return max(max_sub,max_subarray(A[i+1:]))

A = [-3,20,50,300,-400,80,10,-4]
print max_subarray(A)
A = [-3,-5,-4]
print max_subarray(A)
A = [-3,20,50,-400,80,10,-4]
print max_subarray(A)
A = [-3,20,50,-40,80,10,-4]
print max_subarray(A)
A = [-30,20,50,-400,80,10,10,-400,100,20,-40]
print max_subarray(A)

- Mohsen Jamali March 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are you talking about the abs max sum?
Cause in the example 5 -17 gives you -12 where as -2 5 gives you 3.
And so the biggest sum would be due to -2 5 .

- Gravier Carl March 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a simple approach

public static int kadane(int[] a){
        int maxTillNow = a[0];
        int overallMax = 0;
        for(int i=1;i<a.length;i++){
            if(maxTillNow+a[i]>0)
                maxTillNow += a[i];
            overallMax = Math.max(maxTillNow,overallMax);
        }
        return overallMax;
    }

- xyz June 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a simple approach

public static int kadane(int[] a){
        int maxTillNow = a[0];
        int overallMax = 0;
        for(int i=1;i<a.length;i++){
            if(maxTillNow+a[i]>0)
                maxTillNow += a[i];
            overallMax = Math.max(maxTillNow,overallMax);
        }
        return overallMax;
    }

- lks June 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]){
        
		int[] arr = {-2,5,3,-1,7,-3};
		int arrLen = arr.length;
		int maxSum = 0;
		String str ="";
		String maxStr = "";
		for (int i = 2; i <= arrLen; i++){
			for (int j=0; j< arr.length; j++){
				int temp =0;
				int k = j;
				str ="";
				while (k < j+i && (j+i <arrLen)){
					temp += arr[k];
					str = str + " " + arr[k];
					k++;
				}
				if (temp > maxSum){
					maxSum = temp;
					maxStr = str;
				}
			}
		}
		System.out.println("Sum : " + maxSum);
		System.out.println(maxStr);
	}

- Gunjan July 22, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More