Your algorithm should satisfy the following criteria:
1. It should be able to accept as input 0 to k collections, stored as simple arrays. We’re
restricting the data structure to arrays since we haven’t covered higher order data
structures yet.
2. The elements of the collections should all be of type Comparable, and they should all be derived from the same base class (not counting the Object class). Implementation of the Comparable interface is necessary since the elements must be compared to each other in order to determine commonality. They must all be derived from the same base class since comparisons between different data types is undefined.
3. Duplicate elements should be allowed; e.g., if there are M instances of the value, “XYZ”, in all the input collections, there should be M instances of the value, “XYZ”, in the collection of common elements. For example, suppose you have the following collections:
banana
quince
plum
apple
raspberry
pomegranate
pear
banana
lime
banana
lemon
banana
pomegranate
apple
jujube
pineapple
banana
blueberry
cherry
cherry
apple
jujube
blueberry
cherry
cherry
jujube
grape
orange
mango
banana
The collection of common elements would be (order doesn’t matter):
banana
apple
banana
cherry
jujube
4. The collections should be allowed to be of varying lengths; i.e., some collections may have more items than others.
5. One of the collections must be designated as the “query” collection, which is the collection containing the elements to which the elements in the other collections are compared.
6. The total number of element comparisons performed should be less than the value for the quadratic solution described above. That is, the total number of comparisons in the worst case should be less than (k – 1)N2. Do not be concerned about average performance or best case performance. Also, the total number of comparisons is defined, for this assignment, to be only those comparisons that are performed once the traversal of the query collection begins, and the other collections are checked for the presence of the elements in the query collection. Any comparisons performed to manipulate the data prior to searching for the common elements should be ignored.