Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Let us create a difference array, an array where each element is the difference (Y-X). Note that the difference should not be an absolute value.
Once the difference array is formed, we can apply the logic of subset of integers in an array summing to 0.
example:
X | 1 | 2 | 4 | 3 | 1 | 1 |
Y | 2 | 3 | 3 | 7 | 1 | 2 |
D | 1 | 1 | -1 | 4 | 0 | 1 | ---- Di=(Yi - Xi)
Now, on D, all we need to do is find a subset of integers which sums upto 0 (Dynamic programming can be used). The corresponding pairs of X and Y will be our answer.
Example, here we have 6 <x,y> pairs. Lets call them p1...p6.
Based on the values of D, possible solutions are as follows:
a) p5
b) p1, p3
c) p2, p3
d) p6, p3
struct _ratio {
double sug;
double wtr;
};
void conv_ratio_to_vol(struct _ratio* r, int n) //convert to volume in unit of cups
{
int i;
double denom;
denom = r->sug + r->wtr;
for (i = 0; i < n; i++) {
r[i].sug /= denom;
r[i].wtr /= denom;
}
}
bool find_comb(struct _ratio* v, int n, double sum_sug, double sum_wtr)
{
int i;
int ret = false;
if (n = 0) {
return false;
}
// Two Choices for current cup 1. Not Sum it, 2 Sum it
// 1 Dont Sum it
for (i = n; i > 0; i--) {
ret = find_comb(v + 1, n - 1, sum_sug, sum_wtr);
if (ret) return ret;
}
// 2 Sum it
sum_wtr += v->wtr;
sum_sug += v->sug;
if (sum_wtr == sum_sug) {
return true;
}
for (i = n; i > 0; i--) {
ret = find_comb(v + 1, n - 1, sum_sug, sum_wtr);
if (ret) return ret;
}
return ret;
}
bool can_find_one_to_one(struct _ratio* r, int n)
{
conv_ratio_to_vol(r, n);
return find_comb(r, n, 0, 0); // O(2^n), can optimize this with DP?
}
struct _ratio {
double sug;
double wtr;
};
void conv_ratio_to_vol(struct _ratio* r, int n) // volume in unit of cups
{
int i;
double denom;
denom = r->sug + r->wtr;
for (i = 0; i < n; i++) {
r[i].sug /= denom;
r[i].wtr /= denom;
}
}
bool find_comb(struct _ratio* v, int n, double sum_sug, double sum_wtr)
{
int ret = false;
if (n = 0) {
return false;
}
// Two Choices for current cup 1. Not Sum it, 2 Sum it
// 1 Dont Sum it
ret = find_comb(v + 1, n - 1, sum_sug, sum_wtr);
if (ret) return ret;
// 2 Sum it
sum_wtr += v->wtr;
sum_sug += v->sug;
if (sum_wtr == sum_sug) {
return true;
}
ret = find_comb(v + 1, n - 1, sum_sug, sum_wtr);
return ret;
}
bool can_find_one_to_one(struct _ratio* r, int n)
{
conv_ratio_to_vol(r, n);
return find_comb(r, n, 0, 0);
}
We need to find cups so that the sum of rato should be equal to number of cups. But this will take so much complexity..
For example if we take two random cups with ratio 1/2 and 3/2 then sum is two and we took 2 cups so we found the result..Finding such cups will take finding all combinations of 1 cups to 50 cups which will result in exponential complexity..Please correct if i m wrong..
It is simple math problem.
Just check whether there exists some ratio <1 and some ratio > 1.
If yes, then possible , else not.
Say, there exists 2 cups one with ratio 1:6, and one with ration 2:1,
then as 1/6<1<2, so it is possible to create the final part by mixing different percentage from these 2 mixtures.
In this case, if we fill 7/22 part of the glass with sugar mixture of 1:6 and 15/22 part by 2:1 mixture, we will get the resultant mixture of water:sugar ratio of 1:1 .
That was my initial thought and that would be a super easy answer, but I don't think that's correct; the way the question is worded is vague, but I imagine you'd have to mix full cups. Ie, if your set of cups happened to have a 2:1 cup and a 1:2 cup, you could mix just those two cups and you'd have a 1:1 ratio combination of cups.
Essentially, what I would do is convert the "ratio" given for every cup to a difference, ie, how much more sugar in the cup than water. Since each cup has the same volume, we can assume a volume of '1', such that, for example, 2 sugar : 1 water = 0.6666 sugar and 0.3333 water = +0.3333. 1 sugar : 4 water = 0.2 sugar and 0.8 water = -0.6
Then, with this data set, you would just need to find a subset such that the sum of all values in the subset is 0.
I think this is a variant of the knapsack algorithm without repetition. Assume you have an array of doubles that have the ratios, and then you iterate through the array, and for each index you try every possible combination of ratios that can be formed with that index's ratio and all the indices ahead of it in the array. So for each index you iterate from index to end of array and add up weights seen of each current index to list of already seen weights of which you keep track of. If you find something equal to 1 you return true. If you find something greater than 1 you remove from list as that combo can't form anything less than 1. If you find something less than 1 you append to list as it might contribute to 1 with the adding of a weight in the future. So for each index i, you iterate from j=i to 50, and for each j you update the list of weights k which are just the ratios of sugar in the combo already seen. Runtime is still 0(2^n) because you still have to go through all possible combinations of the indices in the cups array.
Here's the code in java. If you see any bugs please comment below.
public boolean findMix(double [] cups)
{
for(int i=0; i< cups.length; i++)
{
ArrayList<Double> totals = new ArrayList<Double>();
if(cups[i] == 1)
return true;
if(cups[i] < 1)
{
totals.add(cups[i]);
if(findMixHelper(cups,totals,i))
return true;
else
continue;
}
}
return false;
}
boolean findMixHelper(double[] cups, ArrayList<Double> totals, int index)
{
if(index >= cups.length)
return false;
Object[] totalsArray = totals.toArray();
for(Object o: totalsArray)
{
double t = (double) o;
double curr = t + cups[index];
if(curr == 1)
return true;
else if(curr < 1)
totals.add(curr);
//if curr > 1 it doesn't get added to totals, No Point!
}
return findMixHelper(cups,totals,++index);
}
I think we can solve this problem using knapsack.
1. We do a linear run and find the total amount of water in the cups. Let this be C - capcity in knapsack
2. Then we sort the cups in terms of decreasing Sugar:Water ratio.
3. Then we feed the above values to 0-1 Knapsack problem.
4. In that we decrease the amount of water by C-c_cup_i and increase sugar by S+s_cup_i
5. If we get the 2 values equal we return the result.
If (x:y) represent ratio (water:sugar) in a cup, then we need to find a subset out of 'n' cups where [Sum of x's] = [Sum of y's].
- Learner September 12, 2013O(2^n) solution is trivial since there are 2^n subsets. How to optimize this?