## Interview Question

• 0

Country: India

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

Doubt there is a known algorithm for NlogN time?

I think this problem can be reduced to 3SUM in both directions, and there is nothing sub quadratic known for 3SUM.

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

You're right, the best solution for 3-SUM would be O(n*n).

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

You can store the values of the first array in a HashMap, recursively break down the second array and for each element in the second array, search linearly in the third array.

a = k - b - c

Check if a exists in the HashMap.

``````import java.util.*;

public class SumOfThree {

static boolean isSumInC(int val, int[] c, int k, HashMap<Integer, Integer> hash){
for(int i=0;i<c.length;i++)
{int rem = k - val - c[i];
if(hash.containsValue(rem))
return true;
}

return false;

}

static boolean divideb(int[] b, int st, int end, int[] c, int k, HashMap<Integer, Integer> hash){
if(st==end)
return isSumInC(b[st], c, k, hash);
else{
int mid = (st+end)/2;
return divideb(b, st, mid, c, k, hash) || divideb(b, mid+1, end, c, k, hash);
}

}

static boolean isSumOfThree(int[] a, int[] b, int[] c, int k){
HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();

for(int i=0;i<a.length;i++)
hash.put(i,  a[i]);

return divideb(b, 0, b.length-1, c, k, hash);

}

public static void main(String args[]){
int[] a = {30, 20, 5, 10};
int[] b = {5, 12, 18, 20};
int[] c = {7, 10, 12, 20};

int k = 27;

boolean result = isSumOfThree(a, b, c, k);
System.out.println(result);

}
}``````

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

The good ole slow O(n*n) time solution.

``````public static boolean abcSum(int a[], int b[], int c[], int k){
HashSet<Integer> bcCombos = new HashSet<Integer>();
for (int i = 0; i < b.length; i++){
for (int j = 0; j < c.length; j++){
}
}
for (int i = 0; i < a.length; i++){
if (bcCombos.contains(k-a[i])) return true;
}
return false;
}``````

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

1 Firat Sort all the strings then
2.1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
2.2) Else If x < y, we can move ahead in ar1[] as x cannot be a common element 3) Else If y < z, we can move ahead in ar2[] as y cannot be a common element 4) Else (We reach here when x > y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

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

1 First Sort the arrays.
2.1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
2.2) Else If x < y, we can move ahead in ar1[] as x cannot be a common element 3) Else If y < z, we can move ahead in ar2[] as y cannot be a common element 4) Else (We reach here when x > y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Sort all three arrays, then sequentially scan them to find the triplet. In the second phase, you have a pointer to each of the 3 arrays, call it i1, i2, i3 for A, B, C. If A[i1]+B[i2]+C[i3]==k return true. Otherwise, move the index to the next smallest element and so on.
Cost of sorting: O(N*log(N)), cost of second phase is O(N)

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

@lyad: Dude why don't you write the program for this. I think this is more tough than you think to be finished with n*log(n) complexity.

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

Why this doesn't work:

A = {10,15,20,25}
B = {3,6}
C = {1,5}
K = 27

Based on your algorithm, we would start at i1=0, i2=0, i3=0. So the current sum is 10 + 3 + 1 = 14
Next lowest element is 5 so i3++. Now our sum is 18.
Next lowest element is 6 so i2++. Now our sum is 21.
Next lowest element is 15 so i1++. Now our sum is 26.
Next lowest element is 20 so i1++. Now our sum is 31.
..

We skipped our value and will not return to it using your algorithm. We will return false when the actual return value should be true. We can get 27 by adding 20 + 6 + 1.

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.