FastPrepDo Two Nodes Share a Proper Ancestor?

Do Two Nodes Share a Proper Ancestor?

Karat logoKarat● EasyFULLTIMEPHONE SCREEN
Learn

Problem statement

Each row of pairs is [parent,child]. Return whether node IDs a and b share a proper ancestor: a node reached by one or more steps toward parents.

A query node never counts as its own ancestor. If one query is a parent of the other, it can share an earlier ancestor only when it has a parent of its own; a root query has no proper ancestor.

For this exercise, assume a directed acyclic graph that permits several parents; repeated copies of a pair count as one relationship. Only IDs appearing in pairs are represented.

For this exercise, assume equal query IDs are allowed and a query absent from all pairs has no ancestors. Return true exactly when their proper-ancestor sets intersect.

Function

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

Examples

Example 1

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

This authored root/child query returns false: query1 is not its own ancestor, so no earlier common ancestor exists.

Example 2

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

This authored query returns true because node1 is a proper ancestor of both query2 and query3, matching the reported corner-case rule.

Constraints

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

More Karat problems

See Karat hiring insights
public boolean shareProperAncestor(int[][] pairs,int a,int b) {
    // Write your code here.
    return false;
}
pairs[[1,2]]
a1
b2
expectedfalse
Checking account…