A better solution to hierarchy sorting question (JavaScript)-CodePudding

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.

CodePudding user response：

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

CodePudding user response：

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