Design a Multi-Level In-Memory Cloud Storage Service

Problem Statement

Implement an in-memory cloud storage manager that supports staged modifications, user capacity quotas, ranking queries, and snapshot backups with conflict resolution.

Implement the CloudStorageService class:

• __init__(user_capacity: int): Initializes the service where each user is allocated a maximum capacity of user_capacity bytes across their committed files.
• stage_file(user_id: str, path: str, size: int) -> bool: Places a file in the user's staging area. If path is already staged, its size is updated. Staging fails and returns False without modifying state if committing all currently staged files (with this file included) would exceed user_capacity. Otherwise, returns True.
• commit(user_id: str) -> int: Merges all staged files for user_id into their committed storage (overwriting existing committed files with matching paths). Staged changes for user_id are cleared. Returns the number of files committed. If no files are staged, returns 0.
• top_k_by_prefix(user_id: str, prefix: str, k: int) -> list[str]: Searches only the user's committed files whose paths start with prefix. Returns up to k paths sorted primarily by size in descending order, and secondarily by lexicographical order of path ascending. If fewer than k files match, return all matches.
• backup(snapshot_id: str) -> bool: Creates an immutable backup of all users' current committed files. Returns False if snapshot_id already exists, otherwise returns True.
• restore(snapshot_id: str, conflict_strategy: str) -> bool: Restores committed files from the backup. Staged files are not modified. Returns False if snapshot_id does not exist or if conflict_strategy is invalid. Valid strategies are:
  • "overwrite": Completely replaces current committed storage for all users with the backup.
  • "keep_newer": For each file in the snapshot, if it does not exist currently in committed storage, add it. If it already exists, keep whichever version has a larger size (ties keep the current version).
  • If restoring under either strategy would cause any user's total committed storage to exceed user_capacity, the entire restore operation aborts without changes and returns False. Otherwise, returns True.

Example

storage = CloudStorageService(user_capacity=100)

# Stage files for user "alice"
assert storage.stage_file("alice", "/docs/resume.pdf", 40) is True
assert storage.stage_file("alice", "/docs/cover.pdf", 30) is True
assert storage.stage_file("alice", "/media/photo.png", 50) is False  # 40 + 30 + 50 > 100

# Commit alice's files
assert storage.commit("alice") == 2  # Committed: resume.pdf (40), cover.pdf (30)

# Top prefix search
assert storage.top_k_by_prefix("alice", "/docs", 5) == ["/docs/resume.pdf", "/docs/cover.pdf"]

# Create backup
assert storage.backup("snap_1") is True

# Update file and stage
assert storage.stage_file("alice", "/docs/resume.pdf", 50) is True
assert storage.commit("alice") == 1  # resume.pdf is now 50 bytes; total = 80

# Restore with keep_newer: resume.pdf (50 > 40) remains 50
assert storage.restore("snap_1", "keep_newer") is True
assert storage.top_k_by_prefix("alice", "/docs", 1) == ["/docs/resume.pdf"]

Constraints

• 1 <= user_capacity <= 10^9
• 1 <= len(user_id), len(path), len(snapshot_id) <= 64
• 1 <= size <= user_capacity
• 1 <= k <= 100
• Up to 10^4 calls will be made in total.