## Amazon Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

I would use a hash table and add numbers of both arrays to the hash table keeping count of the occurrences. If count is more than 1, we add that element it to the intersection array. This gives O(m+n) efficiency.

Those two arrays are not necessary unique. Your implementation will take any integers appear two or more time in the same array, but not in the other array. That output isn't correct.

Here is my solution. Please let me if it fails to for any scenario.

public class IntersectionOfArrays {

public static void main(String[] args) {

int[] A = {3,6,1,13,4,3,8,9,1,5,2};

int[] B = {13,4,1,3,9,17,12,25,6};

ArrayList<Integer> c = findIntersection(A,B); //O(m+n)

for(Integer i : c){

System.out.println(i +",");

}

}

public static ArrayList<Integer> findIntersection(int[] A, int[] B){

ArrayList<Integer> intersection = new ArrayList<Integer>();

// Add A into hashMap

HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();

for(int i : A){ // O(m)

if(map.containsKey(i))

{

int tmp = map.get(i);

map.remove(i);

map.put(i, tmp+1);

}else{

map.put(i, 1);

}

}

// Now start compare with B array

for(int i : B){ // O(n)

if(map.containsKey(i)){

intersection.add(i);

if(map.get(i) == 1)

{

map.remove(i);

}else{

int tmp = map.get(i);

map.remove(i);

map.put(i, tmp - 1);

}

}

}

return intersection;

}

}

```
private static void findInterSection(int a[], int[] b){
HashSet<Integer> checkDups=new HashSet<Integer>();
HashSet<Integer> dups=new HashSet<Integer>();
for(int i=0;i<a.length;i++)
checkDups.add(a[i]);
for(int i=0;i<b.length;i++){
if(!checkDups.add(b[i]))
dups.add(b[i]);
else
checkDups.remove(b[i]);
}
for(Integer abc:dups)
System.out.println(abc);
}
```

I think the best way to do this is to use the sets

public static void setFunction(List<Integer> firstList,List<Integer> secondList)

{

Set<Integer> firstSet=new HashSet<Integer>();

Set<Integer> resultSet=new HashSet<Integer>();

for(int i:firstList)

{

firstSet.add(i);

}

for(int i:secondList)

{

if(!firstSet.add(i))

{

resultSet.add(i);

}

}

for(int i:resultSet)

{

System.out.println(i);

}

}

```
def intersect(arr: Array[Int], a1: Array[Int], a2: Array[Int], i: Int): Array[Int] = a1 match {
case Array() => arr
case Array(x, a@_*) if(a2.indexOf(x) < 0) => arr(i) = 0;intersect(arr, a.toArray, a2, i+1)
case Array(x, a@_*) => intersect(arr, a.toArray, a2, i+1)
}
val arr = Array(1,2,3,4,5,6)
scala> val r = intersect(arr ,arr, Array(2,3,4,6,7,8,9,12,34), 0).filterNot(e => e == 0)
r: Array[Int] = Array(2, 3, 4, 6)
```

Here is a solution provided the arrays are sorted:

vector<int> findIntersection(vector<int> A, vector<int> B) {

vector<int> intersection;

int n1 = A.size();

int n2 = B.size();

int i = 0, j = 0;

while (i < n1 && j < n2) {

if (A[i] > B[j]) {

j++;

} else if (B[j] > A[i]) {

i++;

} else {

intersection.push_back(A[i]);

i++;

j++;

}

}

return intersection;

}

```
private static void intersection(int[] a, int[] b) {
List<Integer> listA = new ArrayList<Integer>();
Set<Integer> intersectedElements = new HashSet<Integer>();
for(int i=0;i<a.length;i++){
listA.add(a[i]);
System.out.println("added.. "+listA.get(i));
}
for(int j=0;j<b.length;j++){
if(listA.contains(b[j])){
intersectedElements.add(b[j]);
}
}
}
```

This is my first thought (I'm sure it can be improved, but as a first solution):

- Anonymous November 21, 2012int [] intersection(int [] a, int [] b) {

List<integer> intersection = new LinkedList<Integer>();

Set<Integer> values = new HashSet<Integer>();

for(int i:a) {

values.add(i);

}

for(int i:b) {

if(values.contains(i)) {

intersection.add(i);

}

}

return buildArrayFromList(intersection);

}