## Salesforce Interview Question

Software Engineers**Country:**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;
}
```

What are the assumptions ??

- Hari February 10, 2020Can there be negative integers ??