Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
small correction. the inner loop should be:
for(; ;) {
int s = b[l] + c[r];
if(s == x) {
printf("%d = %d + %d\n", x, b[l], c[r]);
if(l < n - 1 && b[l] == b[l + 1])
l++;
else
r--;
} else if(s < x) {
l++;
} else
r--;
if(l == n || r == -1)
break;
}
to handle duplicates properly
You could have gotten O(N^2) with hashing. You can get O(N^2 log N) by producing a sorted version of the result array and doing binary searches on it (O(N^2) searches, O(log N) each).
@Puru:
There is no need to merge it. Just sort B & C: (Both A & B are in ascending order now).
Now for every a belongs to A, search element say b in B and say c in C whose some is equal to a.
keep in mind that start the search from End of B and C and see if the sum of b & c is greater than a then fall back to element that just smaller element from just previous elements in B & C.
O(n) = nlogn+n*n
a - b = c
So a = b + c
Sort B and C in decreasing order.
Then create a 2-D array D where D[i][j] = B[i] + C[j];
This 2-D array has all the rows in descending order and all cols also in descending order. Now do a zizag search in O(N) time for each value in A in D.
int a[] = {8, 9, 10, 11, 20, 22};
int b[] = {1, 5, 6, 6, 9, 11};
int c[] = {3, 4, 7, 11, 12, 15};
sorted b = 11,9,6,6,5,1 <-- O(nlgn)
sorted c = 15,12,11,7,4,3 <-- O(nlgn)
D = 26,23,22,18,15,14
24,21,20,16,13,12
21,18,17,13,10,09
21,18,17,13,10,09
20,17,16,12,09,08
16,13,12,08,05,04
Now in this 2-D array search each element of A in O(N) time.
solution complexity: o(nlogn) were n is the size of the longest array.
1. sort all 3 arrays.
2. The range of C is [C[1] .. C[n]]
3. have two pointers to the end of A and B.
4. each time subtract pointer to B from pointer to A: if out of C range (from 3) : if less than range reduce pointer to B by 1. if bigger than range than reduce pointer to A by one. if In range of C hash the pair (A,B) according to the result A - B.
5. Go trough all elements of C and search them in the hash. if they exist, print the tuple (A,B,C).
In order to find a pair (a, b) (s.t. a is in A, b is in B) whose sums equals x, we would :
a. Sort A, B (O(nlogn))
b. initialize i, j with
i = A[0]
j = B[n] (Assuming size of all arrays is same, n)
Then:
a. If A[i]+B[j] < x , increment i
b. If A[i]+B[j] > x, dec j
c. If A[i]+B[j] == x, print A[i], B[j]
This takes O(n).
So total time complexity is O(nlogn) and space complexity is O(1)
Now we can easily extend this approach to this qs by :
Sort A,B : O(nlogn)
For each k in C
Find if there exists a pair, (a, b) s.t. a+b = k
Now the complexity of the algo is O(nlogn)+O(n^2) = O(n^2).
a-b = c implies a = b + c
Sort B and C in place O(n log n)
Now merge B and C into D
Define a function Search that searches for indices in D whose sum is a given number.
bool Search (int[] D, int x, out int i, out int j)
{
if ((D == null) || (D.length < 2))
{
return false;
}
i = 0;
j = D.length - 1;
while (i < j)
{
int sum = D[i] + D[j];
if (sum == x)
{
return true;
}
else if (sum < x)
{
i++;
}
else
{
j--;
}
}
return false;
}
For each element of A, if Search returns true, then look for D[i] in C and D[j] in D using binary search and also D[j] in C and D[i] in D also using binary search if first search yields false. If found print the tuple.
The complexity is O(nlogn) for sorting, O(n) for merging. Then for each element of A, it will take O(n) search. Hence O(n^2) in total. Hashing can reduce this to O(nlogn).
@Ashish, I think we need to sort after merge. Other wise it will lost order of b and c array.
The question didn't say a,b,c has to be have same index, which mean it can be any combination. So your merging from B and C to D will take n^2 time, and D array will be size of B*C. I don't think this is appropriate.
The flaw here is that you assume that you can merge B and C and then ask whether the result list has two numbers adding up to a certain sum. But if you do that, both numbers could have originated from B, or from C. Implemented more correctly, your approach would end up being O(N^2) or more.
@Eugene
I know that the numbers can come from the same array that's why I mentioned that we need to search numbers to ensure they come from different sets. That was the last piece of my explanation above.
Sort B and C, it takes O(n logn) and now add B and C and create another array D of size n^2, O(n^2). Apply binary search in that array for each element in A each element:2*log n, O(n logn),So total complexity would be O(n^2).
The order would be O((n^2)*log(n)) not O(n^2). When checking each sum in the A array, one would apply binary search(log(n)) n^2 times.
SumArray(int A[], int B[], int C[], int a, int b, int c){
if ( a== Length(A) || b== Length(B) || c== Length(C) ) return;
if ( A[a] == B[b] + C[c]) print A[a],B[b],C[c];
else{
SumArray(A, B, C, a+1, b, c);
SumArray(A, B, C, a, b+1, c);
SumArray(A, B, C, a, b, c+1);
}
}
// complexity (n^3) - without doing sorting O(1)
// Above algo can be improved to n^2 using memory (n*n)
what if we do not need to merge the sorted arrays ?
that is, sort B and C, then for each element of A check if A[i] == B[j] + C[k]
using standard approach. Complexity: O(n^2)
output:
- Anonymous November 17, 20118 = 1 + 7
8 = 5 + 3
9 = 5 + 4
9 = 6 + 3
9 = 6 + 3
10 = 6 + 4
10 = 6 + 4
20 = 5 + 15
20 = 9 + 11
22 = 11 + 11
brute force check:
all: 8 = 1 + 7
all: 8 = 5 + 3
all: 9 = 5 + 4
all: 9 = 6 + 3
all: 9 = 6 + 3
all: 10 = 6 + 4
all: 10 = 6 + 4
all: 20 = 5 + 15
all: 20 = 9 + 11
all: 22 = 11 + 11