Yahoo Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
S = 0;
for (int i=0; i < N; i++)
S += a[i];
S = S/2;
int dp[N][S+1];
memset(dp, 0, sizeof(dp)) ;
dp[0][0] = 1;
for (int j=0; j <= S j++)
if (j >= a[0]) dp[j] = 1;
for (int i=1; i < N; i++)
for (int j=0; j <= S; j++) {
dp[i][j] = dp[i-1][j];
if (j >= a[i]) dp[i][j] += dp[i-1][j-a[i]];
}
return dp[N-1][S]; // returns number of subsets
Partition problem : pseudo polynomial time solution:
import sys
import argparse
def partition(arr, n):
if arr is None:
return "Error: No array provided";
'solved via dynamic programming approach'
p = [[0 for x in xrange(arr.__len__() + 1)] for x in xrange(n / 2 + 1)];
initGraph(p, n / 2, arr.__len__());
'''Apply dynamic programming approximation
P(i,j) = P(i, j-1) or P(i-xj, j-1)
'''
res = setUpGraph(arr, p, n / 2, arr.__len__());
if res is None:
return "Error: No graph returned!";
else:
return res[n / 2][arr.__len__()];
def setUpGraph(arr, p, rows, cols):
i = 1;
j = 1;
while i <= rows:
j = 1;
while j <= cols:
p[i][j] = p[i][j - 1] | p[i - int(arr[j - 1])][j - 1];
j = j + 1;
i = i + 1;
return p;
def initGraph(p, rows, cols):
i = 0;
while i <= cols:
'set first row to True'
p[0][i] = True;
i = i + 1;
i = 1;
while i <= rows:
'set first col to False except p[0][0]'
p[i][0] = False;
i = i + 1;
1. What language are you using? Looks like python and executes like python, but the convention is very different.
2. You are only returning a boolean value. What are you trying to return, or what problem are you trying to solve?
3. I believe your code can be rewritten as follows to execute identically. Correct me if I am wrong:
def half_sum(nums, max_sum):
p = [[True] * (len(nums)+1)] + [[False] + [0] * (len(nums)) for x in range(max_sum/2)]
# Apply dynamic programming approximation : P(i,j) = P(i, j-1) or P(i-xj, j-1)
for i in range(1, (max_sum/2)+1):
for j in range(1, len(nums)+1):
p[i][j] = p[i][j - 1] | p[i - int(nums[j - 1])][j - 1]
print p[max_sum/2][len(nums)]
it is basically a problem of finding the subset sum with sum r/2 where r is the sum of the array. This code prints all the necessary subsets possible for summing upto r/2
#include <stdio.h>
#include <stdlib.h>
int arr1[]={6,5,4,3,2,1};
int sumOfSubset(int s,int k,int w[],int r,int n,int m,int x[])
{
int i,j,sum=0;
x[k]=1;
if(s+w[k]==m)
{
for(i=0;i<n;i++)
{
if(x[i]==1)
{
for(j=0;j<n;j++)
{
if(w[i]==arr1[j])
{
printf("%d",j);
}
}
}
}
printf("\n");
}
else if(s+w[k]+w[k+1]<=m)
sumOfSubset(s+w[k],k+1,w,r-w[k],n,m,x);
if((s+r-w[k]>=m)&&(s+w[k+1])<=m)
{
x[k]=0;
sumOfSubset(s,k+1,w,r-w[k],n,m,x);
}
}
int main()
{
int arr[]={6,5,4,3,2,1};
int n=sizeof(arr)/sizeof(arr[0]);
int i,r=0;
int x[n];
for(i=0;i<n;i++)
{
x[i]=0;
}
for(i=0;i<n;i++)
{
r=r+arr[i];
}
sumOfSubset(0,0,arr,r,n,r/2,x);
}
@vgeek:Don't you think applying kadane's algo will be simpler to apply on this??What's your thought?
Yes you can apply the kadane's algo for finding a subset. But that could only be used to find one subset. This code finds all the possible subsets that could lead to the given sum. It uses greedy approach
@vgeek:We can find a subset and then apply kadane algo from the index after the index where the previous subset ends..Suppose in an array a subset matching a sum lies in 1...5..We can again apply kadane algorithm from 6th index and find for any other possible subset that matches the sum.
I see very complicated solutions not sure why they are not making any sense to me.
I'll do mine using C#.
I'm pretty much creating a hash of all unique numbers and their total occurrences then I use each number to see if the adding them conforms with the wanted total.
I also do some checks in order to determine if the array is valid to do this operation because the question ask to give exactly half the total sum.
List<int> HalfTotalSubSet(int[] input)
{
// This is to store each number and how many occurrences are found
Dictionary<int, int> numberHash = new Dictionary<int, int>();
int total = 0;
foreach (int n in numbers)
{
if(!numberHash.ContainsKey(n))
{
numberHash.Add(n, 1);
}
else
{
numberHash[n]++;
}
total += n;
}
if (total%2 != 0)
{
throw new ArgumentException(
"The total sum of the array is an even number.\nTotal: " + total);
}
List<int> subset = new List<int>();
if(TotalSumSubSetCore(numberHash, subset, total/2))
{
return subset;
}
// Either this or just return an empty subset or null. I'm leaving it implicit for now.
throw new ArgumentException(
"There is no subset that sum half the total.\nTotal:" + total);
}
bool TotalSumSubSetCore(Dictionary<int, int> numberHash, List<int> subset, int sum)
{
foreach(KeyValuePair nh in numberHash)
{
if(nh.Value > 0)
{
int newSum = sum - nh.Key;
// This means that there are no remaining numbers to process
if(newSum == 0)
{
subset.Add(nh.Key);
return true;
}
// This assuming that they are non-negative numbers otherwise there is not
// no need to have to do this check but it will go through all numbers assuming
// that there is one that could be negative and make it sum equal to zero.
if(newSum < 0)
{
continue;
}
nh.Value--;
if(TotalSumSubSetCore(numberHash, subset, newSum))
{
subset.Add(nh.Key);
return true;
}
nh.Value++;
}
}
// This means that no number could give the exact sum.
return false;
}
Essentially you would have to sort the list, then cycle from the front to back decreasing your back pointer towards the front each time you have cycled thru and not found the correct sum. Function in Ruby
def halfSum (nums, sum)
front = 0
back = nums.length - 1
currBack = 0
currFront = 0
i = 0
nums.sort!
while back > 1
currBack = nums[back]
back -= 1
i = 0
while i < back
currFront += nums[i]
if(currFront + currBack == sum/2)
return nums[0, i].concat( nums[back, nums.length-1] )
elseif(currFront + currBack > sum/2)
break
else
i+=1
end
end
end
return -1
end
Forgot to check if just the largest value element was half the sum before entering the first while loop
1. I don't think you are given the sum. You are given a number K that is >= sum. You can calculate the sum in O(n), but then you will be ignoring K, which seems wrong.
2. What of the case
[1, 2, 4, 5, 8]
? The valid answers would be [2, 8] or [1, 4, 5], but this algorithm wouldn't find either. It relies on the valid answers to contain some number + the smallest x numbers.
Basically the same problem as the "Combination Sum" problem in leetcode.
- coderfe December 23, 2013