Loading page…
Practice problem · easy
A cloud drive shows the size of every folder. The size of a folder is the size of its own files, plus the sizes of all the folders inside it, at every level below.
The drive has up to 100,000 folders. You are given each folder's parent, and the size of the files that sit directly in it.
Write folder_totals(parents, sizes).
0 to n - 1. Folder 0 is the top folder, and parents[0] is -1.i, parents[i] is the number of the folder that holds it. A folder's number can be smaller or larger than its parent's.sizes[i] is the size of the files directly in folder i.i is the total size of folder i: its own files, plus everything in the folders below it.Input: parents = [-1, 0, 0, 1, 1], sizes = [5, 3, 4, 2, 1]
Output: [15, 6, 4, 2, 1]| Folder | Holds folders | Own files | Total |
|---|---|---|---|
| 3 | none | 2 | 2 |
| 4 | none | 1 | 1 |
| 2 | none | 4 | 4 |
| 1 | 3 and 4 | 3 | 3 + 2 + 1 = 6 |
| 0 | 1 and 2 | 5 | 5 + 6 + 4 = 15 |
A folder's total needs the totals of the folders inside it first, so the table starts at the bottom.
Input: parents = [-1], sizes = [7]
Output: [7]One folder with no subfolders: its total is its own files.
Input: parents = [-1, 0, 1, 2], sizes = [1, 1, 1, 1]
Output: [4, 3, 2, 1]Each folder holds the next one, so every total is the number of folders from that one down.
1 ≤ length of parents = length of sizes ≤ 10^5parents[0] = -1, and every other parents[i] is a folder number from 0 to n - 1parents from any folder leads to folder 00 ≤ sizes[i] ≤ 10^4A plan that adds each folder's size to every folder above it costs the depth of the folder for each folder. If the folders are nested 100,000 deep, that is about 5 × 10^9 additions, which is too slow.
A solution that calls itself for each subfolder also needs 100,000 nested calls, and many languages stop long before that. Use a loop with a list instead.
folder_totals · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.