Uber Interview Question
Senior Software Development EngineersCountry: 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.