## Yahoo Interview Question Software Engineer / Developers

• 0

Given a set of positive integers S = { a1,a2,a3,...,an} find two subsets s1 and s2 of A such that S2 = S - S1 and difference of | sum(S1) - sum(S2) | is minimum.
For example if we have a set S={12,4,7,1,6,3,3 }then S1= {12,6} and S2={ 4,7,1,3,3} such that sum(S1) - sum(S2) = 0 . It is not necessary that two subsets will always have the same sum.

Country: India
Interview Type: Written Test

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

This is example of famous balanced partitioning problem. You need to basically find if any subset of set S sums up to N=(a1+a2+a3+...an)/2. If yes then other set will automatically have sum (a1+..+an)/2. However if that is not true then we will try if a subset has sum N-1, N-2,N-3 etc. Now the question is how to find if a subset of S sums up to some number. For this we use dynamic programming.
P(i,j) is true if there is a subset from among first i elements that sum up to j. The recurrence relation will be
P(i,j) = 1 if P(i-1,j) = 1 // there is a subset of (i-1) elements that sum up to j
OR if P(i-1, j-a(i) ) = 1 // include the ith element in the subset

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

The above solution is correct, to understand this solution you can watch this tutorial

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

wow .. nice viedo...worth watching...

I wondered is there a better way than DP regarding to the time and space complexity?

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

1. Sort the set in decreasing order.
2. Repeat the following until set is empty:
a) Put 1st/next element in first set
b) Traverse and keep putting the next elements in the second list until sum of second exceeds sum of first.
c) Go to a) if list is not empty

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

This is the greedy approach for the problem but it will not return the optimal result. Try to use the following array: {3, 3, 2, 2, 2}

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

I think we should maintain 2 indices after sorting it some order.

one pointing to the start of the array for first set and one points to the last of the array for second set. Try to add the elements into the set to minimize the difference of their sums!

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

This is greedy approach. It won't lead you to the correct answer.
The idea of posting it is to show the sorting won't lead you to the actual solution.

You can try yoursef with different inputs. The array given here is the apt example. Why the sorting will not work!

``````#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std ;

int getDifference (int *arr, int size) {
int i, start = 0, end = size-1 ;
int sum1 = 0, sum2 = 0;
vector<int> set1, set2 ;
printf ("\n%d\n", size );
while (start <= end) {
if ( sum1 > sum2 ) {
sum2 += arr[end] ;
set2.push_back (arr[end]) ;
end --;
} else {
sum1 += arr[start] ;
set1.push_back (arr[start]) ;
start ++ ;
}
}

vector<int>::iterator it1, it2 ;
printf ( "\nFirst set contains : " ) ;
for ( it1 = set1.begin(); it1 < set1.end() ; it1++ )
printf ( " %d", *it1 ) ;
printf ( "\nSecond set contains : " ) ;
for ( it2 = set2.begin(); it2 < set2.end() ; it2++ )
printf ( " %d", *it2 ) ;

return abs(sum1-sum2) ;
}

int main () {
int ptr[] = {12,4,7,1,6,3,3} ;
int len = sizeof(ptr) / sizeof(ptr[0]) ;
sort (ptr, ptr+len) ;
printf ( "\nMinimum difference is: %d", getDifference (ptr, len) ) ;
getchar ();
return 0;
}``````

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

hii i m not sure for this solution but please have a look:
1)lets put all the elements in a array nad sort them
2)then map 1st element and last element to first set and 2ns and second last to secondset and 3rd and 3rd last to first like this.......

may be we will end up in minimum difference....

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

#include<conio.h>
#include<stdio.h>
int diff(int a,int b) // finding |a-b|
{
if(a>b)
return a-b;
else
return b-a;
}

int main()
{
int arr[100]; // input array
int n; // no. of elements
printf("enter no. of element in array");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("enter element..");
scanf("%d",&arr[i]);
printf("\n");
}
int s1[100]; //subset s1
int s2[100]; //subsets2
for(int i=0;i<n;i++)
{
s1[i]=0; // all elements of s1 to be 0
s2[i]=0; // ''
}
int sum1,sum2,difference1,difference2;
s1[0]=arr[0];
sum1=s1[0]; // current sum of s1 array elements
s2[0]=arr[1]; // current sum of s2 array elements
sum2=s2[0];
int a,b;
a=1; // free index of s1
b=1; // free index of s2
for(int i=2;i<n;i++)
{
difference1=diff((sum1+arr[i]),sum2); // adding new element to s1 and finding difference b/t s1 & s2
difference2=diff(sum1,(sum2+arr[i])); //adding new element to s2 and finding difference b/t s1 & s2
if(difference1 < difference2)
{
s1[a]=arr[i];
sum1+=arr[i];
a++;
}
else
{
s2[b]=arr[i];
sum2+=arr[i];
b++;
}
}

