FastPrepTree Nodes with Zero or One Parent

Tree Nodes with Zero or One Parent

Wayfair logoWayfair● EasyFULLTIMEPHONE SCREEN
Learn

Problem statement

Each row of pairs is [parent,child]. Return the represented nodes with no direct parents and those with exactly one direct parent. Count immediate parents rather than every ancestor.

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

For this exercise, assume the result is exactly [roots,nodesWithOneParent], with both rows sorted by increasing numeric ID. Empty pairs represent an empty tree and return [[],[]]. Do not change the input.

Function

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

Examples

Example 1

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

Authored example: node 8 is the root. Nodes 2,5,9 each have one direct parent, even though node 5 has two ancestors.

Example 2

pairs = [[4,1],[4,1],[1,7]]return = [[4],[1,7]]

Authored example: the repeated 4-to-1 record is one relationship. Node 4 has no parent; nodes 1 and 7 each have one.

Example 3

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

Authored example: no represented nodes give two empty groups.

Constraints

  • For this exercise, assume 0 <= pairs.length <= 1000.
  • Each row has exactly two positive integer IDs, each at most 10^9.
  • After duplicate pairs are ignored, nonempty input forms one connected rooted tree. Separate isolated nodes are not encoded by this interface.

More Wayfair problems

See Wayfair 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…