Amazon Interview Question


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
7
of 9 vote

Per my understanding, this is a subset-sum problem.
There is a dynamic programming solution, see
en.wikipedia.org/wiki/Subset_sum

- linzhu February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 8 vote

Ok, i somehow missed that its subset sum problem which can be solved using dynamic programming.

array is a[ 1.. n ]
set dp[ target+10001 ] => all initialized to false
dp[i] = true iff array has a subset whose sum is i

dp[0] = true

for i = 1 to n:
   for j = target-a[i] to 0 ( decrement ): 
       if dp[j] == true:
               dp[ j+a[i] ] = true
  if dp[target] == true:
          return true

return false

This won't work if target < 0 but by using the dp range [ target+10001 to 2*target+10000 ], we can change it to work for that case also.

Time Complexity : O(target*n)
Space Complexity : O(target)

- Cerberuz February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't see any problem with that case.

- Cerberuz February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Array has been sorted here to prevent that thing only ( checking all combinations ). Both the left and right pointers move conditionally ( check the condition ). The algorithm returns true for your test case.

- Cerberuz February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cerberuz Solution works and it is straight forward.

I would like to add one more point. Out of Merge sort, Quick sort and Heap sort. Prefer heap sort, as it takes O(1) space for sorting as compared to Merge/Quick sort.

With this approach Complexity: O(nlogn) + O(n).

Please add, If you anything missing.

Thanks.

- Manpreet February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

works only if sum of two integers is considered. as per problem we can use any number of integers.

- Anonymous February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please elaborate when hashing would be used and how it would be done?

- Nisha February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

^actually its subset-sum problem, i've edited the post.
For target = X+Y case we can use hashing to set hash[ target-a[i] ] = true for every a[i] if its not true. If its already true then we found the solution.

- Cerberuz February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the variable pos in this line:

if dp[pos] == true:

I didn't understand this code, could you please provide full code?

- rodrigoreis22 February 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its dp[j] == true, made the change. Its the complete code except you have to make changes so that it works with -ve target as well.

- Cerberuz February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Cerberuz i think i will work with but there is something missing

in the following statement

if dp[j] == true:
               dp[ j+a[i] ] = true

you set true in dp when there was some other element in dp was already true..... but you never set any element of dp to true(before the main for loop)


I think it can be easily fixed by initializing dp[a[i]] = true (and rest as false) . so that you have elements to start with in dp who are true so that dp can grow on top of them (as you already have 1 element who has a sum equal to index of j)

//before main for loop
for i = 1 to n:
    dp[a[i]] = true

- vik February 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How is this the correct solution? Take the target value as given in the problem: target = 13. Now in iteration i=1, j = target - a[i] is 18. The initial dp[ ] array was set to be only of length 14.

Write code if you can, rather than giving a hand waving pseudo-code snippet. Or at least check your solution before stating it.

- CodeBit February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@vik, its fine as i am doing dp[0] = 1 ( true ), though there is a bug in the code pointed out by CodeBit.

@CodeBit, I usually give a pseudo code based on my ideas and improve it on the basis of comments and corner test cases suggested by others. Just think of an interview scenario were you have to give the solution/code within 10-20 minutes. You will usually put your idea/code before the interviewer with basic testing and he will ask you to improve it. Giving a perfect solution in single shot means either you are genius ( which i am not ) or you already knew the exact solution beforehand ( sometimes it occurs in my case, sometimes it doesn't ).

I tried to update my current solution but getting some server side exception, so will do it later.

- Cerberuz February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This can be solved by dynamic programming

- Ravi February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

if I didn't miss anything, can be done by dp. sort it first, then use dp to calculate the sum from smallest number to target number for every number.
it'll be O(n*(target-samllest number))

- zyfo2 February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

this problem can be solve in nlogn
steps 1: sort the array , (nlogn)
steps 2: for each element subtract the target value and search it in the rest of the element which is already sorted : (nlogn)

- sjain February 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in step 2 can you explain why are you trying to search in the rest of array because i dont think it will work for any number of elements
btw this is a subset problem

- vik February 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

let say the sorted array is : {2,4,5,6,7,8,9}
target sum is: 12.
so if you substract second element from 12 (i.e: 12-4=8) now you have to search 8 in the rest of the array whioch is already sorted. if you get 8 in the arraay then (4,8) as pair.

- sjain February 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do it with target sum = 28 . You will get fault in your approach.

- anonymous May 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can think of the following approach, not sure if this is the best way to do it:

Lets say the target is T, and array given is 'a' having 'n' elements

Sort the array by any sorting algorithm say merge sort or quick sort - that will take (n (log n)) as the total time, now if a is sorted where a[0] is the smallest element, if a[0] < T then return false and exit

If a[0] > T then, I will use a random approach now,

Pick any element in the array a, say element x, now you know the value of a[x], so we have the following equation

a[x] + y = T, and we can find out y using this, this will take a constant time,

now we can quickly scan the array to see if y exists or not, that will take n-1 comparisons, if we find 'y' then return true and exit, if we don't then we continue scanning the remaining n-1 elements , the worst case is that we scan all the elements and don't find a match so this will take O(n2) time,

so the worst case time will be O(n2)
and the best case is n log n

Can't think of a better solution. any comments highly appreciated.

- Sidhu February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why if a[0] < T then return false and exit?

Shouldn't it be if a[0] >= T then return false and exit?

- whoever February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you think the problem is asking you to find integers x and y in the array such that x + y = T, you could achieve O(n^2) worst case and, look, O(1) best case by just the most naive method: try summing every pair of numbers, return true as soon as you see a pair summing to T. Why use randomization at all?

- eugene.yarovoi February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

dp solution code:

static void SubsetSum(int[] input, int sum)
{
	int rows = sum + 1;
	var cols = input.Length + 1;
	var dMatrix = new byte[rows,cols];
	for (var ci = 0; ci < cols; ci++)
		dMatrix[0, ci] = 1;
	for (var ri = 1; ri < rows; ri++)
	{
		for (var ci = 0; ci < cols; ci++)
		{
			dMatrix[ri, ci] = 0;
			if (ci > 0 && dMatrix[ri, ci - 1] == 1)
			{
				dMatrix[ri, ci] = 1;
			}
					
			if (ci > 0)
			{
				var restSum = ri - input[ci - 1];
				if (restSum >= 0 && dMatrix[restSum, ci - 1] == 1)
				{
					dMatrix[ri, ci] = 1;
				}
			}
		}
	}
	var solution = rows - 1;
	if(dMatrix[rows-1, cols - 1] == 1)
	{
		Console.WriteLine("yes");
	}
	else
	{
		Console.WriteLine("no");
	}
}

- S.Abakumoff February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
bool check(int array[], int S, int N, int i, int size) {
if (i >= size) return false;

if (S + array[i] == N) return true;
else return check(array, S, N, i+1, size) || check(array, S+array[i], N, i+1, size);
}
}

