## Google Interview Question

Development Support EngineersYou talking about the Balanced Partition right? I think that's a harder problem than the one being asked here. The one here is about splitting the array somewhere in the middle. In other words, each subarray consists of contiguous elements.

```
public static void partitionNegArray(int data[]){
int minElement = 0;
for(int index = 0; index < data.length; index++){
if(minElement > data[index]){
minElement = data[index];
}
}
int copyData[] = new int[data.length];
minElement = Math.abs(minElement);
for(int index = 0; index < data.length; index++){
copyData[index] = data[index] + minElement;
}
partitionArray(copyData);
}
public static void partitionArray(int data[]){
// Find Sum
int sum = 0, maxSubSetSize = data.length>>1;
for(int value : data){
sum += value;
}
int halfSum = sum>>1;
int subsetSum[][] = new int[maxSubSetSize +1][halfSum + 1];
subsetSum[0][0] = 1;
for(int i = 0; i < data.length; i++){ //consider taking i-th item
for(int k = maxSubSetSize - 1; k >= 0; k--){ //each item must be taken once, hence loop backwards
for(int j = 0; j <= halfSum - data[i]; j++){
if (subsetSum[k][j] == 1 && (data[i] + j <= halfSum)){
subsetSum[k+1][j+data[i]] = 1;
}
}
}
}
for(int j = halfSum; j >= 1; j--){
if(subsetSum[maxSubSetSize][j] == 1){
System.out.println("Difference between sum: "+ ((sum - j) - j));
break;
}
}
}
```

With or without re-arrangement? If without re-arrangment, then it is pretty easy (even bruce force method only has a O(n^2) time complexity.)

1 -2 3 4 is the array

first we separate into 2 subarrays like this:

[1] and [-2,3,4]

then we check for [1,-2] and [3,4]

and so on...

so i think we need only o(n^2) for this brute force technique.

Please correct if i am wrong

we can not solve it in o(n^2) by this brute force technique,even the solution will be wrong if u use this tricks.

@Anonymous: you got the right idea (or at least understood the question) but you can optimize to O(n). Think about it: do you really need to re-compute the sums of each sub-array from scratch at each step? If at a given step I have sub-array sums S and T and the integer to be "shifted" next from the right sub-array to the left is X, what is the most efficient way to update S and T?

S = S+X

T = T-X

And that's how you make it O(n) instead of O(n^2). Bonus question an interviewer might ask: is O(n) the best possible time for solving this?

As for the rest of you who talk about NPC and DP, you either completely missed the point of the question (would Google really give you an NPC question?) or just plain don't understand how DP works and are just throwing out algorithmic buzzwords.

I have a question. How will you generate all the possible sequences. Generating all the sequences is the trick part not the summation

geniusxsy is right.Its a DP problem but it is NP-complete actually if we look at the sample input

[1,2,3,4]

worst case we need to calculate all possible partitions (sub partitions ) .

That way its same as generating subsets so would be of the order 2^ n-1 .Or there is no polynomial solution available hence it is NPC.

1.Construct a BST using the array

2. Select the max value for array1

3. Select the second max value for array2.

4. Now it is array1's turn to select a number

5. compare the difference btw sum of array1 and sum of array2

6. if ( array1 > array2)

then select the closest value which would bridge the difference

else if ( array2 > array1)

then select the closest value which would bridge the difference

else (array2 == array1)

then select the next max value;

Repeat step 6 till every number from input array is selected

not sure about this... plz evaluate

Hi SK,

I looked at your solution. It is O(n log n).This is similar to you have a problem in real life. Like you have a number of fruits. And you have a traditional Indian weighing tool( analog tool). Now idea is to fill both the pans with fruits such that the pan is almost equal. The BST is only meant to make searching the appropriate fruit faster.

What about this? This method will find and save the pivotal element of the original array.

This pivotal element is the last element of the lhs partition. Complexity O(2n)?

```
int main(int argc, char* argv[])
{
int array[] = {1,2,3,4,5,6,7,8,9};
int size = sizeof(array)/sizeof(int);
int total = 0;
int imbalance = -1;
int pivotal_elem = -1;
split_array(array, size, size, &total, &imbalance, &pivotal_elem);
return 0;
}
int split_array(int* curr_elem,
int curr_size,
int orig_size,
int* total,
int* imbalance,
int* pivotal_elem)
{
int prev_rhs_elems = 0;
*total += *curr_elem;
if (curr_size > 1)
{
prev_rhs_elems = split_array(curr_elem+1, curr_size-1, orig_size, total, imbalance, pivotal_elem);
}
int rhs = *curr_elem + prev_rhs_elems;
int lhs = *total - rhs;
int temp = (rhs > lhs) ? (rhs-lhs) : (lhs-rhs);
if (*imbalance < 0 || *imbalance > temp)
{
*imbalance = temp;
*pivotal_elem = orig_size - curr_size - 1;
}
return *curr_elem;
}
```

