Google Interview Question
SDE1sCountry: United States
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: no, that's not true. The algorithm would say the answer is 0, which is a valid breaking point.
@FL: ideone . com/78jOcj . It gives the correct answer of 0 and 3. finds both points actually
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)
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
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
}
Along with (endSum == beginningSum) , you will have to ensure that (startIndex == endIndex - 1)
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 ...
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;
}
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)
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
}
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;
}
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.
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.
//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;
}
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);
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");
}
}
}
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.
Java Code
}
- RG January 23, 2014