Amazon Interview Question Java Developers
Country: United States
Interview Type: In-Person
subset sum problem
int total=0;
#define SIZE(a) sizeof(a)/sizeof(a[0])
int arr[] = {1, 2, 3, 4};
int counter = 0;
void IsSubArray(int n, int N, int sum) // N is the number of elements in the array
{
if(sum == N) {
total++;
return;
}
if((n <= (SIZE(arr)-1)) && arr[n]+sum <= N) {
IsSubArray(n+1, N, sum+arr[n]);
}
if((n <= (SIZE(arr)-1)) && arr[n+1]+sum <= N) {
IsSubArray(n+1, N, sum);
}
}
int main()
{
int j, i;
int target_sum=3;
IsSubArray(0, target_sum, 0);
printf("%d\n", total);
return 0;
}
achieve the goal with deep recursions,may lack efficiencies
def subsum(target,arr):
result = [];
for idx in range(len(arr)):
if arr[idx] == target:
result.append([arr[idx]])
else:
mres = subsum(target-arr[idx],arr[0:idx])
for mset in mres :
mset.insert(0, arr[idx])
result.append(mset)
return result
result = subsum(3,[1,2,3,4,-1,-3]);
for x in result:
print x
@Kanha
Your algorithm returns {{1,5},{2,4},{3,3},{6}} when there is only one 3 in the set
array problem set of{1,2,3,4,5,6}.
Your inner loop index should be initialized 1 beyond the outer loop to avoid comparing a[i] to itself when j == i. Better to initialize j with [ j = i + 1;]. Like this for(int j=i+1; j<a.length; j++).
int total_sums(vector<int> & nums, int sum)
{
int sums =0;
for(size_t i =0; i < nums.size(); i++)
{
if (nums[i] < sum && nums.size()>1)
{
//keep going
vector<int> remaining;
remaining.insert(remaining.begin(),nums.begin(), nums.end());
remaining.erase(remaining.begin()+1);
sums+= total_sums(remaining,sum-nums[i]);
}
if (nums[i] == sum)
sums++;
}
return sums;
}
Start thinking about subtracting from sum. Values in array are sorted. Start eliminating those bigger once then the sum (from the end of array) as those are not part of the sum. First combination is number equal sum or less (in case there is no equal). You now need to check-subtract only half of what's left as second half is symmetric (the same combinations). Divide and conquer rather than brute force of all combinations. The end result will be multiplication from all successful subtraction sets (success is measured if zeroed sum recursively).
#include<stdio.h>
int main()
{
int a[]={1,2,3,4},i,j,num,size;
printf("enter number: ");
scanf("%d",&num);
size=sizeof(a)/sizeof(a[0]);
for(i=0;i<size;i++)
{
if(a[i]==num)
printf(" {%d}, ",a[i]);
for(j=i;j<size;j++)
{
if((a[i]+a[j])==num)
{
printf("{%d %d},",a[i],a[j]);
}
}
}
return 0;
}
Assuming array is sorted
int arr[] = new int[]{1,2,3,4,5,6,7,8,9,10};
List<Integer> filter = new ArrayList<Integer>();
int num = 9 ,k =0;
for(int i = 0;arr[i]<num;i++)
filter.add(num-arr[i]);
int [] b = new int[filter.size()];
for(int i : filter)
{
b[k] = i;
k++;
}
for(int i=0,j=b.length-1;i<j;i++,j--)
System.out.println("combination :"+b[j]+","+b[i]);
Assuming array is sorted.
int arr[] = new int[]{1,2,3,4,5,6,7,8,9,10};
List<Integer> filter = new ArrayList<Integer>();
int num = 9 ,k =0;
for(int i = 0;arr[i]<num;i++)
filter.add(num-arr[i]);
int [] b = new int[filter.size()];
for(int i : filter)
{
b[k] = i;
k++;
}
for(int i=0,j=b.length-1;i<j;i++,j--)
System.out.println("combination :"+b[j]+","+b[i]);
int arr[] = new int[]{1,2,3,4,5,6,7,8,9,10};
List<Integer> filter = new ArrayList<Integer>();
int num = 9 ,k =0;
for(int i = 0;arr[i]<num;i++)
filter.add(num-arr[i]);
int [] b = new int[filter.size()];
for(int i : filter)
{
b[k] = i;
k++;
}
for(int i=0,j=b.length-1;i<j;i++,j--)
System.out.println("combination :"+b[j]+","+b[i]);
public static void main(String[] args)
{
int arr[] = new int[]{3,4,5,6,9,10,13,34,45,46,49,50,28,38};
List<Integer> filter = new ArrayList<Integer>();
int num = 13 ,k =0;
for(int i = 0;arr[i]<=num;i++)
filter.add(arr[i]);
int [] b = new int[filter.size()];
for(int i : filter)
{
b[k] = i;
k++;
}
for(int i=0,j=b.length-2;i<j;i++,j--)
{
int sum = b[i] + b[j];
if(sum == num)
System.out.println("Combination :"+b[i]+","+b[j]);
}
}
public static void main(String[] args)
{
int arr[] = new int[]
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38
,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,89,90,100,121,134,157,189,190,200,249,250,253,278,280
,300,301,304,340,350,367,369,379,380,400,400,458,457,490,491,500,501,502,505,508,550,587,590,600};
int n = 0, num = 90, k = 0, l = 0;
List<Integer> filterEven = new ArrayList<Integer>();
List<Integer> filterOdd = new ArrayList<Integer>();
while (n < arr.length)
{
if (arr[n] < num)
{
if (arr[n] % 2 == 0)
filterEven.add(arr[n]);
else
filterOdd.add(arr[n]);
}
n++;
}
int evenArr[] = new int[filterEven.size()];
int oddArr[] = new int[filterOdd.size()];
for (int i : filterEven)
{
evenArr[k] = i;
k++;
}
for (int i : filterOdd)
{
oddArr[l] = i;
l++;
}
if (num % 2 == 0)
{
for (int i = 0; i < evenArr.length; i++)
{
for (int j = 0; j < evenArr.length; j++)
if (evenArr[i] < evenArr[j]
&& num == evenArr[i] + evenArr[j])
System.out.println("Combination is: " + evenArr[i]
+ "," + evenArr[j]);
}
for (int i = 0; i < oddArr.length; i++)
{
for (int j = 0; j < oddArr.length; j++)
{
if (oddArr[i] < oddArr[j] && num == oddArr[i] + oddArr[j])
System.out.println("Combination is: " + oddArr[i] + ","
+ oddArr[j]);
}
}
} else
{
for (int i = 0; i < evenArr.length; i++)
{
for (int j = 0; j < oddArr.length; j++)
{
if (num == evenArr[i] + oddArr[j])
System.out.println("Combination is: " + evenArr[i]
+ "," + oddArr[j]);
}
}
}
}
1)First Sort Array.
2) Then iterate the array,
a) if element is greater than the sum then continue
b) if element is equal to the sum then just print the element and continue
c) if both a & b if not true then ,
i) we need to iterate only for half of the array to avoid duplicates. Example (1,6) and (6,1).
ii) find the element in array by using binary search whose value is (sum - element at i), if it is found then print the pair
package com.problems;
public class FindCombinationOfSum
{
public static void main(String[] args)
{
findComibination();
}
public static void findComibination()
{
int[] a = { 2, 3, 1, 4, 5, 7, 6 };
int sum = 7;
a = mergeSort(a, 0, a.length - 1);
int search = -1;
int searchIndex = -1;
for (int i = 0; i < a.length; i++)
{
if (a[i] > sum)
{
continue;
}
if (a[i] == sum)
{
System.out.println(a[i]);
continue;
}
if (i < a.length / 2)
{
search = sum - a[i];
searchIndex = binarySearchIterative(a, search, 0, a.length - 1);
if (searchIndex != -1)
{
System.out.print(a[i] + "," + search);
System.out.println();
}
}
}
}
public static int[] mergeSort(int[] a, int p, int r)
{
if (p < r)
{
int q = (r + p) / 2;
mergeSort(a, p, q);
mergeSort(a, q + 1, r);
merge(a, p, q, r);
}
return a;
}
private static int[] merge(int[] a, int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
for (int i = 0; i < n1; i++)
{
leftArray[i] = a[p + i];
}
for (int j = 0; j < n2; j++)
{
rightArray[j] = a[q + 1 + j];
}
int i = 0, j = 0, k = p;
while (i < n1 && j < n2 && k <= r)
{
if (leftArray[i] <= rightArray[j])
{
a[k++] = leftArray[i++];
}
else
{
a[k++] = rightArray[j++];
}
}
while (i < n1 && k <= r)
{
a[k++] = leftArray[i++];
}
while (j < n2 && k <= r)
{
a[k++] = rightArray[j++];
}
return a;
}
private static final int NOT_FOUND = -1;
public static int binarySearchIterative(int[] a, int value, int start, int end)
{
while(start <= end)
{
int middle = (start + end)/2;
if(value == a[middle])
{
return middle;
}
else if(value > a[middle])
{
start = middle + 1;
}
else
{
end = middle - 1;
}
}
return NOT_FOUND;
}
public static void printArray(String tag, int[] a)
{
System.out.print(tag + ": ");
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + ",");
}
System.out.println("");
}
}
int sum = 5;
List<Integer> input = Arrays.asList(2,3,4,9,-1,9,12);
List<Integer> current = Arrays.asList();
List<List<Integer>> results = new ArrayList<List<Integer>>();
getCombinationsThatSumTo(sum, input, current, results);
static void getCombinationsThatSumTo(int desiredSum, List<Integer> input, List<Integer> current, List<List<Integer>> results)
{
if (input.isEmpty()) return;
int sum = 0;
for (int i = 0; i < current.size(); i++) {
sum += current.get(i);
}
if (sum == desiredSum) {
results.add(current);
//for ease, just print it.
for (int j = 0; j < current.size(); j++) {
System.out.print(current.get(j)+",");
}
System.out.println("");
}
getCombinationsThatSumTo(desiredSum, input.subList(1, input.size()), current, results);
List<Integer> newCurrent = new ArrayList<Integer>(current);
newCurrent.add(input.get(0));
getCombinationsThatSumTo(desiredSum, input.subList(1, input.size()), newCurrent, results);
}
This is the variation of Subset Sum problem, where subset sums to 0. The problem is NP-Complete. Naive algorithm is exponential time, where you try all the combinations in the array and check to see if it adds to the given sum. The running time of the naive implementation is, 2^n subsets and n times addition, O(n* 2^n).
- math.matt May 23, 2013Wikipedia says there is a better exponential time algorithm that runs in O(2^(n/2)) time and a pseudo-polynomial time dynamic programming solution. For implementation, you can Google "Subset Sum Problem".