Common Ancestor in Forest Graph | Dataford Interview Questions

Given two nodes ("rabbits") in a forest/graph of ancestor relationships, determine whether they share a common ancestor (i.e., belong to the same connected component / have the same root).

Asked in the phone_screen stage. Reconstructed from commenter replies, which mention union-find and LCA framing; OP did not paste the literal question text, likely because it was an embedded image not captured by the page scrape.

Input and Output

Implement share_common_ancestor(parent, rabbit_a, rabbit_b). parent maps each non-root node to its immediate parent; roots are absent as keys. Return True if both rabbits reach the same root, otherwise False.

Constraints

The parent mapping describes a valid acyclic forest.
Roots are absent as keys in parent.
1 <= number of nodes <= 10^5
Node labels are unique strings.
Both queried rabbits exist in the forest.

Function Signature

def share_common_ancestor(parent, rabbit_a, rabbit_b):

Your question is Common Ancestor in Forest Graph. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem