Facebook Interview Question Software Developers
Country: United States
@chrisk, I could be wrong or else some else has similar but robust logic above code snippets submitted, can you please let me know if you think this will work
1) find max negative number and offset with his value so that all numbers are positive or zero
2) Sort the numbers
2) iterate i from 1 to n-1
perform perfect sum problem with (0, i-1) with sum = nums[i] , using dp this costs O(n * sum) to calculate subsets, (If there are duplicate sums, I am not sure if first one or longest one to pick to mark as removed along with ith index, may be this decision may result in np complete like you said)
the numbers that remaining, count is the answer, it will take it O(n^2 * sum)?
@trying to learn: indeed there is a dp solution to calculate subsets that sum up to a target value (a pseudo polynomial solution). One can modify it for this problem, one can even get all subsets for a given target, but at this point you need to choose one or none of this subsets and repeat for all choices and all following choices to build the min. It's codeable, certainly, but it's ugly, more efficient then the other solutions here, but still not nice. There might be a more elegant step from the sum-problem to deciding which subsets to use, but I haven't really found that. It looks like a contest question, so there might be some hacky dp that works with special conditions, which are not really given here (maybe elements are unique, etc..)
btw. for the perfect sum dp, you do not need to sort - as for knapsack, no soting is required, because the question is only is the element in or not and basically what you do is iterate over the range of the desired sum and mark all sums that you can reach with (and without from previous iterations) that element. How ever, sort doesn't hurt, because it's an order of magnitude faster than the actual DP ;-)
public List<Integer> findAll(List<Integer> nums) {
// the list should contain at least 3 elements
if(nums.size() < 3){
return nums;
}
Stack<Integer> stack = new Stack<>();
// sort in descending order (actually it can be sorted only first time the list sent,
// so wrapping it with another method will do the job)
nums = nums.stream().sorted((i1, i2) -> Integer.compare(i2, i1)).collect(Collectors.toList());
// pick the maximum number from the list
int curSum = nums.get(0);
// put the second number in the list to the top of the stack and set the loop to start from the 3rd element
int lastIndex = 2;
stack.add(nums.get(1));
// loop until all the permutations tested
while (!stack.isEmpty()) {
// loop till the end of the list starting from the last element added to the stack in the previous round
for (int ind = lastIndex; ind < nums.size(); ind++) {
// in case the difference > 0 you can subtract another number
if(curSum - stack.peek() > 0){
curSum-=stack.peek();
// in case it equals 0, all the elements in the stack added will equal to first element in the list
}else if(curSum - stack.peek() == 0){
// remove all the elements in the stack and the 1st element
nums.removeAll(stack);
nums.remove(nums.get(0));
return findAll(nums);
// lesser than zero means the last number you tried can not be a part of the expression
}else{
stack.pop();
}
// add next number ot stack and update the last index
stack.add(nums.get(ind));
lastIndex = ind;
}
}
return nums;
}
At first glance, the solution seems simple (when assuming: no duplicate numbers in the array). Even when adding duplicate entries, this is still solvable with not much of change.
The idea here is to visit each permutation (per target number) only once. We keep on recursing on the array until we find the lowest result.
Running the example numbers will yield 5 possible solutions, from which we pick the least one (which is one)
std::unordered_set<int> all_numbers;
std::unordered_set<std::string> visited_matches;
std::string make_key(const std::vector<int>& numbers, int target)
{
std::string key;
for(int i = 0; i < (int)numbers.size(); ++i) {
key += std::to_string(numbers[i]);
}
key += std::to_string(target);
return key;
}
bool is_equal(const std::vector<int>& numbers, int target)
{
int res = 0;
std::string k = make_key(numbers, target);
if(visited_matches.count(k)) {
return false;
}
visited_matches.insert(k);
for(int i = 0; i < (int)numbers.size(); ++i) {
res += numbers[i];
}
if(res == target) {
// remove these numbers from the set
for(int i = 0; i < (int)numbers.size(); ++i) {
std::cout << numbers[i] << " ";
all_numbers.erase(numbers[i]);
}
std::cout << " => " << target << std::endl;
all_numbers.erase(target);
return true;
} else if(res < target) {
return false;
}
// recurse
for(int i = 0; i < (int)numbers.size(); ++i) {
std::vector<int> v = numbers;
v.erase(v.begin() + i); // remove the i-th entry to create a new subset and try again
if(is_equal(v, target)) {
return true;
}
}
return false;
}
int search_subset_groups(const std::vector<int>& numbers)
{
std::cout << "--------------------------------------------" << std::endl;
// initialize the hash
all_numbers.clear();
all_numbers.insert(numbers.begin(), numbers.end());
bool cont = false;
while(true) {
// create the list of numbers to work on
// We copy it from the hash
std::vector<int> numbersLeft;
std::for_each(all_numbers.begin(), all_numbers.end(), [&](int n) { numbersLeft.push_back(n); });
// sort the list in desc order
std::sort(numbersLeft.begin(), numbersLeft.end(), [](int a, int b) { return a > b; });
// And try to find matches
for(int i = 0; i < (int)numbersLeft.size(); ++i) {
std::vector<int> v = numbersLeft;
int target = numbersLeft[i];
v.erase(v.begin() + i);
if(is_equal(v, target)) {
cont = true;
break;
}
}
if(cont) {
cont = false;
continue;
}
break;
}
std::cout << "==> we are left with array of size " << all_numbers.size() << std::endl;
std::for_each(all_numbers.begin(), all_numbers.end(), [&](int n) { std::cout << " " << n << std::endl; });
return all_numbers.size();
}
int getNumbers(const std::vector<int>& numbers)
{
int size = search_subset_groups(numbers);
if(size == 0) return 0;
while(size < (int)numbers.size()) {
int newIterSize = search_subset_groups(numbers);
if(newIterSize == (int)numbers.size()) {
break;
}
if(newIterSize < size) size = newIterSize;
if(newIterSize == size) continue;
}
return size;
}
///------------------------------------------------------
/// Main
///------------------------------------------------------
int main(int argc, char** argv)
{
std::vector<int> numbers = { 48, 20, 1, 3, 4, 6, 9, 24 };
// std::sort(numbers.begin(), numbers.end(), [](int a, int b) { return a > b; });
int minArrSize = getNumbers(numbers);
std::cout << "The best match leaving us with an array of size: " << minArrSize << std::endl;
return 0;
}
@chrisK, as always thanks for your detailed response :), I was also concerned about which subset to chose, the problem does not say minimization but being FB interview question it may be implied like you suggested. The only reason I sorted because, we don't have to consider elements greater than index i, for subset problem and you are right, it won't improve that much but it won't hurt either.
@tryingtolearn: an other thing, the offset is tempting but you need to take into account the following:
if you create a sum over k element, and each element is original value + offset, you have k offsets in the sum. if a+b+c=d, then sum(a+o,b+o,c+o) = d+3*o, but you would offset d only by one o (as it is in the array). For the dp to work, you either assume positive numbers or, create a dp range into the negative and positive (which actually should be possible)
import b.k.P;
import java.util.*;
public class Main {
public static void main(String[] args) {
int[]n = new int []{1,2,3,5,6,11};
boolean[] used =new boolean[n.length];
int r = solve(n.length,n,used);
}
static int solve(int remain, int[] nums, boolean[] used){
int res = remain;
if(remain<3){
return remain;
}
for(int i=0;i<nums.length;i++){
if(!used[i]){
//try it as sum-> get all subsets
used[i]=true;
remain--;
List<List<Integer>> subsets = new ArrayList<List<Integer>>();
getsets(nums[i],nums,used,new ArrayList(),subsets,0);
if(subsets.size()>0){
for(List<Integer> l :subsets){
for(Integer j:l){
used[j]=true;
remain--;
}
res = Math.min(solve(remain,nums,used),res);
for(Integer j:l){
used[j]=false;
remain++;
}
}
}
used[i]=false;
remain++;
}
}
return res;
}
static void getsets(int target,int[]nums,boolean[]used,ArrayList<Integer> temp,List<List<Integer>> res,int idx){
if(target==0){
res.add(new ArrayList<Integer>(temp));
return;
}
for(int i=idx;i<nums.length;i++){
if(used[i]||target-nums[i]<0){continue;}
used[i]=true;
target-=nums[i];
temp.add(i);
getsets(target,nums,used,temp,res,i+1);
temp.remove(temp.get(temp.size()-1));
used[i]=false;
target+=nums[i];
}
}
}
I wrote another solution based on my previous solution. A bit more elegant (this time using queue (vector based)
The code:
#include <memory>
#include <vector>
#include <list>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <unordered_map>
#include <unordered_set>
#include <stdlib.h>
#include <algorithm>
#include <queue>
#include <vector>
#include "PriorityQueue.h"
std::unordered_set<int> Numbers;
std::vector<int> TargetNumbers;
std::unordered_set<std::string> Visited;
std::vector<std::vector<int> > Matches;
// Create a unique key to identify this combination (numbers + their target value)
std::string makeKey(const std::vector<int>& numbers, int targetNumber)
{
std::string s;
std::for_each(numbers.begin(), numbers.end(), [&](int n) { s += std::to_string(n); });
s += std::to_string(targetNumber);
return s;
}
bool find_subsets(const std::vector<int>& numbers, int targetNumber)
{
// assume: numbers is sorted in desc order
std::string k = makeKey(numbers, targetNumber);
if(Visited.count(k)) return false;
// Calc the sum
int sum = 0;
std::for_each(numbers.begin(), numbers.end(), [&](int n) { sum += n; });
if(sum == targetNumber) {
// Remove this array from the global array
std::vector<int> matchedNumbers = numbers;
matchedNumbers.push_back(targetNumber);
Matches.push_back(matchedNumbers);
std::for_each(matchedNumbers.begin(), matchedNumbers.end(), [&](int n) { Numbers.erase(n); });
Visited.insert(k);
return true;
}
if(sum < targetNumber) return false;
// Try other permutations
for(size_t i = 0; i < numbers.size(); ++i) {
std::vector<int> v = numbers;
v.erase(v.begin() + i);
if(find_subsets(v, targetNumber)) {
return true;
}
}
return false;
}
int get_min_array_size(const std::vector<int>& numbers)
{
//Visited.clear();
Numbers.clear();
TargetNumbers.clear();
Matches.clear();
// Initialise the Numbers set
TargetNumbers = numbers;
std::for_each(numbers.begin(), numbers.end(), [&](int n) { Numbers.insert(n); });
std::sort(TargetNumbers.begin(), TargetNumbers.end(), [](int a, int b) { return a > b; });
while(!TargetNumbers.empty()) {
// Pop the first number to try
int targetNumber = TargetNumbers[0];
// Always remove the number from the queue
TargetNumbers.erase(TargetNumbers.begin());
if(Numbers.count(targetNumber) == 0) {
// this number was already processed
continue;
}
// Create an array of numbers from the remaining numbers and sort it in desc order
std::vector<int> arr;
std::for_each(Numbers.begin(), Numbers.end(), [&](int n) {
if(n != targetNumber) {
arr.push_back(n);
}
});
std::sort(arr.begin(), arr.end(), [](int a, int b) { return a > b; });
// Process all possibilities
find_subsets(arr, targetNumber);
}
return Numbers.size();
}
int main(int argc, char** argv)
{
// Print the path
std::vector<std::vector<int> > BestMatches;
std::vector<int> numbers = { 48, 20, 1, 3, 4, 6, 9, 24 };
int minSize = (int)numbers.size();
int arrSize = 0;
while(arrSize != (int)numbers.size()) {
arrSize = get_min_array_size(numbers);
if(arrSize < minSize) {
BestMatches.swap(Matches);
minSize = arrSize;
}
}
// Print the groups
std::cout << "We are left with an array of size: " << minSize << std::endl;
std::cout << "Removed the following groups:" << std::endl;
std::for_each(BestMatches.begin(), BestMatches.end(), [&](const std::vector<int>& v){
std::cout << "[";
std::for_each(v.begin(), v.end(), [](int n){
std::cout << n << " ";
});
std::cout << "]" << std::endl;
});
return 0;
}
This is a fast solution in python also (not the optimal one though):
def sum1(list_):
ord_list = sorted(list_,reverse=True)
all_values = []
i=0
while i < len(ord_list):
max_ = ord_list[i]
a = [max_]
for k in range(i+1,len(ord_list)):
if max_ - ord_list[k] > 0:
a.append(ord_list[k])
max_ = max_ - ord_list[k]
elif max_ - ord_list[k] == 0:
a.append(ord_list[k])
all_values.append(a)
for m in a:
ord_list.remove(m)
break
if k == len(ord_list)-1:
i = i + 1
return ord_list, all_values
Special case of subset sum
1.Sort the array, say descending order
2.A[i] >= A[j] for all i<j<N (SUBSET SUM PROBLEM)
3.For each A[i] find subset in j=i+1..N that adds to A[i]
4.For all elements in A eliminated in step 3 mark them as -1 assuming array is of natural numbers
5.Run 2..4 for the entire scan.
Time complexity nlogn + n^2
Space complexity = n if modification of original array is not allowed.
What do you guys think of this approach?
int min_left_after_sum_removal_aux(const std::multiset<int>& s, int sum) {
int min = std::numeric_limits<int>::max();
for (auto& i = s.rbegin(); i != s.rend(); ++i) {
if (sum - *i > 0) {
std::multiset<int> new_s(s);
new_s.erase(new_s.lower_bound(*i));
min = std::min(min, min_left_after_sum_removal_aux(new_s, sum - *i));
}
else if (sum - *i == 0) {
std::multiset<int> new_s(s);
new_s.erase(new_s.lower_bound(*i));
min = std::min(min, min_left_after_sum_removal(new_s));
}
}
return min;
}
int min_left_after_sum_removal(const std::multiset<int>& s) {
if (s.size() == 0) {
return 0;
}
std::multiset<int> new_s(s);
int sum = *new_s.rbegin();
new_s.erase(new_s.lower_bound(sum));
int v1 = 1 + min_left_after_sum_removal(new_s);
int v2 = min_left_after_sum_removal_aux(new_s, sum);
return std::min(v1, v2);
}
int min_left_after_sum_removal(const std::vector<int>& v) {
std::multiset<int> sorted(v.begin(), v.end());
return min_left_after_sum_removal(sorted);
}
public static void main(String[] args) {
int[] arr = { 48, 20, 1, 3, 4, 6, 9, 24 };
sort(arr, 0, arr.length - 1);
int l = left(arr);
System.out.println(l);
}
public static int left(int[] nums) {
int n = nums.length - 1;
int count = 0;
for (int i = n; i >= 0; i--) {
if(nums[i] > -1){
List<Integer> indexes = new ArrayList<Integer>();
left(nums, nums[i], i-1, indexes, false);
if (indexes.size() > 0) {
nums[i] = -1;
for (Integer ind : indexes) {
nums[ind] = -1;
}
}
}
}
for (int i = 0; i < nums.length; i++) {
if(nums[i] > -1)
count++;
}
return count;
}
public static boolean left(int[] nums, int sum, int p, List<Integer> indexes, boolean found) {
if (sum < 0)
return found;
if (sum == 0)
return true;
if (p < 0)
return found;
if (!found && nums[p] != -1) {
indexes.add(p);
found = left(nums, sum - nums[p], p - 1, indexes, found);
if (!found) {
indexes.remove(new Integer(p));
found = left(nums, sum, p - 1, indexes, found);
}
}else if (!found) {
found = left(nums, sum, p - 1, indexes, found);
}
return found;
}
public static void sort(int[] arr, int l, int h) {
int i = l;
int j = h;
int mid = arr[(h - l) / 2 + l];
while (i <= j) {
while (arr[i] < mid)
i++;
while (arr[j] > mid)
j--;
if (i <= j) {
swap(arr, i, j);
i++;
j--;
}
}
if (l < j)
sort(arr, l, j);
if (i < h)
sort(arr, i, h);
}
public static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
1. I need to find subsets that sum up to an element in the array, that is actually itself an NP complete problem. So I run this problem n times (for each element in the array). But it's worse, because I need the actual subsets which can be many (Teta(n!) .. e.g. assume 0,1,-1,1-1,1,-1,1,-1)
- Chris September 07, 20172. of all this subsets I need to find out what the set of disjoint subsets is that has the most elements.
difficult, any hints, ideas?