parents-noparents.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   9

Write a function that takes this data as input and returns two collections: one containing all individuals with zero known parents, and one containing all individuals with exactly one known parent.

Sample output:
Zero parents: 1, 2, 4
One parent: 5, 7, 8, 9


Below is some sample data in JavaScript and Java. Feel free to solve this problem in any language of your choice.


// JavaScript
var parentChildPairs = [
    [1, 3], [2, 3], [3, 6], [5, 6],
    [5, 7], [4, 5], [4, 8], [8, 9]
];

 ***/

/***
 * Not sure if this the most efficient but it gets us there
 **/ 
function showRelations(A) {
	var cMap = {};
	var size = A.length;
	
	for(let i = 0; i < size; i++) {
		let [p,c] = A[i];
		if(!cMap[c]) { cMap[c] = 1; } else { cMap[c] += 1; }
	}
	
	for(let i = 0; i < size; i++) {
		let [p] = A[i];
		if(!cMap[p]) { cMap[p] = 0; };
	}
	let noparent = [], oneparent = [];

	for(k in cMap) {
		let z = (cMap[k] === 0), o = (cMap[k] === 1);
		if(z) noparent.push(+k);
		if(o) oneparent.push(+k);
	}
	return {noparent, oneparent};
}

Here's my own attempt in C++ , this seems to be a popular interview question recently... given by the Karat company at least twice

#include iostream
#include string
#include vector
#include algorithm
#include list

using namespace std;

/*
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 positive 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 15
\ / / | \ /
3 5 8 9
\ / \
6 7 11

Sample input/output (pseudodata):

parentChildPairs = [
(1, 3), (2, 3), (3, 6), (5, 6), (15, 9),
(5, 7), (4, 5), (4, 8), (4, 9), (9, 11)
]

Write a function that takes this data as input and returns two collections: one containing all individuals
with zero known parents, and one containing all individuals with exactly one known parent.

Output may be in any order:

findNodesWithZeroAndOneParents(parentChildPairs) => [
[1, 2, 4, 15], // Individuals with zero parents
[5, 7, 8, 11] // Individuals with exactly one parent
]

n: number of pairs in the input

*/

struct collection {
std::list zero_parents;
std::list one_parent;
} results;

//
// Updates our global structure containing two std::lists
// - zero parents
// - one parent only
//
void findNodesWithZeroAndOneParents(vector<pair<int, int>>& vp) {

vector<pair<int, int>>::iterator itr = vp.begin();
list<int>::iterator v_itr;
list<int>::iterator d_itr;

for (auto& i : vp) {
    results.zero_parents.push_back(i.first);
    results.one_parent.push_back(i.second);
}
results.zero_parents.sort();
results.one_parent.sort();

// Remove duplicates from the one parent list
v_itr = results.one_parent.begin();
while (next(v_itr) != results.one_parent.end()) {
    results.zero_parents.remove(*v_itr);
    if (*v_itr == *(std::next(v_itr))) {
        d_itr = v_itr;
        while (*d_itr == *v_itr) {
            d_itr++;
        }
        results.one_parent.remove(*v_itr);
        v_itr = d_itr;
        continue;
    }
    v_itr++;
}
// Make zero parent list unique items only
results.zero_parents.unique();

}

void print_results() {

cout << "\n\nItems with one parent: \n";
for (auto& i : results.one_parent) {
    cout << "  " << i;
}
cout << "\n\nItems with zero parents: \n";
for (auto& i : results.zero_parents) {
    cout << "  " << i;
}
cout << "\n\n\n";

}

int main() {

vector<pair<int, int>> parent_child_pairs = {
  make_pair(1, 3),
  make_pair(2, 3),
  make_pair(3, 6),
  make_pair(5, 6),
  make_pair(15, 9),
  make_pair(5, 7),
  make_pair(4, 5),
  make_pair(4, 8),
  make_pair(4, 9),
  make_pair(9, 11),
};

findNodesWithZeroAndOneParents(parent_child_pairs);
print_results();
return 0;

}