Flatten a Dictionary interview question

I recently tackled a challenge that involved flattening a dictionary. Allow me to share the objective we aimed to achieve:

You are given a dict and you need to flattening it:

Map<String, Object> dict = new HashMap<>();
dict.put("Key1", "1");

Map<String, Object> inner2 = new HashMap<>();
inner2.put("a", "2");
inner2.put("b", "2");
dict.put("Key2", inner2);

Map<String, Object> inner3 = new HashMap<>();


Map<String, Object> inner4 = new HashMap<>();
inner4.put("b", "3");
inner4.put("d", "3");
inner3.put("a", inner4);

Result:

key Key1 val 1
key Key4.a.d val 3
key Key2.a val 2
key Key2.b val 2
key Key4.a.b val 3

Here is the solution I devised along with some accompanying notes:

private static final String DOT = ".";

/**
 * Flattens a nested dictionary into a single-level dictionary.
 *
 * @param dict The nested dictionary to be flattened.
 * @return The flattened dictionary.
 * @throws IllegalArgumentException if the nested dictionary contains an unsupported type.
 */
public Map<String, String> flattenDictionary(Map<String, Object> dict) {
    Map<String, String> result = new HashMap<>();
    flattenHelper(result, null, dict);
    return result;
}

/**
 * Recursive helper method to flatten a nested dictionary.
 *
 * @param result The map to store the flattened dictionary.
 * @param key The current key in the nested dictionary.
 * @param obj The value associated with the current key.
 * @throws IllegalArgumentException if the nested dictionary contains an unsupported type.
 */
private void flattenHelper(Map<String, String> result, String key, Object obj) {
    if (obj instanceof Map) {
        Map<String, Object> inner = (Map<String, Object>) obj;

        for (String innerKey : inner.keySet()) {
            Object innerObj = inner.get(innerKey);

            if (key == null) {
                flattenHelper(result, innerKey, innerObj);
            } else {
                flattenHelper(result, key + DOT + innerKey, innerObj);
            }
        }
    } else if (obj instanceof String) {
        String innerString = (String) obj;
        result.put(key, innerString);
    } else {
        throw new IllegalArgumentException("Unsupported type " + obj);
    }
}

Explanation:

• The flattenDictionary method takes a nested dictionary (Map<String, Object> dict) as input and returns a flattened dictionary (Map<String, String>).
• The flattenHelper method is a recursive helper function that performs the actual flattening operation.
• The result map is used to store the flattened dictionary.
• The key parameter represents the current key in the nested dictionary.
• The obj parameter represents the value associated with the current key.

The flattenHelper method follows these steps:

1. It checks if the obj is an instance of Map. If true, it means there is a nested dictionary, and the method recursively calls flattenHelper for each key-value pair in the nested dictionary.

• If the key parameter is null, it means we are at the top level of the dictionary, so the current innerKey becomes the new key.
• If the key parameter is not null, it means we are inside a nested dictionary, so the current innerKey is appended to the existing key using a dot separator (key + DOT + innerKey).

2. If the obj is an instance of String, it means we have reached a leaf node in the nested dictionary. In this case, the current key and obj are added to the result map.

3. If the obj is neither a Map nor a String, it means it's an unsupported type, and an IllegalArgumentException is thrown.

4. Once the recursion is complete, the flattenDictionary method returns the result map, which contains the flattened dictionary.

Let’s try to write some simple test:

public static void main(String[] args) {
        Map<String, Object> dict = new HashMap<>();
        dict.put("Key1", "1");

        Map<String, Object> inner2 = new HashMap<>();
        inner2.put("a", "2");
        inner2.put("b", "2");
        dict.put("Key2", inner2);

        Map<String, Object> inner3 = new HashMap<>();

        Map<String, Object> inner4 = new HashMap<>();
        inner4.put("b", "3");
        inner4.put("d", "3");
        inner3.put("a", inner4);

        Map<String, String> stringStringMap = new Program().flattenDictionary(dict);

        stringStringMap.forEach((key, val) ->  System.out.println("key " + key + " val " + val));
    }

The output will be the same as above.

Time and Space Complexity: The time complexity of the solution is O(N), where N is the total number of key-value pairs in the input dictionary. The space complexity is also O(N) since the function creates a new dictionary to store the flattened key-value pairs.

Feel free to leave your comments in the section below! Remember to follow me and remember that practice makes perfect!