Palantir Technology Interview Question for iOS Developers


Country: United States




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

Use the exhaustive force utilities in java.force.utils

- ExhaustiveForcer November 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

very useful reply, I owe you one..

- Anonymous November 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

- codeScriber November 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- fgfsdgs November 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous November 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- alfasin November 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use BFS here

- Miguel Oliveira November 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous November 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kyle March 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- meow March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about the case like this:
a = [0, 0, 0, 0],
target = 0

- Anonymous September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

  }

- diloreto.p October 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- arox October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sets = []
for i in xrange(2 ** len(C)):
  sum = 0
  used = []
  for j in xrange(len(C)):
    if (i >> j) & 1:
      used.push(j)
      sum += C[j]
   if sum == Sum:
     sets.push(used)

- Iterate through all combinations and test them November 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous January 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous January 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Pedro February 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Victor September 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looks more like a dynamic programming to me though, standard bottom-up solution would be way faster than brutal force

- dk September 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

please code completo its erros

- fgfsdgs November 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1
of 1 vote

F*ck off, Troll.

- Anonymous November 14, 2013 | Flag


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