## Google Interview Question for Development Support Engineers

• 0

Comment hidden because of low score. Click to expand.
1
of 3 vote

there is a good DP solution provided here
://people.csail.mit.edu/bdean/6.046/dp/

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

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

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

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

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

Classic DP, balanced partition.

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

NPC
You can easily reduce Set Partition to this one.

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

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

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

really?? I don't think so. since DP is O(n^2), How can brutal force come with O(n^2).

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

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

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

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.

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

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

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

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

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

@Bullocks

How do you track the minimum difference, if the difference does not in any increasing/decreasing order? Save all of them and sort them? I don't see it's a O(n) this way.

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

geniusxsy is right. Although it can be solved by DP, it is still in NPC. Not all problems solvable by DP is O(N^2).

This problem is pseudo-polynomial, which means it's polynomial to the NUMERIC VALUE of N, but not the input size (unless numbers are encoded in unary.)

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

guys what is DP...i hv no idea...plz pas on links regarding DP

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

Hey Anonymous, DP = dynamic programming

en.wikipedia.org/wiki/Dynamic_programming

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

Generate all combinations.
Find the sum of the halves.
keep track of the one that has the least difference in sums.

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

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.

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

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

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

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.

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

you should sort it and then go over it from largest to smallest
if a[i] increase the gap then throw to 2nd array
else throw to first array.
O(nlogn+n)=O(nlogn)

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

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

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

As said earlier, this is NP complete.

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

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

@Anonymous: Do you mean the maximum set splitting problem: csc.kth.se/~viggo/wwwcompendium/node145.html

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

``````int ar[] = ...
ar = sort(ar);

if(ar.length < 3) return ar;

for(i=0, j=n; i<j; i+=2; j-=2)
{

int temp = ar[i+1]; ar[i+1] = ar[n-1]; ar[n-1] = t;

}``````

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

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

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

Not working for {1, 2, 3} - your solution are arrays {1, 3} and {2}, correct one is {1, 2} and {3}

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

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.

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

small correction in step.4
its time complexity is O(n log n)

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

You have no solution if there is not such subset - {1, 2, 5}, val = 4 :-/

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

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

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

How do you find the elements which sum up to val?

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

btw DP is O(n^3)

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

@Bala is there a mathematical proof for your algorithm?

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

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.

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

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.

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

Simple problem...
Just have an array c[] for cumulative sum.

Eg.

1,2,3,-4,5

cumulative arrray: 1,3,6,2,7

now just see all the partitions: diff= a[n]-2*c[i], if i is the place of partition.
Take the maximum.
Algorithm is clearly O(n)

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

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.

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

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.

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

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.

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

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

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

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.

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

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) )
{
n2++;
}
else
{
n1++;
}
5. n1 + n2 == n .

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

7. Time complexity O(nlogn)

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

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.

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

convert the array into a BST.

Now do an inorder traversal. While doing the traversal, put the min value into arr1 and the next min value to arr2. In the next step, put max value to arr2 and the next value to arr1.

For ex: inorder 1 2 3 4 12 13 15 17

arr1 1 4 12 17
arr2 3 13 15

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

"Java codes that will accept 20 different numbers both negative and positive and their sum"

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

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

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

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

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

this shud work.. shouldn't it??

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

what if no negative numbers at all??...and i think question demands min. mod value of difference..

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

This would produce the max difference.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

it's not true, for array {1, 2, 3} you create array1 as {1, 3} and array2 as {2}, difference 2, correct solution is {1, 2} and {3} - difference is 0

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

Not working :-/ If array is {1, 2, 5}, average is 4, there is no such subset.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

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

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

so O(n)

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

@chanakya, o(n) + o(n-1) + o(n-2) .... != o(n)
it is o(n^2)
obviously, sorting is o(nlgn) and will be better.

Assuming your solution is correct, which it is not.

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.