Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
The logic -- find out smaller array.. for each element in smaller array lookup in larger array using binary search. so complexity will be O(nlgn)
Here is the working code--
public class findCommon {
/**
* @param args
*/
static int a1[] = {1,2,3,4,5,6};
static int a2[] = {2,3,4,5,6,7,8,9,10,11,15};
public static void main(String[] args) {
// larger one should be binary searched.
// add logic based on array length to iterate over smaller array and
// binary search larger array.
boolean found =false;
int i;
//complexity - O(nlgn)
for(i=0;i<a1.length;i++){
found = binarySearch(a1[i]);
if(found){
System.out.println(a1[i]);
found = false;
}
}
}
public static Boolean binarySearch(int num){
int start = 0;
int end = a2.length - 1;
int mid = start + end / 2;
//System.out.println(mid);
boolean found = false;
//binary search condition - Search continues till
// element not found AND start index < end index (means only on element left)
while(!found && start < end){
if(num == a2[mid])
found = true;
else
if(num < a2[mid]){
end = mid-1;
mid = (start + end) / 2;
}
else{
start = mid + 1;
mid = (start + end) / 2;
}
}
//compares the last element remaining. (condition useful for boundary elements)
if(num == a2[mid]){
found = true;
}
if(found){
//System.out.println("found at "+mid);
}
else{
//System.out.println("not found");
}
return found;
}
}
This approach is only taking advantage of the fact that one of the two arrays is sorted (the array you're binary searching). The other array could be unsorted and this algo would still work. However, it's possible to take advantage of the fact that both arrays are sorted to produce an O(n) algo. This is the merge algorithm used as part of mergesort.
O(n)
static void commonNum(int* arr1, int* arr2, int n, int m)
{
int i, j;
i = 0;
j = 0;
while (i < n && j < m)
{
if (arr1[i] == arr2[j])
{
cout << arr1[i] << ' ';
for (++i; i < n; i++)
{
if (arr2[j] < arr1[i])
{
break;
}
}
}
else if (arr1[i] < arr2[j])
{
for (++i; i < n; i++)
{
if (arr2[j] <= arr1[i])
{
break;
}
}
}
else if (arr1[i] > arr2[j])
{
for (++j; j < m; j++)
{
if (arr2[j] >= arr1[i])
{
break;
}
}
}
}
cout << endl;
}
Agreed.. O(n)
- nil_dream June 23, 2012