FastPrepParent and Child Counts for Every Node

Parent and Child Counts for Every Node

Karat logoKarat● EasyFULLTIMEPHONE SCREEN
Learn

Problem statement

Each row of pairs is a directed relationship [parent,child]. Return a count of direct parents and direct children for every represented node.

For this exercise, assume a represented node is any ID appearing as either endpoint. Count distinct immediate neighbor IDs: repeated copies of a pair have no effect. These counts do not include more distant ancestors or descendants.

For this exercise, assume cycles and self-loops are allowed. A self-loop contributes one to both the parent count and child count of its node.

For this exercise, assume the result consists of rows [node,parentCount,childCount], sorted by increasing numeric node ID. Empty input returns an empty array.

Function

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

Examples

Example 1

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

Node 3 has two distinct direct parents and one direct child. Roots 1 and 2 still receive their own rows.

Example 2

pairs = [[7,9],[7,9],[9,7],[7,7]]return = [[7,2,2],[9,1,1]]

This authored cyclic graph counts each distinct relationship once; the self-loop contributes once to both degree columns of node 7.

Constraints

  • For this exercise, assume 0 <= pairs.length <= 1000.
  • Each row contains exactly two positive integer IDs, each at most 10^9.
  • Repeated records are permitted; counts use distinct directed relationships.

More Karat problems

See Karat hiring insights
public int[][] parentChildCounts(int[][] pairs) {
    // Write your code here.
    return new int[0][0];
}
pairs[[1,3],[2,3],[3,4]]
expected[[1,0,1],[2,0,1],[3,2,1],[4,1,0]]
Checking account…