Google Interview Question Software Engineer / Developers
Country: United States
I think using binary search is O( min(a.length, b.length) + max(log(a.length), log(b.length)). It's better than O(a.length + b.length) if, say, b.length >> a.length
"I think using binary search is O( min(a.length, b.length) + max(log(a.length), log(b.length))."
Except it's O( min(a.length, b.length) * max(log(a.length), log(b.length)).
We can use binary search for this, inorder to achieve O(log (M+N)). Refer below code
package com.sunpria;
public class FindSumInSortedArray {
public static void main(String[] args) {
int [] a= {1,2,3,5,6,8};
int [] b= {1,2,7,8,9};
findSum(11,a,b,0,5,0,4);
}
public static boolean findSum(int sum, int[] a, int[] b, int l1, int r1, int l2, int r2)
{
int mid1 = (l1+r1)/2;
int mid2 = (l2+r2)/2;
if((l1<0) || (l2<0) || (l1>r1) || (l2>r2))
return false;
int trySum = a[mid1]+b[mid2];
if (trySum==sum) {
System.out.println("Found sum at "+mid1+","+mid2+", Sum ="+a[mid1]+"+"+b[mid2]+"="+sum);
return true;
}
if ((trySum<sum) && (l1!=r1) && (l2!=r2)) {
return (findSum(sum, a, b, mid1+1, r1, l2, r2) ||
findSum(sum, a, b, l1, r1, mid2+1, r2));
}
if ((trySum>sum) && (l1!=r1) && (l2!=r2))
return (findSum(sum, a, b, l1, mid1-1, l2, r2) ||
findSum(sum, a, b, l1, r1, l2, mid2-1));
return false;
}
}
This doesn't look like O(lg(m+n)) at all. For simplicity sake assume m=n, and mark the size of the input 2n=N. According to the code the recursive function is
T(N) = 2*T((3/4)*N) + O(1)
T(0) = O(1)
Which is actually O(n^(lg(2) in base (4/3)) = O(n^(2.4094)) which is far worst than linear.
Let x be the value to which pair of elements sums up to.
Algorithm: Assume that a has a smaller size than b. Now, iterate over a. For each element e in a, do a binary search for (x-e) in b.
This algorithm will run in O(a.length * log(b.length)). This runtime will be less than O(a.length + b.length) when b.length >> a.length.
I think more correct estimation of this algoritm is O(a.length + a.length*log(b.length)). Isn't it?
Is it possible to get O(a.length + b. length) algorithm? GZ_Penny can you clarify whether it was not O(a.length*b. length).. I think the best is using Binary search on the longer array while considering each value in the smaller array could be the best run time as mentioned above by others..
Start at pointer i at beginning of a and pointer j at end of b, then:
while i < a.length || j >= 0
If a[i] + b[j] == k then return (i, j)
If a[i] + b[j] < k then i := i + 1
else j := j - 1
My bad, trying it again.
while i < a.length && j >= 0:
If a[i] + b[j] == k then return (i, j)
If a[i] + b[j] < k then i := i + 1
else j := j - 1
1. initialize idxA = 0, representing index in a[]
2. Do binary search for possible pair in b[0]. have a idxB record the resulting position
3. At this point idxB points to closest possible value (or equal) to the desired sum.
4. do linear search through a[] & b[], follow the rule:
if (a[idxA] + b[idxB] > x) idxB--
else if (a[idxA] + b[idxb] < x) idxA++
else found.
This should have worst case O(a.len+b.len) but slightly better in average case.
It is obvious to use each value, say n, in shorter list to conduct binary search in longer list for value sum - n. The trick is that after first search, any following search can be restricted to range of (0, p) of the longer list, where p, returned by the previous search, is the index in the longer list, and whose value + n > sum. Here is Java implementation:
public class SearchPairsFromTwoLists {
public static void findPairOfSum(int[] a, int[] b, int sum) {
if (a == null || b == null || a.length == 0 || b.length == 0) {
return;
}
if (a.length > b.length) {
int[] temp = a;
a = b;
b = temp;
}
int to = b.length;
for (int n : a) {
int temp = Arrays.binarySearch(b, 0, to, sum - n);
if (temp > 0) {
System.out.printf("%d = %d + %d\n", sum, n, b[temp]);
return;
}
to = Math.abs(temp);
}
System.out.println("No found.");
}
public static void main(String[] args) {
int[] a = { 2, 4, 7, 11, 16, 19, 20, 21, 21, 22, 27, 28, 29, 30, 30,
31, 35, 36, 39, 43, 43, 57, 58, 62, 65, 67, 71, 71, 71, 77, 85,
87, 87, 94, 95, 95, 96, 96, 98, 99 };
int[] b = { 10, 29, 30, 30, 33, 35, 37, 42, 44, 46, 49, 67, 69, 70, 71,
84, 88, 92, 94, 98 };
int sum = 78;
findPairOfSum(a, b, sum);
}
}
Micheal J Keating, did you count the fact that the for loop only need to loop min(a, log(b)) times, where a < b?
Let's assume a < b (if not swapping them), and m = min(a, log(b)), then it's
O(m*(log(b)-(m-1)/2)) =
If a and b are within the same order of magnitude in size, then O(a.length * log(b.length)) is not an improvement over O(a.length + b.length). But if you know that a << b, then yeah, this is probably better. For instance, a.length = 5, b.length=32, a.length+b.length = 37, and a.length * log(b.length) = 25. But suppose both are 32. Then a.length+b.length = 64, but a.length * log(b.length) = 160. Like a lot of optimizations on this problem, it comes down to knowing something about your data. In this case, a quick test could tell you if this is likely to speed up your running time.
Michael J Keating, if a function's running time is in the order of a.len + a.len * log(b.len), in big-Oh notation, we typically just call it O(a.len * log(b.len)). Since we're considering only the asymptotic running times, the linear term in a.len becomes negligible for higher values of a.len and b.len.
The approach i would prefer is:
1) First choose the smaller array from the two. Get lengths, compare.
2) for each number in the chosen array, compute the diff of required sum, perform binary search on the second array. if found, preserve the pair and continue.
worst case would be A and B of equal size. assuming N
then complexity would be O(NlogN)
Correct me if i am wrong!
Take the smaller of the two arrays. Do a binary search to find whether there exists an element in the longer array s.t. a[0]+b[x] = N. That search just takes log(b) time. Now, walk backwards along the longer array from that point, looking for elements that satisfy a[i] + b[j] = N. Each time you either find an element s.t. a[i] + b[j] <= N move forward once in a and re-test. Continue going forward in a until a[i] + b[j] >= N. Then resume going backward through b.
I think that's the optimal algorithm, but yeah, it's going to run in O(a+b). I mean, you could get cute about it and if you know N is odd, you could only test a[i] with b[j] when one is odd and the other is even, or if N is even, only test a[i] and b[j] when both are odd or both are even. Testing for evenness means only looking at the least order bit, which might be faster than actually adding two numbers, especially if they're very large. But in the worst case, all pairs between a and b are potentially valid by this test, and all you've done is add a small piece of work to every step. So, perhaps there are optimizations possible depending on what you know about your data, but for the general case, I think O(a+b) is as good as you're liable to get.
public class SortedListPairSum {
/*
* Finding a pair of elements from two sorted lists(or array) for which the sum of the elements is a certain value.
* Anyway solution that can do better than O(a.length + b.length)?
*/
static int[] a = { 2, 4, 7, 11, 16, 19, 20, 21, 21, 22, 27, 28, 29, 30, 30,
31, 35, 36, 39, 43, 43, 57, 58, 62, 65, 67, 71, 71, 71, 77, 85,
87, 87, 94, 95, 95, 96, 96, 98, 99 };
static int[] b = { 10, 29, 30, 30, 33, 35, 37, 42, 44, 46, 49, 67, 69, 70, 71,
84, 88, 92, 94, 98 };
static int sum = 78;
public void find(int sum, int startA, int endA, int startB, int endB){
int midA = (startA + endA) / 2;
int midB = (startB + endB) / 2;
System.out.println("came here midA " + midA + " val: " + a[midA] +" midB: " + midB + " val:" + b[midB]);
if(a[midA] + b[midB] == sum){
System.out.println("found the pair:");
return;
}
if(midA <= 0 || midB <= 0){
System.out.println("Pair not found!!");
return;
}
if(a[midA] < b[midB]){
if(a[midA] + b[midB] < sum){
while(a[midA] + b[midB] < sum){
++midA;
}
startA = midA;
}
else{
while(a[midA] + b[midB] > sum){
--midB;
}
endB = midB;
}
find(sum, startA, endA, startB, endB);
}
else{
if(a[midA] + b[midB] < sum){
while(a[midA] + b[midB] < sum){
++midB;
}
startB = midB;
}
else{
while(a[midA] + b[midB] > sum){
--midA;
}
endA = midA;
}
find(sum, startA, endA, startB, endB);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
new SortedListPairSum().find(sum, 0, a.length, 0, b.length);
}
}
Clearly you cannot beat O(lengths).
while(1) {
sum_heads=a[i]+b[j];
if( sum_heads > sum) break; // not found
if ( sum_heads == sum) println( whatever ), break; // found
if ( sum_heads < sum ) {
if(i==a.length-1 && j==b.length-1) break;
else if(i==a.length-1) j++;
else if(j==b.length-1)i++;
else if( a[i+1] < b[j+1] ) i++;
else j++;
}
} /* ends while */
Given two arrays A and B such that either their length is same or one of them is longer. Let say if A is longer then,
- Delta March 10, 2014indexA = 0; indexB = B.length -1;
initialize sum = B[indexB] + A[indexA].
while(indexA < A.length && indexB >= 0)
{
if( sum == target )
done
else if( sum > target )
indexB--;
else
indexA++;
}
Time complexity - We can think of above traversal as diagonal traversal that we do in sorted matrix to find a element, which will have complexity O(A.length + B.length ).
We can improvise above logic, by doing binary search on the hypothetical diagonal (0,0) to (A.length, B.length ) and follow the same logic for searching the element in a sorted matrix.