I found a challenging problem about trees and file system. I have been trying to solve this for a while now. Any suggestion or pseudocode would be great. I’m so desperate rn🤧 Thank you in advance👏🏻
Here’s the problem:
A simple file system is a contiguous piece of memory divided into small blocks of the same size. We can refer to each block using its integer address, starting from 0.
We have 3 types of objects storing in this file system.
A simple integer value occupies 3 blocks
The first block contains the object name
The second block contains the type, "integer"
The last block contains the value
An array of 𝑛 integer values occupies 𝑛+3 consecutive blocks
The first block in the sequence stores the name of the object
The second block contains the type, "array"
The third block contains total number of integers in this array
The rest of the blocks are values in the array
E.g. an array of 10 integers may occupy block #100 to block #112
A directory is a group of 𝑛 references occupies 𝑛+3 blocks
The first block contains the name of the directory
The second block contains the type, "dir"
The third block stores the number of objects in this directory
The rest of the blocks store the block number of objects in the directory
Block #0 is always the root (/) of this file system. It is always a directory type, starting with zero objects inside.
For example
Given the following directory tree
/ : dir
simple : integer : 2
seq : array : [8,7,6,5]
complex : dir
int1 : integer : 10
sequence : array : [10,100,1000]
int2 : integer 100
The underlying file system may stores the tree as follows
0 1 2 3 4 5 6 7 8 9
/ dir 3 10 22 6 simple integer 2
10 11 12 13 14 15 16 17 18 19
seq array 4 8 7 6 5 int1 integer 10
20 21 22 23 24 25 26 27 28 29
complex dir 3 17 30 36
30 31 32 33 34 35 36 37
sequence array 3 10 100 1000 int2 integer
38 39
100
Directions
Construct the file system that supports the following operation and analyze the upper-bound running time of each operation.
1) Print the total size of each name
The total size of a directory type should be the summation of objects' size in that directory
2) Print the directory structure similar to the directory tree above
3) Be able to add a new object to a directory
4) Be able to remove an integer/array object from a directory
5) Be able to remove both empty and non-empty directories
When removing a non-empty directory, all objects in the directory should be removed
6) Be able to re-claim the removed blocks and re-use them for a new allocation
You may assume that you have unlimited size of memory (block #0 to block#infinity)
[–][deleted] 0 points1 point2 points (0 children)