FastPrepCount Distinct Rooted-Tree Grafts

Count Distinct Rooted-Tree Grafts

The D.E. Shaw Group logoThe D.E. Shaw Group● HardFULLTIMEPHONE SCREEN
Learn

Problem statement

You are given two rooted trees. Tree 1 is encoded by parent1 and Tree 2 by parent2. In each array, node 0 is the root and has parent -1; for every other node i, parent[i] is its parent.

Perform exactly one operation:

  1. Choose any node u in Tree 2 and keep the complete subtree rooted at u.
  2. Choose any leaf in Tree 1 and attach u as a new child of that leaf.
  3. Discard every node of Tree 2 outside the chosen subtree.

Two results are identical when one can be transformed into the other by reordering children and renumbering non-root nodes. Return the number of distinct rooted, unordered tree structures obtainable over all valid choices.

Function

countDistinctGrafts(parent1: int[], parent2: int[]) → int

Examples

Example 1

parent1 = [-1]parent2 = [-1,0]return = 2

Keeping the root of Tree 2 creates a three-node chain; keeping only its leaf creates a two-node chain.

Example 2

parent1 = [-1,0,0]parent2 = [-1]return = 1

The two leaves of Tree 1 are structurally symmetric, so both attachment choices produce the same rooted tree.

Example 3

parent1 = [-1,0]parent2 = [-1,0,0]return = 2

Choosing the branching root or choosing either symmetric leaf yields two distinct structures.

Constraints

  • 1 <= parent1.length, parent2.length <= 60
  • parent1[0] = parent2[0] = -1
  • For each i > 0, 0 <= parent[i] < i.
  • Both arrays describe valid rooted trees.

Source note: The source image is a source-neutral excerpt of the author-reported prompt.

More The D.E. Shaw Group problems

See The D.E. Shaw Group hiring insights
public int countDistinctGrafts(int[] parent1, int[] parent2) {
  // Write your code here.
}
parent1[-1]
parent2[-1,0]
expected2
Checking account…