File Encryption Tree Optimization
Updated
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[]) → longExamples
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 = 7Encrypting 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 <= 200000parent[0] = -1; fori > 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.
More Databricks Onsite Interview questions
- Path Between Two Nodes of a Fibonacci TreeONSITE INTERVIEW · Seen Oct 2026
- Rectangular K-in-a-RowONSITE INTERVIEW · Seen Oct 2026
- Customer Revenue with Direct ReferralsPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Cipher Cover Interval EditingONSITE INTERVIEW · Seen Aug 2026
- Hybrid Run-Length and Bit-Packing EncoderONSITE INTERVIEW · Seen Aug 2026
- Concurrent Buffered File LoggerONSITE INTERVIEW · Seen Aug 2026
- Key-Value Store with Hit CounterONSITE INTERVIEW · Seen Jul 2026
- Blocking Keyed Cache with Waiting ReadersONSITE INTERVIEW · Seen Jul 2026
- Snapshot Set IteratorPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Durable Data WriterONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
- Lowest Common Manager for Employee GroupsAmazon · PHONE SCREEN
- Binary Tree Maximum Path SumGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Binary Tree Maximum Path SumBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Binary Tree Maximum Path SumGlobalization Partners · ONSITE INTERVIEW
- Maximum Path Sum Between Marked NodesDoorDash · PHONE SCREENDoorDash interview questions
- House Robber IIIOkta · PHONE SCREENOkta interview questions
- House Robber IIIVisa · PHONE SCREENVisa interview questions
- Transitive Employee Referral CountsRobinhood · ONSITE INTERVIEWRobinhood interview questions
- Maximum Nonadjacent Sum in a General TreeZip · PHONE SCREEN · ONSITE INTERVIEWZip interview questions