Salesforce Interview Question
Software EngineersCountry: United States
Doing brute force with memorization
Tuple<List<int>, List<int>> divideWithMinimunDifference(List<int> a) {
var min = divide(a, a1, a2, 0, 0, new Dictionary<string, Tuple<int, List<int>, List<int>>())
return new Tuple<List<int>, List<int>>(min.value1, min.value2);
}
Tuple<int, List<int>, List<int>> divide(a, a1, a2, sum1, sum2, Dict<string, Tuple<int, List<int>, List<int>> memo) {
if(a.length == 0)
return new Tuple<int, List<int>, List<int>(Math.abs(sum1-sum2), new List<int>(a1), new List<int>(a2))
string hash = getHash(a, a1, a2)
if(memo.containsKey(hash))
return memo[hash]
int min = new Tuple<int, List<int>, List<int>>(int.MinValue, null, null)
for (int i = 0; i < a.length; i++) {
ai = a[i]
a1.append(ai)
a.removeAt(i)
cand = divide(a, a1, a2, sum1+ai, sum2)
if(min.value1 > cand.value1) {
min = cand
}
for (int j = 0; j < a.length; j++) {
aj = a[j];
a2.append(aj);
sum2 += aj;
a.removeAt(j, ai);
divide(a, a1, a2, sum1 + ai, sum2 + aj);
a.insertAt(j);
if(min.value1 > cand.value1) {
min = cand;
}
}
a.insertAt(i, ai);
for (int j = 0; j < a.length; j++) {
aj = a[j];
a2.append(aj);
sum2 += aj;
a.removeAt(j);
divide(a, a1, a2, sum1, sum2 + aj);
a.insertAt(j);
}
}
memo[hash] = min;
return min;
}
string getHash(List<int> a, List<int> a1, List<int> a2) {
string a_str = string.join(a, ',');
string a1_str = string.join(a1, ',');
string a2_str = string.join(a2, ',');
string hash = string.Format('{0};{1};{2}', a_str, a1_str, a2_str);
return hash;
}
In order for both sums to be as close as possible - each needs to be as close as possible to half of the total sum.
In my approach i first sort the initial set, then go through it from highest to lowest and sum the numbers. If the result of adding a number to the current sum is greater than the half of the total sum - i continue iterating (to the lower numbers) and try to add them
Examples:
{1,2,3,4,90}
s1: 90 (sum 90)
s2: 1,2,3,4 (sum 10)
{1,2,3,14,15,16}
s1: 16,3,2,1 (sum 22)
s2: 15,14 (sum 29)
public static void minSum(List<Integer> set) {
List<Integer> set1 = new ArrayList<>();
List<Integer> set2 = new ArrayList<>();
List<Integer> sortedSet = set.stream().sorted().collect(Collectors.toList());
int totalSum = sortedSet.stream().mapToInt(Integer::valueOf).sum();
int halfSum = totalSum/2;
//put highest element n set1
int maxElement = sortedSet.get(sortedSet.size()-1);
set1.add(maxElement);
int s1Sum = maxElement;
int s2Sum = 0;
for(int i=sortedSet.size()-2; i>=0; i--) {
int curr = sortedSet.get(i);
if(s1Sum <= halfSum && s1Sum + curr <= halfSum) {
set1.add(curr);
s1Sum+=curr;
} else {
set2.add(curr);
s2Sum+=curr;
}
}
System.out.println("S1: sum = " + s1Sum);
System.out.println("S2: sum = " + s2Sum);
}
What are the assumptions ??
- Hari February 10, 2020Can there be negative integers ??