Katkat
Back

Determine whether two nodes are related

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to determine connectivity between two nodes in a directed graph, specifically modeling ancestry relationships.

Problem Statement

You are given a collection of parent-child relationships representing a family tree structure (which may be a forest of multiple disconnected trees). Each relationship is represented as a pair [parent, child].

Given two individuals, personA and personB, determine if personA is an ancestor of personB. An ancestor is defined as either the direct parent, or an ancestor of the parent.

Function Signature

def is_ancestor(relationships: list[list[str]], personA: str, personB: str) -> bool

Constraints

  • relationships length: 0 to 10,000.
  • Names are unique strings.
  • The graph may contain multiple disconnected components.
  • Ensure your solution handles cycles (if the input data is malformed, though standard trees are acyclic).

Examples

Example 1: Input: relationships = [["Alice", "Bob"], ["Bob", "Charlie"]], personA = "Alice", personB = "Charlie" Output: True Explanation: Alice is the parent of Bob, and Bob is the parent of Charlie, therefore Alice is an ancestor of Charlie.

Example 2: Input: relationships = [["Alice", "Bob"], ["David", "Eve"]], personA = "Alice", personB = "Eve" Output: False Explanation: There is no path between Alice and Eve.

Edge Cases

  • personA equals personB (is an individual their own ancestor? Assume False unless specified otherwise).
  • Graph contains cycles (avoid infinite loops).
  • Empty relationship list.

Hints

Hint 1

Represent the relationships as an adjacency list where each parent maps to a list of their children.

Hint 2

Perform a graph traversal such as Breadth-First Search (BFS) or Depth-First Search (DFS) starting from personA.

Hint 3

Keep track of visited nodes during your traversal to handle potential cycles and prevent redundant work.

Follow-up questions

  • How would you modify your solution if the relationships were undirected, and you needed to find if two people are simply in the same family 'component'?
  • If this function is called millions of times on the same static set of relationships, how could you optimize the lookup time?
  • What if the input contains a cycle (e.g., A is parent of B, B is parent of A)? Does your current traversal handle it?