In-Memory Cloud Storage: Design and Implementation

Design and implement an in-memory cloud storage system that maps file names to their metadata (specifically, size) and supports both single-user and multi-user operations.

Assumptions and Constraints

• File names must be unique per user. Single-user functions operate within a special default user namespace.
• File sizes are non-negative integers, representing bytes.
• Each user has a capacity, which is the maximum total size (sum of all file sizes) allowed for that user.
• The get_n_largest(prefix, n) operation should return the n largest files across all users whose names start with the given prefix. Each result entry must include the user_id, name, and size.
• The merge_user(u1, u2) operation combines user2's data into user1. user1 persists, user2 is deleted. The new user1's capacity becomes the sum of user1's and user2's original capacities.
• During a merge_user operation, if file name collisions occur (a file in user2 has the same name as a file in user1), the incoming conflicting file(s) from user2 must be renamed by appending a suffix to ensure uniqueness (e.g., "name (merged 2)").
• backup_user and restore_user operations are performed per user and do not affect other users' files or capacities.

Required API

Single-user (default namespace):

1. add_file(name, size)
2. get_file_size(name) → size or None
3. delete_file(name)
4. get_n_largest(prefix, n) → list of (user_id, name, size)

Multi-user:

1. add_user(user_id, capacity)
2. add_file_by(user_id, name, size): Enforce per-user capacity limits.
3. merge_user(user_id1, user_id2): Combines users and their files; capacity sums; rename on conflicts.
4. backup_user(user_id) → version_id: Creates versioned backups per user.
5. restore_user(user_id, version_id=None): Restores a user to a saved version (latest if version_id is None).

Deliverables

• Detailed data structures and algorithms to support all specified operations.
• Clear semantics for edge cases, including capacity enforcement, file name collisions during merge, and restore behavior.
• A discussion of time and space complexity, with potential optimizations, especially for prefix queries.
• A working in-memory implementation in any mainstream language, accompanied by small usage examples and tests.