CareerCup

For 2nd solution you dont need to traverse the hash table,
1st insert the elements of 1st array in hash table(let their value be 1), for each element from 2nd array check if its already present or not, if it is present and its value is 1 then put 2 there and count that as one duplicate else if its value is 2 then dont count it because it has already been counted.

another approach is to construct a BST with each node also containing a count of occurances

Assuming sizes of the two lists n, m.
1. If |n - m| is not very large, then sort both and merge -> O(nlogn + mlogm)
2. If |n - m| is very large (assume n <<< m), then create Balanced BST
   for the list of size n, and do look up for elements in list of size m
   O(nlogn + mlogn)