Problem:

One common pattern when using hash tables requires building a Map whose values are Collection instances. In this challenge, we’ll take the output of the previous challenge and invert it.

Write a program that takes as its input a HashMap<String,Integer> and returns a HashMap<Integer,HashSet<String>> containing the same data as the input map, only inverted, such that the input map’s values are the output map’s keys and the input map’s keys are the output map’s values.

Example:

Consider the example output for Hash Table Word Count. Using that map as the input, the output for this challenge would be:

2 → ["to", "be"]
1 → ["or", "not", "that", "is", "the", "question"]

1. Understand

# Write a function that takes the output from getFreqDict
# (a dictionary with String:Int key:value pairs)
# and returns a dictionary with Int:HashSet<String> key:value
# pairs where the int is the unique counts and the
# Set is the set of unique words that have that count
# For example, for the string input 
# "To be or not to be, that is the question."
# The output of this function would be the dictionary:
# 2 → ["to", "be"]
# 1 → ["or", "not", "that", "is", "the", "question"]

2. Match

# This is a HashMap / dictionary problem
# We already created a dictionary of all the unique words
# and their counts. We need to iterate on each of these entries
# to create a new dictionary with unique counts as keys
# and a set of words that have these counts as the value

3. Plan/Pseudocode

# Need a new empty dictionary to store results
# Take the dictionary we get from getFreqDict() as input
# Iterate on each entry and check if the value (count) already
# exists as a key in our new dictionary.
# If it doesn't, add the count as the key in this new dictionary
# and a Set containing the word as the value
# If it does exist, add the newly encountered word to the 
# set existing at this key
# return the new dictionary after iteration halts

4. Implement

5. Review

Output for the sentence “To be or not to be, that is the question.”:

6. Evaluate

The solution is a complexity of:

O(N) space and O(N) time