Interview Question
Country: India
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);
}
}
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++){
bcCombos.add(b[i]+c[j]);
}
}
for (int i = 0; i < a.length; i++){
if (bcCombos.contains(k-a[i])) return true;
}
return false;
}
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.
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.
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)
@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.
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.
Doubt there is a known algorithm for NlogN time?
- RecruitingForSandvineCanada August 05, 2015I think this problem can be reduced to 3SUM in both directions, and there is nothing sub quadratic known for 3SUM.