- sol0ist February 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use dp..

- ananam February 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Put the numbers in a hash. Start with each of the numbers. Subtract from the target andsee if you have the remainder in the hash.

Set<Integer> inputSet = new HashSet<Integer>(Arrays.asList(new Integer[]   {1,2,3,4,5,6}));
		
		int target = 6;
		
		for(int aNum : inputSet) {
			if(aNum > target)
				continue;
			
			int otherNum = target - aNum;
			
			if(otherNum == aNum)
				continue;
			
			if (inputSet.contains(otherNum)) {
				System.out.println(aNum+","+otherNum+"="+target);
				break;
			}
			
		}

- bagu February 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class FindPairSum {

    public boolean findSum(int[] data, int sum) {
        Arrays.sort(data);

        for (int i = 0, j = data.length-1; i!=j;) {
            int tmp = data[i] + data[j];

            if (tmp > sum) {
                j--;
            } else if (tmp < sum) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String... args) {
        FindPairSum fps = new FindPairSum();
        int[] data = new int[] {-5,6,7,1,0,12,5,-6,100};

        System.out.println(fps.findSum(data, 13));
        System.out.println(fps.findSum(data, 8));
        System.out.println(fps.findSum(data, 200));
    }

}

- Anonymous February 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This should give all subsets of array which totals the given sum.

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

- sudharshan.nn March 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

enDOTwikipediaDOTorg/wiki/Subset_sum_problem

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

package com.trails;

import java.util.Arrays;
import java.util.HashSet;

public class Try {

	public static void main(String[] args) {
		Try t = new Try();
		Integer[] items = new Integer[]{-5,6,7,1,0,12,5,-6,100};
		HashSet<Integer> values = new HashSet<Integer>(Arrays.asList(items));
		t.findSubset(values, 13);
			
	}

	private void findSubset(HashSet<Integer> values, int target) {
		int count = 0;
		for(Integer value : values){
			if(values.contains(target - value)){
				count++;
				System.out.println("Value 1 : " + value + " Value 2 : " + (target-value) + " Target : " + target);
			}
		}
		
		if(count == 0)
			System.out.println("Value not found to make target : " + target);
	}
}

- Digi Digi April 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we need to find 2 elements that adds up to target it can be done O(nlogn) .

but if we need all possible subsets that sums upto target then it becomes subset sum which is NP Complete and u can't do in polynomial time O(n*target) is psuedo-polynomial not a polytime solution. If you are able to find a polytime solution u can win million dollars .. :)

- pras July 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Logic for a kind of optimization:

-sort the array (nlogn)
-select first element say x
-now you have to find element which is (target - x)
-traverse upto [element<=(target-x)]
-in case met (target-x) return true
-else select second element and repeat the above procedure
-in case no (target-x) found return false

- PKT February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use hash table, put all numbers in hash table. This will take O(n) time, then traverse complete array and check whether target-a[i] exist in the array. This is again done in O(n), as hash table check is O(1) and array traversing is O(n).

Total complexity = O(n) (putting in hash table) + O(1)(hash table search)*O(n)(array traversal) = O(n)

- Mitesh February 28, 2013 | Flag Reply


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