Associate Professional

So the intersection of sets … additional info could be important …

If the lists are sorted (the same way), you could traverse them simultaneously (moving the pointer “to smaller” and copy elements to the result list when smaller is simultaneously in both lists ( Θ(n) solution).

If the lists are not sorted, making a hashmap would be faster than trivial Θ(n2) solution or a solution sorting them first Θ(nlogn) .

So traverse one list and update the hashmap addressed by the keys to contain the number of elements with the given key in the traversed portion of the list.

Then traverse the other list and if the key is not in the hashmap with a count greater than 0, ignore it. In the other case decrement the count and copy the element to the result list. The hashmap can be discarded after the second traversal.

In the case you know there are no duplicate keys in the input lists, you could use a hashset rather the hashmap as you need not border with maintaining counters. … Θ(n) solution (randomized by the hash function choice).

A hash table (or hashmap) is essentially a map from one object to another. The most basic example of a hashmap is an Array, since an Array maps integers to data elements.

The elements which are mapped from are termed as keys (in an array, the integer indices act as keys) and the elements that are mapped to are called values (in an array, the data elements are values).

Generally, the keys need to be unique in a hashmap (else on quering a key, the language can’t determine which value to return, for instance mapping the index 0 of an array to 2 different objects).