How should I practice Common Ancestors in a Directed Acyclic Graph?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Rippling phone screen problems in FastPrep.

Is Common Ancestors in a Directed Acyclic Graph associated with Rippling?

FastPrep tags this as a Rippling phone screen coding practice problem when the problem catalog has that company and stage context.

Common Ancestors in a Directed Acyclic Graph

Rippling● MediumFULLTIMEPHONE SCREEN

Learn

Problem statement

Nodes are labeled from 0 through nodeCount - 1. Each row [parent, child] in parentEdges is a directed parent relationship, and the graph is acyclic.

Return every strict ancestor of both first and second, sorted increasingly. A node is not its own ancestor.

Function

commonAncestors(nodeCount: int, parentEdges: int[][], first: int, second: int) → int[]

Examples

Example 1

nodeCount = 6parentEdges = [[0,2],[1,2],[1,3],[2,4],[3,4],[4,5]]first = 4second = 5return = [0,1,2,3]

Every ancestor of 4 is also an ancestor of 5.

Example 2

nodeCount = 5parentEdges = [[0,2],[1,2],[1,3]]first = 2second = 3return = [1]

Node 1 reaches both targets.

Example 3

nodeCount = 4parentEdges = [[0,1],[2,3]]first = 1second = 3return = []

The targets are in disconnected components.

Constraints

1 <= nodeCount <= 10^5.
0 <= parentEdges.length <= 2 * 10^5.
The edges form a directed acyclic graph and contain no duplicates.