• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Jeanne Boyarsky
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Junilu Lacar
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Ganesh Patekar
  • Tim Moores
  • Pete Letkeman
  • Stephan van Hulst
Bartenders:
  • Carey Brown
  • Tim Holloway
  • Joe Ess

finding elements in the list  RSS feed

 
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.
 
Ranch Hand
Posts: 893
Java Tomcat Server Ubuntu
  • 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.
 
(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.
 
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.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!