Design an in-memory cloud file system

In-Memory Cloud File System (OOD)

Design an in-memory cloud file system that supports files owned by users with storage quotas.

Data model / rules

• Each file has a unique name (string) and a size (positive integer).
• Each file is owned by exactly one user.
• Each user has a remaining capacity (how many bytes they can still store).
• Special user "admin" exists and has infinite capacity.
• Adding a file consumes the owner’s remaining capacity by size.
• Deleting a file refunds its size back to the owner’s remaining capacity.

API to implement

Implement a class with the following methods (exact names not required, behavior is):

1. add_user(user_id, capacity) -> bool

   • Create a new user with the given remaining capacity.
   • Return false if the user already exists.

2. add_file(name, size) -> bool

   • Convenience method: add a file owned by admin.
   • Return false if the file already exists.

3. add_file_by(user_id, name, size) -> int | null

   • Add a file owned by user_id.
   • Return the user’s remaining capacity after adding.
   • Return null if:
     • user_id does not exist
     • name already exists
     • size exceeds the user’s remaining capacity

4. get_file_size(name) -> int | null

   • Return the file size, or null if not found.

5. delete_file(name) -> int | null

   • Delete the file.
   • Return the deleted file’s size, or null if not found.

6. get_n_largest(prefix, n) -> list<string>

   • Consider only file names starting with prefix.
   • Return up to n files formatted as: "<name>(<size>)".
   • Sort by:
     1. size descending
     2. name ascending (lexicographic) for ties

7. merge_user(user_id_1, user_id_2) -> int | null

   • Merge user_id_2 into user_id_1.
   • All files owned by user_id_2 become owned by user_id_1.
   • user_id_1’s remaining capacity increases by user_id_2’s remaining capacity.
   • Delete user_id_2.
   • Return user_id_1’s new remaining capacity.
   • Return null if either user doesn’t exist or the IDs are the same.

8. backup_user(user_id) -> int | null

   • Store a snapshot of the current set of files owned by user_id (name -> size).
   • Return the number of files included in this backup.
   • Return null if the user doesn’t exist.

9. restore_user(user_id) -> int | null

   • Restore user_id’s files from the most recent backup for that user.
   • First, remove all files currently owned by user_id.
   • Then, for each file in the backup, restore it only if its name is not currently used by some other user.
   • Return the number of files actually restored.
   • If the user exists but has no backup, return 0.
   • If the user doesn’t exist, return null.

Notes

• Assume up to ~1e5 operations.
• You may choose any internal data structures, but must satisfy the behavior above.

Implement an In-Memory Cloud File System

You are given a sequence of operations to run on an in-memory cloud file system. Implement solution(operations) and return the result of every operation in order.

Rules:

• Each file has a unique string name, a positive integer size, and exactly one owner.
• Each user has a remaining storage capacity.
• The system starts with a built-in user "admin" that has infinite capacity.
• Adding a file consumes the owner's remaining capacity by its size.
• Deleting a file refunds its size to the owner's remaining capacity.
• backup_user stores only the current set of files owned by that user (name -> size). Only the most recent backup per user is kept.
• restore_user first removes all files currently owned by that user, then restores each file from the latest backup only if that file name is not currently used by someone else.
• To keep the built-in admin account always available, merge_user(x, "admin") is considered invalid.
• When a user is deleted by merge_user, that user's backup is also discarded.

Return Python values: use None for null.

Constraints

• 1 <= len(operations) <= 10^5
• 0 <= capacity <= 10^9
• 1 <= size <= 10^9
• 0 <= n <= 10^5
• 1 <= len(user_id), len(name) <= 50
• The sum of lengths of all file names appearing in the input is at most 2 * 10^5
• admin exists from the start, cannot be re-added, and cannot be removed by merge_user(x, 'admin')
• No successful test operation requires returning admin's infinite remaining capacity

Examples

Example 1

Input: [('add_user', 'alice', 10), ('add_user', 'alice', 5), ('add_file', 'sys.log', 4), ('add_file_by', 'alice', 'a.txt', 3), ('add_file_by', 'alice', 'a.txt', 2), ('add_file_by', 'alice', 'b.txt', 8), ('get_file_size', 'sys.log'), ('get_n_largest', '', 3), ('delete_file', 'a.txt'), ('add_file_by', 'alice', 'b.txt', 8), ('get_n_largest', '', 5)]
Output: [True, False, True, 7, None, None, 4, ['sys.log(4)', 'a.txt(3)'], 3, 2, ['b.txt(8)', 'sys.log(4)']]

Explanation: Covers duplicate users, duplicate file names, insufficient capacity, deleting a file to refund space, and querying the largest files across the whole system with an empty prefix.

Example 2

Input: [('add_user', 'u1', 5), ('add_user', 'u2', 10), ('add_file_by', 'u1', 'cat', 3), ('add_file_by', 'u2', 'car', 4), ('add_file_by', 'u2', 'cap', 4), ('get_n_largest', 'ca', 5), ('merge_user', 'u1', 'u2'), ('delete_file', 'car'), ('get_n_largest', 'ca', 5), ('merge_user', 'u1', 'u1'), ('merge_user', 'u1', 'u2')]
Output: [True, True, 2, 6, 2, ['cap(4)', 'car(4)', 'cat(3)'], 4, 4, ['cap(4)', 'cat(3)'], None, None]

Explanation: Files with prefix 'ca' are sorted by size descending, then name ascending for ties. After merging, u1 gains u2's remaining capacity and ownership of u2's files.

Hints

1. Use multiple hash maps: one for file -> (size, owner), one for user -> remaining capacity, and one for user -> owned file names.
2. For get_n_largest(prefix, n), avoid scanning every file each time by maintaining a mapping from every prefix to the set of file names currently using that prefix.