This was a bit different from the other report on this same file storage question. The first two parts were about the same: create a file, create a user. The third part was about adjusting capacity — when you reduce a user's capacity, you need to consider deleting the largest-size files. The fourth part was about compressing and decompressing a file.
One thing to watch out for: Level 2's requirement to sort in lexicographical order of the names needs extra attention — if you use a priority queue, you need to handle the string comparison separately. Other than that, you just need to implement it without worrying about any performance optimization, so write it in the simplest, most direct way possible — that makes it a lot easier to debug afterward.
Your task is to implement a simple cloud storage system. All operations that should be supported are listed below.
Requirements: Your task is to implement a simple cloud storage system that maps objects (files) to their meta information. Specifically, the storage should maintain files and information about them (name, size, etc.). Note that this system should be in-memory: you don't need to work with the real filesystem.
Level 1: The cloud storage system should support adding a new file and retrieving and deleting files. Level 2: The cloud storage system should support displaying the largest files. Level 3: The cloud storage system should support adding users with limited capacities and merging two users. Level 4: The cloud storage system should support backing up and restoring a user's files.
Level 1 — The cloud storage system should support file manipulation.
add_file(self, name: str, size: int) -> bool — should add a new file name to the storage. size is the amount of memory required in bytes. The operation fails if a file with the same name already exists. Returns True if the file was added successfully or False otherwise.
get_file_size(self, name: str) -> int — Return the size of the file name if it exists, or None otherwise.
delete_file(self, name: str) -> int | None — should delete the file name. Returns the deleted file's size if the deletion was successful, or None if the file does not exist.
Level 2
Implement an operation for retrieving some statistics about files with a specific prefix. get_n_largest(self, prefix, n) should return the list of strings representing the names of the top n largest files with names starting with prefix in the following format. Returned files should be sorted by size in descending order, or in case of a tie, sorted in lexicographical order of the names. If there are no such files, return an empty list. If the number of such files is less than n, all of them should be returned in the specified format. Example queries: add_file("/dir/file1.txt", 5), add_file("/dir/file2.txt", 20), add_file("/dir/deeper/file3.mov", 9), get_n_largest("/dir", 2), get_n_largest("/dir/file", 3), get_n_largest("/another_dir", file.txt), add_file("/big_file.mp4", 20), get_n_largest("/", 2).
Level 3 — Implement support for queries from different users. All users share a common filesystem in the cloud storage system, but each user is assigned a storage capacity limit. add_user(self, user_id: str, capacity: int) -> bool should add a new user in the system, with capacity as their storage limit in bytes. The total size of all files owned by user_id cannot exceed capacity. The operation fails if a user with user_id already exists. Returns True if a user with user_id was successfully created, or False otherwise.
add_file_by(self, user_id: str, name: str, size: int) -> int | None — should behave in the same way as the add_file from Level 1, but the added file should be owned by the user with user_id. A new file cannot be added to the storage if doing so would exceed the user's capacity limit. Returns the remaining capacity of the user if the file is added successfully, or None otherwise. Note that all queries calling the add_file operation implemented during Level 1 are run by the user with user_id "admin", who has unlimited storage capacity.
Level 4 — implement support to allow users to back up their files.
backup_user(self, user_id: str) -> int | None — should back up the current state of all files owned by user_id, i.e., file names and sizes. The backup is stored on a separate storage system and is not affected by any new file manipulation queries. Overwrites any backups for the same user if previous backups exist. Return the number of backed-up files, or None if user_id does not exist.
restore_user(self, user_id: str) -> int | None — should restore the state of user_id's files to the latest backup. If there was no backup, all of user_id's files are deleted. If a file can't be restored because another user has added another file with the same name, it is ignored. Returns the number of files that were successfully restored, or None if user_id does not exist.
Note that merge_user does not affect user_id_1's backup, and user_id_2 is deleted along with its backup. Note that the restore_user operation does not affect the user's capacity.
Overall the question wasn't too different from that other post, but the details from Level 2 onward were different for me.
Level 2 required finding a user's files by both prefix and suffix, then sorting them in a certain order. Level 3 required dynamically changing a user's capacity — if the new capacity wasn't enough to hold everything, you had to delete existing files according to some rules. Level 4 required doing compress and decompress, which was basically size halved / doubled.
Some tips: a prefix scan doesn't need a trie — just compare each name against the prefix directly. Top N doesn't need an ordered set / priority queue — just sort directly and take the top N. You can click open the file for a given test case to see exactly what that failed test case contained, which makes debugging a lot easier.
Discussion
Loading comments…