## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

classic knapsack problem
dp[i][j][s] - means whether it's possible to get sum s after consideration of i elements and taking exactly j of them.
Overall complexity (N^2 * SUM)

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

Sounds good.

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

The complexity is (N * M * SUM).

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

The runtime should be O(n^m)

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

Here's a JS recursive solution:

``````function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);
}``````

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

Use the fact that addition is commutative to solve this. You don't need to try a number again if you used it higher up the recursion layer, and found it didn't work. But you do for each different prefix set of numbers.

``````public class SubsetSum
{

public SubsetSum()
{

}

@Test
public void testThis()
{
NavigableSet<Integer> remaining = new TreeSet<>();
Set<Integer> inUse = new HashSet<>();

// want 23 out of 3.

Set<Integer> result = calculateSubSetSum(remaining, inUse, 0, 23, 3);
for (Integer i: result)
{
System.out.println(i);
}

}

// Return a set of additions if successful, otherwise null.
public Set<Integer> calculateSubSetSum(NavigableSet<Integer> remaining, Set<Integer> inUse, int sum, int goal, int M)
{

if (M > remaining.size())
{
return null;
}
if (M == 1)
{
if (remaining.contains(goal-sum))
{
// SUCCESS!!!!
return inUse;
} else {
return null;
}
}
else {
while (remaining.size() > 0)
{
// Always safe to take the lowest value.
Integer i = remaining.pollFirst();
// We can safely remove this int, and not return it until the end.
Set<Integer> result = calculateSubSetSum(remaining, inUse,
sum + i,
goal, M-1);
if (result != null)
{
// We got a result!
return result;
}
// No result, try the next addition.
inUse.remove(i);
}
}
{
}
return null;
}
}``````

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

This is great code, but it only works if we assume the input array does not have any repeated elements. For example, if the following input array were turned into a TreeSet, you'd lose all the duplicated 3's and it would fail.

``````int[] input = new int[] { 3, 3, 3, 5, 6, 7};
int M = 3;
int SUM = 9;``````

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

Recursively move the input array and build each possible subset by recursively including and not-including the number at the current index.

``````public static ArrayList<Integer>subset(int[] input, int targetSum, int targetSize,
ArrayList<Integer> currentSet, int currentSum, int currentIndex) {
if (currentSum > targetSum) {
return null;
}
if (currentIndex == input.length) {
return null;
}
if (currentSet.size() == targetSize) {
if (currentSum == targetSum) {
return currentSet;
} else {
return null;
}
}

ArrayList<Integer> withCurrentIndexSubset = (ArrayList<Integer>) currentSet.clone();
withCurrentIndexSubset = subset(input, targetSum, targetSize, withCurrentIndexSubset,
currentSum + input[currentIndex], currentIndex++);

ArrayList<Integer> withoutCurrentIndexSubset = (ArrayList<Integer>) currentSet.clone();
withoutCurrentIndexSubset = subset(input, targetSum, targetSize, withoutCurrentIndexSubset,
currentSum, currentIndex++);

if (withCurrentIndexSubset != null) {
return withCurrentIndexSubset;
} else {
return withoutCurrentIndexSubset;
}

}``````

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

The runtime of this algorithm is O(2^n) even if targetSize is very low, let's say 2.

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

Here is the C++ version of solution using DFS.
It is using permutation algorithm with fixed length.
I am not proud of this solution though. Will post better.

Time complexity is O(N^M) where N is # of numbers in the array and M is the fixed subset.

Any critics or suggestions are welcomed.

``````#include<iostream>
#include<list>
using namespace std;

bool dfs(int left, list<int>&found, int max_depth, bool* marked, int *input, int len)
{
if (found.size() == max_depth)
{
if (left == 0)
{
return true;
}
return false;
}

for (int i = 0; i < len; i++)
{
if (!marked[i] && input[i] <= left)
{
left -= input[i];
marked[i] = true;
found.push_back(input[i]);
if (dfs(left, found, max_depth, marked, input, len))
{
return true;
}
left+= input[i];
marked[i]= false;
found.pop_back();
}
}
return false;
}

