Cloud storage with user quotas and backups

Clarify first. This is a multi-part design problem. Each part adds methods and must keep the earlier ones working, so the data model matters more than any single algorithm. Ask: are names full paths and compared as exact strings (yes)? Are sizes positive integers? What do the "by user" methods return on failure (None)? How are ties ordered in search results (size descending, then name ascending)? Is the original add_file an admin call with no quota (yes)?

Data model. Keep one dictionary files: name -> File(size, owner) and one dictionary users: id -> User(capacity, used). Seed a built-in admin user with unlimited capacity, and make add_file(name, size) a thin wrapper around add_file_by("admin", name, size). Then every later part changes only the user layer, and Part 1 never has to be rewritten. All writes go through two helpers, _put and _drop, which update the file map and the owner's used counter together.

Invariant. For every user, used equals the sum of the sizes of the files they own, and no name appears twice in files. Every mutation (add, copy, evict, merge, restore) goes through _put / _drop, so the invariant holds after each call. Capacity checks are then an O(1) comparison instead of a re-scan.

Part 1 (add, copy, size). Name lookup is a dictionary hit. copy_file fails when the source is missing or the destination exists. The copy belongs to the source file's owner and is charged to their quota, which only matters once Part 3 exists.

Part 2 (search). Brute force is the right first answer: scan all files, keep those matching the prefix and suffix, sort by (-size, name), and return the first 10 formatted as name(size). Mention the better structures (a trie on names for the prefix, a heap of size k instead of a full sort) as follow-ups. Don't build them before the interviewer asks.

Part 3 (users and quotas). add_file_by checks that the user exists, that the name is free, and that used + size <= capacity, then returns the remaining capacity. update_capacity sets the new limit and evicts the user's largest files (ties by name) until they fit. It returns how many files it removed.

Part 4 (merge, backup, restore). merge_user(target, source) reassigns the source's files, adds both capacity and usage to the target, and deletes the source and its backup. backup_user snapshots {name: size} for the user's files and replaces any older snapshot. restore_user deletes the user's current files, then re-adds each backed-up file whose name is still free. A name another user took in the meantime is skipped, not overwritten. With no backup, restore just empties the user's files.

from dataclasses import dataclass
from typing import Optional

ADMIN = "admin"


@dataclass
class File:
    size: int
    owner: str


@dataclass
class User:
    capacity: Optional[int]  # None means unlimited (the admin)
    used: int = 0

    def fits(self, size: int) -> bool:
        return self.capacity is None or self.used + size <= self.capacity

    def remaining(self) -> int:
        return -1 if self.capacity is None else self.capacity - self.used


class CloudStorage:
    def __init__(self) -> None:
        self.files: dict[str, File] = {}
        self.users: dict[str, User] = {ADMIN: User(capacity=None)}
        self.backups: dict[str, dict[str, int]] = {}

    # ---- Part 1 -------------------------------------------------------
    def add_file(self, name: str, size: int) -> bool:
        return self.add_file_by(ADMIN, name, size) is not None

    def copy_file(self, name_from: str, name_to: str) -> bool:
        src = self.files.get(name_from)
        if src is None or name_to in self.files:
            return False
        owner = self.users[src.owner]
        if not owner.fits(src.size):
            return False
        self._put(name_to, src.size, src.owner)
        return True

    def get_file_size(self, name: str) -> int:
        f = self.files.get(name)
        return f.size if f else -1

    # ---- Part 2 -------------------------------------------------------
    def find_files(self, prefix: str, suffix: str, limit: int = 10) -> list[str]:
        hits = [
            (name, f.size)
            for name, f in self.files.items()
            if name.startswith(prefix) and name.endswith(suffix)
        ]
        hits.sort(key=lambda h: (-h[1], h[0]))
        return [f"{name}({size})" for name, size in hits[:limit]]

    # ---- Part 3 -------------------------------------------------------
    def add_user(self, user_id: str, capacity: int) -> bool:
        if user_id in self.users:
            return False
        self.users[user_id] = User(capacity=capacity)
        return True

    def add_file_by(self, user_id: str, name: str, size: int) -> Optional[int]:
        user = self.users.get(user_id)
        if user is None or name in self.files or not user.fits(size):
            return None
        self._put(name, size, user_id)
        return user.remaining()

    def update_capacity(self, user_id: str, capacity: int) -> Optional[int]:
        user = self.users.get(user_id)
        if user is None or user_id == ADMIN:
            return None
        user.capacity = capacity
        # Evict largest first; ties broken by name so the result is deterministic.
        owned = sorted(
            ((f.size, name) for name, f in self.files.items() if f.owner == user_id),
            key=lambda t: (-t[0], t[1]),
        )
        removed = 0
        for size, name in owned:
            if user.used <= capacity:
                break
            self._drop(name)
            removed += 1
        return removed

    # ---- Part 4 -------------------------------------------------------
    def merge_user(self, target_id: str, source_id: str) -> Optional[int]:
        if target_id == source_id or ADMIN in (target_id, source_id):
            return None
        target, source = self.users.get(target_id), self.users.get(source_id)
        if target is None or source is None:
            return None
        for f in self.files.values():
            if f.owner == source_id:
                f.owner = target_id
        target.capacity += source.capacity  # type: ignore[operator]
        target.used += source.used
        del self.users[source_id]
        self.backups.pop(source_id, None)
        return target.remaining()

    def backup_user(self, user_id: str) -> Optional[int]:
        if user_id not in self.users:
            return None
        snap = {n: f.size for n, f in self.files.items() if f.owner == user_id}
        self.backups[user_id] = snap
        return len(snap)

    def restore_user(self, user_id: str) -> Optional[int]:
        if user_id not in self.users:
            return None
        for name in [n for n, f in self.files.items() if f.owner == user_id]:
            self._drop(name)
        restored = 0
        for name, size in self.backups.get(user_id, {}).items():
            if name not in self.files:  # taken by someone else since: skip
                self._put(name, size, user_id)
                restored += 1
        return restored

    # ---- helpers ------------------------------------------------------
    def _put(self, name: str, size: int, owner: str) -> None:
        self.files[name] = File(size, owner)
        self.users[owner].used += size

    def _drop(self, name: str) -> None:
        f = self.files.pop(name)
        self.users[f.owner].used -= f.size

