FastPrepNodes With Zero or One Parent

Nodes With Zero or One Parent

Karat logoKarat● EasyFULLTIMEPHONE SCREEN
Learn

Problem statement

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

For this exercise, assume a directed acyclic graph that permits several parents; repeated copies of a pair count as one relationship. Only IDs appearing in pairs are represented.

For this exercise, assume exactly two rows [roots,nodesWithOneParent], each in increasing numeric order. Empty input returns [[],[]].

Function

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

Examples

Example 1

pairs = [[10,30],[20,30],[40,20],[40,70]]return = [[10,40],[20,70]]

This authored graph has roots 10 and 40, with one-parent nodes 20 and 70. Node30 has two parents.

Example 2

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

These authored groups count direct parents rather than all preceding generations.

Constraints

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

More Karat problems

See Karat hiring insights
public int[][] findParentGroups(int[][] pairs) {
    // Write your code here.
    return new int[0][0];
}
pairs[[10,30],[20,30],[40,20],[40,70]]
expected[[10,40],[20,70]]
Checking account…