list<int> find_sub_set(int * input, int max_size, int sum, int len)
{
bool *marked = new bool[len];
int left = sum;

list<int> found;
for (int i = 0; i < len; i++)
{
if (!marked[i] && input[i] <= left)
{
marked[i] = true;
left -= input[i];
found.push_back(input[i]);
if (dfs(left, found, max_size, marked, input, len))
{
break;
}
marked[i] = false;
left += input[i];
found.pop_back();
}
}
return found;
}

int main()
{
int input[5] = {1,2,4,5,9};
list<int> result = find_sub_set(input, 2, 9, 5);
list<int>::iterator iter;
for (iter = result.begin(); iter != result.end(); iter++)
cout <<(*iter)<<", ";
cout<<endl;
return 1;
}``````

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

``````private static int[] ArraySubSum(int[] input, int num, int sum)
{
return SubSum(input, num, sum, 0);
}

public static int[] SubSum(int[] input, int num, int sum, int idx)
{

for (int i = idx; i < input.Length; i++)
{
if (num == 1 && input[i] == sum)
return new int[1] { input[i] };
else if (num > 1)
{
int[] a = new int[num];
a[0] = input[i];
var p = SubSum(input, num - 1, sum - input[i], i + 1);
for (int k = 0; k < p.Length; k++)
{
a[k + 1] = p[k];
}
if (Sum(a) == sum)
return a;

}

}
return new int[0];
}

public static int Sum(int[] arr)
{
int sum = 0;
for(int i=0;i<arr.Length;i++)
{
sum += arr[i];
}
return sum;
}``````

Using c#

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

stackoverflow.com/questions/31803275/sum-exactly-using-k-elements-solution

``````#include <stdio.h>
#define SIZE(a) sizeof(a)/sizeof(a[0])
int binary[100];
int a[] = {1, 2, 5, 5, 100};

void show(int* p, int size) {
int j;
for (j = 0; j < size; j++)
if (p[j])
printf("%d\n", a[j]);
}

void subset_sum(int target, int i, int sum, int *a, int size, int K) {
if (sum == target && !K) {
show(binary, size);
} else if (sum < target && i < size) {
binary[i] = 1;
foo(target, i + 1, sum + a[i], a, size, K-1);
binary[i] = 0;
foo(target, i + 1, sum, a, size, K);
}
}

int main() {
int target = 10;
int K = 2;
subset_sum(target, 0, 0, a, SIZE(a), K);
}``````

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

I think you meant "subset_sum" instead of "foo"

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

and int binary[100] should be (after a) int binary[SIZE(a)]

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

Here's a quick JS recursion function

``````function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);
}``````

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

There is a simple, elegant and efficient solution (similar to the knapsack problem) if the array only contains non-negative integers. My guess is that condition was part of the problem and was omitted in the question posted on the site.

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

sort the list and iterate over of each element and build a list of tuples containing the minSum and maxSum that can be made when the number is included in the desired subset

iterate of the resulting "sum" list to see which bucket the given sum fits in; eliminate the number from list if its corresponding minSum > sum or maxSum < sum and make a filtered list

recursively do the above method on the remaining list until minSum == sum or maxSum==sum or we run out of elements in the list

``````def subset_helper(ls, n):
subl = []
min = sum(ls[:n-1])
max = sum(ls[-(n-1):])
for i, j in enumerate(ls):
if i < n - 1:
vmin = min + ls[n-1]
else:
vmin = min + j
if i > len(ls) - (n):
vmax = max + ls[len(ls)-n]
else:
vmax = max + j
subl.append((vmin, vmax))
return subl

