FastPrepShared Ancestor of Two People
Problems/Shared Ancestor of Two People

Shared Ancestor of Two People

Indeed logoIndeed● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: In a Karat interview, the report gives the full task: decide whether two given people have any ancestor in common, in a family graph of parent and child pairs. Example 1 uses the report's own family graph.

A later Karat report asks the same question and describes the pairs as (child, parent). This version follows the full text, which gives (parent, child). The report does not say whether a person counts as their own ancestor, and it gives no limits. Here, nobody is their own ancestor, so a person with no parents shares no ancestor with anyone. The two people are different and both appear in the pairs, the family has no cycles, and the size limits are practice choices.

The judged task matches the report at about 95%.

You are given data about parents and children over several generations. Each entry of parentChildPairs is [parent, child], and every person has a unique integer ID.

An ancestor of a person is one of their parents, a parent of one of their parents, and so on up the family. A person is not their own ancestor.

Return true if person1 and person2 have at least one ancestor in common, and false otherwise.

For example, the pairs [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[9,11],[14,4],[13,12],[12,9]] describe this family, with parents above their children:

         14  13
         |   |
1   2    4   12
 \ /   / | \ /
  3   5  8  9
   \ / \     \
    6   7     11

Here 6 and 8 have the common ancestor 4.

Function

hasCommonAncestor(parentChildPairs: int[][], person1: int, person2: int) → boolean

Examples

Example 1

parentChildPairs = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[9,11],[14,4],[13,12],[12,9]]person1 = 6person2 = 8return = true

This is the family graph from the statement. The ancestors of 6 are 3, 5, 1, 2, 4 and 14. The ancestors of 8 are 4 and 14. Both lists contain 4 (and 14), so the answer is true.

Example 2

parentChildPairs = [[10,20],[10,30],[20,40],[30,40],[50,60]]person1 = 10person2 = 40return = false

10 is an ancestor of 40, but that alone is not enough. 10 has no parents, so it has no ancestors at all, and the two people cannot share one. The answer is false.

Example 3

parentChildPairs = [[10,20],[10,30],[20,40],[30,40],[50,60]]person1 = 20person2 = 30return = true

20 and 30 both have the parent 10, so 10 is an ancestor of both. The answer is true.

Constraints

  • 1 <= parentChildPairs.length <= 500
  • parentChildPairs[i].length == 2
  • 1 <= parentChildPairs[i][j] <= 10^5
  • parentChildPairs[i][0] != parentChildPairs[i][1], and no pair appears twice.
  • The pairs have no cycle: nobody is their own ancestor.
  • person1 != person2, and both appear in parentChildPairs.

More Indeed problems

  • Insert into an Unrolled Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Course Completion OrderPHONE SCREEN · Seen May 2025
  • Recipes You Can PreparePHONE SCREEN · Seen May 2025
All Indeed interview questionsSee Indeed hiring insights
Saved
class Solution {
    public boolean hasCommonAncestor(int[][] parentChildPairs, int person1, int person2) {
        // Write your code here.
    }
}
Checking account…