FastPrepNodes With Zero or Three Parents

Nodes With Zero or Three Parents

Compass International Holdings logoCompass International Holdings● EasyFULLTIMEPHONE SCREEN
Learn

Problem statement

Each row of pairs is [parent,child] and describes one directed parent-child relationship. Return all represented nodes with no direct parents and all represented nodes with exactly three distinct direct parents. Count direct parents, rather than all ancestors.

For this exercise, assume the relationships form a directed acyclic graph that permits multiple parents. Repeated copies of the same pair count as one relationship.

Return exactly two rows: [roots,nodesWithThreeParents]. For this exercise, assume each row is sorted by increasing numeric ID; only nodes appearing as a parent or child are represented, and empty input returns [[],[]].

Function

getRootAndNodesWithThreeParents(pairs: int[][]) → int[][]

Examples

Example 1

pairs = [[1,9],[2,9],[3,9],[9,10]]return = [[1,2,3],[9]]

Nodes 1, 2, 3 have no parents. Node 9 has exactly three distinct direct parents; node 10 has only one and is excluded from the second row. This sample is authored for practice.

Example 2

pairs = [[4,1],[4,2],[2,3]]return = [[4],[]]

Only direct parents are counted. Node 4 is a root; the remaining nodes each have one direct parent.

Constraints

  • For this exercise, assume 0 <= pairs.length <= 1000.
  • Every row contains exactly two positive integer IDs, each at most 10^9.
  • The directed relationships contain no cycles; duplicate pairs may appear.

More Compass International Holdings problems

See Compass International Holdings hiring insights
public int[][] getRootAndNodesWithThreeParents(int[][] pairs) {
    // Write your code here.
    return new int[0][0];
}
pairs[[1,9],[2,9],[3,9],[9,10]]
expected[[1,2,3],[9]]
Checking account…