Google Interview Question for SDE1s


Country: United States




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

Java Code

public class BreakContiArray {

    public static void getBreakEvenPoint(int[] arr) {
        int first = 0;
        int second = 0;
        for(int i: arr) { second += i; }

        for(int i=0; i < arr.length-1; i++) {
            first = first + arr[i];
            second = second - arr[i];
            if(first == second ) {
                System.out.println("Break even point is: "+i);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,0,-1,-1,1};
        BreakContiArray.getBreakEvenPoint(arr);


    }

}

- RG January 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect !!!

- Vishal S Kumar January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You solution does not generalize. Consider the array {1,-1,0,1,1} ...

Your algorithm would say the breaking point is 1, which is incorrect.
{1, -1} = 0
{0,1,1} = 2.

The correct breaking point is 3, which would give us:
{1,-1,0,1} = 1
{1} = 1

- FL January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@FL: no, that's not true. The algorithm would say the answer is 0, which is a valid breaking point.

- Anonymous January 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@FL: ideone . com/78jOcj . It gives the correct answer of 0 and 3. finds both points actually

- Anonymous January 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about for this example : 1,0,0,1 ... what should be the breaking point ?

- Anonymous January 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the breaking point for {1,0,0,1} is {0,1,2} because
1 = 0+0+1
1+0 = 0 + 1
1+0+0 = 1

- meow February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

My solution would be:
1. divide the array to 2 sum sets, at this step first = 0, second = sum(arr)
2. maintain an index "i" initialized to 0
3. substract arr[i] from "second" and add the value to "first", then increment "i"
4. repeat the previous step until "first" and "second" are not equal, the solution will be "i-1" (but of course you can rearrange the loop as you like)

- aalmos January 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Really all you're asking for is to find an index k such that arr[0] + ... + arr[k] = 1/2 * sum of entire array. You could sum up the list, set your target value as 1/2 of the sum, and then start summing elements from the beginning until the total reaches the target value.

using System;
using System.Linq;

public static int GetBreakingPoint (int[] arr)
{
    int totalSum = arr.Sum(x => x);
    //no breaking point if numbers can't be divided by 2
    if (totalSum % 2 == 1)
    {
        return -1;
     }	
    int totalSoFar = 0
    for (int i=0; i<arr.Length; i++)
    {
         totalSoFar += arr[i];
         if (totalSoFar == totalSum/2)
         {
             return i;
         }
     }
     return -1;
}

You can see this working at ideone dot com / Y9S9vO

- eugene.yarovoi January 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simply use a cumulative array. Keep summing up the elements until the end. If the value at the end is n, the breaking point is the location where the sum is n/2.

- Murali Mohan January 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think in the above mentioned approach we will have to traverse the array twice. I am suggesting a small change.
Better we maintain two sums as mentioned above. lets say beginningSum, endingSum.
beginningSum = endingSum = 0 ;
two indices, startIndex and endIndex;
startIndex = 0;
lastIndex= arrayLength -1;
while(startIndex < lastIndex)
{
beginningSum = beginningSum+array[startIndex];
endSum = endSum+array[lastIndex];
if(beginningSum < endSum)
{
beginningIndex++;
}
else
{
lastIndex++;
}
}
if(endSum == beginningSum)
{
print start index as breaking point
}
else
{
print no breaking point exists
}

- timepass January 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

lastIndex should be decremented.actually

- timepass January 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Along with (endSum == beginningSum) , you will have to ensure that (startIndex == endIndex - 1)

- Murali Mohan January 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There's also a bug with calculating beginningSum/endSum (incremented even if their index have not changed).

Also need to note that this approach only works for non-negative numbers, because you assume the "sum at the breaking point" to be greater-equal than the beginningSum/endSum.

The funny thing with negative numbers is that you could actually have more than one breaking point. For example, in [ 1, -1, 2, -2, 3, -3 ] you could break after -1 or -2 ...

- Anonymous January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findBreakPoint(int [] array){
		int sum = 0;
		for (int i = 0;i<array.length ;++i){
			sum+=array[i];
		}
		
		if (sum%2!=0){
			return -1;
		}
		
		int res = 0;
		int breakingPoint = 0;
		for (; res<=sum/2;++breakingPoint){
			res+=array[breakingPoint];
			if (res==sum/2){
				return breakingPoint;
			}
		}
		
		return -1;

}

- Scott January 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findBreakingPoint (int[] arr) {
  int sum = 0;
  for (int i:arr) {
    sum += i;
  }
  int newSum=0;
  for (int brPoint=0; brPoint<arr.length; brPoint++) {
    newSum += arr[brPoint];
    if (2*newSum == sum) return brPoint;
  }
  return -1;
}

- Anonymous January 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findBreakingPoint (int[] arr) {
	if (arr.length > 0) {
		int sum = 0;
		for (int i:arr) sum += i;
		if (sum^1 != 0) return -1; \\sum cannot be odd
		sum >>= 1;
		for (int pos = 0; pos < arr.length; pos++) {
			target -= arr[pos];
			if (target == 0) return pos;
		}
	}
	return -1;
}

- chriscow January 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use dynamic programming
here is a solution in python:

def f(a):
	s=sum(a)
	m=0
	for i in range(len(a)):
		m=m+a[i]
		s=s-a[i]
		if m==s:
			return i

time complexity : O(n)

- anon123 January 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This isn't dynamic programming.

- Anonymous January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

m for each i is computed from previous value of m. made me think that there are overlapping subproblems
theres no optimal substructure
you might be right

- anon123 January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sum=sum of all of the elements at array a
int tempSum=0;
int j;
for(j=N-1;j<=0;j--)
{
sum-=a[j];
tempSun+=a[j];
if(sum==tempSum)break;
}
return j-1;

- hirajhil January 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I started with 2 sub-Arrays. Front-Array starts with only one element and grows till the 2nd last element ((n-1)st element). The Back array consists all the elements from 2nd element to the last element (nth element) and it reduces to just one element(last element).

Loop Invariant: 
	The sum of the size of sub-arrays = size of the input array
	The total elements' sum of sub-arrays = elements' sum of the input array

public static int findBreakPoint(int[] array)
	{
		int sumFrontArray = array[0], sumBackArray = 0;
		for(int i = 1 ; i < array.length ; i++)
			sumBackArray += array[i];
	
		if(sumFrontArray == sumBackArray)
			return 0;				// returning 0th index
		
		for(int i = 1 ; i < array.length - 1 ; i++)
		{
			sumFrontArray += array[i];
			sumBackArray -= array[i];
			if(sumFrontArray == sumBackArray)
				return i;			// return the index when found
		}
		
		return -1;					// return -1 when breaking point not found
	}

- Amit Kumar Yadav January 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getBreakingPoint( int[] array )
{
int sum = 0;

for( int element : array)
sum += element;

if((sum & 1) != 0)
return -1;

int breakVal = sum >> 1;

int breakSum = 0;

for (int i = 0; i < array.length - 1; i++) {
breakSum += array[i];
if(breakSum == breakVal)
return i;
}

return -1;
}

- Anonymous January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step1 : First sum all the element of array.and store this in variable part2,

Step 2: Initialize variable part1 to 0 and iterate array from index  0.

Step 3: For each iteration part1=part1+array[index]  and part2=part2-array[index] and chk for (part1==part2), if it satisfy this condtion den current index is the breaking point.

- Ankit Garg January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step1 : First sum all the element of array.and store this in variable part2,

Step 2: Initialize variable part1 to 0 and iterate array from index 0.

Step 3: For each iteration part1=part1+array[index] and part2=part2-array[index] and chk for (part1==part2), if it satisfy this condtion den current index is the breaking point.

- Ankit Garg January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//works with negative values
	int GetBreakingPoint(int arr[], int nSize)
	{
		int nTotalSum = 0;

		for(int i = 0; i < nSize; ++i)
		{
			nTotalSum += arr[i];
		}

		if(nTotalSum % 2)
			return -1;


		int nItemVal = nTotalSum/2;

		int nBPIndex = -1;

		for(int i = 0; i < nSize; ++i)
		{
			if(i != 0)
			{
				arr[i] = arr[i] + arr[i - 1];
				if(arr[i] == nItemVal)
				{
					nBPIndex = i;
					break;
				}
			}
		}

		//restore the array
		if(nBPIndex != -1)
		{
			for(int i = nBPIndex; i > 0; --i)
			{
				arr[i] = arr[i] - arr[i - 1];
			}

		}

		return nBPIndex;
	}

- Anonymous January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int findBreakingpt(int[] in) {
		int result1=0;
		int result2=0;
		for(int i =0;i<in.length;i++) {
			result1 +=in[i];
			result2=0;
			for(int j=i+1;j<in.length;j++) {
					result2 +=in[j];
					if(result2>result1)
						break;
			}
			if(result1 == result2)
				return i;
		}
		
		return -1;
	}

- Vikas January 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In case someone wants a recursive approach , not the most optimal, but simple to understand

var getSum = function(inputs, start, end){

var ret = null;

for(var i = start; i <= end; i++)
    ret += inputs[i];
    
return ret;

}


var breakPt = function breakPt(inputs, leftIndex, rightIndex){
    
    if(leftIndex >= inputs.length)
        return -1;
    
    if(rightIndex < 0)
        return -1;

    if(leftIndex + 1 == rightIndex){
    
        var leftSum = getSum(inputs, 0, leftIndex);
        var rightSum = getSum(inputs, rightIndex, inputs.length - 1);
        
        if(leftSum === rightSum){
            return leftIndex;
        }
        
    }

    var leftAdvance = breakPt(inputs, leftIndex + 1, rightIndex);
    var rightAdvance = breakPt(inputs, leftIndex , rightIndex - 1);
    
    if(leftAdvance >= 0)
        return leftAdvance;
    else if(rightAdvance >= 0)
        return rightAdvance;
    else 
        return -1;

}

var test = [1,0,-1,-1,1];

breakPt(test,0,test.length);

- anni January 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One more approach. Using the sum/2 method.

#include <stdio.h>

int main()
{

    int a[100];

    int n =0;
    int sum, i, sum1;

    while (1)
    {

        printf ("\nEnter number of elements in array \n");
        scanf("%d", &n);
        printf ("\nEnter elements of array \n");

        for (i = 0; i <n; i++)
        {
            scanf ("%d", &a[i]);
        }

        sum = 0;
        for (i=0; i < n; i++)
        {
            sum+=a[i];
        }
        sum /=2;

        sum1=0;
        for (i =0; i <n; i++)
        {
                sum1 += a[i];


            if (sum == sum1)
            {
                printf ("The breaking point is %d\n", i);
                break;
            }
        }
        if (sum != sum1)
        {
            printf("\n Did not find breaking point\n");
        }
    }

}

- Sandeep January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 4 vote

1) Count two cumulative sums from left to right and from right to left. Store the results in corresponding arrays.
2) Iterate over the left -> right array and check if at any position leftRight[i] == rightLeft[i+1] if yes current position is a breaking point.
Code:

public static void main(String[] args) {

	int[] arr = { 1, 2, 3, 4, 5, 2, 5, 4, 4 };
	int[] leftRightSum = new int[arr.length];
	int[] rightLeftSum = new int[arr.length];

	leftRightSum[0] = arr[0];
	for (int i = 1; i < arr.length; i++) {
	    leftRightSum[i] = arr[i] + leftRightSum[i - 1];
	}

	rightLeftSum[arr.length - 1] = arr[arr.length - 1];
	for (int i = arr.length - 2; i >= 0; i--) {
	    rightLeftSum[i] = arr[i] + rightLeftSum[i + 1];
	}

	for (int i = 0; i < arr.length - 1; i++) {
	    if (leftRightSum[i] == rightLeftSum[i + 1]) {
		System.out.println("Breaking point is at " + i);
	    }
	}
 }

Note you can skip one array and keep only running counter. However I kept it for better demonstration.

- thelineofcode January 23, 2014 | 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