Docstore Online TCS CodeVita 2022 Solution

 Docstore Online TCS CodeVita 2022 Solution

- Problem Description

Docstore is a utility which is used to store documents in a file/container. And while writing or storing the file you must know the exact location of the document where you are writing it. You must know what is the starting offset and ending offset of that particular file. And these all entries are inserted into the database so that at the time of reading of file you directly start reading from that offset and return the file.

You have been provided a list of files and its subsequent details. Soft deletion flag will be given. You can use that space to accommodate the new file. If deletion flag is 0 file is not soft deleted. You have been given a list of files with their size. You have insert file at a place where it gets the best fit.

Best fit- Order will be

• Exact match with the free space.
• Insert where there is Least Internal fragmentation.
• If not possible leave that space.

After checking for all free space, the files are remaining append them after the last file present on the disk.

Print the starting offset of every file inserted in sorted order of file name.

Note- b=byte, kb=kilobytes, mb=megabyte

College Rank III  TCS CodeVita 2022 Solution

- Constraints

1<N<100

1<M<100

- Input 

First line contains an integer denoting the number of files (N) already present in the disk.

Next lines contain space separated data about every file in the format given below

Filename Offset Size DeletionStatus

Next line contains an integer denoting the number of files(M) to be inserted.

Next M lines contains space separated data about every file in the format given below

Filename Size

- Output 

Print the starting offset of every file inserted in sorted order of file name.

- Time Limit (secs)

1

- Examples

Input

4

File1 0 2b 0

File2 2 3b 1

File3 5 1b 0

File4 6 4b 0

2

File5 2b

File6 3b

Output

File5 10

File6 2

Explanation-

Here we have free space of 3b at the location. And file6 require space of 3b. We will add file6 to offset 2. And after that we don't have any space remaining so we will add the remaining file to the end of last file on the disk. In that case, we will add file5 at the location 10.

Example 2

Input

3

File1 0 2b 0

File2 2 3b 0

File3 5 1b 0

2

File4 1b

File5 7b

Output

File4 6

File5 7

Explanation-

Here we have to add file4 and file5 so will check of free spaces and all the cases but no space is present to occupy any file so they will be added at the last. One after another.

 For Solution Join Telegram:-