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.
If the lists happen to be in sorted order, this works nicely:
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.
A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
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.
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.