FastPrepZero or One Parent Groups in a Tree

Zero or One Parent Groups in a Tree

Intuit logoIntuit● EasyNEW GRADPHONE SCREEN
Learn

Problem statement

Each row of pairs is [parent,child]. Return the represented nodes with no direct parents and the represented nodes with exactly one direct parent.

For this exercise, assume the unique relationships form one rooted tree when nonempty: they are connected, acyclic, and each non-root node has exactly one parent. Repeated copies of an edge have no effect. Only IDs appearing in a pair are represented; empty input represents an empty tree.

For this exercise, assume the result is exactly [roots,nodesWithOneParent], with each row sorted by increasing numeric ID. Empty input returns [[],[]].

Function

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

Examples

Example 1

pairs = [[8,2],[8,9],[2,5]]return = [[8],[2,5,9]]

This authored rooted tree has root 8 and one-parent nodes 2,5,9.

Example 2

pairs = []return = [[],[]]

The authored empty representation returns two empty groups; no separate isolated-node list is supplied.

Constraints

  • For this exercise, assume 0 <= pairs.length <= 1000.
  • Each row contains two positive integer IDs, each at most 10^9.
  • After duplicate edges are ignored, nonempty input represents one rooted tree.

More Intuit problems

See Intuit hiring insights
public int[][] findTreeParentGroups(int[][] pairs) {
    // Write your code here.
    return new int[0][0];
}
pairs[[8,2],[8,9],[2,5]]
expected[[8],[2,5,9]]
Checking account…