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

Question

I have a variable number of ArrayList<String>'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 &#920;(n²).Thanks for any help!tshredEdit: To clarify, I really just want to know is there a faster way to do it. Faster than &#920;(n²).

Answer 1

The solution requires additional memory.(It's a good solution of using Set)

Here is another approach for large dataset, you can sort both ArrayList, And have two iterators to iterator through both Lists one by one.

Answer 2

I assume your O(n²) solution involves traversing one of the ArrayLists, and for each element, traversing the other ArrayList in its entirety to see if that element is contained.

This can be done in O(n) using hash tables. Start by adding each element from one of the lists to a hash table - this is O(n) total. Then, for the other list, for each element, look it up in the hash table - lookup is a constant-time operation. If it's in the hash table, add it to your result. Thus, we have total runtime of O(n) + O(n) = O(n).

If you're unfamiliar with hash tables, check out the resources here: https://www.geeksforgeeks.org/hashtable-in-java/