How should I practice Root of the Largest Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs phone screen and onsite interview problems in FastPrep.

Is Root of the Largest Tree associated with Goldman Sachs?

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

Root of the Largest Tree

Goldman Sachs● MediumFULLTIMEPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

You are given parallel integer arrays parents and children describing a forest of rooted trees. For every index i, parents[i] is the direct parent of children[i].

The nodes are exactly the distinct IDs that appear in either array. The associations form a valid acyclic forest, and every child appears at most once. A node that never appears in children is the root of its tree.

The size of a tree is its number of distinct nodes. Return the root ID of a tree with maximum size. If several trees have the same maximum size, return the smallest root ID.

Function

findLargestTreeRoot(parents: int[], children: int[]) → int

Examples

Example 1

parents = [1,1,2,10]children = [2,3,4,11]return = 1

The tree rooted at 1 contains nodes {1,2,3,4}. The tree rooted at 10 contains {10,11}, so return 1.

Example 2

parents = [5,8,8,9]children = [6,9,10,11]return = 8

The tree rooted at 8 contains 8,9,10,11, while the other tree contains only 5,6.

Constraints

1 <= parents.length = children.length <= 100000.
-10^9 <= parents[i], children[i] <= 10^9.
The associations form a valid acyclic forest.
Every child ID appears at most once, and parents[i] != children[i].