## Uber Interview Question

Senior Software Development Engineers**Country:**United States

**Interview Type:**Phone Interview

class Solution {

List<List<Integer>> threeSum(int[] a, int[] b, int[] c, int target) {

List<List<Integer>> res = new ArrayList<>();

for(int i = 0 ; i < a.length; i++) {

for(int j = 0; j < b.length; j++) {

int subSum = a[i] + b[j];

if(subSum < target) {

if(search(c, target - subSum)) {

res.add(Arrays.asList(a[i], b[j], target-subSum));

}

}

}

}

return res;

}

boolean search(int[] c, int target) {

int left = 0, right = c.length - 1;

while(left <= right) {

int mid = left + (right -left)/2;

if(c[mid] == target)

return true;

else if(c[mid] < target)

left = mid +1;

else

right = mid -1;

}

return false;

}

public static void main(String[] args) {

int[] a = {1, 2, 3};

int[] b = {2, 3, 4};

int[] c = {1, 2, 4};

Solution test = new Solution();

System.out.println(test.threeSum(a, b, c, 7));

}

}

```
A = [1, 2, 3, 3]
B = [2, 3, 3, 4]
C = [1, 2, 2, 2]
target = 7
def construct_candidates(constructed_sofar):
global A,B,C
array = A
if 1 == len(constructed_sofar) :
array = B
elif 2 == len(constructed_sofar) :
array = C
return array
def over(constructed_sofar):
global target
sum = 0
to_stop, reached_target = False, False
for elem in constructed_sofar:
sum += elem
if sum >= target or len(constructed_sofar) >= 3 :
to_stop = True
if sum == target and 3 == len(constructed_sofar):
reached_target = True
return to_stop, reached_target
def backtrack(constructed_sofar):
to_stop, reached_target = over(constructed_sofar)
if to_stop:
if reached_target :
print constructed_sofar
return
candidates = construct_candidates(constructed_sofar)
for candidate in candidates :
constructed_sofar.append(candidate)
backtrack(constructed_sofar[:])
constructed_sofar.pop()
backtrack([])
```

```
/*
A = [1, 2, 3, 3]
B = [2, 3, 3, 4]
C = [1, 2, 2, 2]
target = 7
*/
function getCombinations(a, b, c) {
var size = a.length;
var tuples = [];
for (var i = 0; i < size; i++) {
if (i >= 0 && a[i - 1] === a[i]) {
continue;
}
for (var j = 0; j < size; j++) {
if (j >= 0 && b[j - 1] === b[j]) {
continue;
}
tuples.push([a[i], b[j]]);
}
}
for (var k = 0, kk = tuples.length; k < kk; k++) {
var tuple = tuples[k];
var difference = 7 - tuple[0] - tuple[1];
if (c.indexOf(difference) >= 0) {
tuples[k].push(difference)
} else {
tuples[k] = null;
}
}
return tuples;
}
```

Complexity: O(n(m+p))

1. Sort all the arrays - a,b,c. - This will improve average time complexity.

2. If c[i] < Sum, then look for Sum - c[i] in array a and b. When pair found, insert c[i], a[j] & b[k] into the result list. This can be done in O(n).

3. Keep on doing the above procedure while going through complete c array.

```
import itertools
from functools import partial
A = [1,2,3,3]
B = [2,3,3,4]
C = [1,2,2,2]
S = 7
def check_sum(N, *nums):
if sum(x for x in nums) == N:
return (True, nums)
else:
return (False, nums)
pro = itertools.product(A,B,C)
func = partial(check_sum, S)
sums = list(itertools.starmap(func, pro))
res = set()
for s in sums:
if s[0] == True and s[1] not in res:
res.add(s[1])
print res
```

```
import itertools
from functools import partial
A = [1,2,3,3]
B = [2,3,3,4]
C = [1,2,2,2]
S = 7
def check_sum(N, *nums):
if sum(x for x in nums) == N:
return (True, nums)
else:
return (False, nums)
pro = itertools.product(A,B,C)
func = partial(check_sum, S)
sums = list(itertools.starmap(func, pro))
res = set()
for s in sums:
if s[0] == True and s[1] not in res:
res.add(s[1])
print res
```

1. initialize 3 dimentioanl array to cache the intermediate sums. arr[4][4][4]

- jugaad April 28, 20162. start 2 nested loops and traverse through first 2 arrays, populate arr[4][4][0].

3. start 1 loop to calculate all other 2 dimensional planes. keep track of the sum for which matches the asked sum.

4. solution is done in n^2, which otherwise would have taken n^3 as brute force approach.