Facebook Interview Question for SDE1s


Country: United States




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

/*
like knapsack, the problem of finding a subset of a set that 
sums up to a sum is a known NP-complete problem. There exists 
a pseudo polynomial solution like with knapsack.

The recursion is
dp(i, k, target, result) = dp(i-1, k, target, result) ++ dp(i-1, k, target, result + {nums[i]}), if k > 0
                           return result, if k == 0 and target == 0
						   return {} if (k == 0 && target !=0) || target < 0 || i < 0 

++: merge the list of sets returned by dp
this is O(n*(n-1)*(n-2)*..*(n-k)) = O(n!/(n-k)!) (if k = 1, its n...)

a common subproblem exists if the sum z of l<k elements of multiple subsets
in the range [o..n) exists, because then, all of those subsets would
lead to a solution if at least one subset of k-l elements in [0..o) would 
sum up to target-z.

...

how to solve it now:
1) first thing we need to do is offset the target and all element values so
we get only positive values and 0s. we can here convert nums to a set to get 
rid of ublicate values (because the result is supposed to be a set)
note: the target has k times the offset
reduced problem set: combinationSumPositive

2) create an empty sums hashtable where the sum is key and the values are all
subsets with size <= k that lead to this sum (only for sum <= target)
sums[0] = list with one empty set

iterate i from 0 to n
  for each key in sums:
	if key+nums[i] <= target:
		for each set in sums[key]
			if(set.size() < k) 
				nums.add(key+nums[i], set + {nums[i]}

3) sums[target] contains all results, but as well those with size < k, filter it

4) remove offset from elements, done.

5) time complexity is O(n*target*n*n) = O(n^3*target) ... hey, it's polinomial :-)
   Space complexity is O(target*n^2) 

of course, if you put this solution into Hackerrank or Leetcode it may produces 
TLEs because it's relatively easy to construct special cases that will kill it. 
To improve, you can either check up front if there is a solution without collecting 
the sets, or better, mark the required subsums and element count that are needed 
for a solution and later on only collect those subsums.
*/


// reduced problem, only positive nums and positive target
vector<vector<int>> combinationSumPositive(const unordered_set<int>& nums, int target, int k) {
	unordered_map<int, vector<vector<int>>> sums;
	sums[0] = vector<vector<int>>(1, vector<int>()); 
	for (int a : nums) {
		decltype(sums) newSums;
		for (auto p : sums) {
			if (p.first + a <= target) {
				for (vector<int>& s : p.second) {
					if (s.size() < k) {
						vector<int> newSet = s;
						newSet.push_back(a);
						newSums[p.first + a].push_back(newSet);
					}
				}
			}
		}
		
		// merge new sums into sums
		for (auto pn : newSums) {
			auto ps = sums.find(pn.first);
			if (ps == sums.end()) {
				sums.emplace(pn.first, move(pn.second));
			} else {
				for (vector<int>& ns : pn.second)
					ps->second.emplace_back(move(ns));
			}
		}
	}

	vector<vector<int>> result;
	for (vector<int>& r : sums[target]) {
		if (r.size() == k) {
			result.push_back(move(r));
		}
	}
	return result;
}



vector<vector<int>> combinationSum(vector<int>& nums, int target, int k) {
	int minA = min(0, target); // case of negative target
	for (int a : nums) minA = min(a, minA);
	if (minA < 0) {
		for (int& a : nums) a -= minA; // TODO: overflow check
		target -= k * minA; // TODO: overflow check
	} 
	vector<vector<int>> result = combinationSumPositive(unordered_set<int>(nums.begin(), nums.end()), target, k);
	for (vector<int>& r : result) {
		for (int& v : r) {
			v += minA;
		}
	}
	return result;
}

ostream& operator << (ostream& o, vector<vector<int>> lofl) {
	cout << "[" << endl;
	for (auto& l : lofl) {
		o << "  [";
		bool first = true;
		for (int v : l) {
			if (first)  o << v; 
			else o << ", " << v;
			first = false;			
		}
		o << "  ]" << endl;
	}
	cout << "]" << endl;
	return o;
}


