Check Whether Two People Are Blood Relatives in a Family Graph
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
A family graph records parent-child relationships between people. Write a function that decides whether two given people are blood relatives, meaning that they share at least one common ancestor.
The question resembles a common-ancestor question on a tree, but a family graph is not a tree: each person can have two recorded parents, there are many founders whose parents are unknown, and separate family lines join whenever two people from different lines have a child together.
### Function Signature
```python
def are_blood_relatives(relations: list[list[str]], a: str, b: str) -> bool:
```
### Rules
- `relations[i] = [parent, child]` records that `parent` is a parent of `child`.
- The ancestors of a person are the person themselves, their parents, their parents' parents, and so on up every recorded line.
- Return `True` if at least one person is an ancestor of both `a` and `b`, and `False` otherwise.
- Under this rule a person is related to their parents, grandparents, children, siblings, half-siblings, cousins, aunts and uncles. Two people linked only through a partner or a shared child, such as the two parents of a child who have no common ancestor themselves, are not related.
- A person who never appears as a child in `relations` has no recorded parents. `a` or `b` may not appear in `relations` at all; such a person's only ancestor is themselves.
### Constraints
- `0 <= len(relations) <= 10^5`
- Every name is a string of 1 to 20 ASCII letters or digits. Names are case-sensitive, and two different strings are two different people.
- A person appears as the child in at most two relations, no relation is listed twice, and no relation has `parent == child`.
- The relations contain no cycle: nobody is their own ancestor through one or more parent links.
- `a` and `b` follow the same name format, and `a != b`.
### Examples
**Example 1**
```text
Input: relations = [["Ann", "Cal"], ["Ben", "Cal"], ["Ann", "Dee"], ["Ben", "Dee"],
["Cal", "Eli"], ["Fay", "Eli"], ["Dee", "Gus"]]
a = "Eli", b = "Gus"
Output: True
```
Eli's ancestors are Eli, Cal, Fay, Ann and Ben; Gus's are Gus, Dee, Ann and Ben. Ann and Ben are ancestors of both, so Eli and Gus (first cousins) are related.
**Example 2**
```text
Input: relations = [["Ann", "Cal"], ["Ben", "Cal"], ["Ann", "Dee"], ["Ben", "Dee"],
["Cal", "Eli"], ["Fay", "Eli"], ["Dee", "Gus"]]
a = "Fay", b = "Cal"
Output: False
```
Fay has no recorded parents, so her only ancestor is herself; Cal's ancestors are Cal, Ann and Ben. Fay and Cal are the two parents of Eli but share no ancestor.
**Example 3**
```text
Input: relations = [["Ann", "Cal"], ["Ben", "Cal"], ["Ann", "Dee"], ["Ben", "Dee"],
["Cal", "Eli"], ["Fay", "Eli"], ["Dee", "Gus"]]
a = "Ann", b = "Gus"
Output: True
```
Ann counts as her own ancestor and is Gus's grandparent, so she is a common ancestor.
Overview: A graph coding question on a family graph given as parent-child pairs, where each person has up to two parents and there is no single root. Decide whether two people are blood relatives, meaning they share at least one common ancestor. It tests modeling a DAG, graph traversal and a precise definition of relatedness.
Read the full Amazon Software Engineer interview experience this question came from
A family graph records parent-child relationships between people. Given the list `relations` and two people `a` and `b`, decide whether `a` and `b` are blood relatives, meaning that they share at least one common ancestor.
This resembles a common-ancestor question on a tree, but a family graph is not a tree: each person can have two recorded parents, there are many founders whose parents are unknown, and separate family lines join whenever two people from different lines have a child together.
### Rules
- `relations[i] = [parent, child]` records that `parent` is a parent of `child`.
- The ancestors of a person are the person themselves, their parents, their parents' parents, and so on up every recorded line.
- Return `True` if at least one person is an ancestor of both `a` and `b`, and `False` otherwise.
- Under this rule a person is related to their parents, grandparents, children, siblings, half-siblings, cousins, aunts and uncles. Two people linked only through a partner or a shared child, such as the two parents of a child who have no common ancestor themselves, are not related.
- A person who never appears as a child in `relations` has no recorded parents. `a` or `b` may not appear in `relations` at all; such a person's only ancestor is themselves.
The answer is a single boolean (`True`/`False` in Python, `true`/`false` in JavaScript, Java and C++). Every input is a string or a list of string pairs, so no value can exceed 2^31 - 1.
### Constraints
- `0 <= len(relations) <= 10^5`
- Every name is a string of 1 to 20 ASCII letters or digits. Names are case-sensitive, and two different strings are two different people.
- A person appears as the child in at most two relations, no relation is listed twice, and no relation has `parent == child`.
- The relations contain no cycle: nobody is their own ancestor through one or more parent links.
- `a` and `b` follow the same name format, and `a != b`.
### Example 1
```text
Input: relations = [["Ann", "Cal"], ["Ben", "Cal"], ["Ann", "Dee"], ["Ben", "Dee"],
["Cal", "Eli"], ["Fay", "Eli"], ["Dee", "Gus"]]
a = "Eli", b = "Gus"
Output: True
```
Eli's ancestors are Eli, Cal, Fay, Ann and Ben; Gus's are Gus, Dee, Ann and Ben. Ann and Ben are ancestors of both, so Eli and Gus (first cousins) are related.
### Example 2
```text
Input: relations = [["Ann", "Cal"], ["Ben", "Cal"], ["Ann", "Dee"], ["Ben", "Dee"],
["Cal", "Eli"], ["Fay", "Eli"], ["Dee", "Gus"]]
a = "Fay", b = "Cal"
Output: False
```
Fay has no recorded parents, so her only ancestor is herself; Cal's ancestors are Cal, Ann and Ben. Fay and Cal are the two parents of Eli but share no ancestor.
Constraints
- 0 <= len(relations) <= 10^5
- relations[i] = [parent, child] records that parent is a parent of child.
- Every name is a string of 1 to 20 ASCII letters or digits. Names are case-sensitive, and two different strings are two different people.
- A person appears as the child in at most two relations, no relation is listed twice, and no relation has parent == child.
- The relations contain no cycle: nobody is their own ancestor through one or more parent links.
- a and b follow the same name format, and a != b. a or b may not appear in relations at all.
Examples
Input: ([['Ann', 'Cal'], ['Ben', 'Cal'], ['Ann', 'Dee'], ['Ben', 'Dee'], ['Cal', 'Eli'], ['Fay', 'Eli'], ['Dee', 'Gus']], 'Eli', 'Gus')
Expected Output: True
Explanation: Source Example 1: first cousins share grandparents Ann and Ben, reached through Eli's first-listed parent Cal (keeping only the last parent per child misses them).
Input: ([['Ann', 'Cal'], ['Ben', 'Cal'], ['Ann', 'Dee'], ['Ben', 'Dee'], ['Cal', 'Eli'], ['Fay', 'Eli'], ['Dee', 'Gus']], 'Fay', 'Cal')
Expected Output: False
Explanation: Source Example 2: Fay and Cal are the two parents of Eli with no common ancestor; an undirected walk would wrongly connect them.
Hints
- Each person counts as their own ancestor, so a parent and a child are already related through the parent.
- Relationship only flows upward along parent links: a shared child or a partner does not make two people related.
- Several different lines can lead from one person to the same ancestor; make sure that does not multiply your work.
Community answers
Answer by charles.kuncheria
// https://prachub.com/interview-questions/check-whether-two-people-are-blood-relatives-in-a-family-graph
class PersonNode {
constructor(name) {
this.parents = [];
this.name = name;
}
}
function are_blood_relatives(relations, a, b) {
// might look like common ancestor in tree.
// but is not really a tree.
// my logic:
// 1. contruct the person node and map for each person.
// 2. for a and b, find all ancestor array
// 3. just check if any person is common in both array?
const personMap = new Map();
for (const [p, c] of relations) {
if (!personMap.has(p)) {
personMap.set(p, new PersonNode(p));
}
if (!personMap.has(c)) {
personMap.set(c, new PersonNode(c));
}
const cNode = personMap.get(c);
cNode.parents.push(personMap.get(p));
}
for (const name of [a, b]) {
if (!personMap.has(name)) {
personMap.set(name, new PersonNode(name));
}
}
const aAncestorSet = new Set();
const bAncestorSet = new Set();
const queue = [personMap.get(a)];
let head = 0;
while (head < queue.length) {
const node = queue[head];
head++;
if (aAncestorSet.has(node.name)) continue;
aAncestorSet.add(node.name);
for (const parent of node.parents) {
queue.push(parent);
}
}
// now lets do for b.
queue.length = 0;
queue.push(personMap.get(b));
head = 0;
while (head < queue.length) {
const node = queue[head];
head++;
if (bAncestorSet.has(node.name)) continue;
bAncestorSet.add(node.name);
for (const parent of node.parents) {
queue.push(parent);
}
}
// now we just do a check between 2 sets?
const commonAncestors = aAnces
Answer by shivangstreak
Build a map parents[child] -> [parent, ...] (at most 2 entries per child).
Traverse upward from a, starting with a itself, and collect every reachable person into anc_a.
Traverse upward from b, also starting with b. If any visited person is in anc_a, return True.
If the traversal finishes without a hit, return False.
from collections import defaultdict, deque
def are_blood_relatives(relations: list[list[str]], a: str, b: str) -> bool:
parents = defaultdict(list)
for parent, child in relations:
parents[child].append(parent)
def ancestors(person):
found = {person} # a person is their own ancestor
queue = deque([person])
while queue:
cur = queue.popleft()
for p in parents[cur]:
if p not in found:
found.add(p)
queue.append(p)
return found
return len(ancestors(a) & ancestors(b)) > 0