trjhtr

I have a question about this coding challenge for "Flatten a Dictionary":

Given a dictionary dict, write a function flattenDictionary that
returns a flattened version of it .

If you’re using a compiled language such Java, C++, C#, Swift and Go,
you may want to use a Map/Dictionary/Hash Table that maps strings
(keys) to a generic type (e.g. Object in Java, AnyObject in Swift
etc.) to allow nested dictionaries.

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 concatenating Key2, c and d the result key would be Key2.c.d.

def flatten_dictionary(dictionary):

 def items():
 # loop through each item inside the dictionary k, v
 #Appending
 # check if the sub-key and sub-value are 
 # inside the flatten_dict(value)
 # join on subkey array
 # add to result
 # clear out prev_keys
 for key, value in dictionary.items():
 if isinstance(value, dict):
 for subkey, subvalue in flatten_dictionary(value).items():
 if key == "":
 yield subkey, subvalue
 yield key + "." + subkey, subvalue

 else:

 yield key, value

 return dict(items()) 


# test cases 1

dictionary2 = 
 "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"
# 

print(flatten_dictionary(dictionary2))

1. Bugs

1. 
   

   The special case for empty keys:

   
   
   

   if key == "":
    yield subkey, subvalue
   yield key + "." + subkey, subvalue
   

   
   
   

   is missing an else: and so leads to items appearing twice:

   
   
   

   >>> flatten_dictionary("": "a":1)
   'a': 1, '.a': 1
   

   
   


2. 
   

   Even if we fix the bug by adding the else:, there's still a problem. Consider this example:

   
   
   

   >>> flatten_dictionary("a": "": "b": 1, "": "a": "b": 2)
   'a.b': 2
   

   
   
   

   What happened to the 1? Ignoring the empty string keys has led two different keys to be collapsed into one. It would be better to remove the special case for empty strings, so that:

   
   
   

   >>> flatten_dictionary("a": "": "b": 1, "": "a": "b": 2)
   'a..b': 1, '.a.b': 2
   

   
   


3. 
   

   Python has a limited stack, but dictionaries can be nested arbitrarily deeply:

   
   
   

   >>> d = 
   >>> for i in range(1000): d = 'a':d
   ... 
   >>> flatten_dictionary(d)
   Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    File "cr186013.py", line 22, in flatten_dictionary
    return dict(items()) 
    [... many line omitted ...]
    File "cr186013.py", line 13, in items
    for subkey, subvalue in flatten_dictionary(value).items():
   RecursionError: maximum recursion depth exceeded
   

   
   
   

   This problem can be avoided using the stack of iterators pattern.

   
   

2. Other review points

1. 
   

   The comment does not match the code: there is nothing in the code corresponding to "check if the sub-key and sub-value are inside the flatten_dict(value)" or "join on subkey array" or "clear out prev_keys". Incorrect comments like this are worse than useless: they make it harder to understand and maintain the code.

   
   
   

   Did this comment describe an earlier version of the code, and then you changed the code but forgot to edit the comment? It is worth getting into the habit of changing the comment first so that you don't forget.

   
   


2. 
   

   The construction of the result keys has unnecessary quadratic runtime. For example, in this situation:

   
   
   

   >>> flatten_dictionary('a': 'a': 'a': 'a': 'a': 'a': 1)
   'a.a.a.a.a.a': 1
   

   
   
   

   there is only the need to concatenate one result key ('a.a.a.a.a.a'), but the code concatenates five result keys: not just the one that we need, but 'a.a', 'a.a.a', 'a.a.a.a' and 'a.a.a.a.a' as well. The way to avoid this is to keep a stack of dictionary keys currently being visited, and use str.join on the stack when you need to concatenate the result key.

   
   

3. Revised code

def flatten_dictionary(d):
 result = 
 stack = [iter(d.items())]
 keys = 
 while stack:
 for k, v in stack[-1]:
 keys.append(k)
 if isinstance(v, dict):
 stack.append(iter(v.items()))
 break
 else:
 result['.'.join(keys)] = v
 keys.pop()
 else:
 if keys:
 keys.pop()
 stack.pop()
 return result