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.