FastPrepCommon Ancestors in a Directed Acyclic Graph
Problems/Common Ancestors in a Directed Acyclic Graph

Common Ancestors in a Directed Acyclic Graph

Rippling logoRippling● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report identifies a graph question about common ancestors but preserves no statement. The multi-parent DAG contract is the smallest general graph interpretation and matches the recognizable seed at about 76%.

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.

More Rippling problems

  • Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Dependency-Aware Task SchedulerPHONE SCREEN · Seen Nov 2026
  • Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
All Rippling interview questionsSee Rippling hiring insights
Saved
public int[] commonAncestors(int nodeCount, int[][] parentEdges, int first, int second) {
    // Write your solution here.
}
Checking account…