int main()
{
	cout << combinationSum(vector<int>({1,6,12,2,-5,8}), 9, 3);
	/* output
	[
	[1, 6, 2]
	[12, 2, -5]
	[6, -5, 8]
	]
	*/
}

- Chris May 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution {

    public static List<List<Integer>> combinationSum(int[] nums, int target, int k){
        if(nums.length == 0 || k ==0)
                return new ArrayList<List<Integer>>();

        List<List<Integer>> result = new ArrayList<List<Integer>>();
        combinationSumUtil(nums, k, 0, target, new ArrayList<Integer>(), result);

        return result;
    }

    public static void combinationSumUtil(int[] nums, int k, int start, int target, List<Integer> tempList, List<List<Integer>> result) {

        if(k < 0) return;
        if(k == 0 && target == 0){
            result.add(new ArrayList<Integer>(tempList));
            return;
        }

        for(int i = start; i< nums.length; i++){
            tempList.add(nums[i]);
            combinationSumUtil(nums, k - 1, i + 1, target - nums[i], tempList, result);
            tempList.remove(tempList.size()-1);
        }
    }

    public static void main(String args[]){
       int[] nums = {-1,2,-2,3,4,1};
        List<List<Integer>> result = combinationSum(nums, 3, 2);

        System.out.print(result.toString());
    }
}

- aravindbros May 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Find all k length subsets and calculate the sum of each of them
 * When the sum equals target - add the subset to the solution list
 * Use a hashMap to avoid duplications
 */
public class Solution {

  public static void main(String[] args) {
    List<List<Integer>> solution = combinationSum(new int[]{5,3,1,6,2,-1,0}, 5, 3);
    System.out.println(solution);
  }

private static List<List<Integer>> combinationSum(int[] nums, int target, int k) { 
    List<List<Integer>> solution = new ArrayList<List<Integer>>();
    Map<Integer,List<Integer>> solutionMap = new HashMap<Integer, List<Integer>>();
    ArrayList<Integer> list = new ArrayList<Integer>();
    for(int i=0; i<nums.length; i++) {
      list.add(nums[i]);
    }
    combinationSum(solutionMap, new ArrayList<Integer>(), list ,k ,target);
    solution.addAll(solutionMap.values());
    return solution;
  }

  private static void combinationSum(Map<Integer,List<Integer>> solutionMap, ArrayList<Integer> subList1, ArrayList<Integer> subList2, int k, int target) {
    if(subList1.size() == k && subList1.stream().mapToInt(Integer::intValue).sum() == target) {
      Integer hash = subList1.hashCode();
      if(!solutionMap.containsKey(hash)) {
        subList1.sort(Integer::compareTo);
        solutionMap.put(subList1.hashCode(), subList1);
      }
    }
    for(int i=0; i<subList2.size(); i++) {
      ArrayList<Integer> newSubList1 = new ArrayList<Integer>();
      newSubList1.addAll(subList1);
      newSubList1.add(subList2.get(i));
      
      ArrayList<Integer> newSubList2 = new ArrayList<Integer>();
      newSubList2.addAll(subList2);
      newSubList2.remove(i);
      combinationSum(solutionMap, newSubList1, newSubList2, k, target);
    }
  }

Result:
[[0, 2, 3], [-1, 1, 5], [-1, 0, 6]]

- Sivan May 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Sivan:
when studying your code, I noticed

Integer hash = subList1.hashCode();
      if(!solutionMap.containsKey(hash)) {
        subList1.sort(Integer::compareTo);
        solutionMap.put(subList1.hashCode(), subList1);
      }

this doesn't only prevent adding duplicates but as well different lists that by chance result in the same hash value.You need to deep compare to ensure it's not the case (of course this happens only once in 2^31 cases ...) anyway I just noticed

further, I think [0,2] and [2,0] would produce different Hash codes but represent the same set.

When solving the problem I concluded best to avoid dublicate sets is to produce a set from the input values... (as well because the amount of entries go into the factorial for the O(n!) runtime)

- Chris May 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def printSubsets(items,Sum,tempList,list):
    if Sum == 0:
       i1= copy.copy(tempList);
       list.append(i1); 
       return;
    if 0 == len(items):
       return;
    index = 0; 
    items.sort();
    i = items[0];
    tempList.append(i);
    j1= copy.copy(items);
    j1.remove(i);
    printSubsets(j1,Sum-i,tempList,list);
    tempList.remove(i);
    printSubsets(j1,Sum,tempList,list); 
    return list;

tempList=[];
list=[];
print printSubsets([8,2,3,13,11,5],13,tempList,list)

- koustav.adorable May 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The brute force can be computed using the powerset the cost is 2^n

def powerset(a):
    solutions = [[]]
    for x in a:
        solutions = solutions[:] + map(lambda r: r + [x], solutions)
    return solutions

def computesum(sequence, desired_sum):
    results = []
    for x in powerset(sequence):
        if desired_sum == sum(x):
            results.append(x)
    return results

As for the recursive version I like it more this version. You recurse using the set of elements and the sum.
C(S, sum)
if sum < 0: do nothing
if sum == 0:
S is a valid subset
else:
for each i in S do C({S} - i, sum - i)
Here is the code that does it in python

def computesum(sequence, desired_sum):
    results = []
    if desired_sum == 0:
        return [answers]
    elif desired_sum > 0:
        for e in sequence:
            s = sequence.copy()
            s.remove(e)
            results.extend(computesum(s, desired_sum - e))
    return results

Please take note that the previous code returns the complements if you want to return the actual sets you can pass the original set as a function parameter and return the complement when desired_sum is 0
Finally here is a nice iterative version that computes the same as before pruning the subsets that can't contain a valid sum

def computesum(a, s):
    solutions = [[]]
    for x in a:
        solutions = solutions[:] + map(lambda r: r + [x], solutions)
        solutions = filter(lambda x: sum(x) <= s, solutions)
    return filter(lambda x: sum(x) == s, solutions)

- Fernando June 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Time Complexity: O(c(n,k)) Space: O(n + c(n,k)). Avoids dupicates.
public class Detail{
	int value;
	int count;
	
