A better solution to hierarchy sorting question (JavaScript)

Question

I got this challenge.

const hierarchy = [
  { memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' },
  { memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' },
  { memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' },
  { memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' },
  { memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' },
  { memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' },
  { memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' },
  { memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' },
  { memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' },
  { memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' },
];

Using this data, I should print the hierarchy by level. Result example:

Tony Soprano
John Doe -> Tony Soprano
Deena Duarte -> Tony Soprano
Shawn Huynh -> Tony Soprano
Daniel Thorpe -> John Doe -> Tony Soprano

I did it this way:

const printHierarchy = hierarchy => {
  hierarchy.sort((memberA, memberB) => memberA.level - memberB.level);

  const hierarchyObj = {};

  for (let member of hierarchy) {
    const { name, memberId, parentMemberId } = member;
    hierarchyObj[memberId] = name;

    if (hierarchyObj[parentMemberId] != undefined) {
      hierarchyObj[memberId] += ` -> ${hierarchyObj[parentMemberId]}`;
    }
  }

  for (let member of hierarchy) {
    const { memberId } = member;
    console.log(hierarchyObj[memberId]);
  }
}

const hierarchy = [
  { memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' },
  { memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' },
  { memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' },
  { memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' },
  { memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' },
  { memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' },
  { memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' },
  { memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' },
  { memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' },
  { memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' },
];
printHierarchy(hierarchy);

.as-console-wrapper { min-height: 100%!important; top: 0; }

The manager said this works great, but added:

"If the array would contain 100,000 elements, would you still use the iterative solution? if not, what would you do?"

I can't really find a better way. What am I missing? We do need to loop to sort.

@flow24 ... How does the manager want to go through a list at least once without iterating it? Performance is something one should have in mind when choosing an approach and implementing it. But performance optimization is something one does not touch until one runs into performance problems. — Peter Seliger, May 15 '22 at 13:33
@flow24 ... thus said, the only candidate for (edge) performance optimization I spot in the OP's code is the concatenation of the name path via the addition assignment operator / `+=`. I would push names into an array and then `join` them e.g. via `join(' -> ')`. — Peter Seliger, May 15 '22 at 13:42
@flow24 ... just out of own curiosity and as proof that one more/less iteration cycle does not likewise contribute to performance losses/gains ... https://jsbench.me/v4l37gntiz/1 — Peter Seliger, May 15 '22 at 15:41
@PeterSeliger brilliant. Can you explain why the changes you made to the original gave such a performance boost? i'm curious to learn — flow24, May 15 '22 at 16:11
@flow24 - I followed my gut feeling and it turned out ...pushing an item's final string directly into a result array and later iterating (`forEach`) this array for logging purposes apparently is cheaper than the (inner) `for...of` loop with an additional object based lookup for each iteration step. But again ...it also depends on the client's js-engine, and the performance test can show much different results for a much grater amount of data. That's another reason for doing performance optimization only in case one runs into issues. I always try to not mix data creation and presentation tasks. — Peter Seliger, May 15 '22 at 16:32
Speaking of optimizations, @Peter: I don't know if your change to a function statement had anything to do with optimization; if so, I doubt it has any significant effect. In fact, in my one run in a single browser of a version more like the original function expression (at https://jsbench.me/orl38tuppa/1), the function expression version was fastest. — Scott Sauyet, May 16 '22 at 14:38

Nina Scholz · Answer 1 · 2022-05-15T11:53:24.340

You could build a tree and then print all names of the tree.

This approach does not need sorted data.

const
    getTree = (data, id, parent, children, root) => {
        const t = {};
        data.forEach(o => ((t[o[parent]] ??= {})[children] ??= []).push(Object.assign(t[o[id]] ??= {}, o)));
        return t[root][children];
    },
    print = (parents = []) => ({ name, children = [] }) => {
        const p = [name, ...parents];
        console.log(p.join(' -> '));
        children.forEach(print(p));
    },
    hierarchy = [{ memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' }, { memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' }, { memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' }, { memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' }, { memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' }, { memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' }, { memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' }, { memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' }, { memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' }, { memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' }],
    tree = getTree(hierarchy, 'memberId', 'parentMemberId', 'children', 0);
    
tree.forEach(print());

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

By the way, regardless of the sort - is this solution more efficient to a large array? If so why? (The absence of two loops?) — flow24, May 15 '22 at 13:51

Peter Seliger · Answer 2 · 2022-05-15T19:45:33.263

The next provided approach is based mainly on a single sort and a map task.

In a first intermediate step one would create a Map based lookup for memberId based member items.

Then one creates a sorted list of member items which already resemble the final member precedence for it compares and sorts member items by both properties, level (top level category) and memberId (2nd level category).

The final mapping task iterates the sorted list of member items, for each item, into a string based graph of hierarchical ordered member names. It does so by aggregating, for each item, a list of related hierarchical member names while looking up the always next parent member until no parent is/was found.

function getSortedListOfMemberHirarchyGraphs(memberList) {
  // create a `memberId` based map of member items for looking it up.
  const memberLookup = new Map(
    memberList.map(item => [item.memberId, item])
  );

  return Array
    // 1) compare and sort hierarchy levels descending.

    // create shallow copy of `memberList` in order to not mutate it.
    .from(memberList)
    // - top level category: `level`
    // - 2nd level category: `memberId`
    .sort((a, b) => (a.level - b.level) || (a.memberId - b.memberId))

    // 2) map sorted list of member items ...
    .map(({parentMemberId, name}) => {

      let nameList = [name];
      let parentMember;

      // 2a) ... while aggregating for each member's name ... 
      while (parentMember = memberLookup.get(parentMemberId)) {
        parentMemberId = parentMember.parentMemberId;

        // 2b) ... a list of related hierarchical member names ...
        nameList.push(parentMember.name);
      }
      // 2c) ... into a graph of hierarchical member names.
      return nameList.join(' => ');
    });
}

const hierarchy = [
  { memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' },
  { memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' },
  { memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' },
  { memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' },
  { memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' },
  { memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' },
  { memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' },
  { memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' },
  { memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' },
  { memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' },
];
console.log(
  getSortedListOfMemberHirarchyGraphs(hierarchy)
);
console.log(
  getSortedListOfMemberHirarchyGraphs(hierarchy)
    .join('\n')
);
getSortedListOfMemberHirarchyGraphs(hierarchy)
  .forEach(graph => console.log(graph));

.as-console-wrapper { min-height: 100%!important; top: 0; }

The above implementation again without comments ...

function getSortedListOfMemberHirarchyGraphs(memberList) {
  const memberLookup = new Map(
    memberList.map(item => [item.memberId, item])
  );
  return Array
    .from(memberList)
    .sort((a, b) => (a.level - b.level) || (a.memberId - b.memberId))
    .map(({parentMemberId, name}) => {

      let nameList = [name];
      let parentMember;

      while (parentMember = memberLookup.get(parentMemberId)) {
        parentMemberId = parentMember.parentMemberId;

        nameList.push(parentMember.name);
      }
      return nameList.join(' => ');
    });
}

The above approach with the next provided 2nd code refactoring does not map twice (creating the lookup and mapping the list); it instead directly reduces the hierarchically ordered member list which allows for the programmatic aggregation of the member lookup (the one necessary for creating a member item's name-path).

function getSortedListOfMemberHirarchyGraphs(memberList) {
  function collectMemberNameGraph(collector, item) {

    const { memberLookup, result } = collector;
    let { memberId, parentMemberId, name } = item;

    memberLookup.set(memberId, item);

    const nameList = [name];
    let parentMember;

    while (parentMember = memberLookup.get(parentMemberId)) {
      parentMemberId = parentMember.parentMemberId;

      nameList.push(parentMember.name);
    }
    result.push(nameList.join(' => '));

    return collector;
  }
  return memberList
    // skip creation of a shallow `memberList`
    // copy and don't care about `sort` mutation.

    .sort((a, b) => (a.level - b.level) || (a.memberId - b.memberId))
    .reduce(collectMemberNameGraph, {

      memberLookup: new Map,
      result: [],

    }).result;
}

const hierarchy = [
  { memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' },
  { memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' },
  { memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' },
  { memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' },
  { memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' },
  { memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' },
  { memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' },
  { memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' },
  { memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' },
  { memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' },
];
console.log(
  getSortedListOfMemberHirarchyGraphs(hierarchy)
);
console.log(
  getSortedListOfMemberHirarchyGraphs(hierarchy)
    .join('\n')
);
getSortedListOfMemberHirarchyGraphs(hierarchy)
  .forEach(graph => console.log(graph));

.as-console-wrapper { min-height: 100%!important; top: 0; }

score 0 · Answer 3 · answered May 17 '22 at 17:18

Here is a solution that produces exactly the output OP wanted. It builds on the following assumptions:

the memberId property of each object in the hierarchy array is actually redundant as it corresponds directly with the index+1 of the object in the array,
a parentMemberId==0 signals there is no parent to that element.

const h = hierarchy = [{ memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe' }, { memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe' }, { memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez' }, { memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee' }, { memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte' }, { memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines' }, { memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements' }, { memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano' }, { memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh' }, { memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh' }];

function add2Array(el, arr = []) {
  const [k, v] = Object.entries(el)[0];
  arr.push(k)
  if (typeof v == "object") add2Array(v, arr)
  return arr
}
function ancestors(h) {
  h.forEach(el => { if (el.parentMemberId) el.parent = h[el.parentMemberId - 1] })
  h.forEach(el => {
    el[el.name] = el.parent || "";
    ["memberId", "parentMemberId", "level", "name", "parent"].forEach(p => delete el[p]);
  });
  return h.map(e => add2Array(e)).sort((a, b) =>
    a.length - b.length || a[0].localeCompare(b[0]));
}

const res = ancestors(hierarchy);
console.log(res.map(e =>e.join("->")).join("\n"));

.as-console-wrapper {
  max-height: 100% !important;
  top: 0;
}

score 0 · Answer 4 · answered May 17 '22 at 20:35

I would choose to break this down a bit. First, I would convert that flat list into a tree (or really a forest, as there is no guarantee of a single root.) Then I would do a breadth-first scan of the structure, capturing the node along with its ancestors into an array. Then my main function would extract the names and reverse each ancestry, adding the arrows between nodes. Here's one version:

const nest = (xs, id = 0) => xs
  .filter ((x) => x .parentMemberId == id) 
  .map (({memberId, parentMemberId, children = nest (xs, memberId), ...rest}) => ({
    memberId, ...rest, ... (children .length ? {children} : {})
  }))

const breadthFirst = (xs) => 
  xs .length == 0 ? [] : [
    ... xs .map (x => [x]), 
    ... xs .flatMap (x => breadthFirst (x .children || []) .map (ns => [x, ...ns]))
  ]

const display = (xs) => 
  breadthFirst (nest (xs)) .map (xs => xs .map (x => x .name) .reverse () .join (' --> ')) .join ('\n')

const hierarchy = [{memberId: 1, parentMemberId: 8, level: 2, name: 'John Doe'}, {memberId: 2, parentMemberId: 1, level: 3, name: 'Daniel Thorpe'}, {memberId: 3, parentMemberId: 5, level: 3, name: 'David Suarez'}, {memberId: 4, parentMemberId: 5, level: 3, name: 'Felix Mcgee'}, {memberId: 5, parentMemberId: 8, level: 2, name: 'Deena Duarte'}, {memberId: 6, parentMemberId: 3, level: 4, name: 'Ron Gaines'}, {memberId: 7, parentMemberId: 9, level: 5, name: 'Kellie Clements'}, {memberId: 8, parentMemberId: 0, level: 1, name: 'Tony Soprano'}, {memberId: 9, parentMemberId: 3, level: 4, name: 'John Kavanagh'}, {memberId: 10, parentMemberId: 8, level: 2, name: 'Shawn Huynh'}]


console .log (display (hierarchy))

Here nest will turn your input into something like this:

[
  {memberId: 8, level: 1, name: "Tony Soprano", children: [
    {memberId: 1, level: 2, name: "John Doe", children: [
      {memberId: 2, level: 3, name: "Daniel Thorpe"}
    ]},
    {memberId: 5, level: 2, name: "Deena Duarte", children: [
      {memberId: 3, level: 3, name: "David Suarez", children: [
        {memberId: 6, level: 4, name: "Ron Gaines"},
        {memberId: 9, level: 4, name: "John Kavanagh", children: [
          {memberId: 7, level: 5, name: "Kellie Clements"}
        ]}
      ]},
      {memberId: 4, level: 3, name: "Felix Mcgee"}
    ]},
    {memberId: 10, level: 2, name: "Shawn Huynh"}
  ]}
]

And then a very generic breadthFirst will convert that to

[
  [{name: "Tony Soprano", /* ... */}],
  [{name: "Tony Soprano", /* ... */}, {name: "John Doe", /* ... */}],
  [{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}],
  [{name: "Tony Soprano", /* ... */}, {name: "Shawn Huynh", /* ... */}],
  [{name: "Tony Soprano", /* ... */}, {name: "John Doe", /* ... */}, {name: "Daniel Thorpe", /* ... */}],
  [{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "David Suarez", /* ... */}],
  [{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "Felix Mcgee", /* ... */}],
  [{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "David Suarez", /* ... */}, {name: "Ron Gaines", /* ... */}],
  [{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "David Suarez", /* ... */}, {name: "John Kavanagh", /* ... */}],
  [{name: "Tony Soprano", /* ... */}, {name: "Deena Duarte", /* ... */}, {name: "David Suarez", /* ... */}, {name: "John Kavanagh", /* ... */},{name: "Kellie Clements", /* ... */}]
]

Finally, display just converts those arrays to simple arrow-separated (reversed) lists of names.

nest could be built instead atop a more generic forest function as described in another answer, like this:

const forest = (build, isChild, root) => (xs) => 
  xs .filter (x => isChild (root, x))
     .map (node => build (node, root => forest (build, isChild, root) (xs)))
    
const nest = forest (
  ({memberId, parentMemberId, ...rest}, f) => ({memberId, parentMemberId, ...rest, children: f (memberId)}),
  (id, x) => x .parentMemberId == id,
  0
)

A better solution to hierarchy sorting question (JavaScript)

4 Answers4