Do Two People Share a Strict Ancestor?
Updated
Problem statement
Each pair [parent, child] in parentChildPairs records one directed parent-to-child relationship. The graph has no cycles. A person may have multiple parents and any number of children; integer IDs need not be consecutive.
Given two different people, personA and personB, return whether they share at least one strict ancestor. An ancestor is reachable by following one or more parent links upward. A person is not their own ancestor. The shared ancestor may be any number of generations away from either person, and the two distances may differ.
If either person has no recorded parent, return false. For this exercise, assume an ID absent from the relationship pairs has no recorded ancestors, and repeated copies of a relationship have no additional effect.
Function
hasCommonAncestor(parentChildPairs: int[][], personA: int, personB: int) → booleanExamples
Example 1
parentChildPairs = [[1,3],[2,3],[3,6],[4,5],[4,8],[5,6],[5,7],[8,9]]personA = 3personB = 8return = falseThe strict ancestors of 3 are 1 and 2. The only strict ancestor of 8 is 4. These sets do not overlap, so the result is false.
Example 2
parentChildPairs = [[1,3],[2,3],[3,6],[4,5],[4,8],[5,6],[5,7],[8,9]]personA = 6personB = 8return = truePerson 4 is an ancestor of 6 through 4 → 5 → 6, and an ancestor of 8 through 4 → 8. The generation distances differ, but the shared ancestor still makes the result true.
Constraints
- For this exercise, assume
0 <= parentChildPairs.length <= 2000. - Every pair contains exactly two IDs. Every ID, including personA and personB, is an integer from 0 to 10^9.
- Pair endpoints differ, personA differs from personB, and the directed relationship graph is acyclic.
More Intuit Online Assessment questions
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Shortest Path from an Encoded GraphOA · Seen Sep 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
- Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
- Submask Sum QueriesOA · Seen Sep 2026
Similar questions at other companies
- Do Two Nodes Share a Proper Ancestor?Compass International Holdings · OACompass International Holdings interview questions
- Evolving Merchant Clusters and Persistent PinsStripe · OAStripe interview questions
- Package Install OrderVerily · ONSITE INTERVIEW
- Task Build Order and File-Change RerunsVanta · PHONE SCREEN
- Resolve Variable Equations with Dependency ErrorsApplied Intuition · PHONE SCREENApplied Intuition interview questions
- Nested Substitutions with Cycle DetectionKikoff · PHONE SCREENKikoff interview questions
- Validate and Resolve Evaluation ChainsPlaid · PHONE SCREEN · ONSITE INTERVIEWPlaid interview questions
- Page Referrer ReachabilityAmazon · ONSITE INTERVIEW
- Route Graph Reachability with a Broken LinkFigma · PHONE SCREENFigma interview questions
- Root of the Largest TreeGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions