Amazon Interview Question Software Engineer in Tests
public static void main(String[] args) {
int[] a = { 5, 5, 10, 2, 3 };
// int[] a={1, 2, 3, 4, 5};
int i = find15Combi(a, 0, 15);
System.out.println(i);
}
private static int find15Combi(int[] a, int start, int toSearch) {
int i = 0;
for (; start < a.length; start++) {
if (a[start] == toSearch) {
i++;
} else if (a[start] < toSearch)
i = i + find15Combi(a, start + 1, toSearch - a[start]);
}
return i;
}
I believe both the space and time complexity of this solution are non-polynomial, am I right?
Using dp, we can solve it in o(n^2) time and o(n) space.
I don't think dynamic programming applies here. There are total 2^5=32 combinations for 5 numbers. Dynamic programming doesn't reduce the number of subproblems, it only solves each subproblem atmost once. verma.tech's code doesn't hit same subproblem twice.
This is the code I used:
#include <stdio.h>
// a: array
// n: last index of a
// sum: desired sum
// curr: current sum
int subsetSum(int a[], int n, int sum, int curr) {
if(curr==sum)
return 1;
if(curr>sum || n<0)
return 0;
return subsetSum(a, n-1, sum, curr+a[n]) + subsetSum(a, n-1, sum, curr);
}
int main() {
int a[] = {5, 5, 10, 2, 3};
printf("%d\n", subsetSum(a, 4, 15, 0));
system("pause");
return 0;
}
public static void main(String[] args) {
int[] a = { 5, 5, 10, 2, 3 };
// int[] a={1, 2, 3, 4, 5};
int i = find15Combi(a, 0, 15);
System.out.println(i);
}
private static int find15Combi(int[] a, int start, int toSearch) {
int i = 0;
for (; start < a.length; start++) {
if (a[start] == toSearch) {
i++;
} else if (a[start] < toSearch)
i = i + find15Combi(a, start + 1, toSearch - a[start]);
}
return i;
}
works fine only if the input is sorted (ascending).
Also,u need to invoke this function for all the indexes of array and den add the final sum to have all the values
I tested this for variety of inputs and seems to be working fine.
input int[] a = { 5, 5, 10, 2, 3 }; is not sorted and it works for that and returns 4
also, we need not generate all combinations, if we can check mid-way that whether the current combi is valid one or not.
please update if u find some bug in above.
I think it does not have a polynomial time solution .. as it is a well known subsetsum problem
<pre lang="java" line="1" title="CodeMonkey69130" class="run-this">int findSumComb(int a[], int sum)
{
int s[MAX_SUM]={1};
for (int i = 0; i < SIZEA; ++i)
for (int j = sum; j>=a[i]; --j )
s[j] += s[j-a[i]];
return s[sum];
}
</pre><pre title="CodeMonkey69130" input="yes">
</pre>
This is my solution. I dont know how to post the code so ...
Anyway, give u the main function too. u can check it if u like.
the limitation is all integers must be positive.
to handle both positive and negative, the algo can not be so elegant and compact. but the idea is similar.
#include <iostream>
using namespace std;
#define SIZEA 5
#define MAX_SUM 20
int main()
{
int aa[] ={1,2,3,4,5};
int bb[] = {5,7,10,2,3};
cout << findSumComb( bb, 15) << endl;
getchar();
return 0;
}
Another thing I want to clarify is that: precisely speaking, this is not a polynomial solution because its in O(n*sum) where sum is actually nonlinear with the n. Suppose we have 5 numbers: 100000, 200000, 3000000, 4000000, 500000. The time comp is O(5*150000). But in this case, since 15 is not that big, dp works perfectly well.
A small problem with your findSumComb code....For an input like the following:
int bb[] = {5,5,10,2,3};
The program returns 4 whereas the answer should be 6. Any insight or correction in ur algo?
@fentoyal - A very elegant solution! I too had a DP approach, but was far from this elegant!
int []array_Max={5, 5, 10, 2, 3};
int combine=0;
for (int i=0;i<array_Max.length;++i)
{
int j=i+1;
combine+=findCombination(array_Max,array_Max[i],j,15);
}
System.out.println(combine);
public static int findCombination(int []array, int sum, int iStart, int iTarget)
{
int n=0;
for (int i=iStart;i<array.length;++i)
{
if (sum+array[i]==iTarget)
{
n++;
}
n=n+findCombination(array,sum+array[i],++iStart,iTarget);
}
return n;
}
nt []array_Max={5, 5, 10, 2, 3};
int combine=0;
for (int i=0;i<array_Max.length;++i)
{
int j=i+1;
combine+=findCombination(array_Max,array_Max[i],j,15);
}
System.out.println(combine);
public static int findCombination(int []array, int sum, int iStart, int iTarget)
{
int n=0;
for (int i=iStart;i<array.length;++i)
{
if (sum+array[i]==iTarget)
{
n++;
}
n=n+findCombination(array,sum+array[i],++iStart,iTarget);
}
return n;
}
// count how many different combinations that sum up to X
int countSum(vector<int> v, int X) {
if (X == 0) { // termination case: this combination satisfied
return 1;
}
if (v.empty()) { // termination case: this combination unsatisfied
return 0;
}
int n = v.back();
v.pop_back();
if (n <= X) { // try two cases: with n or without n
return countSum(v, X - n) + countSum(v, X);
} else { // since n is too large, try only one case: without n
return countSum(v, X);
}
}
Take the combination of all the elements in the array, use them to find the sum of each set extracted. Still this can be optimized.
- Anonymous December 26, 2010