FastPrep
Problem · Tree

Minimum Height

Learn this problem
● MediumSnowflake logoSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

A database is represented as a rooted tree with tree_nodes tables, where Table 1 is the root.

Up to max_operations operations are allowed. In one operation:

  • Select a child table u of a parent table v and remove the edge between u and v.
  • Move u and its subtree to become a direct child of the root, reducing its depth.

Determine the minimum possible height of the tree.

Note:

  • The height of the tree is defined as the maximum depth of any table.
  • The depth of a table is the number of edges from the root to that table.
  • A subtree in a rooted tree is a subgraph of the tree consisting of a vertex, the root of that subtree, and its descendants, along with all edges incident to these descendants.

Function

getMinimumHeight(tree_nodes: int, tree_from: int[], tree_to: int[], max_operations: int) → int

Complete the function getMinimumHeight in the editor with the following parameters:

  • int tree_nodes: the number of nodes in the tree
  • int tree_from[tree_nodes - 1]: the starting node of the edge
  • int tree_to[tree_nodes - 1]: the ending node of the edge
  • int max_operations: the maximum number of operations

Returns

int: the minimum possible height of the tree after as many as max_operations operations

Examples

Example 1

tree_nodes = 4tree_from = [3, 1, 2]tree_to = [2, 3, 4]max_operations = 1return = 2
1324

One possible operation can be:

  • Remove the edge (2, 4) and add an edge (1, 4).
4132

So, the height of the tree is 2.

More Snowflake problems

drafts saved locally
public int getMinimumHeight(int tree_nodes, int[] tree_from, int[] tree_to, int max_operations) {
  // write your code here
}
tree_nodes4
tree_from[3, 1, 2]
tree_to[2, 3, 4]
max_operations1
expected2
checking account