In-Memory Cloud Storage System Design

Design and implement an in-memory cloud storage system that manages file paths, their associated metadata, and supports multi-user quotas. The implementation should primarily use simple data structures, as performance optimizations are explicitly not required for this exercise.

Constraints and Invariants

• Global Namespace: Every file path must be unique across all users within the system.
• File Ownership: Each file is owned by exactly one user.
• User Quotas: For any non-admin user, the total size of their owned files must never exceed their allocated capacity.
• Admin User: A special "admin" user exists with unlimited capacity. All Level 1 operations are performed under the context of this admin user by default.
• Sorting Rule: Wherever sorting is applied (e.g., for top-N retrieval or quota enforcement deletions), files must be sorted primarily by size in descending order. As a tie-breaker, names should be sorted in lexicographical (ASCII) ascending order.

Operations

The system must support the following operations, categorized by level:

Level 1: Basic File Manipulation (Admin Context)

These operations are implicitly performed by the "admin" user.

• add_file(self, name: str, size: int) -> bool: Adds a new file. Returns True on success, False if a file with the given name already exists.
• get_file_size(self, name: str) -> int | None: Returns the size of the file if it exists, otherwise None.
• delete_file(self, name: str) -> int | None: Deletes the file and returns its size if it existed, otherwise None.

Level 2: Top-N Retrieval with Filtering (Per-User)

• get_n_largest(self, user_id: str, prefix: str | None, suffix: str | None, n: int) -> list[str]: Retrieves the names of the top n files owned by user_id. Files must match the optional prefix (if not None or empty) and suffix (if not None or empty). The results should be sorted according to the global sorting rule. If fewer than n files match, all matching files should be returned. If no files match, an empty list [] should be returned.

Level 3: User Management, Quotas, and Merging

• add_user(self, user_id: str, capacity: int) -> bool: Creates a new user with the specified capacity. Returns True on success, False if user_id already exists.
• add_file_by(self, user_id: str, name: str, size: int) -> int | None: Adds a new file owned by user_id. This operation fails if the name already exists globally or if adding the file would cause user_id to exceed their capacity. On success, returns the user's remaining capacity (capacity - total_owned_size). Returns None on failure.
• adjust_capacity(self, user_id: str, new_capacity: int) -> int | None: Modifies user_id's capacity to new_capacity. If new_capacity is less than the user's current total file usage, the system must repeatedly delete the user's largest files (using the global sorting rule for ties) until their total size is less than or equal to new_capacity, or no files remain. Returns the count of files deleted, or None if user_id does not exist.
• merge_users(self, target_id: str, source_id: str) -> int | None: Moves all files from source_id to target_id. If a file being moved from source_id has a name that conflicts with an existing global file name (owned by any user, including target_id), that specific file is skipped. After moving, target_id's capacity invariant must be maintained; if necessary, target_id's largest files are deleted (using the global sorting rule) until within capacity. Following the merge, source_id and any associated backup are deleted. target_id's backup (if any) remains unchanged. Returns the count of files successfully moved, or None if either target_id or source_id does not exist.

Level 4: Backup/Restore and Size Transformations

• backup_user(self, user_id: str) -> int | None: Creates a snapshot of user_id's current files (names and sizes) in a separate backup store, overwriting any previous backup for that user. Returns the number of files backed up, or None if user_id does not exist.
• restore_user(self, user_id: str) -> int | None: Replaces user_id's current files with their latest backup snapshot. If no backup exists for user_id, all of their current files are deleted. During restoration, if a file from the backup conflicts with an existing global file name (owned by another user), that specific file is skipped. The user's capacity value is not altered by this operation. Returns the number of files restored, or None if user_id does not exist.
• compress_user(self, user_id: str) -> int | None: For each file owned by user_id, its size is updated to floor(size / 2). Returns the number of files updated, or None if user_id does not exist.
• decompress_user(self, user_id: str) -> int | None: For each file owned by user_id, its size is updated to size * 2. Subsequently, the capacity invariant for user_id must be enforced; if the new total size exceeds capacity, the user's largest files are deleted (using the global sorting rule) until within capacity. Returns the number of files remaining after decompression and quota enforcement, or None if user_id does not exist.

Additional Notes

• Implement exact lexicographical tie-breaking on names when file sizes are equal, as specified in the sorting rule.
• Comparisons for prefix/suffix filtering may be performed directly on strings; the use of advanced data structures like tries or priority queues is not required for this problem.
• All method names, arguments, and return types must precisely match the specifications provided.