Practice-It

Write a method duplicateValues that accepts a Map from strings to strings as a parameter and returns a count of how many values in the map are duplicates of another value in the map. For example, if a variable named map contains the following key/value pairs:

{Marty=Stepp, Jessica=Miller, Mike=Stepp, Stuart=Reges, James=Hale, Amanda=Camp,
 Hal=Perkins, Biz=Camp, Kendrick=Perkins, Sam=Perkins, Eve=Riskin, Jane=Perkins}

In the above map, there are two occurrences of the value Stepp, so one (1) of them is a duplicate; there are two occurrences of the value Camp, so one (1) of them is a duplicate; and there are four occurrences of the value Perkins, so three (3) of them are duplicates. Therefore the call of duplicateValues(map) would return 1+1+3 = 5. (One way of thinking of it is that we could hypothetically remove 1 occurrence of Stepp, 1 occurrence of Camp, and 3 occurrences of Perkins; and those values would still be represented in the map.) If the map contains no duplicate values or contains no values at all, your method should return 0. Note that we are asking about duplicate values, not keys. You should not make any assumptions about the order in which the keys or values appear in the map. You may assume that the map is not null and that none of its keys or values are null strings.

Obey the following restrictions in your solution:

• You may create only up to two (2) new data structures of your choice (list, stack, queue, set, map, array, etc.) as auxiliary storage. (You can have as many simple variables as you like.)
• Your solution should run in strictly less than O(N²) time, where N is the number of pairs in the map.
• You should not modify the contents of the map passed to your method.