As said earlier, this is NP complete.

Why waste time? Sorting might be fast, but still it is a waste of time.

first sort the array..take two arrays arr1 and arr2.....now scan the main array from the end and place last element in aar1 and second last element in arr2...then place third last also in arr2 and fourth last in arr1...proceed this way until we reach the the first element of main array...thats it now the arr1 and arr2 will have minimum difference between them

step 1. find the sum of elements in the array.--O(n)

step 2. find the val = sum/2 -- o(1)

step 3. sort the array.--O(n log n)

step 4. find the set of elements whose sum is equals to val. ---O(n)

overall TC is O(n log n)

please correct me if some thing is wrong.

Another correction

step 4. find the set of elements whose sum is closest (not equals) to val. ---O(n)

Remaining elements in the other set

A better algorithm by greedy approach.

1. Sort array

2. for each element: if sum(array1)<sum(array2) then put it in first array else into second.

3. Once all elements are split. iteratively minimize difference value by moving elements from one to other

while(true)

diffValue = sum(array1)-sum(array2)

by binary search find closer value to difValue/2 in array2 and move it to the other or vice versa

compute difference again if no change then break.

vector<int> array1,array2;

vector<int> elements; //contains the array to be split

long sumOfArray1=0,sumOfArray2=0;

sort(elements.begin(),elements.end()); //its better to sort

//For each element

for(int i=0;i<elements.size();i++){

//if first array has lesser sum then push 'i'the element it in the firstarray

(sumOfArray1<=sumOfArray2) ?array1.push_back(elements[i]):array2.push_back(elements[i]);

}

//once the values are split into two arrays

//do as in step 3 //hint:: use lower_bound from STL and find closer value to difference/2 and move it to the other set.

A better algorithm by greedy approach.

1. Sort array

2. for each element: if sum(array1)<sum(array2) then put it in first array else into second.

3. Once all elements are split. iteratively minimize difference value by moving elements from one to other

while(true)

diffValue = sum(array1)-sum(array2)

by binary search find closer value to difValue/2 in array2 and move it to the other or vice versa

compute difference again if no change then break.

vector<int> array1,array2;

vector<int> elements; //contains the array to be split

long sumOfArray1=0,sumOfArray2=0;

sort(elements.begin(),elements.end()); //its better to sort

//For each element

for(int i=0;i<elements.size();i++){

//if first array has lesser sum then push 'i'the element it in the firstarray

(sumOfArray1<=sumOfArray2) ?array1.push_back(elements[i]):array2.push_back(elements[i]);

}

//once the values are split into two arrays

//do as in step 3 //hint:: use lower_bound from STL and find closer value to difference/2 and move it to the other set.

If all numbers are positive

1) sort in decreasing order

2) for each element, if sum(array1) < sum(array2) then add to array1 else add to array2.

Done. This is the optimal solution, no need to "iteratively minimize" (as chenna suggested).

If numbers are both positive and negative

1) order in decreasing order of their absolute values. O(n log n)

2) if a_i >= 0, do the same as above. If a_i < 0, do the opposite. O(n)

Done.

No DP needed. BTW, I'd like to see somebody actually solving this using DP, I personally don't see how.

I have been trying to figure out how to prove that the algorithm above indeed produces the optimal solution, so far I am not exactly sure. Induction seems like the best choice but I got stuck halfway through.

Boy, do I wish I could take the previous post back :-)

Anyway, the above algo is a good approximation but there are cases where it does not work (e.g. {3,3,2,2,2}).

The problem is very similar/identical to the Knapsack problem which is NP hard (and the decision version is NP complete). In other words, there is no known polynomial-time algorithm that would guarantee to find optimal solution. There are pseudo-polynomial-time algorithms (using DP) that solve this. Note that pseudo-polynomial is in the size of the input and not size of n!!! In other words, if all the numbers are within a given range, then there's a polynomial time algorithm that solves this problem. The difficulty arises when the numbers are arbitrarily big. See wikipedia for more details.

O(n) in space and time.

1. take 2 arrays, T and S.

2. traverse the main array and keep adding elements on the following condition..

(Let the next number be x, let the current sum of the two arrays be S and T respectively)

