The intersection is useful for, among other things, displaying options or values common to multiple selections. An action can then be performed on the common item in each list. For example, to provide a way to delete keywords that are common to objects that each maintain their own list of keywords, the intersection of those keyword lists is needed.

The naive algorithm is quadratic (O(n^2)).

To do this in O(n) use a Dictionary

Go through each list of strings. If a string hasn't been added to the Dictionary then add it with count=1. If the string already exists in the Dictionary then increment its counter. Finally iterate over every Dictionary entry accumulating only those keys with counter values equal to k. The keys with counter values equal to k form the intersection of the string lists.

As long as the underlying hashing function executes in constant time then this algorithm will execute in O(n).

## No comments :

## Post a Comment