How should I practice File Encryption Tree Optimization?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Databricks onsite interview problems in FastPrep.

Is File Encryption Tree Optimization associated with Databricks?

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

Problem · Tree

File Encryption Tree Optimization

Learn this problem

● Hard

DatabricksFULLTIMEONSITE INTERVIEW

Problem statement

A rooted file-system tree contains directory nodes and file nodes. Node 0 is the root. For each node i, parent[i] is its parent, type[i] is 0 for a directory or 1 for a file, and cost[i] is the cost of invoking encryption on that node.

For a file, one file-level call encrypts that file. For a directory, one directory-level call encrypts every currently unencrypted file in its subtree. Calls are idempotent, and already encrypted files need no action.

Return the minimum total cost needed to make every file encrypted.

Function

minimumEncryptionCost(parent: int[], type: int[], encrypted: boolean[], cost: int[]) → long

Examples

Example 1

parent = [-1,0,0,1,1]type = [0,0,1,1,1]encrypted = [false,false,false,false,true]cost = [10,3,5,2,100]return = 7

Encrypting file 2 costs 5 and file 3 costs 2. The directory call at node 1 costs 3, so direct file encryption is cheaper there; the total is 7.

Constraints

1 <= parent.length = type.length = encrypted.length = cost.length <= 200000
parent[0] = -1; for i > 0, 0 <= parent[i] < i.
The root is a directory. File nodes have no children.
0 <= cost[i] <= 10^9.
encrypted[i] is false for directory nodes.
The answer fits in a signed 64-bit integer.