FastPrepAncestor and Descendant Counts in a DAG

Ancestor and Descendant Counts in a DAG

Google logoGoogle● HardNEW GRADONSITE INTERVIEW
Learn

Problem statement

You are given a directed acyclic graph with vertices 0 through n-1.

For every vertex, count its distinct ancestors and its distinct descendants. An ancestor reaches the vertex through one or more directed edges; a descendant is reachable from it through one or more edges.

Return an n x 2 matrix where row i is [ancestorCount, descendantCount]. Duplicate edges have no additional effect.

Function

countAncestorsAndDescendants(n: int, edges: int[][]) → int[][]

Examples

Example 1

n = 4edges = [[0,1],[0,2],[1,3],[2,3]]return = [[0,3],[1,1],[1,1],[3,0]]

Vertex 0 reaches all others; vertex 3 is reached by all earlier vertices.

Example 2

n = 3edges = []return = [[0,0],[0,0],[0,0]]

An edgeless DAG has no nontrivial reachability.

Example 3

n = 3edges = [[0,1],[1,2],[0,2]]return = [[0,2],[1,1],[2,0]]

Reachability is counted by distinct vertices, so the direct and indirect paths from 0 to 2 count once.

Constraints

  • 1 <= n <= 500.
  • 0 <= edges.length <= 10000.
  • Every edge contains two distinct valid vertices and the graph is acyclic.

More Google problems

See Google hiring insights
public int[][] countAncestorsAndDescendants(int n, int[][] edges) {
    // Write your code here.
}
n4
edges[[0,1],[0,2],[1,3],[2,3]]
expected[[0,3],[1,1],[1,1],[3,0]]
Checking account…