Google Interview Question Software Engineer in Tests
Country: India
Interview Type: Phone Interview
Lets see if we can re-phrase the question:
Divide the array into two EQUAL halves which has same AVERAGE
which means, the array is of even size, and the question can be rephrased as:
Divide the array into two EQUAL halves so that they have the same SUM
Algorithm:
1. compute the total sum of the array elements: lets say it is X
2. We need to find two subarrays of equal length which adds to X/2
3. Use subset sum algorithm to see if such subarrays exist
Divide the array into two equal halves array1, array2. Say each one has sum S1, S2.
if(S1 > S2)
Then recurse on left array.
(i.e
divide array1 in two equal halves S11, S12.
if(S11 < S22 + S2)
Then recurse on array[n/4... n/2]....
else if (S11 > S22 + S2)
Then recurse on array[0... n/4]
and so on....
)
else if( S1 < S2)
Recurse on right half....
Partition(int a[], int l, int n1, int n2, int k1, int k2)
{
int S1 = sum(a[0 ... l/2 - 1]) + k1;
int S2 = sum(a[l/2 .... l - 1]) + k2;
n1 = l/2 ;
n2 = l/2 ;
if(k1 != 0 && k2 == 0)
n1 += k1;
else if(k2 != 0 && k1 == 0)
n2 += k2;
if(S1 * n1 > S2 * n2)
{
Partition(a, l / 2, 0, n2, 0, S2);
}
else if( S1 * n1 > S2 * n2)
{
Partition(a, l / 2, n1, 0, S1, 0);
}
else
return l/2;
}
// call in main
Partition(a, l, 0, 0, 0, 0);
this is even harder than the original partition problem because the partition needs to be of equal size
Actually, I think the constraint of equal size makes the problem easier. You can partition the problem into two arbitrary halves, and then start exchanging elements. After each exchange, you see if the problem is solved, if not, you recurse on the remaining n/2-1 elements for each side. You could use memoization to prevent repeated computations. I think this avoids an NP complete problem, no?
The problem is different from careercup.com/question?id=8872057 .
- Anonymous October 09, 2011Here the array needs to be divided in two Equal parts not just two parts. Though I think it won't always be possible to find such solution for each input (equal parts with equal average.) But another problem could be try to minimize the difference between average of two equal parts.