Kpro Solutions Interview Question
AnalystsTeam: Dev
Country: India
Interview Type: Phone Interview
The algorithm is good, but should take care the negative value case more carefully. I would suggest you to abs each value. You can see the case, first add 100, then add 250, the logic would throw away the 150, but only the 350.
Something is wrong with this solution. After processing each weight, we will at most double the output size.
But for 1,3,9,27, we have 40 weights possible, while your will probably output only 16 (or 32).
This seems essentially correct, apart from the fact that you are not handling the negative case correctly.
@Anonymous, it is not doubling, but tripling!
In case there are many ways to measure the same weight this is more efficient than brute force enumeration. O(n L) where L is the total number of weights.
In case the measurements are unique, this is possibly slightly worse than the brute force. Theta(3^n) vs Omega(n 3^n) (if my calculations are correct).
+1.
You missed 350.
Assuming it is a two pan balance, and we are allowed to place weight in any pan.
Each weight has 3 states: Left pan, not in any pan, Right pan.
Assign being in left pan as -1, and right pan as 1.
In each possible weighing, each weight w_i gets a coefficient a_i where a_i is -1, 0 or 1.
The weight that can be measured is the absolute value of a_1 w_1 + a_2 w_2 + ... + a_n w_n.
This gives us an algorithm.
Try to enumerate possible coefficients (a_1, a_2, .., a_n) and compute.
This can be done using the odometer trick, or if n is small enough, interpreting as a base 3 number.
This will visit each weight at least twice, but is asymptotically optimal in the worst case(the case when all weights are powers of 3, you will have Theta(3^n) possible measurements).
Here is quick python code
def generate_odometer(limits_list):
odometer_list = map(lambda x: 0, limits_list)
has_more = True
n = len(odometer_list)
while has_more:
yield odometer_list
has_more = False
for j in range(0,n):
limit = limits_list[j]
if odometer_list[j] < limit-1:
odometer_list[j] = odometer_list[j]+1
has_more = True
break
else:
odometer_list[j] = 0;
continue
def weights(lst):
feasible = {}
limits_list = map(lambda x:3, lst)
# 2 is treated as -1
for coeffs in generate_odometer(limits_list):
sum,idx = 0,0
for coeff in coeffs:
if coeff == 2:
sum -= lst[idx]
if coeff == 1:
sum += lst[idx]
idx += 1
if sum < 0:
sum = -sum
feasible[sum] = True
print feasible.keys()
def main():
weights([100,250])
weights([1,3,9,27])
if __name__ == "__main__":
main()
and here is the output
[0, 250, 100, 150, 350]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40]
so, any given weight can be of three forms
(-1, 0, 1) where
-1 : when is on the left side(i.e. its weight is getting subtracted)
0: not on any side (does not contribute to the weight)
1: when it is on the right side (i.e. its weight is getting added).
So, for n weights, the answer will be permutation of (-1, 0, 1) + (-1, 0, 1) + ..... + n times..where for any weight choices are: (-1, 0, 1).
Valid answers are sum greater than zero.
Taking example from the question, weights are 100, 250. Thus, the combination will be
(-1, 0, 1) + (-1, 0, 1)
-1 + -1 = -100 + -250 = invalid
-1 + 0 = -100 + 0 = invalid
-1 + 1 = -100 + 250 = 150
0 + -1 = 0 + -250 = invalid
0 + 0 = 0 + 0 = invalid
0 + 1 = 0 + 250 = 250
1 + -1 = 100 + -250 = invalid
1 + 0 = 100 + 0 = 100
1 + 1 = 100 + 250 = 350
thus making 100, 250, 150, 350 as answer.
comment if you find any bug with the logic
Did not check his algo. I coded this on my computer and posted my solution with illustrative example
Here is the CPP code for the above question.
Since all the answers will be between Zero and Sum of all the weights. I initialized an array of that length of structure node. (see code). For every weight, I check the previous entries and find the every new possible answer.
The code runs in time complexity O(n^2).
#include<iostream>
using namespace std;
typedef struct node
{
bool present;
int small;
int large;
}node;
int main()
{
cout << "Enter the number of values you want to enter\n";
int num,sum=0;
cin >> num;
int* array = new int[num];
cout << "Enter the numbers\n";
for(int i = 0; i < num; i++)
{
cin >> array[i];
sum +=array[i];
}
node* result = new node[sum+1];
for(int i = 0; i <= sum; i++)
result[i].present = false;
result[0].present = true;
result[0].small = 0;
result[0].large = 0;
sum = 0;
for(int i=0; i<num; i++)
{
sum += array[i];
for(int j = 0; j <= sum; j++)
{
if(result[j].present == true)
{
if(result[result[j].large + array[i]].present == false)
{
result[result[j].large + array[i]].present = true;
result[result[j].large + array[i]].small = 0;
result[result[j].large + array[i]].large = result[j].large + array[i];
}
if(result[result[j].small + array[i]].present == false)
{
result[result[j].small + array[i]].present = true;
result[result[j].small + array[i]].small = 0;
result[result[j].small + array[i]].large = result[j].small + array[i];
}
if(result[result[j].large + array[i] - result[j].small].present == false)
{
result[result[j].large + array[i] - result[j].small].present = true;
result[result[j].large + array[i] - result[j].small].small = result[j].small;
result[result[j].large + array[i] - result[j].small].large = result[j].large + array[i];
}
if((result[j].small + array[i] - result[j].large) > 0)
if(result[result[j].small + array[i] - result[j].large].present == false)
{
result[result[j].small + array[i] - result[j].large].present = true;
result[result[j].small + array[i] - result[j].large].small = result[j].large;
result[result[j].large + array[i] - result[j].small].large = result[j].small + array[i];
}
}
}
}
for(int i = 0; i<= sum; i++)
{
if(result[i].present == true)
cout << i << " ";
}
cout << endl;
delete result;
delete array;
return 0;
}
I think the problem is NP complete problem and we don't have any polynomial solution we can possibly check for all combination,
so what we need to do is to calculate
choose k numbers and sum them,
choose r numbers from remaining ones and sum them
and calculate difference.
Now this k vary from 1 to N and r vary from 1 to N-k,
so the complexity goes to exponential.
Did you read Loler's answer? He gives a case where you need to enumerate all anyway (1,3,9,27) (powers of three).
Yes, with n weights, Theta(3^n) is the worst case(i edited my answer to mention that).
btw, why talk about NP-Completeness (or more accurately NP-hardness as it is not a decision problem)? Why do you think it is even relevant?
(Checking if 0 is possible using at least one weight, is NP-Complete and same as subset sum though).
Ok, loler solution is essentially saying the same thing, he uses another way to say the same thing, using these 3 states, actually -1 represent the elt is in first chosen k number, 1 means it is chosen by next r numbers and 0 means is not being chosen, Yes i didn't wrote the code here, I just explain the algo and the property of the problem
Simply adding pounds to already existing possibilities (~dynamic programming in 1d array)
- tpcz March 13, 2013