FastPrep
Problem · Tree

Google Drive Folder Hierarchy Sync

Learn this problem
● MediumGoogle logoGoogleINTERNOA
See Google hiring insights

Problem statement

A Google Drive folder hierarchy contains tree_nodes folders numbered from 1 to tree_nodes. The hierarchy is a tree described by the undirected edges (tree_from[i], tree_to[i]). Folder i initially has the integer access level access_levels[i - 1].

The hierarchy is synced when the absolute difference between the access levels of every pair of directly connected folders is at most 1.

You may increase a folder's access level by any nonnegative integer amount, but you cannot decrease an access level. Return the minimum possible total increase across all folders that makes the entire hierarchy synced.

Function Details

Implement findMinIncrease with the following parameters:

  • int tree_nodes: the number of folders
  • int[] tree_from: one endpoint of each hierarchy edge
  • int[] tree_to: the other endpoint of each hierarchy edge
  • int[] access_levels: the initial access level of each folder

Return a long equal to the minimum total access-level increase required.

Function

findMinIncrease(tree_nodes: int, tree_from: int[], tree_to: int[], access_levels: int[]) → long

Examples

Example 1

tree_nodes = 5tree_from = [1,2,2,3]tree_to = [2,3,4,5]access_levels = [1,4,2,6,5]return = 6

Increase folder 1 by 3, folder 2 by 1, and folder 3 by 2. The resulting levels are [4,5,4,6,5].

Every edge then connects levels whose difference is exactly 1, and the total increase is 3 + 1 + 2 = 6. No smaller total increase can sync the hierarchy.

Example 2

tree_nodes = 5tree_from = [1,2,2,3]tree_to = [2,3,4,5]access_levels = [1,5,7,8,3]return = 10

The smallest feasible final levels are [6,7,7,8,6]. Their edge differences are at most 1, and the increases sum to 5 + 2 + 0 + 0 + 3 = 10.

Constraints

  • 1 <= tree_nodes <= 2 * 10^5
  • tree_from.length = tree_to.length = tree_nodes - 1
  • 1 <= tree_from[i], tree_to[i] <= tree_nodes
  • The given edges form a valid tree with folders numbered from 1.
  • access_levels.length = tree_nodes
  • 1 <= access_levels[i] <= 10^9

More Google problems

drafts saved locally
public long findMinIncrease(int tree_nodes, int[] tree_from, int[] tree_to, int[] access_levels) {
    // write your code here.
}
tree_nodes5
tree_from[1,2,2,3]
tree_to[2,3,4,5]
access_levels[1,4,2,6,5]
expected6
checking account