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
– Peter Seliger, Commented May 15, 2022 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
– Peter Seliger, Commented May 15, 2022 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 ... jsbench.me/v4l37gntiz/1 — Peter Seliger
– Peter Seliger, Commented May 15, 2022 at 15:41
@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
– Peter Seliger, Commented May 15, 2022 at 16:32

Nina Scholz · Accepted Answer · 2022-05-15 11:53:24Z

1

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; }

edited May 15, 2022 at 11:53

answered May 15, 2022 at 11:22

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

flow24 Over a year ago

Thank you, but I do need the output to be sorted by levels.

flow24 Over a year ago

By the way, regardless of the sort - is this solution more efficient to a large array? If so why? (The absence of two loops?)

Peter Seliger · Accepted Answer · 2022-05-15 19:45:33Z

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; }

Carsten Massmann · Accepted Answer · 2022-05-17 17:18:09Z

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;
}

Scott Sauyet · Accepted Answer · 2022-05-17 20:35:32Z

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
)

Collectives™ on Stack Overflow

A better solution to hierarchy sorting question (JavaScript)

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related