FastPrepAll Common Ancestors in a Parent Graph

All Common Ancestors in a Parent Graph

Compass International Holdings logoCompass International Holdings● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Each row of pairs is [parent,child]. Given node IDs a and b, return all their common ancestors.

For this exercise, assume a proper ancestor is a node reached by one or more steps toward parents. A node is not its own ancestor. Equal query IDs are allowed; a query absent from all pairs has no ancestors.

For this exercise, assume relationships form a directed acyclic graph that permits several parents and duplicate pairs have no effect.

For this exercise, assume every common ancestor is returned once in increasing numeric ID order. Return an empty array if there is none. Return all shared generations; do not reduce the answer to lowest common ancestors.

Function

allCommonAncestors(pairs: int[][], a: int, b: int) → int[]

Examples

Example 1

pairs = [[1,2],[1,3],[2,4],[3,4],[2,5],[3,5]]a = 4b = 5return = [1,2,3]

This query and expected result are authored; all common ancestors are returned, including higher generations.

Example 2

pairs = [[1,2],[2,3]]a = 1b = 3return = []

This authored query has no shared proper ancestor: root1 is not its own ancestor.

Constraints

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

More Compass International Holdings problems

See Compass International Holdings hiring insights
public int[] allCommonAncestors(int[][] pairs, int a, int b) {
    // Write your code here.
    return new int[0];
}
pairs[[1,2],[1,3],[2,4],[3,4],[2,5],[3,5]]
a4
b5
expected[1,2,3]
Checking account…