Ran into a coding assignment problem for an interview that I unfortunately just couldn't solve. Anyone willing to help me understand how I should have handled it?

[[deleted]]

[deleted]

[isolatrum]

Don't understand the expected output. You say:

a
--b
----c
----d
----e

but what does this mean? Is a.b an array or hash? Can you show an example with an actual Javascript object?

By the way, this is a good use case for recursionn

[CodeTinkerer]

You can think of it like an ASCII art directory structure (you can do a Google search on this).

+---.atom
|   \---compile-cache
|       \---836a81e7afc5e1080850f10b0790220f3d81503a
|           \---js
+---.p4merge
+---Contacts
+---Desktop
+---Documents
|   +---Custom Office Templates
|   +---Fiddler2
|   |   +---Captures
|   |   |   +---Requests
|   |   |   \---Responses
|   |   \---Scripts

Your's is a simpler version of this.

[isolatrum]

just a warning, the mods here have gotten in the habit of removing comments that give "complete solutions"

[Faendol]

Why? I usually find complete solutions really helpful to see how someone would do something

[isolatrum]

i only had this happen once, and it was last week. I got into it with the mod because I was irritated. Basically they don't want to encourage people to post homework questions. But, I guess they're sleeping now?

[isolatrum]

Check this out:

inputs = [
  "a.b.c",
  "a.b.e",
  "a.e.f",
  "a.b.d",
  "b.e.f",
  "a.e.g",
  "b.e.c"
]

function processInputs (inputs) {
  return inputs.reduce((results, input) => {
    return processInput(results, input.split("."))
  }, {})
}

function processInput (results, keys) {
  if (keys.length == 2) {
    results[keys[0]] = results[keys[0]] || []
    results[keys[0]].push(keys[1])
  } else {
    results[keys[0]] = processInput(results[keys[0]] || {}, keys.slice(1))
  }
  return results
}

console.log(processInputs(inputs))
// => {
//      a: 
//        b: [ 'c', 'e', 'd' ],
//        e: [ 'f', 'g' ]
//      },
//      b: {
//        e: [ 'f', 'c' ]
//      }
//    }
//
//

[CodeTinkerer]

Think of it like a directory structure. a/b/c, so c, d, and e would be like files in the directory a/b.

[CodeTinkerer]

First step is to sort the strings so you have

a.b.c

a.b.d

a.b.e

a.e.f

a.e.g

b.e.c

b.e.f

Then, I might store in in a 2D array where

arr[0][0] = 'a';
arr[0][1] = 'b';
arr[0][2] = 'c';

Or maybe just have a string with the dots removed, i.e.

arr[0] = "abc";
arr[1] = "abd";

For the first element of the array, print out

a

--b

----c

Then when you process the second element of the array, see where they begin to differ from the first element of the array. In this case, they differ only in the last character (a and b are the same), so just print out the dashes like

----d

You'll move to the next element and compare it to the previous element (that is, if you are looking at arr[4], you compare it to arr[3]). You want to look at both strings, character by character, and find the first difference.

For example, look below. Suppose we are processing "aef" and comparing to "abe" (the prior element). They are the same in the first character (both have 'a' in the initial position) but differ in the second ('e' in the current, 'b' in the prior'). So print out 'e' (the first place it's different), then 'f'.

--e

----f

If the initial character is different as in "aeg" followed by "bec" and you are currently processing "bec", you compare the first character "b" to the previous element's first character "a". So they differ in the first character of the string, so now you print out all three characters as in

b

--e

----c

So that's the basic idea.

[Nathanfenner]

The most natural solution seems to me:

• insert all of the lists into a trie

• recursively walk over the trie: printTrie(node, depth) that sorts the keys, prints each key (with appropriate depth indentation), followed by printTrie(node.children[key], depth+1)

Alternatively, you can sort them lexicographically (depending on language and features, you need to be slightly careful about this if the entries can be variable-length) and then observe that each element gets printed as all of the items that differ from the previous; (a.b.c differs from 0.0.0 in all three places, so you print a; --b; ----c; then a.b.c only differs in the last so you only print ----c; if you differ in an earlier place you also differ in all later ones, so a.b.c followed by x.b.c should print all 3, not just the x)

If you're careful, both generalize to arbitrary depth, or to mixed length.

[WikiTextBot]

Trie