Let F be the number of files in the system and f_u the number owned by user u.

• add_file, add_file_by, copy_file, get_file_size, add_user: O(1) average time (dictionary operations), O(1) extra space.
• find_files: O(F * L + m log m) time, where L is the prefix/suffix length and m the number of matches. Space O(m). With a heap of size 10 the sort becomes O(m log 10).
• update_capacity: O(F + f_u log f_u), a scan to find the user's files plus a sort. Keeping a per-user name set makes the scan O(f_u).
• merge_user: O(F) here, or O(f_source) with per-user file sets.
• backup_user: O(F) time to scan, O(f_u) space for the snapshot.
• restore_user: O(F + b), where b is the snapshot size.
• Total space: O(F + U + B) for files, users, and stored backups.

• add_file("/docs/a.txt", 100) → True; repeat with any size → False.
• get_file_size("/docs/a.txt") → 100; get_file_size("/nope") → -1.
• copy_file("/docs/a.txt", "/docs/b.txt") → True; the same call again → False (destination exists); copy_file("/missing", "/x") → False.
• With /docs/a.txt(100), /docs/b.txt(100), /docs/c.log(300), /img/d.txt(300): find_files("/docs/", ".txt") → ["/docs/a.txt(100)", "/docs/b.txt(100)"] (equal sizes ordered by name); find_files("/", ".txt") → ["/img/d.txt(300)", "/docs/a.txt(100)", "/docs/b.txt(100)"]; no match → [].
• add_user("u1", 500) → True; again → False. add_file_by("u1", "/u1/x", 200) → 300; add_file_by("u1", "/u1/y", 250) → 50; add_file_by("u1", "/u1/z", 60) → None (over quota). Unknown user → None.
• copy_file("/u1/x", "/u1/x2") → False, because the copy would push u1 over quota.
• u1 owns 200, 250 and 50 (full at 500). update_capacity("u1", 300) → 1: it evicts /u1/y (250), and usage drops to 250. Raising the capacity → 0. Unknown user → None.
• u2 (capacity 100) owns /u2/p(40). backup_user("u2") → 1. Add /u2/q(10). restore_user("u2") → 1: /u2/q is gone and /u2/p is back.
• merge_user("u1", "u2") → remaining 1100 - 290 = 810; u2 no longer exists. Merging a user into itself → None.
• Restore conflict: u3 backs up /shared, loses it, and then admin adds /shared. restore_user("u3") → 0, and the admin's file is untouched.

1. Directories. Names become hierarchical and copy_file must reject a source that is a directory. Store a trie of path segments, where a node is a directory if it has children and a file if it carries a File. Add list_dir and recursive delete. Check capacity for a recursive copy against the total subtree size before writing anything.
2. Faster search. For a prefix-only search, keep the names in a sorted list (bisect over the range) or a trie with subtree size maxima. For prefix plus suffix, intersect a prefix trie with a reversed-name suffix trie, or index suffix + "#" + name (as in LeetCode 745). Use heapq.nsmallest(10, ...) so the work for top-k is O(m log k).
3. Timestamps and TTL. Every method takes a timestamp, and files may have a time to live. Store an expiry per file, treat expired files as absent in every read, and clean them up lazily (on access) or with a min-heap of expiries. Backup and restore then have to say whether restored files keep their original TTL relative to the backup time.
4. History / rollback to a timestamp. Instead of one backup per user, keep an append-only log of operations and rebuild the state as of any time t, or keep versioned values per name (name -> list[(t, File)]) and binary-search them.
5. Concurrency and scale. Many clients write at once. Lock per user for quota checks, plus a lock or compare-and-set on the name for uniqueness, taken in a fixed order to avoid deadlock. Copy and merge touch two users and need both locks. Sharding by name breaks the per-user quota, so a separate quota service with reservations is needed.

Mid-level (L4)

• Gets Parts 1 and 2 right, including -1 for missing files and the size-then-name tie-break.
• Reaches Part 3 with a working quota check, even if eviction needs a hint.
• Tests duplicates, missing names, and empty search results.

Senior (L5)

• Picks a model up front (admin user, used counter, shared _put / _drop) so later parts don't require rewriting earlier ones.
• Finishes Parts 1-3 quickly and cleanly, and handles subtle cases such as copies charged to the owner and deterministic eviction order.
• Completes most of Part 4, including the restore name-conflict rule, and states the complexity of each method.

Staff (L6+)

• States the used == sum(owned sizes) invariant and shows that every mutation preserves it.
• Finishes all parts with time to spare and discusses per-user indexes, trie or suffix indexes for search, and lazy TTL expiry.
• Thinks about where the single-process design breaks: concurrent quota checks, multi-user atomicity in merge and copy, and sharding versus global name uniqueness.