Palantir Technology Interview Question
iOS DevelopersCountry: United States
1. what's exactly is the question ? i see for example {5} is not a subset so i can understand a number on it's own doesn't count ?
2. can the list contain 0 ? negative numbers ?
3. brute force ? that's the demand ?
the list can not contain negative or 0
I want one given set of integer numbers, and given an integer, calculate much all subsets that are part of conjunto.usando and exhaustive research and shows the total number of combinations
void ExhaustiveSearchSubsetSum::TryRun(){
std::vector<int> numbers = { 1, 2, 2, 3, 4 };
printSubsetsOfSum(5, numbers);
}
void ExhaustiveSearchSubsetSum::printSubsetsOfSum(int sum, const std::vector<int>& numbers){
std::vector<int> emptySet;
recursivePrintSubsetsOfSum(sum, numbers, 0, 0, emptySet);
}
void ExhaustiveSearchSubsetSum::recursivePrintSubsetsOfSum(const unsigned int& targetSum,
const std::vector<int>& numbers,
unsigned int currIndex,
unsigned int currSum,
std::vector<int> currSet){
if (currSum == targetSum){
for each (auto var in currSet)
std::cout << var <<",";
std::cout << std::endl;
}
else if (currIndex >= numbers.size() || currSum > targetSum)
return;
else{
recursivePrintSubsetsOfSum(targetSum, numbers, currIndex + 1, currSum, currSet);
currSet.push_back(numbers[currIndex]);
recursivePrintSubsetsOfSum(targetSum, numbers, currIndex + 1, currSum + numbers[currIndex], currSet);
}
}
C++ code, you can convert it to Java. It does not handle duplicates.
Recursive solution in Java:
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
/**
* User: alfasin
* Date: 11/9/13
*/
public class Palantier {
// main method: calls recursively to the algorithm to begin running starting in every i in arr
private static Set<LinkedList<Integer>> sumToN(int[] arr, int n){
Set<LinkedList<Integer>> res = new HashSet<LinkedList<Integer>>();
for (int i=0; i<arr.length; i++){
Set<LinkedList<Integer>> subResult = new HashSet<LinkedList<Integer>>();
subResult = calcFrom(arr, i, n, subResult);
res.addAll(subResult);
}
return res;
}
// add elements starting from i until we reach n - sum the results into res
private static Set<LinkedList<Integer>> calcFrom(int[] arr, int i, int n, Set<LinkedList<Integer>> res) {
// base conditions: stop if we finished going over the array or if n was reached
if(i == arr.length || n == 0){
return res;
}
// base condition II: if element i equals n - add it
else if(arr[i] == n){
LinkedList<Integer> curr = new LinkedList<Integer>();
curr.add(n);
res.add(curr);
}
else if(arr[i] <= n){
//build solution that includes arr[i]
Set<LinkedList<Integer>> tmp = new HashSet<LinkedList<Integer>>();
tmp = calcFrom(arr, i+1, n-arr[i], tmp);
for(LinkedList<Integer> sub : tmp){
sub.add(arr[i]);
}
res.addAll(tmp);
}
//build solution that doesn't includes arr[i]
res = calcFrom(arr, i+1, n, res);
return res;
}
public static void main(String[] args) {
int[] arr = {1,2,2,3,4,5};
Set<LinkedList<Integer>> res = sumToN(arr, 5);
for(LinkedList<Integer> solution : res){
for(Integer i : solution){
System.out.print(i + " ");
}
System.out.println();
}
}
}
OUTPUT:
4 1
5
3 2
2 2 1
I think the question is:
Having a sorted array "a" of ints, and a number "N", find all subsets of "a" that sum to "N".
If this is it, here is my solution using recursion:
public class FindSubsetsThatSumToN {
public static List<List<Integer>> findSubsetsThatSumToN(int[] arr, int n){
List<List<Integer>> result = new LinkedList<List<Integer>>();
for(int i = 0; i < arr.length; i++){
for(List<Integer> l : findSubsetsThatSumToN(arr, i, n))
result.add(l);
}
return result;
}
public static List<List<Integer>> findSubsetsThatSumToN(int[] arr, int begin, int n){
List<List<Integer>> result = new LinkedList<List<Integer>>();
if(n < arr[begin]) return result;
if(arr[begin] == n){
List<Integer> oneElement = new LinkedList<Integer>();
oneElement.add(arr[begin]);
result.add(oneElement);
return result;
}
else{
for(int i = 0; i< arr.length; i++){
List<List<Integer>> childSubsets = findSubsetsThatSumToN(arr, i, n - arr[begin]);
for(List l : childSubsets){
if(!l.isEmpty()){
l.add(arr[begin]);
result.add(l);
}
}
}
return result;
}
}
}
public static void findAll(int [] array, int sum){
int count = 0;
int start = 0;
StringBuilder sb = new StringBuilder();
doFind(count ,sum, array,sb, start);
}
private static void doFind(int count , int sum, int [] array, StringBuilder sb, int start){
if (count == sum){
System.out.println(sb.toString());
}else{
for (int i =start ;i<array.length; ++i){
if (count < sum){
count +=array[i];
sb.append(new Integer(array[i]));
doFind(count , sum, array, sb,++start);
//restore to the original value before next run
count-=array[i];
sb.setLength(sb.length()-1);
}
}
}
}
Here are a few things you can do to optimize your code:
public void printCombos(int sum, int curCount, ArrayList<Integer> array, int startPos, StringBuilder combo) {
if (sum == curCount) {
System.out.println(combo.toString());
return;
}
if (curCount > sum)
return;
for (int i = startPos; i < array.length(); i++) {
if (curCount + array[i] <= sum) {
curCount += array[i];
combo.append(array[i]);
printCombos(sum, curCount, array, i + 1, combo);
curCount -= array[i];
combo.setLength(combo.length() - 1)
}
else
break;
}
}
this is just a backtracking solution
public static ArrayList<ArrayList<Integer>> sumSubset(int[] a, int start, int target,
ArrayList<ArrayList<Integer>> result, ArrayList<Integer> cur){
if(target==0){
result.add(new ArrayList<Integer>(cur));
}
else if(target>0){
int i = start;
while(i<a.length && a[i]<=target){
if(i==0 || i==start || a[i]!=a[i-1]){
cur.add(a[i]);
sumSubset(a, i+1, target-a[i], result, cur);
cur.remove(cur.size()-1);
}
i++;
}
}
return result;
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
int[] a = new int[]{1,2,2,3,4,5};
res = sumSubset(a,0,5,res, new ArrayList<Integer>());
}
Solution with immutable list.
This solution can be improved removing the usage of foldLeft (because each foldLeft costs O(n) so a valueAccumulator will simply solve the problem.
def subsets(elements: List[Int]): List[List[Int]] = {
def subsetsBranch(c: List[Int], acc: List[Int]): List[List[Int]] = (c, acc) match {
case (Nil, a) => if (a.foldLeft(0)(_ + _) == 5) a :: Nil else Nil
case (_, Nil) => Nil
case (h :: t, _) if (acc.foldLeft(h)(_ + _) == 5) => (h :: acc) :: subsetsBranch(c.tail, acc)
case (h :: t, _) if (acc.foldLeft(h)(_ + _) < 5) => subsetsBranch(t, h :: acc)
case (h :: t, _) if (acc.foldLeft(h)(_ + _) > 5) => subsetsBranch(c.tail, acc.tail) // > 5
}
elements match {
case Nil => Nil
case h :: t => subsetsBranch(t, List(h)) ++ subsets(t)
}
}
Simple recursive solution in Python:
def sumSubsets(lst, num):
if num == 0 and lst == []:
return [[]]
if num == 0:
return [[]]
if lst == [] or num < 0:
return []
first = lst[0]
rest = lst[1:]
restSetsFirst = sumSubsets(rest, num - first)
restSets = sumSubsets(rest, num)
if restSetsFirst != None:
for elem in restSetsFirst:
restSets.append(elem + [first])
return restSets
I'm sure the same logic can be used for a Java program using some dynamic data structure like ArrayList.
import java.util.ArrayList;
public class Sum {
public static void main(String[] args) {
int sum = 5;
int array[] = {1,2,2,3,5};
findSubsets(array,sum,0);
}
private static void findSubsets(int[] array, int sum, int j) {
int temp = 0;
ArrayList arrayList = new ArrayList<Integer>();
for(int i = j; i<array.length;i++){
temp = temp + array[i];
arrayList.add(array[i]);
if(temp > sum){
arrayList = new ArrayList<Integer>();
break;
}
if(temp == sum){
break;
}
}
if(arrayList.size() != 0){
System.out.print("{ ");
for(int i = 0; i<arrayList.size();i++){
System.out.print(arrayList.get(i) + " ");
}
System.out.print("}");
System.out.println();
}
if(j+1 < array.length){
findSubsets(array,sum,j+1);
}
}
}
def subsetSum(l, target, start = 0, sol = []):
if target == 0:
return [sol]
if start == len(l):
return []
if start > 0 and l[start] == l[start - 1] and (not sol or sol[-1] != l[start]):
return subsetSum(l, target, start + 1, sol)
subsWith = subsetSum(l, target - l[start], start + 1, sol + [l[start]])
subsWithout = subsetSum(l, target, start + 1, sol)
return subsWith + subsWithout
def subsetSum(l, target, start = 0, sol = []):
if target == 0:
return [sol]
if start == len(l):
return []
if start > 0 and l[start] == l[start - 1] and (not sol or sol[-1] != l[start]):
return subsetSum(l, target, start + 1, sol)
subsWith = subsetSum(l, target - l[start], start + 1, sol + [l[start]])
subsWithout = subsetSum(l, target, start + 1, sol)
return subsWith + subsWithout
I know it's supposed to be Java, but here's a simple Python solution:
def subsum(C, sum):
subsets = []
for i in xrange(len(C)):
if C[i] == sum:
subsets.append([C[i]])
elif C[i] > sum:
return subsets
else:
if (i + 1 == len(C)):
return subsets
subsubsets = subsum(C[i+1:len(C)], sum - C[i])
for s in subsubsets:
subsets.append([C[i]] + s)
return subsets
#include <bits/stdc++.h>
using namespace std;
int c[] = {1, 2, 2, 3, 4, 5};
int n = sizeof(c) / sizeof(int);
set< vector <int> > solutions;
ostream& operator<< (ostream& os, const vector<int> v)
{
os << "{";
for (int i = 0; i < v.size() - 1; i++)
os << v[i] << ", ";
os << v[v.size() - 1] << "}";
return os;
}
void find_sol(int sum, vector<int> accum, int curr)
{
if (sum < 0)
return;
if (curr == n && sum != 0)
return;
if (sum == 0)
{
solutions.insert(accum);
return;
}
vector<int> new_accum = accum;
new_accum.push_back(c[curr]);
find_sol(sum - c[curr], new_accum, curr + 1);
find_sol(sum, accum, curr + 1);
return ;
}
int main()
{
ios_base::sync_with_stdio(false);
int sum(5);
find_sol(sum, vector<int> (), 0);
for (auto &solution : solutions)
cout << solution << endl;
return 0;
}
Use the exhaustive force utilities in java.force.utils
- ExhaustiveForcer November 09, 2013