## 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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@ 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??

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

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]);

return res;
}``````

Comment hidden because of low score. Click to expand.
0

Please correct me if i miss anything.

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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.

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

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;
}``````

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);
}

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]``````

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]``````

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);
}``````

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.

Comment hidden because of low score. Click to expand.
0

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.

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++)

return result;
}``````

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);``````

}

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);``````

}

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;
}``````

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;
}``````

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;
}``````

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)``````

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)``````

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;
}

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;
}``````

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])``````

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])``````

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 ....

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)``````

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 .

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;
}``````

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;
}``````

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);
}``````

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.

### 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.