demparent.js

// Suppose we have some input data describing a graph of relationships between parents and children over multiple generations. The data is formatted as a list of (parent, child) pairs, where each individual is assigned a unique integer identifier.

// For example, in this diagram, 3 is a child of 1 and 2, and 5 is a child of 4:
            
// 1   2   4
//  \ /   / \
//   3   5   8
//    \ / \   \
//     6   7   10


// Write a function that takes the graph, as well as two of the individuals in our dataset, as its inputs and returns true if and only if they share at least one ancestor.

// Sample input and output:
// hasCommonAncestor(parentChildPairs, 3, 8) => false
// hasCommonAncestor(parentChildPairs, 5, 8) => true
// hasCommonAncestor(parentChildPairs, 6, 8) => true
// hasCommonAncestor(parentChildPairs, 1, 3) => false




var parentChildPairs = [
    [1, 3], [2, 3], [3, 6], [5, 6],
    [5, 7], [4, 5], [4, 8], [8, 10]
];

// O (2N + M)
// Space complexity = 

const findNodesWithZeroAndOneParents = (parentChildPairs) => {
  const zeroParents = new Set();
  const oneParent = [];
  const parents = {} // key child, value: parents[]
  
  // For children
  parentChildPairs.forEach(([parent, child]) => {
    if (!parents[child]) {
      parents[child] = [parent];
    } else {
      parents[child].push(parent);  
    }
  });
  
  parentChildPairs.forEach(([parent, child]) => {
    if(!parents[parent]) {
      zeroParents.add(parent)
    }
  });
  
  for (let key in parents) {
    if (parents[key].length === 1) {
      oneParent.push(Number(key));
    }
  }
  
  console.log(parents);
  
  
  return [ [...zeroParents], oneParent ];
};


const getParentRelations = (parentChildPairs) => {
  const parents = {};
  
  parentChildPairs.forEach(([parent, child]) => {
    if (!parents[child]) {
      parents[child] = [parent];
    } else {
      parents[child].push(parent);  
    }
  });
  
  return parents;
};

const getParentChain = (parentsRel, child, chain) => {
  console.log('getParentChain', child, chain);
 if (!parentsRel[child]) {
  return chain;
 }

  if (parentsRel[child]) {
    const parents = parentsRel[child];
    
    return parents.map((parent) => {
      return getParentChain(parentsRel, parent, chain.push(parent))
    });
  }
  
}

const hasCommonAncestor = (parentChildPairs, child1, child2) => {
  const parents = getParentRelations(parentChildPairs);
  
  const child1Chain = getParentChain(parents, child1, []);
  const child2Chain = getParentChain(parents, child2, []);
  console.log(child1Chain);
  console.log(child2Chain);
  
  
}

console.log(hasCommonAncestor(parentChildPairs, 3, 8));
// console.log(findNodesWithZeroAndOneParents(parentChildPairs));