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