finding elements in the list

[radha MS]

Assume you are given two fixed lists of numbers (arbitrary size, but you can assume the lists are large):

a) Write a method that can efficiently find out if there is any element in the 2nd list that is an element of the first list.

boolean b = listA.retainAll(listB);
if(listA.isEmpty())
System.out.println("No common elements of listA found in list b");
else
System.out.println("common elements of listA found in list b");

Is this correct?

b) Describe some of the tradeoffs you can make with regards to memory and complexity.

[Remko Strating]

If you want to do the comparision multiple times I would convert the list to seach into a HashMap which is more efficient in finding.

[Stan James]

If the lists happen to be in sorted order, this works nicely:

while not a at end and not b at end
   if a < b
      handle a only
      next a
   else
   if b < a
      handle b only
      next b
   else
      handle match
      next a
      next b
end while

It would be interesting to compare the overhead of sorting the lists to the overhead of building a hashmap and testing keys. The hashmap may well come out ahead.

[Anupam Sinha]

Yeah you can use a key only HashMap which is a HashSet for this purpose. But that would not allow any duplicates. I would suggest that if the list is large, do a binary search on the list(which would require a sorted list).

If only finding a duplicate is concerned and the chances are that there would be a lot of duplicates then you can do away with the sorting part and simply use the contains method then exit out of the loop the first duplicate is found. If only the count of duplicates is not required.

The retainAll method would actually modify the list and would iterate through all the elements.

[Anupam Sinha]

Plus it would be better to know if the lists contains objects of different kinds or of the same kind. That is there are different Strings or there can be an Integer, String, UserData etc.