Cloud File System

Problem Overview

Design and implement an in-memory cloud file system that supports file management, prefix-based search, user storage quotas, and backup/restore functionality. This is a multi-level problem where each level builds upon the previous one.

You'll build this incrementally across four levels.

Level 1: Basic File Operations

Problem Statement

Implement a CloudFileSystem class that supports adding, copying, retrieving, and removing files. Each file has a unique name and an associated size.

class CloudFileSystem:
    def __init__(self):
        """Initialize the cloud file system."""
        pass

    def add_file(self, name: str, size: int) -> bool:
        """
        Add a new file to the system.

        Args:
            name: The name of the file.
            size: The size of the file (positive integer).

        Returns:
            True if the file was successfully added,
            False if a file with the same name already exists.
        """
        pass

    def get_file_size(self, name: str) -> int:
        """
        Get the size of a file.

        Args:
            name: The name of the file.

        Returns:
            The size of the file, or -1 if the file does not exist.
        """
        pass

    def delete_file(self, name: str) -> bool:
        """
        Delete a file from the system.

        Args:
            name: The name of the file to delete.

        Returns:
            True if the file was successfully deleted,
            False if the file does not exist.
        """
        pass

    def copy_file(self, source: str, dest: str) -> bool:
        """
        Copy a file to a new name.

        Args:
            source: The name of the file to copy.
            dest: The name of the new copy.

        Returns:
            True if the copy was successful,
            False if the source file does not exist or a file
            with the dest name already exists.
        """
        pass

Example Usage

fs = CloudFileSystem()

fs.add_file("report.txt", 100)       # True
fs.add_file("data.csv", 250)         # True
fs.add_file("report.txt", 50)        # False (duplicate)

fs.get_file_size("report.txt")       # 100
fs.get_file_size("missing.txt")      # -1

fs.copy_file("report.txt", "report_backup.txt")  # True
fs.get_file_size("report_backup.txt")             # 100
fs.copy_file("missing.txt", "new.txt")            # False (source doesn't exist)
fs.copy_file("data.csv", "report.txt")            # False (dest already exists)

fs.delete_file("data.csv")           # True
fs.delete_file("data.csv")           # False (already deleted)

---

Level 2: Prefix Search

Problem Statement

Extend the system to support searching for files by name prefix, returning the largest files first.

def find_files(self, prefix: str, n: int) -> list:
    """
    Find up to N files whose names start with the given prefix,
    sorted by size in descending order.

    Args:
        prefix: The prefix to match file names against.
        n: The maximum number of files to return.

    Returns:
        A list of strings in the format "name(size)", sorted by
        file size in descending order. If two files have the same
        size, sort them alphabetically by name. If fewer than n
        files match the prefix, return all of them.
    """
    pass

Example Usage

fs = CloudFileSystem()

fs.add_file("report.txt", 100)
fs.add_file("report_v2.txt", 250)
fs.add_file("readme.md", 50)
fs.add_file("data.csv", 300)
fs.add_file("report_final.txt", 100)

fs.find_files("report", 2)
# ["report_v2.txt(250)", "report.txt(100)"]
# report_v2.txt has size 250, report.txt and report_final.txt both have
# size 100, but "report.txt" comes before "report_final.txt" alphabetically

fs.find_files("report", 10)
# ["report_v2.txt(250)", "report.txt(100)", "report_final.txt(100)"]

fs.find_files("data", 5)
# ["data.csv(300)"]

fs.find_files("missing", 5)
# []

---

Level 3: User Storage Management

Problem Statement

Extend the system with user accounts. Each user has a storage capacity limit. Files can be owned by a user, and a user's total file sizes must not exceed their capacity. Users can also be merged together.

Files created without a user (via add_file) are owned by a special "admin" user with unlimited capacity.

def add_user(self, user_id: str, capacity: int) -> bool:
    """
    Create a new user with a given storage capacity.

    Args:
        user_id: Unique identifier for the user.
        capacity: The maximum total file size this user can store.

    Returns:
        True if the user was successfully created,
        False if a user with the same ID already exists.

    Notes:
        - The "admin" user is reserved and cannot be created
          via this method.
    """
    pass

def add_file_by(self, user_id: str, name: str, size: int) -> bool:
    """
    Add a new file owned by a specific user.

    Args:
        user_id: The owner of the file.
        name: The name of the file.
        size: The size of the file (positive integer).

    Returns:
        True if the file was successfully added,
        False if:
        - The user does not exist, or
        - A file with the same name already exists, or
        - Adding the file would exceed the user's capacity.
    """
    pass

def merge_user(self, user_id1: str, user_id2: str) -> bool:
    """
    Merge user_id2 into user_id1.

    Args:
        user_id1: The target user (survives the merge).
        user_id2: The source user (removed after merge).

    Returns:
        True if the merge was successful,
        False if either user does not exist, or they are the same user.

    Notes:
        - user_id2's capacity is added to user_id1's capacity.
        - All files owned by user_id2 are transferred to user_id1.
        - user_id2 is removed from the system.
        - The "admin" user cannot be merged (neither as source
          nor target).
    """
    pass