	public Detail(int v, int c){
		value = v;
		count = c;
	}
}

public List<List<Integer>> subset(int[] arr, int t,int k){
	List<List<Integer>> res = new ArrayList<List<Integer>>();
	Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
	for(int i = 0; i < arr.length; i++){
		int ct = 1;
		if(mp.containsKey(arr[i])){
			ct += mp.get(arr[i]);
		}
		mp.put(arr[i],ct);
	}
	Detail[] arr = new Detail[mp.size()];
	int idx = 0;
	for(Map.Entry<Integer,Integer> e: mp.entrySet()){
		arr[idx++] = new Detail(e.getKey(),e.getValue());
	}
	subsetHelp(0,arr,new ArrayList<Detail>(),res,t,k);
	return res;
}

private void subsetHelp(int idx,Detail[] arr, List<Detail> tmp, List<List<Integer>> res, int t, int k){
	if(k == 0){
		if(t == 0){
			res.add(expand(tmp));
		}
		return;
	}
	if(k < 0 || idx == arr.length){
		return;
	}
	subsetHelp(idx + 1, arr, tmp, res, t , k);
	for(int j = 1; j <= arr[idx].count; j++){
		tmp.add(new Detail(arr[idx].value,arr[idx].count);
		subsetHelp(idx + 1, arr, tmp, res, t - (j * arr[idx].value), k - j);
		tmp.remove(tmp.size() - 1);
	}

}

private List<Integer> expand(List<Detail> ls){
	List<Integer> r = new ArrayList<Integer>();
	for(Detail d: ls){
		for(int c = d.count; c > 0; c--){
			r.add(d.value);
		}
	}
	return r;
}

- divm01986 June 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

class Solution {
public ArrayList<ArrayList<Integer>> findSets(int[] nums, int k, int target) {
int setSize = nums.length;
int maxElement = 1 << setSize;
// 1 << 3 = 1000
// 0 1 2 3 4 5 6 7, 7 = 111
ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < maxElement; i++) {
ArrayList<Integer> foundSet = convertIntToSet(nums, i);
output.add(foundSet);
}
for(ArrayList<Integer> eachSet: output) {
for(Integer setElement : eachSet) {
System.out.print(setElement + " ");
}
System.out.println("");
}
ArrayList<ArrayList<Integer>> finalOut = new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> eachSet : output) {
if(eachSet.size() != k) {
continue;
}
int sum = 0;
for(Integer setElement : eachSet) {
sum += setElement;
}
if(sum == target) {
finalOut.add(eachSet);
}
}
return finalOut;
}
//
public ArrayList<Integer> convertIntToSet(int[] num, int index) {
ArrayList<Integer> findSet = new ArrayList<Integer>();
int counter = 0;
while(index > 0) {
int indexBit = 1 & index;
if(indexBit == 1) {
findSet.add(num[counter]);
}
index = index >> 1;
counter++;
}
return findSet;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {-1,6,9,-4};
// output = 170 (-5,85,90)
// output = 170 (90,30,50)
// k = 3
// n = 10
// [2 3]
// - - -
//generate all possible subsets of size k
ArrayList<ArrayList<Integer>> output = solution.findSets(nums, 2, 5);
//solution.findSets(nums);
for(ArrayList<Integer> eachSet: output) {
for(Integer setElement : eachSet) {
System.out.print(setElement + " ");
}
System.out.println("");
}
}
}

