Lowest Common Ancestor in View Tree

MediumPython00:00

Practice interviewer

Your interviewer

In session

Interviewer

Welcome to the Python screen.

The question is on your right: Lowest Common Ancestor in View Tree. Read through the requirements first.

Run and submit your code as often as you need. You also have five interviewer messages this session - want to talk through your approach, or are you ready to start coding?

You need to log in / sign up to run or submit.

Problem

In a Meta mobile UI hierarchy, each view is a node in a rooted tree. Given the root of the view tree and two target views, return their lowest common ancestor: the deepest view that is an ancestor of both targets.

If either target view does not exist in the tree, return None.

Formal Specification

Implement a function:

Input: root (root ViewNode), view1 (ViewNode), view2 (ViewNode)
Output: the ViewNode representing the lowest common ancestor, or None

Each node has:

id: unique integer identifier
children: list of child ViewNode objects

Constraints

1 <= number of views <= 10^5
Each node has a unique id
The tree is rooted and contains no cycles
view1 and view2 may refer to the same node
If either target view is not present in the tree, return None

Function Signature

def lowest_common_ancestor_view(root, view1, view2):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output