Flatten a Dictionary
Given a dictionary dict, write a function flattenDictionary that returns a flattened version of it. Assume that values are either an integer, a string, or another dictionary.
If a certain key is empty, it should be excluded from the output (see e in the example below).
Example
input: dict = { "Key1" : "1", "Key2" : { "a" : "2", "b" : "3", "c" : { "d" : "3", "e" : { "" : "1" } } } } output: { "Key1" : "1", "Key2.a" : "2", "Key2.b" : "3", "Key2.c.d" : "3", "Key2.c.e" : "1" }
Important: when you concatenate keys, make sure to add the dot character between them. For instance, when concatenating Key2, c, and d the resulting key would be Key2.c.d.
Begin by analyzing the input. Can you identify a pattern?
Remember that a recursive approach can often work well when dealing with nested structures.
If you find yourself stuck while figuring out a recursive solution, consider how the keys of the dictionary can be built up with each recursive call.
How do you handle cases where the key is an empty string or null?
Recursion is a natural choice for this kind of problem. We iterate over the keys in dict and distinguish between two cases: If the value mapped to a key is a primitive, we take that key and simply concatenate it to the flattened key we've created up to this point. We then map the resulting key to the value in the output dictionary. If the value is a dictionary, we again concatenate the keys, but instead of adding the resulting key and value to the output dictionary, we recurse on the value with the newly formed key.
Because it is useful to create the output dictionary outside of the recursive function, it makes sense to use a helper function in this problem.
Pseudocode:
function flattenDictionary(dict): flatDictionary = {} flattenDictionaryHelper("", dict, flatDictionary) return flatDictionary function flattenDictionaryHelper(initialKey, dict, flatDictionary): for (key : dict.keyset()): value = dict.get(key) if (!isDictionary(value)): # the value is of a primitive type if (initialKey == null || initialKey == ""): flatDictionary.put(key, value) else: flatDictionary.put(initialKey + "." + key, value) else: if (initialKey == null || initialKey == "") flattenDictionaryHelper(key, value, flatDictionary) else: flattenDictionaryHelper(initialKey + "." + key, value, flatDictionary)
Time Complexity: O(N), where N is the number of keys in the input dictionary. We visit every key in the dictionary only once, hence the linear time complexity.
Space Complexity: O(N) since the output dictionary is asymptotically as big as the input dictionary. We also store recursive calls in the execution stack which in the worst-case scenario could be O(N), as well. The total is still O(N).
def flatten_dictionary(dictionary):
def flatten_dictionary_helper(initial_key, dictionary, flat_dictionary):
for key in dictionary:
value = dictionary[key]
if initial_key and key:
new_key = "{}.{}".format(initial_key, key)
elif initial_key:
new_key = initial_key
else:
new_key = key
if isinstance(value, dict):
flatten_dictionary_helper(new_key, value, flat_dictionary)
else:
flat_dictionary[new_key] = value
flat_dictionary = {}
flatten_dictionary_helper("", dictionary, flat_dictionary)
return flat_dictionary
def flatten_dictionary(dictionary): # return a flattened dictionary - int/string/another dictionary values # if the key is empty, exclude from the output # concat using a "." btwn them # add to res which is { "key.a.b.etc": "value" } # iterate through the key value pairs # while there is a key value pair in the value # continue going through that, until the value is an int/string flatDic = {} flatDicHelper("", dictionary, flatDic) print(flatDic) return flatDic def flatDicHelper(initialKey, dictionary, flatDic): for key in dictionary: value = dictionary.get(key) if (isinstance(value, int) or isinstance(value, str)): if (initialKey == "" or initialKey == null): flatDic.put(key, value) else: flatDic.put(initialKey+"."+key, value) else: if (initialKey == "" or initialKey == null): flatDicHelper(key, dictionary, flatDic) else: flatDicHelper(initialKey+"."+key, value, flatDic)