Home
hackerrank
hackerrank certification

Balanced System Files partition - Problem Solving (Basic) certification | HackerRank

Balanced System File partition

The directory structure of a system disk partition is represented as a tree. Its n directories are numbered from 0 to n-1, where the root directory has the number 0. The structure of the tree is defined by a parent array, where parent[i] = j means that the directory i is a direct subdirectory of j. Since the root directory does not have a parent, it will be represented as parent[0] = -1. The value in files_size[i] denotes the sum of the sizes in kilobytes of the files located in directory i, but excluding its subdirectories. The size of the content of a directory is defined as the size of all files contained in this directory, plus the sum of the sizes of all of its subdirectories. Partition the tree into two smaller ones by cutting one branch so that the sizes of the resulting subtrees are as close as possible.

Example

parent = [-1, 0, 0, 1, 1, 2]
files_size = [1, 2, 2, 1, 1, 1]
The structure of the system is shown in the diagram below. The nodes are labeled as <directory>/<file_size>



. Cut the branch between directories 1 and 0. The partition (0, 2,5) has size files_size[0] + files_size[2] + files_size[5] = 1 + 2 + 1 = 4. The partition {1,3,4} has size files_size[1] + files_size[3] + files_size[4] = 2 + 1 + 1 = 4. The absolute difference between the sizes of the two new trees is 4 - 4 = 0.
Since no other partition can have a smaller absolute difference, the final answer is 0.



Function Description

Complete the function mostBalancedPartition in the editor below.
The function has the following parameter(s):     int parent[n]: each parent[i] is the parent directory of directory i
    int files_size[n]: each file_sizes[i] is the sum of file sizes in directory i


Returns

    int: the minimum absolute difference in the size of content between two subtrees


Constraints

  • 2 ≤ n ≤ 105
  • 1 ≤ files_size[i] ≤ 104
  • parent[0] = -1
  • parent[i] < i for 1 ≤ i < n
  • The depth of each directory tree is at most 500.


Solution in Python:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#!/bin/python3

import math
import os
import random
import re
import sys


#
# Complete the 'mostBalancedPartition' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY parent
#  2. INTEGER_ARRAY files_size
#

def mostBalancedPartition(parent, files_size):
    n = len(parent)
    children = [[] for _ in range(n)]
    for i in range(1, n):
        children[parent[i]].append(i)
    size_sums = [None for _ in range(n)]
    
    def size_sums_rec(i):
        size_sums[i] = files_size[i] + sum(size_sums_rec(c) for c in children[i])
        return size_sums[i]
        
    size_sums_rec(0)
    return min(abs(size_sums[0] - 2 * ss) for ss in size_sums[1:])

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    parent_count = int(input().strip())

    parent = []

    for _ in range(parent_count):
        parent_item = int(input().strip())
        parent.append(parent_item)

    files_size_count = int(input().strip())

    files_size = []

    for _ in range(files_size_count):
        files_size_item = int(input().strip())
        files_size.append(files_size_item)

    result = mostBalancedPartition(parent, files_size)

    fptr.write(str(result) + '\n')

    fptr.close()
Labels : #hackerrank ,#hackerrank certification ,#problem solving ,#problem solving (Basic) ,#python ,

Post a Comment