• Post Reply Bookmark Topic Watch Topic
  • New Topic

finding elements in the list  RSS feed

 
radha MS
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 893
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Anupam Sinha
Ranch Hand
Posts: 1090
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1090
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!