## Facebook Interview Question for Research Scientists

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````/*
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,
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();
return newSol;
}

public void print() {
System.out.println(SubArray);
}
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@NoOne
thanks! Actually I was looking for a site that is a bit more interactive, as i really love solving this little problems :-) and discussing about them...

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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<>();
}

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);
}
}
}
}
return subset[sum][n];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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<>();
}

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);
}
}
}
}
return subset[sum][n];``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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];
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.