Efficiently finding the intersection of a variable number of sets of strings

java theory set big-o intersection
tshred picture tshred · May 17, 2010 · Viewed 13.6k times · Source

I have a variable number of ArrayList's that I need to find the intersection of. A realistic cap on the number of sets of strings is probably around 35 but could be more. I don't want any code, just ideas on what could be efficient. I have an implementation that I'm about to start coding but want to hear some other ideas.

Currently, just thinking about my solution, it looks like I should have an asymptotic run-time of Θ(n2).

Thanks for any help!

tshred

Edit: To clarify, I really just want to know is there a faster way to do it. Faster than Θ(n2).

Answer

Michael Borgwardt picture Michael Borgwardt · May 17, 2010

Set.retainAll() is how you find the intersection of two sets. If you use HashSet, then converting your ArrayLists to Sets and using retainAll() in a loop over all of them is actually O(n).

Related questions

Comparing two Calendar objects

I want to compare two Calendar objects to see if they both contain the same date. I don't care about any value below days. I've implemented this and I can't think about any case where it should fail: private static …

Read More
Calling base class overridden function from base class method

public class A { public void f1(String str) { System.out.println("A.f1(String)"); this.f1(1, str); } public void f1(int i, String str) { System.out.println("A.f1(int, String)"); } } public class B extends A { @Override public void f1(…

Read More
How would you access Object properties from within an object method?

What is the "purist" or "correct" way to access an object's properties from within an object method that is not a getter/setter method? I know that from outside of the object you should use a getter/setter, but from …

Read More