Amazon Interview Question
Research ScientistsCountry: United States
Interview Type: Phone Interview
if arrays are sorted then it is simple ...
1) keep two pointer i and j for both arrays...
2)if a[i]==a[j].
{
. if(no. don't printed already)
print a[i];
i++;j++;
}
else if(a[i]<a[j]) i++;
else if(a[i]>a[j]) j++;
the problem is a little abstract, you should confirm with the inteviewer further,maybe he/she is waiting for you. :)
1. is the array sorted? then we can solve it in O(M+N) complexity and O(1) space.
2. is the array number in certain arrange? for example, between 1-100, then we can use counting sort, with O(M+N) complexity and O(1) space.
3. if we count the same common element only once or actually occurence.
4. if all of these are not guaranteed, then maybe hashmap is possibly the best one.
import java.util.HashSet;
public class Duplicatesin2Arrays {
public static void main(String[] args) {
int[] array1 ={1,2,3,4,5};
int[] array2 ={3,4,5,6,7};
HashSet hs = new HashSet();
int i;
for(i=0;i<array1.length;i++)
{
hs.add(array1[i]);
}
int j=0;
for(i=0;i<array2.length;i++)
{
if(!hs.add(array2[i]))
{
j++;
System.out.println(array2[i]);
}
}
System.out.println("The number of duplicates present is "+j);
}
}
This solution is O(n + m) complexity and O(n) memory.
You get only one occurrence of distinguishable item in result collection. If you need to find all items - change answer HashSet to List.
Does anybody know the linear solution without additional memory (or O(log n) memory)?
- krylloff December 14, 2013