Facebook Interview Question Research Scientists
Country: United States
Interview Type: Phone Interview
Recursive solution, complexity O(2^(countofitems<targetsum))
package main
import (
"fmt"
"sort"
)
func main() {
input := []int{1, 1, 3, 4, 1, 1, 2, 3}
target := 4
// sorting can be done O(n)
sort.Ints(input)
used := make([]bool, len(input))
findSum(input, used, target, 0)
}
func print(used []bool, input []int) {
for i := 0; i < len(input)-1; i++ {
if used[i] {
fmt.Printf("%d ", input[i])
}
}
fmt.Println()
}
func findSum(input []int, used []bool, target, cur int) {
if cur > target {
return
}
if cur == target {
print(used, input)
return
}
for i := 0; i < len(input)-1; i++ {
if input[i] > target {
return
}
if used[i] {
continue
}
used[i] = true
findSum(input, used, target, cur+input[i])
used[i] = false
}
}
Cool to see @ChrisK back. Welcome back dude. However, as a welcome gesture,
I will love to rub something in... and here we go:
/* This is how to ZoomBA */
a = [1, 1, 3, 4, 1, 1, 2, 3]
target = 4
range_a = [0:size(a)].asList
// sequences generates all possible subset of a set
options = from ( sequences( range_a ), set() ) as {
// map back the opt to actual
list( $.o ) -> { a[$.o] }
// the where clause filter around it
} where { sum($.o) == target }
// prints it
println(options)
class subset_sum {
static ArrayList<ArrayList<Integer>> subsetSum(int set[], int n, int sum) {
ArrayList<ArrayList<Integer>> subset[][] = new ArrayList[sum+1][n+1];
for (int i = 0; i <= n; i++) {
subset[0][i] = new ArrayList<>();
subset[0][i].add(new ArrayList<Integer>());
}
for (int i = 1; i <= sum; i++) {
subset[i][0] = null;
}
// Fill the subset table in bottom up manner
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
subset[i][j] = subset[i][j-1];
if (i >= set[j-1] && subset[i - set[j-1]][j-1] != null) {
if (subset[i][j] == null) {
subset[i][j] = new ArrayList<ArrayList<Integer>>();
} else {
subset[i][j] = new ArrayList<ArrayList<Integer>>(subset[i][j-1]);
}
for (ArrayList<Integer> list: subset[i - set[j-1]][j-1]) {
ArrayList<Integer> newList = new ArrayList<Integer>(list);
newList.add(set[j-1]);
subset[i][j].add(newList);
}
}
}
}
return subset[sum][n];
}
class subset_sum {
static ArrayList<ArrayList<Integer>> subsetSum(int set[], int n, int sum) {
ArrayList<ArrayList<Integer>> subset[][] = new ArrayList[sum+1][n+1];
for (int i = 0; i <= n; i++) {
subset[0][i] = new ArrayList<>();
subset[0][i].add(new ArrayList<Integer>());
}
for (int i = 1; i <= sum; i++) {
subset[i][0] = null;
}
// Fill the subset table in bottom up manner
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
subset[i][j] = subset[i][j-1];
if (i >= set[j-1] && subset[i - set[j-1]][j-1] != null) {
if (subset[i][j] == null) {
subset[i][j] = new ArrayList<ArrayList<Integer>>();
} else {
subset[i][j] = new ArrayList<ArrayList<Integer>>(subset[i][j-1]);
}
for (ArrayList<Integer> list: subset[i - set[j-1]][j-1]) {
ArrayList<Integer> newList = new ArrayList<Integer>(list);
newList.add(set[j-1]);
subset[i][j].add(newList);
}
}
}
}
return subset[sum][n];
}
vector<vector<int>> SumSets(vector<int> const &a, int sum,
unordered_map<pair<int, int>, vector<vector<int>>> &memo, int idx = 0)
{
vector<vector<int>> sets;
if (sum == 0) {
sets.push_back(vector<int>());
return sets;
}
if (sum < 0) {
return sets;
}
pair<int, int> memo_key = pair<int, int>(idx, sum);
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
for (int i = idx; i < a.size(); ++i) {
vector<vector<int>> subsets = SumSets(a, sum - a[i], memo, i + 1);
for (auto const & subset : subsets) {
vector<int> set{a[i]};
set.insert(set.end(), subset.begin(), subset.end());
sets.push_back(set);
}
}
memo[memo_key] = sets;
return memo[memo_key];
}
- Chris April 27, 2017/* Assumptions: -- - for simplicity values in array must be > 0 - the sum must be > 0 - it said "sets of values" are looked for, for simplicity I assume, if the input already contains a set, otherwise an additional step would be required to create a set from the array. - "find sets" I interpret as find all sets in the powerset of the input whose elements sum up to sum Brute force solution: -- brute force, try all combinations which are 2^input-size Improvement (inspired by the iterative solution of knap-sack): -- This is complicated to explain. Therefore I simplify the problem for explanation to only say "yes, sum can be reached" or "no...". In this scenario what one can do is, keep a set of sums one can reach. Now for each input value, we add it to all already existing values in the set and put this values back into the set. If we reach the sum, we are done. (...). Of course this starts with the initial set that contains a single 0. Since we need to tell which elements were in this sum, the set of current reachable sums is not enough, we need to store the elements as well, and since a given sum (or part sum) can be reached on multiple ways and all solutions are wanted this is a bit messy. I did it by creating an array of Hashtables. The array is basically of size # of input-values + 1 (+1: start case 0). The Hashtable contains as keys all the reachable sums and as values two flags: - did I reach it by including the current value of index i - did I reach it by not including the current value of index i - both (therefore two flags) This array of Hashtables is created iterative, easily, the ugly part is backtracking to output all the combinations. Note that the assumption about positive sum and positive element values can be removed now, how ever, it's somewhat more comfortable to keep it to define runtime and space: time complexity: O(sum*n), where sum is the integer value of the desired sum and n is the number of elements. space complexity: O(sum*n) */ public class SetOfNumbers { private static final int USE_CURRENT = 1; private static final int USE_LAST = 2; public static void printAllSums(int[] input, int sum) { // initial step, create the array of hash tables List<HashMap<Integer, Integer>> memo = new ArrayList<>(input.length + 1); for(int i = 0; i < input.length + 1; i++) memo.add(new HashMap<>()); memo.get(0).put(0, 0); // start condition for(int i = 0; i < input.length; i++) { for(int currentSum : memo.get(i).keySet()) { memo.get(i+1).compute(currentSum, (k, v) -> v != null ? v | USE_LAST : USE_LAST); if(currentSum + input[i] <= sum) { // since no negative inputs are allowed... memo.get(i + 1).compute(currentSum + input[i], (k, v) -> v != null ? v | USE_CURRENT : USE_CURRENT); } } } // backtrack and print results using Result Helper class (below) if(!memo.get(memo.size()-1).containsKey(sum)) { System.out.println("no solution found"); } else { Stack<ResultHelper> solutionBuilder = new Stack<>(); solutionBuilder.push(new ResultHelper(sum, input.length - 1)); while (!solutionBuilder.empty()) { ResultHelper solution = solutionBuilder.pop(); if (solution.InputIndex == -1) solution.print(); Integer memoEntry = memo.get(solution.InputIndex + 1).get(solution.RemainingSum); if ((memoEntry & USE_CURRENT) > 0) { solutionBuilder.push(solution.createNext(input[solution.InputIndex])); } if ((memoEntry & USE_LAST) > 0) { solution.InputIndex--; solutionBuilder.push(solution); } } } } public static void main(String[] args) { printAllSums(new int[]{1,2,3,4,5,6,7,8}, 12); /* output [5, 4, 2, 1] [5, 4, 3] [6, 3, 2, 1] [6, 4, 2] [6, 5, 1] [7, 3, 2] [7, 4, 1] [7, 5] [8, 3, 1] [8, 4] */ } // Helper class, to help backtracking and creating the results private static class ResultHelper { public ResultHelper(int remainingSum, int inputIndex) { RemainingSum = remainingSum; InputIndex = inputIndex; } public int RemainingSum; public int InputIndex; public ArrayList<Integer> SubArray = new ArrayList<>(); public ResultHelper createNext(int inputValue) { ResultHelper newSol = new ResultHelper(RemainingSum - inputValue, InputIndex - 1); newSol.SubArray = (ArrayList<Integer>)SubArray.clone(); newSol.SubArray.add(inputValue); return newSol; } public void print() { System.out.println(SubArray); } } }