Flatten a Dictionary (Reduzieren Sie ein Wörterbuch)

[esthicodes]

Ein Wörterbuch ist eine Art von Datenstruktur, die von Haus aus von allen wichtigen interpretierten Sprachen wie JavaScript, Python, Ruby und PHP unterstützt wird, wo sie als Objekt, Wörterbuch, Hash bzw. Array bekannt ist. Einfach ausgedrückt ist ein Wörterbuch eine Sammlung von eindeutigen Schlüsseln und deren Werten. Die Werte können in der Regel von einem beliebigen primitiven Typ sein (z. B. Integer, Boolean, Double, String usw.) oder andere Dictionaries (Dictionaries können verschachtelt werden). Für diese Übung nehmen wir jedoch an, dass die Werte entweder eine ganze Zahl, eine Zeichenkette oder ein anderes Wörterbuch sind.

Schreiben Sie eine Funktion flattenDictionary, die eine reduzierte Version des Wörterbuchs dict zurückgibt.

Wenn Sie eine kompilierte Sprache wie Java, C++, C#, Swift und Go verwenden, können Sie eine Map/Dictionary/Hash-Tabelle verwenden, die Strings (Schlüssel) auf einen generischen Typ abbildet (z. B. Object in Java, AnyObject in Swift usw.), um verschachtelte Wörterbücher zu ermöglichen.

Wenn ein bestimmter Schlüssel leer ist, sollte er von der Ausgabe ausgeschlossen werden (siehe e im Beispiel unten).

Pramp Interview

[esthicodes]

[esthicodes]

A recursion is 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 created up to this point. We then map the resultant key to the value in the output dictionary. If the value is a dictionary, we do the same concatenation, but instead of mapping the result to the value in the output dictionary, we recurse on the value with the newly formed key.

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 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).

[esthicodes]

If your peer cannot come up with a solution, ask them to analyze the input and see if they see a pattern.
If still no progress, try to direct them toward a recursive approach.
If your peer makes some progress with the recursive approach, and is stuck at some other point, try to give some hints regarding how keys of the dictionary could be manipulated.
Watch out of cases when the key is an empty string or null. For instance, consider the case where the input dictionary itself isn’t associated with any key

[esthicodes]

function flattenDictionary(dict) {
  const outputDict = {};
  
  const inner = (keySoFar, innerDict) => {
    for (let key of Object.keys(innerDict)) {
      const value = innerDict[key];
      const prefix = keySoFar ? keySoFar + '.' : '';
      const outputKey = key ? prefix + key : keySoFar;
      
      if (typeof value === 'string') {
        outputDict[outputKey] = value;
      } else {
        inner(outputKey, value);
      }
    }
  }
  
  inner('', dict);
  
  return outputDict;
}

[esthicodes]

function flattenDictionary(dict) {
  let outputDict = {};
  // outputDict = {'abc': 'def'};
  
  
  // const inner = (keySoFar, innerDict) => {
  function inner(keySoFar, innerDict, prefixFn) {    
    for (let key of Object.keys(innerDict)) {
      const value = innerDict[key]; // let : declare variable 
      const prefix = prefixFn(keySoFar);
      const outputKey = key ? prefix + key : keySoFar;
      
      if (typeof value === 'string') {
        outputDict[outputKey] = value;
      } else {
        inner(outputKey, value, prefixFn);
      }
    }
  }
  
  //inner('', dict); // depth first search
  
  const anotherInner = inner;
  
  anotherInner('', dict, (keySoFar) => keySoFar ? keySoFar + '.' : '');
  
  console.log(inner.name);
  
  return outputDict;
}

/*
dict = {
    "Key1" : "1",
    "Key2" : {
        "a" : "2",
        "b" : "3",
        "c" : {
            "d" : "3",
            "e" : {
                "" : "1"
            }
        }
    }
}
*/