FastPrepDo Two Nodes Share a Proper Ancestor?

Do Two Nodes Share a Proper Ancestor?

Compass International Holdings logoCompass International Holdings● MediumFULLTIMEOA
Learn

Problem statement

Each row of pairs is [parent,child]. Given node IDs a and b, return whether they share at least one ancestor.

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.

Return true when the proper-ancestor sets intersect and false otherwise.

Function

hasSharedAncestor(pairs: int[][], a: int, b: int) → boolean

Examples

Example 1

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

The relation list is the original sourceQ1 sample; these authored query nodes share proper ancestor4.

Example 2

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

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 boolean hasSharedAncestor(int[][] pairs, int a, int b) {
    // Write your code here.
    return false;
}
pairs[[1,3],[2,3],[4,2],[4,7]]
a2
b7
expectedtrue
Checking account…