## Amazon Interview Question Software Engineer / Developers

- 0of 0 votes
How to most efficiently find duplicates/commons in two sorted arrays of integers. No extra space should be used. My answer as below

`public class Duplicate { //private HashSet<Integer> duplicates = new HashSet<Integer>(); /** * @param args */ public static void main(String[] args) { int a[] = {0,2,2,4,6,8,8,9,9,10}; int b[] = {0,3,3,4,8,8,10,12}; new Duplicate().mergeAndCheck(a, b); } private void mergeAndCheck(int[] arr1, int[] arr2){ int len1 = arr1.length; int len2 = arr2.length; int pointArr1 = 0; int pointArr2 = 0; while((pointArr1<len1)&&(pointArr2<len2)){ if(arr1[pointArr1]<=arr2[pointArr2]){ if((arr1[pointArr1]==arr2[pointArr2])){ if(pointArr1==0){ System.out.print(" "+arr1[pointArr1]); }else if(arr1[pointArr1]!=arr1[pointArr1-1]){ System.out.print(" "+arr1[pointArr1]); } //duplicates.add(arr1[pointArr1]); } pointArr1++; }else{ pointArr2++; } } /*for(Integer iNT:duplicates){ //System.out.print(" "+iNT); }*/ } }`

**Country:**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 on June 23, 2012 Edit | Flag Reply