Lowest Common Ancestors in a Parent DAG
Compass International Holdings● MediumFULLTIMEPHONE SCREENProblem statement
Each pair in pairs is [parent,child]. Return the lowest common ancestors of a and b in that directed graph.
For this exercise, assume the graph is acyclic and may give a node multiple parents. An ancestor reaches a node by following zero or more parent-to-child edges, so every represented node is its own ancestor. Only nodes appearing in a pair are represented; if either query is absent, return an empty array.
A common ancestor reaches both queries. It is lowest when no different common ancestor is its descendant. For this exercise, assume every lowest common ancestor is returned once in increasing numeric order. There may be several incomparable lowest choices. Equal represented queries are allowed, and duplicate pairs do not change the result.
Function
lowestCommonAncestors(pairs: int[][], a: int, b: int) → int[]Examples
Example 1
pairs = [[1,2],[2,3],[2,4],[4,5]]a = 3b = 5return = [2]This authored graph has common ancestors 1 and 2; only 2 is lowest.
Example 2
pairs = [[1,3],[2,3],[1,4],[2,4]]a = 3b = 4return = [1,2]This authored DAG has two incomparable lowest common ancestors, so the selected multiple-result interpretation returns both.
Example 3
pairs = [[9,5],[5,2]]a = 5b = 2return = [5]This authored fixture applies the declared reflexive rule: a query may be its own ancestor, so 5 is lowest.
Constraints
- For this exercise, assume
0 <= pairs.length <= 500and at most 200 distinct labels occur in pairs. - Every row has exactly two integers. For this exercise, assume all labels and query IDs are from
0through1000000. - For this exercise, assume there is no directed cycle; pairs may be unordered or repeated.