PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches
|Home/Coding & Algorithms/Google

Determine whether two nodes are related

Last updated: Mar 29, 2026

Quick Overview

This question evaluates understanding of graph representations, reachability and connectivity concepts for ancestry relationships, including handling disconnected components and potential cycles.

  • medium
  • Google
  • Coding & Algorithms
  • Software Engineer

Determine whether two nodes are related

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given genealogy information for a set of chickens. The data consists of **parent → child** relationships (e.g., `(parentId, childId)` pairs). Not every chicken necessarily appears in every role, and the data may describe multiple independent family groups. Write a function that, given two chicken IDs `a` and `b`, determines whether they have a **blood relationship**. For this interview question, treat two chickens as “blood-related” if **they belong to the same family lineage**, meaning: - one is an ancestor/descendant of the other, **or** - they share at least one common ancestor (i.e., they are in the same connected family component). ## Input / Output - **Input:** - A list of parent-child pairs `relations`, where each pair `(p, c)` indicates `p` is a parent of `c`. - Two chicken IDs `a` and `b`. - **Output:** - Return `true` if `a` and `b` are blood-related under the definition above, otherwise `false`. ## Notes / Edge cases to consider - Either `a` or `b` may not appear in `relations`. - There may be multiple roots (a forest). - A chicken may have 0, 1, or 2 parents depending on the dataset. - Clarify/handle whether the input could contain cycles (invalid genealogy); your solution should not infinite-loop if it does. ## Example Given relations: `(1,2), (1,3), (3,4), (10,11)`: - Query `(2,4)` → `true` (share ancestor `1`) - Query `(2,11)` → `false` (different family groups) - Query `(3,4)` → `true` (ancestor/descendant)

Quick Answer: This question evaluates understanding of graph representations, reachability and connectivity concepts for ancestry relationships, including handling disconnected components and potential cycles.

Related Interview Questions

  • Solve Flower Placement and Directory Deletion - Google (medium)
  • Compute Turnstile Crossing Times - Google (hard)
  • Simulate In-Place Cellular State Updates - Google (hard)
  • Determine Whether a Word Exists in a Graph - Google (medium)
  • Implement Checksums and Feature Rollout Evaluation - Google (medium)
Google logo
Google
Jan 22, 2026, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
22
0
Loading...

Problem

You are given genealogy information for a set of chickens. The data consists of parent → child relationships (e.g., (parentId, childId) pairs). Not every chicken necessarily appears in every role, and the data may describe multiple independent family groups.

Write a function that, given two chicken IDs a and b, determines whether they have a blood relationship.

For this interview question, treat two chickens as “blood-related” if they belong to the same family lineage, meaning:

  • one is an ancestor/descendant of the other, or
  • they share at least one common ancestor (i.e., they are in the same connected family component).

Input / Output

  • Input:
    • A list of parent-child pairs relations , where each pair (p, c) indicates p is a parent of c .
    • Two chicken IDs a and b .
  • Output:
    • Return true if a and b are blood-related under the definition above, otherwise false .

Notes / Edge cases to consider

  • Either a or b may not appear in relations .
  • There may be multiple roots (a forest).
  • A chicken may have 0, 1, or 2 parents depending on the dataset.
  • Clarify/handle whether the input could contain cycles (invalid genealogy); your solution should not infinite-loop if it does.

Example

Given relations: (1,2), (1,3), (3,4), (10,11):

  • Query (2,4) → true (share ancestor 1 )
  • Query (2,11) → false (different family groups)
  • Query (3,4) → true (ancestor/descendant)

Comments (0)

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Google•More Software Engineer•Google Software Engineer•Google Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.