## Amazon Interview Question

• 0

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

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

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

I don't see any problem with that case.

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

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.

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

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

Thanks.

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

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

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

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

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

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

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

What is the variable pos in this line:

``if dp[pos] == true:``

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

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

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.

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

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

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

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.

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

@vik, its fine as i am doing dp = 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.

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

This can be solved by dynamic programming

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

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)

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

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

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

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.

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

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

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 is the smallest element, if a < T then return false and exit

If a > 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.

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

Why if a < T then return false and exit?

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

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

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?

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

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

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

use dp..

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

}``````

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

}``````

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

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

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

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

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

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)

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.