Amazon Interview Question
Country: United States
I believe if they ask this kind of problems, they will say k is not very large and they want this answer.
I downvoted this answer because it makes a wrong statement and just says check the wiki, which IMO, is a bad quality answer, with no scope of being corrected unless changed drastically...
As to the interviewer 'wanting' an answer, you seem to be mistaken. There is no specific 'correct' answer they (usually) look for. They try to look for how you plan and approach to solve the problem, and how the discussion goes.
no problem. but we are always trying to do the best we can in an interview, don't we? and this one is probably the best we can do in time complexity, at least the best I can think of.
@zyfo2, when one talks about 'best' with conviction, it always makes me nervous :-)
The best depends on the circumstances and is not always clear. Even with a theta(n^2) vs theta(nlog n) algorithm, the quadratic one might be 'best' under the circumstances.
For this problem, say you had say fifteen 128bit integers for which you were looking for a particular subset sum. It might potentially be better to just enumerate all subsets, rather than go via the dynamic programming approach.
@Bevan: I am curious. Subset sum is NP-Complete even if the numbers are all positive. What algo do you have?
btw, if you do have an algorithm for positive numbers, you can use it for negative numbers (just add a large enough positive number to each, and also put a constraint on the size of the set, and run multiple times for different sizes).
We can do it in O(n^2) using Dynamic Programming, this code is only for positive integers, we can tweak it to take care of -ve integers as well:
// idea is
// a sum x is possible if for any i x-a[i] is possible
bool subsetsum(int *a, int n, int k){
int *s = new int[k+1];
for(int i=0; i<k+1; i++) s[i] = 0;
s[0] = 1;
for(int i=0; i<n; i++)
for(int j=k; j>=a[i]; j--)
s[j] |= s[j-a[i]];
return s[k];
}
You can test the code using your custom test case @ ideone.com/Zsw3J4
This is not O(n^2). What if k was close to n^1000?
This is Theta(nk) to be more precise, and is the pseudo-polynomial algorithm, which makes subset-sum 'not strongly NP-Complete'.
public static void findSubSetForGivenSumInArray(int sum, int[] arr) throws InterruptedException{
int calSum = 0;
Queue q = new Queue();
boolean flag = false;
for(int i=0; i<arr.length; i++){
q.enqueue(arr[i]);
calSum += arr[i];
if(i!=arr.length-1 && arr[i+1]>0)
while(calSum > sum){
Integer deq = (Integer)q.dequeue();
calSum -= deq;
}
if(calSum == sum){
flag = true;
Enumeration e = q.elements();
while(e.hasMoreElements()){
System.out.println(e.nextElement().toString());
}
break;
}
}
if(!flag){
System.out.println(false);
}
}
public class SumSubset {
public static void main(String[] args) {
int[] nos = { 1, 2, 3, 5, 6, 8, 10 };
int sum = 13;
Map<Integer, List<List<Integer>>> subLists = new HashMap<Integer, List<List<Integer>>>();
List<Integer> inL = new ArrayList<Integer>();
subLists.put(0, new ArrayList<List<Integer>>());
subLists.get(0).add(inL);
for (int p = 1; p <= sum; p++) {
subLists.put(p, new ArrayList<List<Integer>>());
for (int i = 0; i < nos.length; i++) {
if (nos[i] <= p) {
List<List<Integer>> merge = merge(nos[i],
subLists.get(p - nos[i]));
for (List<Integer> l1 : merge) {
if (!subLists.get(p).contains(l1))
subLists.get(p).add(l1);
}
}
}
}
System.out.println(subLists.get(sum));
}
private static List<List<Integer>> merge(int i, List<List<Integer>> list) {
List<List<Integer>> new1 = new ArrayList<List<Integer>>();
for (List<Integer> l1 : list) {
if (!l1.contains(i)) {
List<Integer> n = new ArrayList<Integer>();
n.addAll(l1);
n.add(i);
Collections.sort(n);
if (!new1.contains(n)) {
new1.add(n);
}
}
}
return new1;
}
static int position[] = new int[0];
public void sumOfSubset(int[] value, int k, int sum){
if(position.length == 0){
position = new int[value.length];
}
if(k == value.length){
if(sum == 0){
print(value,position);
}
return;
}
position[k] = 1;
sumOfSubset(value, k+1, sum-value[k]);
position[k] = 0;
sumOfSubset(value, k+1, sum);
}
public void print(int[] value, int[] choice){
for(int i =0 ; i<value.length;i++){
if(choice[i] ==1){
System.out.print(value[i] + " ");
}
}
System.out.println();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Numbers n = new Numbers();
//n.decToHex(1128);
int[] value = {5,5,10,100,10,5};
//n.maxSubSequence(value);
n.sumOfSubset(value, 0, 115);
}
Typical question of hash table. Simple store all numbers in a hash table, then check every sum - number in hash table. If number is there, return true. Traverse complete array, if no element found return false. This is independent of number is +ve or -ve.
Complexity O(n)
Your algorithm will only work if we have find just 2 numbers in the array whose summation= given number? There may be a subset of >2 numbers whose summation= given number.
So, the question asks for a subset.
- Roberto Abreu March 05, 2013There are 2^n subsets. One way is checking every subset. This is adequate if n is small (say, +- 30).
If n is bigger then you can consider this problem as a special case of the Knapsack problem.