How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

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.

You are given genealogy information for a set of chickens as a list of parent-child pairs `relations`, where each pair `(p, c)` means `p` is a parent of `c`. The data may describe multiple independent family groups (a forest), a chicken may have 0, 1, or 2 parents, and either query node may not appear in `relations` at all. Given two chicken IDs `a` and `b`, return `true` if they are **blood-related**, otherwise `false`. Two chickens are blood-related if they belong to the same family lineage, meaning either one is an ancestor/descendant of the other, OR they share at least one common ancestor — equivalently, they fall in the same connected component when each parent-child pair is treated as an undirected edge. Your solution must not infinite-loop even if the input contains a cycle (an invalid genealogy). Example — 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)

Constraints

0 <= len(relations) <= 10^5
Each relation is a pair (p, c) of integer chicken IDs.
Either a or b may be absent from relations; if so the answer is False unless a == b.
Input may contain cycles (invalid genealogy); the solution must terminate.
Treat parent-child edges as undirected when forming family components.

Examples

Input: ([(1, 2), (1, 3), (3, 4), (10, 11)], 2, 4)

Expected Output: True

Explanation: 2 and 4 both descend from 1, so they share a common ancestor and are in the same component.

Input: ([(1, 2), (1, 3), (3, 4), (10, 11)], 2, 11)

Expected Output: False

Explanation: 2 is in the {1,2,3,4} family while 11 is in the separate {10,11} family — different components.

Input: ([(1, 2), (1, 3), (3, 4), (10, 11)], 3, 4)

Expected Output: True

Explanation: 3 is the direct parent of 4 (ancestor/descendant), so they are blood-related.

Input: ([(1, 2), (1, 3), (3, 4), (10, 11)], 5, 6)

Expected Output: False

Explanation: Neither 5 nor 6 appears in any relation, so neither belongs to a known family component.

Input: ([], 1, 2)

Expected Output: False

Explanation: With no relations, no chicken has a recorded family; 1 and 2 are unrelated.

Input: ([(1, 2)], 1, 1)

Expected Output: True

Explanation: A chicken is trivially related to itself (a == b) regardless of the relations.

Input: ([(1, 2), (2, 1)], 1, 2)

Expected Output: True

Explanation: Cyclic/invalid input: edges (1,2) and (2,1) still place 1 and 2 in one component, and the union-find loop terminates without hanging.

Input: ([(1, 2), (3, 4), (5, 6)], 2, 6)

Expected Output: False

Explanation: Three disjoint families; 2 is in {1,2} and 6 is in {5,6}, so they are not related.

Input: ([(1, 2), (2, 3), (4, 3)], 1, 4)

Expected Output: True

Explanation: Node 3 has two parents (2 and 4), linking the 1->2->3 lineage with 4, so 1 and 4 end up in the same component.

Input: ([(-1, -2), (-2, -3)], -1, -3)

Expected Output: True

Explanation: Negative IDs are handled the same way; -1 is an ancestor of -3 through -2.

Hints

Direction does not matter for 'same lineage' — model each (parent, child) pair as an undirected edge and ask whether a and b land in the same connected component.
Union-Find (disjoint set union) handles this cleanly: union every pair, then check whether find(a) == find(b). Path compression keeps it near-linear and avoids the infinite-loop risk of naive graph traversal on cyclic input.
Handle the edge cases explicitly: a == b is trivially True; if a or b never appears in any relation, return False (an isolated chicken shares no ancestry).

Quick Overview

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