## Amazon Interview Question

• 0

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

So, the question asks for a subset.
There 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.

Comment hidden because of low score. Click to expand.
0
of 2 vote

dp. you can do it in n^2. check the subset sum on wiki

Comment hidden because of low score. Click to expand.
0

You do know subset sum is NP-Complete?

It is not strongly NP-Complete though...

Comment hidden because of low score. Click to expand.
0

@Loler alright. for non-negative array, you have dp solutions for O(nk), if not N^2.

Comment hidden because of low score. Click to expand.
0

I believe if they ask this kind of problems, they will say k is not very large and they want this answer.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

hi, do let me know what is "NP" here........ and is the question asking to find the number which can be expressed in sum of other array elements or those numbers which when summed to make a n element......
like {8, 2,6, 3,4,5,}

so we need to get {8, 6, 5} or {2, 4, 6, 5}

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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).

Comment hidden because of low score. Click to expand.
0

@Loler. Check mine

Comment hidden because of low score. Click to expand.
0

Exactly the one posted by HauntedGhost
:)

Comment hidden because of low score. Click to expand.
1
of 1 vote

@Bevan: That is not O(n^2). See my comment.

Comment hidden because of low score. Click to expand.
0

True that :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 = 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

Comment hidden because of low score. Click to expand.
2

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'.

Comment hidden because of low score. Click to expand.
0

@Loler, You are right, my bad. It's O(nk)

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````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>>());
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))
}
}
}

}
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>();
Collections.sort(n);
if (!new1.contains(n)) {
}
}

}

return new1;

}``````

Comment hidden because of low score. Click to expand.
0

Question is for sub-set sum on negative numbers.

Comment hidden because of low score. Click to expand.
0
of 2 vote

suckit fellows

import itertools
vals = [1,2,3,-1,-2,3,4,5,6]
SUM=6
combos = itertools.chain(*((x for x in itertools.combinations(vals, i) if sum(x) == SUM) for i in xrange(len(vals)+1)))
for c in combos: print c

Comment hidden because of low score. Click to expand.
0
of 0 vote

Let's be clear. Is this subsequence or subset?

If subsequence you could just iterate through it in O(n^2), else you'll have to figure out a smarter method... such as the knapsack method

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static int position[] = new int;
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);

}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Vikas is right. You misunderstood the problem statement.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.