Yahoo Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
The above solution is correct, to understand this solution you can watch this tutorial
youtube.com/watch?v=GdnpQY2j064
How about the following logic:
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
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}
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!
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;
}
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....
#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;
}
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.
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){
results.add(test[begin]);
return true;
}
if(whether_sum(test,begin+1,end,aim-test[begin],results)){
results.add(test[begin]);
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);
}
}
- 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]
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.
Please let me know your thoughts
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)
/// Using DP
/// m[i+1][j] = 1 /// IF m[i][j-A[i+1]] = 1
/// m[i+1][j] = 0; /// IF m[i][j-A[i+1]] = 1
/// Time Complexity O(N * S) Space Complexity O(S)
int run()
{
///int A[] = {12, 4, 7, 1, 6, 3, 3};
///int A[] = {12, 100};
int A[] = {3, 3, 2, 2, 2};
int s = 0;
for(int i = 0; i < sizeof(A) / sizeof(A[0]); i ++) {
s += A[i];
}
print_v(A, sizeof(A) / sizeof(A[0]));
int m[s/2 + 1];
memset(m, 0, sizeof(m));
for(int i = 0; i < sizeof(A) / sizeof(A[0]); i ++) {
for(int k = s/2; k >= 0; k --) {
if(m[k] && (k + A[i] < s/2 + 1)) m[k + A[i]] = 1;
}
m[A[i]] = 1;
///print_v(m, s/2 + 1);
}
int i = 0;
for(i = s/2; i >= 0; i --) {
if(m[i]) break;
}
printf("s : %d i : %d\n", s, i);
return 0;
}
int find_balance_point(int *input, int n)
{
int left_sum, right_sum;
int sum = 0;
if (input == NULL)
return -1;
for (int i = 0; i < n; i++)
sum += input[i];
left_sum = input[0];
right_sum = sum - input[0];
for (int i = 1; i < n; i++) {
left_sum += input[i];
if (left_sum == right_sum)
return i;
right_sum -= input[i];
if (left_sum == right_sum)
return i;
}
return -1;
}
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.
- Anonymous August 04, 2012P(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