def find_subset(ls, s, n):
print ls, s, n
if len(ls) < n:
return "Failed 1"
elif len(ls) == n:
if sum(ls) == s:
return ls
else:
return "Failed 2"
subl = subset_helper(ls, n)
print subl
invmin = None
invmax = None
for i, v in enumerate(subl):
print i, v
if v[0] > s:
invmax = i
break
elif v[0] == s:
print 'Found subset at using min:', i
if i <= (n-1):
return ls[:n]
else:
return ls[:(n-1)] + [ls[i]]
if v[1] < s:
invmin = i
elif v[1] == s:
print "Found subset at using max:", i
if i > len(ls) - n:
return ls[-n:]
else:
return ls[-(n-1):] + [ls[i]]
print invmin, invmax

if invmin is not None and invmax is not None and invmin == invmax:
return "Failed 3"

invmin = invmin or -1
invmax = invmax or len(ls) + 1
print 'invmin,invmax', invmin, invmax
return find_subset(ls[invmin+1:invmax], s, n)

if __name__ == '__main__':
l = [0, 4, 5, 6, 14, 13, 1]
s = 14
n = 3
ls = sorted(l)
print find_subset(ls, s, n)``````

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

Starting from the lowest possible sum, work your way up by changing your subset sum by as little as possible. This is done by having a sorted draft subset then swapping the largest element for a slightly bigger element until it's too big then undo the swap and move onto a smaller element in your draft subset. This is basically brute forcing but the extra break in the loop skips the possible subsets where the sum is already too large.

``````public static int[] findSub(int[] nums, int n, int m, int sum) {
Arrays.sort(nums);
printArray(nums);
System.out.println("----------");
int[] subset = Arrays.copyOfRange(nums, 0, m); // Extract the first M smallest elements
int difference;
int original;
int debugCounter = 0;
for (int i = m - 1; i >= 0; i--) {
for (int j = m + 1; j < n; j++) {
printArray(subset);
System.out.println(i + " Sum = " + sum(subset));
difference = sum - sum(subset);
if (difference == 0)
return subset;
if (Arrays.binarySearch(subset, nums[j]) >= 0) {
continue;
}
original = subset[i];
subset[i] = nums[j];
if (sum - sum(subset) < 0) {
subset[i] = original;
break;
}
}
}
return subset;

}
public static int sum(int[] nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
return sum;
}

public static void printArray(int[] nums) {
for (int i : nums) {
System.out.println(i);
}
}
}``````

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

``````<?php

function findSubSet(\$inputs, \$m, \$sum) {
\$length = count(\$inputs);
if (\$length < \$m) return null;

if (\$m == 0) return [];

sort(\$inputs);

for( \$i = 0; \$i <= \$length - \$m; \$i ++) {
\$subset = array_slice(\$inputs, \$i, \$m);
\$tmpSum = array_sum(\$subset);
if (\$tmpSum == \$sum) {
return \$subset;
}
else if (\$tmpSum > \$sum) break;
}

return null;
}

var_dump(findSubSet([7,1,2,3,4,5,6,7,7,7], 4, 14));``````

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

Time: O(n(n+1)/2)=n*n
Space: n(n+1)/2 // to store the limited number of subsets

``````n=length(A)
sets=[ ]
for (i=0 to n-1)
newsets = [ ]
if(M == 1 && setof(A[i]) == SUM) print and break
foreach set in sets
if(s1.size == M && sum(s1)==SUM) print and break
sets.clear()   // we dont need the old sets as we cant add next item to them

Lets say A= {1,2,3,4,5}
M=3
SUM=12

A[i] newsets sets
-----------------------------------------------------------------------------
1 {1} {1}
2 {2}, {1,2} {2}, {1,2}
3 {3}, {2,3}, {1,2,3} {3}, {2,3}, {1,2,3}
4 {4}, {3,4}, {2,3,4}, {1,2,3,4} {4}, {3,4}, {2,3,4}, {1,2,3,4}
5 {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5} {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}

in last iteration we have {3,4,5} whose sum is 12 and size is 3.

Now we went through A only once, but for each elements we iterated over sets which is i times hence n(n+1)/2.
In the last iteration we stored n(n+1)/2 items which is the max

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

