Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Subset-Sum just asks for a subset summing to a value greater than zero. The only additional information we have in this problem is that the target value is less than the number of elements in the set. So this may not be an NP-Hard problem.
For k = 2 all we have to do is to check all pairs... O(n^2)
For k = 3 we would check all triplets.. O(n^3)
For general case: O(n^k).
If we use hashmap we can eliminate single loop - this gives us O(n^(k - 1)).
Sort the array using quick sort and run the below procedure on it:
public static void findNum(int[] arr, int val){
int i = 0, j = arr.length - 1;
while(i < j){
if(arr[i] + arr[j] == val){
System.out.println(arr[i] + " at " + i);
System.out.println(arr[j] + " at " + j);
return;
}else if(arr[i] + arr[j] > val){
j--;
}else{
i--;
}
}
System.out.println("Values not found");
}
Complexity : O(nlogn) for merge sort + O(n) for linear parsing ==> O(nlogn)
Using Dynamic Programing. Time O(n3) pseudo-polymophism, Space O(n3)
bool KSum(vector<int> num, int sum,int N)
{
bool dp[100][100][100];
for(int i=0;i<100;i++)
{
for(int j=0;j<100;j++)
{
for(int k=0;k<100;k++)
{
dp[i][j][k]=false;
}
}
}
//Base Case
for(int i=1;i<=num.size();i++)
{
for(int j=1;j<=i;j++)
dp[i][1][num[j-1]]=true;
}
//Induction
for(int i=2;i<=num.size();i++)
{
for(int j=2;j<=i;j++)
{
for(int k=0;k<=sum;k++)
{
dp[i][j][k]=dp[i-1][j][k]||dp[i-1][j-1][k-num[i-1]];
}
}
}
return dp[num.size()][N][sum];
}
using subset sum code
public class SubsetZero {
public static void main(String[] args) {
int[] w={1,1,-1,-2};
int[] x={0,0,0,0,0,0};
fn(0,0,0,w,x,3);
System.out.println("hi");
}
private static boolean fn(int currSum, int totalNumberUptillNow, int currentIndex,int[] originalArray,int[] trackingArray,int k) {
if(currentIndex>=originalArray.length)
return false;
if(currSum+originalArray[currentIndex]==0&&totalNumberUptillNow==k-1){
trackingArray[currentIndex]=1;
return true;
}
else if(totalNumberUptillNow<k){
boolean l=fn(currSum+originalArray[currentIndex],totalNumberUptillNow+1,currentIndex+1,originalArray,trackingArray,k);
if(!l)
return fn(currSum,totalNumberUptillNow,currentIndex+1,originalArray,trackingArray,k);
if(l) trackingArray[currentIndex]=1;
return l;
}
return false;
}
}
Naive method: Time O(nlogn) Space O(1)
Sort the array and then linear search for 'k' adjacent elements to add upto zero.
In space sorting such as quicksort will allow O(1) space complexity.
I think that there should be a better method to do it in O(nlogk) time and O(k) space!
this solution does not work for array = {1,1,-1,-2} and k = 3.
Sorting the array would give you - {-2,-1,1,1}. Linear search for 3 adjacent elements won't result in a solution. the actual solution is {-2,1,1}
1.Sort the array in O(nlogn)
2. Initialize a BST or min-max heap and insert k/2 elements from the left and right parts of the array of Step 1; initialize curr_sum = sum of the k elements
3. l = k/2; r = array.length-1-k/2
4. while (l <= r)
5. if curr_sum < 0 then extract min(BST) and insert array[r] into the BST; r--;
6. else if curr_sum > 0 then extract max(BST) and insert array[l] into the BST; l++;
7. Recompute curr_sum of the elements in the BST; if curr_sum == 0 then return true;
8. If while loop completes, return false;
@BoredCoder I think your method will fail with the case {-4, -2, 0, 3, 4, 5}, where -4+0+4=0 but your method cannot find it. Please correct me if I'm wrong.
isnt this the subset sum problem?
- Anonymous October 30, 2012