Example Usage

fs = CloudFileSystem()

fs.add_user("alice", 500)             # True
fs.add_user("bob", 300)               # True
fs.add_user("alice", 1000)            # False (duplicate)

fs.add_file_by("alice", "doc.txt", 200)   # True (alice used: 200/500)
fs.add_file_by("alice", "img.png", 400)   # False (200 + 400 = 600 > 500)
fs.add_file_by("alice", "img.png", 250)   # True (alice used: 450/500)
fs.add_file_by("charlie", "x.txt", 10)    # False (user doesn't exist)

fs.add_file_by("bob", "notes.txt", 100)   # True (bob used: 100/300)

# Files added via add_file belong to "admin"
fs.add_file("global.dat", 999)             # True

fs.merge_user("alice", "bob")
# True
# alice capacity: 500 + 300 = 800
# alice now owns: doc.txt(200) + img.png(250) + notes.txt(100)
# alice used: 550/800, bob is removed

fs.add_file_by("bob", "x.txt", 10)        # False (bob no longer exists)
fs.add_file_by("alice", "big.dat", 200)    # True (alice used: 750/800)

---

Level 4: Backup and Restore

Problem Statement

Extend the system with the ability to back up and restore a user's files. Each user can have at most one backup at a time — creating a new backup overwrites the previous one.

def backup(self, user_id: str) -> int:
    """
    Create a backup of all files owned by the given user.

    Args:
        user_id: The user whose files to back up.

    Returns:
        The number of files backed up, or -1 if the user
        does not exist.

    Notes:
        - If the user already has a backup, the old backup is
          replaced with the new one.
        - The backup stores a snapshot of file names and sizes
          owned by the user at this point in time.
        - A user with no files can still be backed up (returns 0).
        - The "admin" user can be backed up.
    """
    pass

def restore(self, user_id: str) -> int:
    """
    Restore a user's files from their most recent backup.

    Args:
        user_id: The user whose files to restore.

    Returns:
        The number of files restored, or -1 if the user
        does not exist.

    Notes:
        - If the user has no backup, delete all of the user's
          current files and return 0.
        - If a file from the backup still exists with the same
          name AND is still owned by this user, skip it (do not
          restore, do not count it, keep the current version).
        - Files currently owned by the user that are NOT in the
          backup are deleted.
        - Files from the backup that no longer exist are re-created
          with the backed-up size. If a backed-up file name is now
          taken by a different user, skip it (do not restore).
        - Restored files must respect the user's capacity. Files
          from the backup are restored in alphabetical order by
          name. If restoring a file would exceed capacity, skip it.
        - The backup is consumed after a restore (cleared).
        - The "admin" user can be restored (with unlimited capacity).
    """
    pass

Corner Cases

1. No backup exists: If restore is called and the user has no backup, all of the user's current files are deleted and 0 is returned.
2. File still exists with same owner: If a backed-up file still exists with the same name and the same owner, it is skipped — the current version is kept, and it does not count toward the restore count.
3. File name taken by another user: If a backed-up file name now exists but is owned by a different user, the file is skipped (we cannot overwrite another user's file).
4. Admin backup: The "admin" user can be backed up and restored. Admin has unlimited capacity, so capacity checks don't apply.
5. Capacity during restore: For non-admin users, files are restored in alphabetical order. If restoring a file would exceed capacity, that file is skipped.

Example Usage

fs = CloudFileSystem()

fs.add_user("alice", 1000)
fs.add_file_by("alice", "doc.txt", 200)
fs.add_file_by("alice", "img.png", 300)

fs.backup("alice")                    # 2 (backed up doc.txt and img.png)

# Alice modifies her files
fs.delete_file("doc.txt")
fs.add_file_by("alice", "new.txt", 150)
# alice now has: img.png(300), new.txt(150)

fs.restore("alice")
# Restoring from backup: {doc.txt: 200, img.png: 300}
# - img.png still exists and is owned by alice → skip (keep current)
# - new.txt is NOT in backup → delete
# - doc.txt is in backup but doesn't exist → restore
# alice now has: img.png(300), doc.txt(200)
# Returns 1 (only doc.txt was restored)

fs.restore("alice")
# No backup exists (consumed after last restore)
# Delete all alice's files → alice now has no files
# Returns 0

# Backup with no files
fs.backup("alice")                    # 0
fs.add_file_by("alice", "x.txt", 100)
fs.restore("alice")
# Backup was empty → delete all current files
# alice now has no files
# Returns 0

fs.backup("nonexistent")             # -1
fs.restore("nonexistent")            # -1

---

Follow-Up Discussion Topics