- Gaurav Kishan June 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

class Solution {
public ArrayList<ArrayList<Integer>> findSets(int[] nums, int k, int target) {
int setSize = nums.length;
int maxElement = 1 << setSize;
// 1 << 3 = 1000
// 0 1 2 3 4 5 6 7, 7 = 111
ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < maxElement; i++) {
ArrayList<Integer> foundSet = convertIntToSet(nums, i);
output.add(foundSet);
}
for(ArrayList<Integer> eachSet: output) {
for(Integer setElement : eachSet) {
System.out.print(setElement + " ");
}
System.out.println("");
}
ArrayList<ArrayList<Integer>> finalOut = new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> eachSet : output) {
if(eachSet.size() != k) {
continue;
}
int sum = 0;
for(Integer setElement : eachSet) {
sum += setElement;
}
if(sum == target) {
finalOut.add(eachSet);
}
}
return finalOut;
}
//
public ArrayList<Integer> convertIntToSet(int[] num, int index) {
ArrayList<Integer> findSet = new ArrayList<Integer>();
int counter = 0;
while(index > 0) {
int indexBit = 1 & index;
if(indexBit == 1) {
findSet.add(num[counter]);
}
index = index >> 1;
counter++;
}
return findSet;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {-1,6,9,-4};
// output = 170 (-5,85,90)
// output = 170 (90,30,50)
// k = 3
// n = 10
// [2 3]
// - - -
//generate all possible subsets of size k
ArrayList<ArrayList<Integer>> output = solution.findSets(nums, 2, 5);
//solution.findSets(nums);
for(ArrayList<Integer> eachSet: output) {
for(Integer setElement : eachSet) {
System.out.print(setElement + " ");
}
System.out.println("");
}
}
}

- gauravkishan June 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.List;
import java.util.ArrayList;
import java.lang.StringBuilder;

public class sumgoal{

public static List<List<Integer>> combinationSum(int[] nums, int target, int k) {
return sum(nums, 0, target, k);
}

public static List<List<Integer>> sum(int[] nums, int pos, int target, int k){
List<List<Integer>> result = new ArrayList<List<Integer>>();

if(pos >= nums.length){
return result;
}

if(k == 1){
for(int i=pos; i < nums.length; i++){
if(nums[i] == target){
List<Integer> r1 = new ArrayList<Integer>();
r1.add(nums[i]);
result.add(r1);
}
}

return result;
}

int val = nums[pos];

List<List<Integer>> r1 = sum(nums, pos + 1, target - val, k-1);
for(List<Integer> item:r1){
item.add(val);
}
result.addAll(r1);
result.addAll(sum(nums, pos + 1, target, k));

return result;
}

public static void main(String[] args) throws Exception{
int[] data = new int[]{1,2,3,4,5,6,7,8,9,10};
List<List<Integer>> result = combinationSum(data, 10, 4);

for(List<Integer> r:result){
StringBuilder sb = new StringBuilder();
for(int v:r){
if(sb.length()!=0){
sb.append(",");
}
sb.append(v);
}
System.out.println(sb);
}
}
}

- justforfun June 17, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More