``````A[i]                      newsets                                       sets
-----------------------------------------------------------------------------
1                         {1}                                           {1}
2                         {2}, {1,2}                                    {2}, {1,2}
3                         {3}, {2,3}, {1,2,3}                           {3}, {2,3}, {1,2,3}
4                         {4}, {3,4}, {2,3,4}, {1,2,3,4}                {4}, {3,4}, {2,3,4}, {1,2,3,4}
5                         {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}   {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}``````

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

[−2,1,−3,4,−1,2,1,−5,4]

a=0
-2

int maxSubArray(int[] array, int sum) {

if(array==null) || array.length==0)
return 0;

int max=array[a];
int maxsofar=array[a];
if(sum==max)
return;

for(int a =1; a<array.length; a++)
maxsofar=getMax(maxsofar+array[a],array[a]);
max=getmax(max,maxsofar);
if(max==sum) {
break;
return true;
}
if(max>sum)
maxsofar=array[i];
max=array[i];
}
}

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

Can the below code work for this requirement? I'm new to programming, so might be missing something

``````def diff(arr,k):
import itertools
return [ i for i in itertools.combinations(arr,2) if abs(i[0]-i[1])==k ]``````

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

``````def k_subset_sum(numbers, k, total):
sorted_numbers = sorted(numbers, reverse=True)
return k_subset_sum_internal(sorted_numbers, k, total, [])

def k_subset_sum_internal(numbers, k, total, current_list):
if k == 0:
if sum(current_list) == total:
return current_list
else:
return None
sum_so_far = sum(current_list)
upper_bound = total - sum_so_far - (k - 1)
for num in numbers:
if num <= upper_bound:
current_list.append(num)
result = k_subset_sum_internal(numbers, k - 1, total, current_list)
if result is not None:
return result
current_list.pop()
return None

print k_subset_sum([6,4,5,2,3,1], 4, 10)``````

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

A Java solution:

``````public static Set<Integer> findSubsetSizeK( int[] set, int sum, int m ) {
Set<Integer> subset = new HashSet<>( m );
if ( set == null || set.length < m ) {
return subset;
}
return findSubsetSizeK( set, set.length-1, sum, m, subset );
}

public static Set<Integer> findSubsetSizeK( int[] set, int n,  int sum, int m, Set<Integer> subset ) {
if ( getSum( subset ) == sum && m == 0 ) {
return subset;
} else if ( m == 0 || n < 0 ) {
return null;
}
if ( set[n] < sum ) {
Set<Integer> subsetWithElement = findSubsetSizeK( set, n-1, sum, m-1, subset );
if ( subsetWithElement != null ) {
return subsetWithElement;
} else {
subset.remove( set[n] );
return findSubsetSizeK( set, n-1, sum, m, subset );
}
} else {
return findSubsetSizeK( set, n-1, sum, m, subset );
}
}

private static int getSum( Set<Integer> set ) {
int sum = 0;
for ( int element : set ) {
sum += element;
}
return sum;
}

public static void main( String[] args ) {
int[] set = { 3, 34, 4, 12, 5, 2 };
int sum = 19; // {12,5,2}
int m = 3;
System.out.println( "A subset for " + Arrays.toString( set ) + " that sums up to " + sum +
" with exactly " + m + " elements is: " + findSubsetSizeK( set, sum, m ) );
System.out.println();

sum = 17;  // {3,12,2}
System.out.println( "A subset for " + Arrays.toString( set ) + " that sums up to " + sum +
" with exactly " + m + " elements is: " + findSubsetSizeK( set, sum, m ) );
System.out.println();
}``````

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

Scala : recursive solution with memorization
Complexity: N * M * SUM

``````def subset(ARR: Seq[Int], M: Int, SUM: Int): Seq[Seq[Int]] = {

if (M > ARR.length) return Seq.empty

val memo = mutable.Map.empty[(Seq[Int], Int, Int), Seq[Seq[Int]]]

def run(arr: Seq[Int], m: Int, sum: Int): Seq[Seq[Int]] = memo.getOrElseUpdate((arr, m, sum), {
if (arr.isEmpty) return Seq.empty

if (m == 1 && sum != head) return Seq.empty

(1 until arr.length)
.flatMap(i => run(arr.drop(i), m - 1, sum - head))
.toSeq
})

(0 until ARR.length).flatMap(i => run(ARR.drop(i), M, SUM)).toSeq
}

