Amazon Interview Question
Country: United States
Interview Type: Phone Interview
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)
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 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.
works only if sum of two integers is considered. as per problem we can use any number of integers.
^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.
What is the variable pos in this line:
if dp[pos] == true:
I didn't understand this code, could you please provide full code?
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 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
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.
@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.
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)
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
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.
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.
Why if a[0] < T then return false and exit?
Shouldn't it be if a[0] >= T then return false and exit?
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?
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");
}
}
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;
}
}
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));
}
}
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();
}
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);
}
}
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 .. :)
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
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)
Per my understanding, this is a subset-sum problem.
- linzhu February 02, 2013There is a dynamic programming solution, see
en.wikipedia.org/wiki/Subset_sum