if (x>0) add x to the array with lesser sum. (ie, if S<T, add x to S)

if (x<0) add x to the array with greater sum. (ie, if S>T, add x to S)

This algo "seems" to be correct. I cant prove it correctness, but havent been able to find a case of failure.

Please point out my mistake if I gt wrong somewhere.

Yes, it seems correct but it's not. In fact, your algorithm is almost the same as the one I described above--I guess you did not see mine when you were posting ...

Well, actually, there's a difference between yours and mine in that you don't sort the array. Which means array like {1,1,2} would be split by your algorithm into {1,2} and {1}, whereas my algorithm would split it correctly into {2} and {1,1}.

O(n) in space and time.

1. take 2 arrays, T and S.

2. traverse the main array and keep adding elements on the following condition..

(Let the next number be x, let the current sum of the two arrays be S and T respectively)

if (x>0) add x to the array with lesser sum. (ie, if S<T, add x to S)

if (x<0) add x to the array with greater sum. (ie, if S>T, add x to S)

This algo "seems" to be correct. I cant prove it correctness, but havent been able to find a case of failure.

Please point out my mistake if I gt wrong somewhere.

I think, we can this problem by using MAX HEAP.

1. array A[n] is given two you. We know size of array i.e n

2. Two Split arrays S1[n1] S2[n2] . here n1, n2 are sizes of split arrays.

3. Construct MAX HEAP by using A[n] elements.

4. for each i =MaxHeapElement() // for all n elements

if ( SUM(S1) > SUM(s2) )

{

add i to S2[]

n2++;

}

else

{

add i to S1[] ;

n1++;

}

5. n1 + n2 == n .

6. SUM(S1) ~= SUM(S2) ;

7. Time complexity O(nlogn)

Problem for O(nlogn) algorithms: {5,4,3,3,3}. Algorithms suggest {5,3} and {4,3,3} but {4,5} and {3,3,3} better. Correcting could end without finding optimal, since maybe we should be at a bigger difference before finding optimal.

Consider correcting {50,30,22} and {50,30,18} we would never find {50,50} and {30,30,22,18} - NP hard problem. It takes O(2^n) to solve.

First of all, since the problem mentions sub-arrays, I think this isn't the same Balanced Partition problem that many have assumed it is. So it's actually much simpler and can be solved in O(n).

First, we iterate once to find the total. Then we iterate again, this time comparing the difference between the left and the right sub-arrays, and see if this difference is the smallest we have seen so far. At the end, we return the index associated with the minimum difference. The index is the index of the last element that we should include in the left sub-array.

```
int findEquilibrium(int[] arr) {
int total = 0;
for(int n : arr) {
total += n;
}
int min = Integer.MAX_VALUE;
int equilibrium = 0;
int left = 0;
int right = total;
for(int i=0; i<arr.length; i++) {
left += arr[i];
right -= arr[i];
int diff = Math.abs(left-right);
if(diff < min) {
equilibrium = i;
min = diff;
}
}
return equilibrium;
}
```

1. Sort the array (increasing order)

2. Make two variables that tracks current sum of each array, sum1, sum2

2. Loop from end and put two elements in two arrays, and add those values to sum1 and sum2.

3. For the next two elements, put the bigger one to the side that has lower sum, and smaller one to the other. Add respective elements to sum.

Hey guys,

If I am not wrong, we can add all the negative numbers in one array and all the positive numbers in another array and then (negative array) - (positive array)

sort the array using quicksort.........now store the 1st half of array into array1 and second half into array 2

sort the array in ascending order. Put all elements at odd indexes into array1 and all elements at even indexes into array2. Then, sum(array1) - sum(array2) will be minimum

1. Find average: Add all the elements in the array and divide it by 2.

2. Now get the ceiling and floor of the average. So if the avg is 6.5, one answer is 7.0 and another is 6.0

3. Make one sub-array whose summation of elements is 7.0 and another one whose is 6.0. And that's the answer.

The difference would be always 1(if the sum%2 !=0) or 0(otherwise). I did it myself with O(n^2).

Solution is O(nlgn)

Sort

take largest number ; put into one sequence

for any other number (+ve) add it to lesser sum sequence

for any other number (-ve) add it to greater sum sequence

Good thinking bala

You don't even need O(nlgn).

1. Find the largest number and remove it from the list: O(n) Add this in subarray 1

2. Find the largest number form remaining numbers and remove : O(n) : add this in subarray 2

and then follow your technique : O(n-2)

so O(n)

there is a good DP solution provided here

- SK December 28, 2009://people.csail.mit.edu/bdean/6.046/dp/