SWAPTON SOLUTIONS Interview Question Java Developers
Team: DEV
Country: India
Interview Type: Written Test
Simple Recursion in Python
def subsets(low, high, n, target):
def f(low, n, target, prefix):
if low >= high:
return
if n == 1:
if low <= target < high:
yield prefix + [target]
return
for i in range(low, high):
cnt = 0
for result in f(i+1, n-1, target-i, prefix + [i]):
yield result
cnt += 1
if cnt == 0:
break
for result in f(low, n, target, []):
yield result
for ans in subsets(10, 100000, 4, 55):
print ans
A Knapsack Problem.
Just give all the elements a value 1, and run the Knapsack algorithm using DP.
That should give u the solution.
Hope it helps. Let me know if you need further clarification.
Given that all the elements are exactly 1 unit apart, one could find one combination that works and then generate other combinations by generating all combinations in which one of the set elements is 'moved left' and another is 'moved right', but only for those elements that can be moved (aren't stuck against another element). This algorithm would exclude a lot of combinations that can't work, like choosing from a set of elements in which no numbers add up to the number sought.
@Anonyomous, you're basically describing a "successor" function, which is always an interesting way to think about problems involving combinations and permutations, and which leads to "odometer" algorithms. Basically, for all the subsets that can produce 55, you know that they have some sort of natural ordering, and if you're given one of the subsets, then there should be a deterministic way to perturb its elements in a minimal way to get the next result.
In this problem, you've already described the basic mechanism to some degree. Start by trying to perturb the second to last element, but it might be "stuck," as you say. In that case, you have to perturb the third to last element instead. And, of course, for every number you perturb in one direction, perturb another number in the opposite direction.
package swaption;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class FindSum {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
printSubsets(arr, 1, 4, 55, 55, new HashSet<Integer>(), new HashSet<Integer>(), new ArrayList<Set<Integer>>());
}
private static void printSubsets(int[] arr, int count, int x, int y, int remainder, Set<Integer> used,
Set<Integer> elements, List<Set<Integer>> previouslyFound) {
for (int i = 0; i < arr.length; i++) {
if (used.contains(i)) {
continue;
}
int diff = remainder - arr[i];
used.add(i);
if (count + 1 < x) {
printSubsets(arr, count + 1, x, y, diff, used, elements, previouslyFound);
} else if (count + 1 == x) {
if (elements.contains(diff) && !isAlreadyFound(used, previouslyFound)) {
previouslyFound.add(new HashSet<Integer>(used));
System.out.println(getElementsFromArray(arr, used, diff) + " = " + y);
}
}
if (count == 1) {
elements.add(arr[i]);
}
used.remove(i);
}
}
private static boolean isAlreadyFound(Set<Integer> newSet, List<Set<Integer>> previouslyFound) {
for(Set<Integer> set : previouslyFound) {
if(set.containsAll(newSet)) {
return true;
}
}
return false;
}
private static String getElementsFromArray(int[] arr, Set<Integer> indexes, int diff) {
StringBuilder sb = new StringBuilder();
for (Integer i : indexes) {
sb.append(arr[i] + " + ");
}
sb.append(diff);
return sb.toString();
}
}
This can be done using DP
- DashDash March 20, 2013void FindSet(int *a, int x, int Sum, int n)
{
if(a[n] > Sum)
FindSet(a,x,Sum,n-1);
else if(Sum == 0 && x == 0)
{
//found print and return
}
else
{
FindSet(a, x, Sum, n-1);
FindSet(a, x-1, Sum-a[n], n-1);
}
}