## Uber Interview Question for Senior Software Development Engineers

Country: United States
Interview Type: Phone Interview

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

1. initialize 3 dimentioanl array to cache the intermediate sums. arr[4][4][4]
2. 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.

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

Could you elaborate a bit more? Beginning with #1 it's not clear which intermediate sums you use to populate arr[4][4][4]

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

What if we sort the third array and then have nested loop on array 1 and array 2 and in each iteration of the inner loop do a binary search on array 3.

For example
Pick 1 from array A
Pick 2 from array B
and since sum is to be 7, check using binary search if 4 is present in the 3rd array.

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

Sort array C
Nested for loop on Array 1 and Array 2
In each iteration of the inner loop.. do a binary search on array C

eg.
Pick 1 from array A
Pick 2 from array B
Try to find 4 in array C using binary search

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

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

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

Put the elements of C in a hashMap.

Do a nested loop for above 2 arrays A and B and lookup the remaining value from the Hashmap of C.
Complexity: O(n2)

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

int main(){
int a[] = {1,2,3,3};
int b[] = {2,3,3,4};
int c[] = {1,2,2,2}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
n = a[i] + b[j] + c[k]
if(n == 7){
printf("[%d,%d,%d]",a[i],b[j],c[k])
}
}
}
}
}

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

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

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([])

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

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

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

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.

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

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:
print res

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

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:
print res

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

This is a fairly simple question.

std::set s1{1, 2, 3, 3}
std::set s2{2, 3, 3, 4}
std::set s3{1, 2, 2, 2}

for (auto & e_1: s1)
for (auto & e_2: s2)
if (s3.count(target - (e_1 + s2))) {
cout << e_1 << ", " << e_2 << ", " << target _ (e_1 + e_2) << endl;
}

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.

### 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.