## EFI Interview Question

Software Engineer / DevelopersI believe the solution the interviewers expect is the algo. They are not interested in which collections object you will be using.

The soultion should be: (lets say the first array has m elements and the second array has n elements. And x are the repeatitions in the first array of m elements)

Step 1: to remove all the duplicates from the first array by a linear search. it will be m*m and crete a new set containing m-x elements.

Step 2: now again perform linear search for each element of m-x elements array on the second array. and break the loop when the identical value is found. So the time taken is (m-x) * logn

So total time taken = m*m + (m-x) * logn

If there is a optimised solution please let me know.

You need to construct a Hash table of one of the arrays(I prefer the smaller one) . Then use to second array to hash into the table to see if they already exist. Solution is O(n).

Binary tree can be an answer but I would suggest an AVL tree rather than just a Binary tree as AVL is balanced and search is almost always lg n but this ofcourse involves additional operations for balancing.

sort both arrays by quicksort.it will take 2O(nlogn) time to sort.

Now number to number match both arrays.for eg.

let after sorting

a=1,2,4,4,6,8

b=2,3,4,5,7

so now match like this..

1!=2 and 1<2

next element frm a

2=2 match

2!= 3 and 2<3

next element frm a.

here length of a and b can be compared to get better result.

you could use a hash table to find common elements in o(n).

- jerry April 03, 2006