Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
O(n^2) time and O(1) space:
1. sort arrays A and B
2. for each element C[k], do linear search in the sorted arrays:
that is, initialize 2 pointers ia = 0 and ib = n-1 (where n is the size of the array)
increment ia if A[ia] + B[ib] < C[k]
decrement ib if A[ia] + B[ib] > C[k]
awsome man ... :), i did not get the idea of moving farward and back ward with pointers, my mind always going into hashing stuff.
awsome man ... :), i did not get the idea of moving farward and back ward with pointers, my mind always going into hashing stuff.
Your solution (2 pointers/indices) shall work properly only when the two arrays (A && B) are sorted and merged, and I am not sure about your algo - will that work for all cases as required in the original problem statement?
Consider the cases:
A < B
A > B
A and B overlap on the left
A and B overlap on the right
Moreover, this solution changes the original order of the arrays A and B. Another point is whether that algo can find all the valid pairs ?
Ashok is onto something. Take the example:
int a[] = {1,2,3,4};
int b[] = {5,6,7,8};
int c[] = {-4,6,2,9};
Here, the valid combinations are
1,5 => -4
2,6 => -4
3,7 => -4
4,8 => -4
But, implementing the above algorithm does not give all combinations. It will only give one combination.
@Anonymous above: nope my solution finds all combinations.
and in fact you missed one )) see below
since the original problem was to find such triples that:
A[i]-B[j]=C[k] which is equivalent to A[i] = B[j] + C[k], I renamed
the arrays 'a' and 'c'.
// check if a == b + c
void find_sum(int *a, int *b, int *c, int n) {
for(int i = 0; i < n; i++) {
int x = a[i];
int l = 0, r = n - 1;
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;
}
}
printf("brute force check:\n");
for(int i = 0; i < n; i++) {
int x = a[i];
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
if(x == b[j] + c[k]) {
printf("all: %d = %d + %d\n", x, b[j], c[k]);
}
}
}
}
}
int main() {
// A[i]-B[j]=C[k] => A[i] = B[j] + C[k]
int c[] = {1,2,3,4};
int b[] = {5,6,7,8};
int a[] = {-4,6,2,9};
int n = sizeof(a) / sizeof(int);
std::sort(a, a + n);
std::sort(b, b + n);
std::sort(c, c + n);
find_sum(a, b, c, n);
return 1;
}
output:
6 = 5 + 1
9 = 5 + 4
9 = 6 + 3
9 = 7 + 2
9 = 8 + 1
brute force check:
all: 6 = 5 + 1
all: 9 = 5 + 4
all: 9 = 6 + 3
all: 9 = 7 + 2
all: 9 = 8 + 1
@ashot: I do not follow you: if the arrays are sorted and then MERGED, we cannot distinguish btw elements of A and B anymore and hence cannot find the triples
nope, you are right, there are 4 solutions,
just run the algo with:
int c[] = {1,2,3,4};
int b[] = {5,6,7,8};
int a[] = {-4,6,2,9};
1 = 5 + -4
2 = 6 + -4
3 = 7 + -4
4 = 8 + -4
brute force check:
all: 1 = 5 + -4
all: 2 = 6 + -4
all: 3 = 7 + -4
all: 4 = 8 + -4
@anonymous: I believe the below pseudocode answers what I meant and what you could not follow.
// arr - the resulting array after sorting and merging the arrays A and B
// N - the size of the array arr
// s - the start index in the sorted/merged array
// e - the end index in the sorted/merged array
// d - the difference to be found
s = 0;
e = N;
while (s < e){
val = arr[s] - arr[e];
if (val == d)
print the arr[s] and arr[e]
++s;
--e;
else if (val > d)
s++;
else
e--;
}
@anonymous: I believe the below pseudocode answers your question
// arr - the resulting array after sorting and merging the arrays A and B
// N - the size of the array arr
// s - the start index in the sorted/merged array
// e - the end index in the sorted/merged array
// d - the difference to be found
s = 0;
e = N;
while (s < e){
val = arr[s] - arr[e];
if (val == d)
print the arr[s] and arr[e]
++s;
--e;
else if (val > d)
s++;
else
e--;
}
@ashot: your pseudocode is a linear search to find if there are two elements in the sorted array that sum up to 'val'. Still I do not understand how this can help us solve the problem: i.e. even if you find such arr[s] and arr[e] that sum to 'val' you have no idea whether arr[s] and arr[e] belong to DIFFERENT arrays A and B.
In my previous post, there is a complete algorithm (I even integrated a brute force check for your convenience). If you do not believe that it works, please try i out and post counterexamples here
findDiffElements = function (arr1, arr2, diffArr){
arr2.sort();
diffArr.sort();
for (var i = 0; i < arr1.length; i++) {
var idx2 = arr2.length - 1;
var idxDiff = 0;
var arr1Elm = arr1[i];
while (idx2 >= 0 && idxDiff < diffArr.length) {
var sum = arr2[idx2] + diffArr[idxDiff];
if(sum === arr1Elm) {
console.log(arr1Elm + '-' + arr2[idx2] + '=' + diffArr[idxDiff]);
idx2--;
} else if(sum > arr1Elm) {
idx2--;
} else {
idxDiff++;
}
}
}
}
O(n logn) time complexity.
Sort all the three arrays in ascending order. O(n logn)
A[i] - B[j] = C[k] is same as A[i] = B[j] + C[k]
Now, have two pointers ptrb, ptrc initialized to B[0], C[0] and binary search for (*ptrb) + (*ptrc) in A in log n time.
If such value exists print the triplet.
Now, if( B[1] < C[1] ) increment ptrb else increment ptrc.
Again search for (*ptrb) + (*ptrc) in A in log n time.
This continues for 2n iterations. Hence 2n log n
So, overall time complexity is O(n log n)
public class FindMatchClass
{
Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();
public int[] FindMatch(int[] ArrA, int[] ArrB, int[] ArrC)
{
AddValstoDictionary(ArrC);
int subval;
ArrayList arlist = new ArrayList();
try
{
for (int i = 0; i < ArrA.Length; i++)
{
for (int j = 0; j < ArrB.Length; j++)
{
subval = ArrA[i] - ArrB[j];
if (dict.ContainsKey(subval))
{
foreach (int item in dict[subval])
{
arlist.Add((int)i);
arlist.Add((int)j);
arlist.Add((int)item);
}
}
#region oldcode //for (int k = 0; k < ArrC.Length; k++)
//{
// if (subval == ArrC[k])
// {
// Console.WriteLine("Matching sets are {0} And {1} And {2}", i, j, k);
// //retArr[m, 0] = i;
// //retArr[m, 1] = j;
// //retArr[m, 2] = k;
// //m++;
// arlist.Add((int)i);
// arlist.Add((int)j);
// arlist.Add((int)k);
// }
//}
#endregion
}
}
int[] retArr = (int[])arlist.ToArray(typeof(int));
return retArr;
}
catch
{
throw;
}
}
private void AddValstoDictionary(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
if (!dict.ContainsKey(arr[i]))
{
dict.Add(arr[i], new List<int>());
dict[arr[i]].Add(i);
}
else
{
dict[arr[i]].Add(i);
}
}
}
}
Is the first solution posted by Anonymous correct? Will it work in all the situations?
O(n^2) time and O(1) space:
1. sort arrays A and B
2. for each element C[k], do linear search in the sorted arrays:
that is, initialize 2 pointers ia = 0 and ib = n-1 (where n is the size of the array)
increment ia if A[ia] + B[ib] < C[k]
decrement ib if A[ia] + B[ib] > C[k]
- Anonymous on May 21, 2012
A=B+C
sort A, B and C (n lg n)
merge B and C into say BC
take 2 pointers, say first and last on BC.
for every index in A
increment first if BC[first] + BC[last] < A[index] else decrement last (n^2)
if a match found, search BC[first] and BC[last] in B and C,
return if separate values found. (lg n)
1. Calculate all the possible differences of A[i] and B[j]. This is i*j operations.
2. Put all the diffs in a HashTable @HTD
3. Now, walk through the array C and look up its value in @HT. This is k operations since look up in HT is O(1).
And here codepad.org/RtXisXzi you can find the implementation of the algorithm along with the driver program and the output.
Your algo has Time Complexity of O(n^2) and Space Complexity is also of O(n^2). But if you do the reverse, i.e store element idf C in hash table and walk through all possible differences and match against HT, your space complexity reduces to O(n)....
Correct, but consider the situation if we are given the arrays A and B and they are fixed and you are supposed to continuously find all the pairs of elements with the given difference (array C in our case). In that case, the lookup is constant O(1) and you will not need to re-walk all the possible pair of elements of both arrays (A and B). So, this algo is much more better when the efficient lookup is at the question.
here you are assuming things .... what you are saying is correct for the case you are describing .... but given the problem statement ... hashing C would be better.... i can cross argue with your assumption that what about the case were C is of fixed length and A and B are infinite streams of integers.... So its totally depend upon the nature of arrays A, B and C.
Add the elements of Array C as keys in hash map and the values corresponding to each key a linked list of objects containing two variables a, b. In the beginning each a,b is -1.
Calculate the difference of a[i] - b[j] and check if this key is present in the map. if it is present add a node to the linked list of that key where the value of node is i, j
/**
* Time: O(N^2)
* Space: O(N)
*/
private void printAllDif(int[] a, int[] b, int[] c) {
Set<Integer> cSet = new HashSet<>();
for( int value : c ){
cSet.add(value);
}
for( int i =0; i < a.length; i++ ){
for( int j = 0; j < b.length; j++ ){
int dif = a[i] - b[j];
if( cSet.contains(dif) ){
System.out.println( a[i] + " - " + b[j] + " = " + dif );
}
}
}
}
1. Put all the elements of array C in a HashTable - O(n) time and O(n) space
2. Calculate all the possible differences of A[i] and B[j]. and check whether diff is present in HT or not. O(n^2) time and O(1) space
Overall Performance:
Time: O(n^2)
Space: O(n)
What if we quicksort the third array C that will be O(nlogn)
- Arjun May 26, 2012then for each element in A and B use a 2 level nested loop to find all combinations for array A and array B and check the sums using binary search in C. So finding combinations O(n2) and for each combination bianry serach: logn.. so overall:
O(nlogn+n^2(logn))
with no extra space reqd