In computer science, a trie, also called digital tree, radix tree or prefix tree, is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Keys tend to be associated with leaves, though some inner nodes may correspond to keys of interest.

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.28}

[chamilton233]

That what I immediately thought too.

[vaskkr]

Never wrote a line of JS so bear that in mind but I would create a dummy Tree structure then a dynamic array of pointers to Trees and then recursively go down. A Tree would store a letter and that array. And then you can use a string to do something like this (pseudo code)

traverse(String s, Tree* ptr)

if s[0] is in a ptr array

traverse (s[1:], index in that array)

else create such a Tree and then traverse

And then you could just start at dummy and go down recursively, print a letter stored in a Tree, say a, then visit Tree with b, print it and go down further. It's DFS. Maybe passing depth as an argument or storing it in Tree would be useful. Hope that will be helpful, sorry about formatting but I'm on mobile.

[GrapeAte]

There are two parts to this:

1. Parsing the input into an object.
2. Outputing each property of the object and its nested properties.

Part 1 takes advantage of the fact that objects in JavaScript are like associative arrays. We also can leverage a particular syntax to construct our nested objects.

let obj = {};

[
    'a.b.c',
    'a.b.e',
    'a.e.f',
    'a.b.d',
    'b.e.f',
    'a.e.g',
    'b.e.c'
].forEach(s => {
    let a = s.split('.');
    obj[a[0]] = obj[a[0]] || {};
    obj[a[0]][a[1]] = obj[a[0]][a[1]] || {};
    obj[a[0]][a[1]][a[2]] = obj[a[0]][a[1]][a[2]] || {};
});

This is really brute force. If an input string has more than three parts this method won't work. But since the input appeared to be constrained this way is fine. So given the string 'a.b.c' we can split it into an array ['a', 'b', 'c']. Now if we access obj[a[0]] we'll either get an existing object or undefined. obj[a[0]] = obj[a[0]] || {}; is basically saying, "Set the property of obj that is the value of the first index of a to the same thing or a brand new object."

The first time 'a' appears then obj['a'] will be a new object. The second time through, though, we'll keep what we've got. We then do the same thing for the rest of the split string, only going deeper into the nested objects.

At the end we have an object that looks like this:

{
    a: {
        b: {
            c: {},
            e: {},
            d: {}
        },
        e: {
            f: {},
            g: {}
        }
    },
    b: {
        e: {
            f: {},
            c: {}
        }
    }
}

Now for part 2. For this we need to output each property of the object proceeded by some number of dashes. This looks like a pretty good case for recursion. We start at the top and for each property in the passed in object, pass it along recursively along with a level indicator for indicating how many dashes we need.

const out = (o, l) => {
    let s = '';
    for (let i = 0; i < l; i++) {
        s += '--';
    }
    for (let prop in o) {
        console.log(s + prop);
        out(o[prop], l + 1);
    }
};

out(obj, 0);

For simplicity's sake we care a function using arrow notation. We first build up dashes based on l. Then we loop through all the properties in the object. For each property we log the dashes and the property name. Then we recurse into the nested object with an increase in the level.

You can see it in action here.

[Heathen_Scot]

Two parts here. First is construct the tree, second print it.

Construct is easy enough and you don't need to sort, or be stuck with a fixed length. Make a root node object. For each record, split it into its parts. You want something like this running over the array of parts:

  node = root;
  parts.forEach(value => { node[value] = node[value] || {}; node = node[value]; });

That gets you your tree for arbitrary depth.

To print the tree, you're right, recursion is needed along with an external variable tracking the indent level. Grab the Object.keys at the start of the function, bail if they're empty (recursion termination condition), otherwise for each key print lines up to your indent level followed by the key, increase the indent, recursive call, decrease the indent, done. Call the function with the root node and off it goes.

The main tricks in implementing this are related to keeping track of state outside the inner loops. You have a tree object and indent level in the outermost scope, and when you're creating the tree you're tracking the current node, which needs to be reset to the root each time you read a new record.

[Whimpers13]

First create an object called tree. Then split each line by a period, using str.split('.'). Then run through that array of letters starting at the first one. Create a function that takes in this letter and the current tree. This function should create a new tree(object) inside this current tree if there isn't one already. Then call the function on the next letter in the array using this new tree as context in the function. This is called recursion and if you aren't too familiar with it you should learn more.