Amazon Interview Question


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.

- Roberto Abreu March 05, 2013 | Flag Reply
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

- zyfo2 March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You do know subset sum is NP-Complete?

It is not strongly NP-Complete though...

- Loler March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zyfo2 March 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zyfo2 March 06, 2013 | Flag
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.

- Loler March 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 March 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Loler March 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- aniket210689 March 06, 2013 | Flag
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).

- Loler March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Loler. Check mine

- HauntedGhost March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Exactly the one posted by HauntedGhost
:)

- Bevan March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Loler March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

True that :)

- Bevan March 05, 2013 | Flag
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[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

- HauntedGhost March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- Loler March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- HauntedGhost March 05, 2013 | Flag
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);
        }   
    }

- Raunak Agarwal March 05, 2013 | Flag Reply
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>>());
		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;

	}

- Anonymous March 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Question is for sub-set sum on negative numbers.

- Second Attempt March 14, 2013 | Flag
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

- suckit March 06, 2013 | Flag Reply
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

- Frank March 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

- sudharshan March 07, 2013 | Flag Reply
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)

- mYth March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Vikas March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Vikas is right. You misunderstood the problem statement.

- Anonymous March 05, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More