How should I practice Are Two People Relatives in a Family Tree??

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon onsite interview problems in FastPrep.

Is Are Two People Relatives in a Family Tree? associated with Amazon?

FastPrep tags this as a Amazon onsite interview coding practice problem when the problem catalog has that company and stage context.

Are Two People Relatives in a Family Tree?

Amazon● MediumFULLTIMEONSITE INTERVIEW

Problem statement

A family tree is given as a list of rows. Each row relations[i] = [parent, child] means that parent is a parent of child. A person can have up to two recorded parents, and some people have no recorded parents at all. Because a child can have two parents, the family is a graph, not a simple tree.

Two people are relatives when they share at least one ancestor. Each person counts as one of their own ancestors. So a person is a relative of every ancestor and every descendant they have, and a person is always a relative of themselves.

Two people who only share a child, such as the two parents of one child, are not relatives unless they also share an ancestor.

Return true if first and second are relatives, and false otherwise. A name that does not appear in relations belongs to a person with no recorded family, so that person's only ancestor is themselves.

Function

areRelatives(relations: String[][], first: String, second: String) → boolean

Examples

Example 1

relations = [["ann","bob"],["ann","cat"],["bob","dan"],["cat","eve"]]first = "dan"second = "eve"return = true

dan's ancestors are dan, bob, and ann. eve's ancestors are eve, cat, and ann. Both sets contain ann, so the two cousins are relatives.

Example 2

relations = [["ann","cat"],["bob","cat"]]first = "ann"second = "bob"return = false

ann and bob are both parents of cat, but neither has a recorded parent. Their ancestor sets are just {ann} and {bob}, which do not overlap. Sharing a child does not make them relatives.

Example 3

relations = [["gus","hal"],["hal","ivy"],["kim","ivy"]]first = "gus"second = "ivy"return = true

ivy has two parents, hal and kim, and gus is the parent of hal. So ivy's ancestors are ivy, hal, kim, and gus. Since gus counts as his own ancestor, both sets contain gus, and a grandparent and grandchild are relatives.

Constraints

0 <= relations.length <= 500
relations[i].length == 2
Every name, including first and second, has 1 to 10 lowercase English letters.
In every row, parent and child are different names.
No row appears more than once.
Each person appears as the child in at most two rows.
The rows contain no cycle: following rows from parent to child never leads back to the same person.