println(subset(Seq(3, 3, 3, 4, 4, 1, 0, 9, 0), 3, 9))``````

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

``````static void PrintSubsets()
{
int source[] = {1,2,3,4,5,6};
int currentSubset = (int)Math.pow(2, source.length)-1;
int total=10;
int tmp=0,noofones;
int size=4;
while(currentSubset>0)
{noofones=0;
int sum=0;
StringBuilder sb=new StringBuilder();
tmp=currentSubset;
for(int k=0;k<source.length;k++)
{
if( (tmp&1)>0)
{
sum+=source[k];
sb.append(source[k]);
sb.append(" ");
noofones++;
}
tmp>>=1;
}
if(sum==total && noofones==size)
System.out.println(total+" = "+sb.toString());

currentSubset--;
}

}``````

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

``````'''
On a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.
'''

import sys
import copy

def findSum(numList, size, sum, start, tmpSum, tmpList):

print str(tmpList)
result = []
if tmpSum == sum and len(tmpList) is size:
return tmpList
elif tmpSum > sum:
return []
elif len(tmpList) is size:
return []

for i in range(start, len(numList)):
tmpSum += numList[i]
tmpList.append(i)
result = findSum(numList, size, sum, i+1, tmpSum, tmpList)
if len(result):
break;
tmpSum -= numList[i]
tmpList.remove(i)

return result

def main():
numList = [1, 2, 3, 4, 5]
size = 4
sum = 10
result = findSum(numList, size, sum, 0, 0, [])

if result:
print 'Found subset of size ' + str(size) + ':' + str(result)
else:

if __name__ == '__main__':
sys.exit(main())``````

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

time: O(2^n) since |powerset(xs)| = 2^|xs|
space: O(n)

``````sizedSubset :: Int -> Int -> [Int] -> Maybe [Int]
sizedSubset m s =
List.find ((== s) . List.sum) . fmap (List.take m) . List.permutations``````

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

Here's a recursive solution in JS

``````function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);``````

}

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

Here's a recursive solution in JS

``````function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);
}``````

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

Here's a JS recursive solution:

``````function findSubset (n, m, sum, subset) {
if (sum === 0 || n.length < 1) return subset;
var n0 = n.shift();
if (n0 === sum) {
subset.push(n0);
return subset;
}
else if (n0 < sum) {
subset.push(n0);
return findSubset(n, m-1, sum - n0, subset);
}
else return findSubset(n, m, sum, subset);
}``````

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

Test post

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

``````public static void main(String[] args) throws Exception {
int[] a = {5,3,2,1,0,4,9,7,8};
subSeqSumSizeM(a,3,5);
}

//On a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.
private static void subSeqSumSizeM(int[] a, int m, int sum) {

if(a == null || (a.length==0) || m<=0 || m>a.length)
return;

for(int i=0; i<m; i++) {
}

for(int j=1; j<a.length-m; j++) {
System.out.println((j-1)+ "-" + (j+m-2));

}
}``````

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

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

``````def diff(arr,m,sumofset):
import itertools
return [ i for i in itertools.combinations(arr,m) if abs(i[0]-i[1])==sumofset ]``````

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

``````def diff(arr,m,k):
''' arr = array of n number
m=size of subset
k=SUM of the subset'''
import itertools
return [ i for i in itertools.combinations(arr,m) if sum(i)==k ]``````

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

Algorithm - iterate over the array - remove all zero's and extract the subset M find the size.

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

You can remove any numbers greater than SUM, but should not remove zeros. for example, N = [0,1,2,3], M = 2, SUM=1. The only valid subset is [0,1], where zero is needed.

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.