3
\$\begingroup\$

I want to ask for code review for my JavaScript implementation of Flatten_dictionary about this coding challenge for "Flatten a Dictionary" can be found at pramp:

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.

#implementation#1


function flattenDictionary(dict) {
 //flattened dictionary = {}
  //iterate through dictionary
  //check for type of value for each key
     //if value is another dictionary, i will recurivec callthis appending it to the dictionary
  let flattened = {}
  let keys = Object.keys(dict) //give me an array of keys
  for (let i=0; i< keys.length; i++){
    if (typeof dict[keys[i]] === "object") {
      let flatObj = flattenDictionary(dict[keys[i]])
      let newKeys = Object.keys(flatObj) //[a,b]
      for (let j=0; j<newKeys.length; j++) {
        if (newKeys[j] === "") {
          flattened[keys[i]] = flatObj[newKeys[j]]
        } else {
           flattened[keys[i]+"."+newKeys[j]] = flatObj[newKeys[j]]
        }

      }
      //get back to this
    } else {
      flattened[keys[i]] = dict[keys[i]]
    }
  }
  return flattened
}


#implementation#2

function flattenDictionary(dict) {
  // your code goes here
  let results = {};
  let currKey = "";

  function flattenUtil(dict) {
    // 1. 'Iterate' over the dictionary
    // Keys will either be 'Key_' for outermost level
    // or a letter/empty string for inner levels
    // 2. If the value is an int/string, append onto output dictionary
    // else if the value is a dictionary, recurse
    // 3. Base case: dict empty, return

    Object.keys(dict).forEach(key => {
      if (typeof dict[key] === 'object') {
        if (!currKey) {
          currKey += key;
        } else {
          currKey += `.${key}`;
        }
        flattenUtil(dict[key]);
      } else {
        if (!currKey) {
          results[`${key}`] = dict[key];
        } else {
          if (!key) {
            results[`${currKey}`] = dict[key];
          } else {
            results[`${currKey}.${key}`] = dict[key];
          }
        }
      }
    });
  }

  flattenUtil(dict);
  return results;
}
\$\endgroup\$

2 Answers 2

Reset to default
1
\$\begingroup\$

Reviewing top function

In general code review is for code you have written, but the presented code looks like it has two authors. The styles do not match.

Style problems.

  • Put spaces between operators. "Wedon'twritewith randomspaces hereandthere" nor should our code look like this for (let i=0; i< keys.length; i++){

    Better as for (let i = 0; i < keys.length; i++) {

  • Always use ; at the end of an expression (the second function is OK)

  • Use constants for values that do not change. Eg the first function flattened, keys, newKeys, and flatObj should be constants.

  • Keep the noise level down. In code noise is code that has no purpose, code that can be expressed in a shorter form, or comments that give no extra information, or worse creates misleading information

    • Example of comments providing no useful information.

      let keys = Object.keys(dict) //give me an array of keys

    • Example of misleading comments. If I was coming to this code I would have to guess, is the code wrong, or the comment. This is a VERY dangerous thing to put in code.

      // Keys will either be 'Key_' for outermost level

    • Example of redundant code. The array keys, the iteration counter i, and the extra array indexing into keys are all redundant because there is a shorter way to write the same

      let keys = Object.keys(dict) //give me an array of keys

      for (let i=0; i< keys.length; i++){

      if (typeof dict[keys[i]] === "object") {

      Can be written as

      for (const [key, value] of Object.entries(dict)) {

      if (typeof value === "object") {

BUGS

You have at least one bug, Maybe two or three in my book.

Null object

The call flattenDictionary({a : null}) will throw the error TypeError : Cannot convert undefined or null to object

The reason is that in JS null is an object eg typeof null === "object"

Cyclic reference

As the object being passed is considered a dictionary this may not apply as a dictionary would general not have a cyclic reference, but it is worth a note.

Consider the object

const A = {};
A.a = A;

A holds a reference to itself, a very common and accepted practice, though the reference is not usually direct. A will hold an object that has the reference to A

Calling flattenDictionary(A) with throw a RangeError Maximum call stack size exceeded

JS recursion bug

This is the third bug, related to the previous one. Not everyone will agree this is a bug but the fact remains that you can not know how long the call stack is when your function is called. This means you can never 100% assure that JS function will complete if it contains a function call.

Generally this is not a problem. JS is event driven and you know that all events always start with a empty call stack.

However recursive functions will have an unknown call depth and you can not guarantee an unknown quantity with fit a fixed sized container.

Thus in my book recursive functions are inherently buggy

Iteration

I would advise against using for in loops (as Joseph's answer suggests) as they will also iterate over all enumerable inherited properties and will require that you check if the property belongs to the object and not from higher up the prototype chain.

I would also avoid using recursion for objects that are unknown. Recursion is just the lazy mans stack and it can be quicker and safer to implement your own stack, storing only what you need rather than a whole function's context for each step.

Alternative to recursion.

Thus a probable solution, ignoring the cyclic recursion but free of call stack overflow problems and null is an object error.

The array pathStack replaces the call stack, and the while continues until the stack is empty.

function flattenDictionary(dict) {
    const result = {}, pathStack = [];
    const push = (obj, path) => pathStack.push({obj, path});
    push(dict, "");
    while (pathStack.length > 0) {
        const node = pathStack.pop();
        const path = node.path + (node.path !== "" ? "." : "");
        for (const [key, value] of Object.entries(node.obj)) {
            if (value !== null && typeof value === "object") { push(value, path +  key) }
            else { result[path +  key] = value }
        }
    }
    return result;
}
\$\endgroup\$
2
\$\begingroup\$

One issue I always come across when implementing this myself is that keys can contain .. But your code simply concatenates nested keys together, your flattener function will not correctly represent the object it just flattened. You'll have to find a way to tell a valid . from a . that was part of the key.

While Object.keys() is a really handy function to get the object keys, you're effectively creating an array with it. Same goes for forEach's callback, you're creating the callback function. For larger objects, you easily generate lots of objects this way. This can cause the GC to kick in more frequently, causing things like jerky scrolling, UI freezing, animation hitching. I recommend using plain for-in loops once you start seeing these issues.

Also, your code overcomplicated itself. At every node, your function is generating a flat object, and its return is merged to the parent node's flat object. Theoretically, this is how things are done in a "functional" manner - create, never mutate. But this becomes very impractical, you're building throw-away objects. What you could do is create just one object. Then as you traverse through the tree, just append to it. To the outside world, the function is still pure even if its implementation isn't.

For instance, your code could have been as simple as this (ignoring the . in key issue):

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

const flatten = (source, parentPath = '', target = {}) => {

  for(const key in source){
    // Construct the necessary pieces of metadata
    const value = source[key]
    const path = parentPath ? `${parentPath}.${key}` : key
    
    // Either append or dive another level
    if (typeof value === 'object'){
      flatten(value, path, target)
    } else {    
      target[path] = source[key]
    }
  }

  return target
}

// To the outside world, you pass in dict, and you get a new object.
// No side effects happen, we're all good.
console.log(flatten(dict))

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.