printf("....s1 set....\n");
for(int i=0; i<n;i++)
{
printf("%d,",s1[i]);
}
printf("\n......s2 set...\n");
for(int i=0; i<n;i++)
{
printf("%d,",s2[i]);
}

printf("\n diffrence is=%d",diff(sum1,sum2));

getch();
return 0;
}

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

This is a dynamic programming question. Here's the approach I would take:

S={12,4,7,1,6,3,3}

1) Single element is itself

2) Two elements is two sets of each

3) Three elements

(12,4,7) => (12,{4,7}) or ({12,4},7) or ({12,4,7})
=> (12,11) or (16,7) or (23)
=> (12,{4,7})

And so on until the table is built up.

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

package yahoo;

import java.util.ArrayList;

public class Divide_Two_Set_Min_Difference {
public static ArrayList<Integer> get_results(int[] test){
ArrayList<Integer> results=new ArrayList<Integer>();
int sum=computer_sum(test);
System.out.println("sum: "+sum);
for(int i=sum/2;i!=sum+1;i++){
if(whether_sum(test,0,test.length-1,i,results)){
System.out.println("haha: "+i);
return results;
}
}
return null;
}
public static boolean whether_sum(int[] test,int begin,int end,
int aim,ArrayList<Integer> results){

if(aim<0){
return false;
}
if(begin>end){
return false;
}
if(test[begin]==aim){
return true;
}
if(whether_sum(test,begin+1,end,aim-test[begin],results)){
return true;
}
if(whether_sum(test,begin+1,end,aim,results)){
return true;
}
return false;
}
public static int computer_sum(int[] test){
int sum=0;
for(int i=0;i!=test.length;i++){
sum+=test[i];
}
return sum;
}
public static void show(ArrayList<Integer> results){
for(int i=0;i!=results.size();i++){
System.out.println(results.get(i));
}
}
public static void main(String[] args) {
int[] test=new int[]{12,4,7,1,6,3,3};
ArrayList<Integer> results=get_results(test);
show(results);

}
}

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

Here's the pseudo-algorithm described in terms of dynamic programming:

``````Subset(empty) = 0
SubSet(i,i) = Subset(i)
Subset(i,i+1)=Subset(i,i) + SubSet(i+1,i+1)
Subset(i,i+n)= For a=i to i+n do
Max(Subset(i,a-1),Subset(a,i+n))``````

Overall, it's a form of tail-recursion.

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

- Create S1=S and S2 empty. Sum1 is the sum of S and sum2 is the sum of S2 (0 to start)
- Keep iterating over S1
- Find an element in S1 which if moved to S2 would minimize (sum1-sum2). If you do find it, then move the element from S1 to S2 and update sum1 and sum2. If you can't find such an element, then break the loop.

I was able to get the following output

``````Input=[12, 4, 7, 1, 6, 3, 3]
S1=[4, 7, 1, 3, 3]
Input=[3, 3, 12, 4, 7, 1, 6]
[3, 3, 4, 7, 1]
Input=[3, 3, 2, 2, 2]
[2, 2, 2]
Input=[5, 3, 2, 13, 2]
[5, 3, 2, 2]
Input=[5, 5, 4, 3, 3]
[4, 3, 3]``````

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

Why can't we follow this approach, and I know sorting has been discussed before but please bear with me:

1. Sort the array
2. Keep two variable, left_sum, right_sum
3. Keep two variable more variable, low, high

``````low = 0;
high = arr.length - 1;
while (low < high) {
if (low_sum > right_sum) {
high--;
right_sum = arr[high];
}
else if (low_sum < right_sum) {
low--;
left_sum = arr[low];
}
else {
if(low>=high) break;
high--;
right_sum = arr[high];
low--;
left_sum = arr[low];
}
}``````

Should this not give a minimised partition? I also checked with the dynamic programming question, it looks better than O(n^2 k) solution, also, we do not need to have the numbers in the range of [0,k] - which means we can do it for negative numbers too.

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

``````def balancePoint(li):
left = li[0]
right = 0
minPoint = 0
location = 0
for i in li:
right = right + i
minPoint = left - right
if minPoint <0:
minPoint = -minPoint

for i in range(0,len(li)-1):
if left == right:
print "Least value "+str(i)
return
else:
temp = left-right
if temp < 0:
temp = -temp
if temp < minPoint:
minPoint = left-right
if minPoint < 0 :
minPoint = -minPoint
location = i
left = left + li[i+1]
right = right - li[i]
print str(minPoint)+" at "+str(location)

if __name__ == '__main__':
li = [1,2,3,4,6,11]
balancePoint(li)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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