Quick Overview

This question evaluates understanding of object-oriented design, stateful data structures, and resource management including user quotas, ownership semantics, and file metadata operations.

Design an in-memory cloud file system

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## In-Memory Cloud File System (OOD) Design an in-memory cloud file system that supports files owned by users with storage quotas. ### Data model / rules - Each file has a unique `name` (string) and a `size` (positive integer). - Each file is owned by exactly one user. - Each user has a **remaining capacity** (how many bytes they can still store). - Special user `"admin"` exists and has **infinite** capacity. - Adding a file consumes the owner’s remaining capacity by `size`. - Deleting a file refunds its size back to the owner’s remaining capacity. ### API to implement Implement a class with the following methods (exact names not required, behavior is): 1. `add_user(user_id, capacity) -> bool` - Create a new user with the given remaining capacity. - Return `false` if the user already exists. 2. `add_file(name, size) -> bool` - Convenience method: add a file owned by `admin`. - Return `false` if the file already exists. 3. `add_file_by(user_id, name, size) -> int | null` - Add a file owned by `user_id`. - Return the user’s **remaining capacity after** adding. - Return `null` if: - `user_id` does not exist - `name` already exists - `size` exceeds the user’s remaining capacity 4. `get_file_size(name) -> int | null` - Return the file size, or `null` if not found. 5. `delete_file(name) -> int | null` - Delete the file. - Return the deleted file’s size, or `null` if not found. 6. `get_n_largest(prefix, n) -> list<string>` - Consider only file names starting with `prefix`. - Return up to `n` files formatted as: `"<name>(<size>)"`. - Sort by: 1) size descending 2) name ascending (lexicographic) for ties 7. `merge_user(user_id_1, user_id_2) -> int | null` - Merge `user_id_2` into `user_id_1`. - All files owned by `user_id_2` become owned by `user_id_1`. - `user_id_1`’s remaining capacity increases by `user_id_2`’s remaining capacity. - Delete `user_id_2`. - Return `user_id_1`’s new remaining capacity. - Return `null` if either user doesn’t exist or the IDs are the same. 8. `backup_user(user_id) -> int | null` - Store a snapshot of the *current set of files owned by* `user_id` (name -> size). - Return the number of files included in this backup. - Return `null` if the user doesn’t exist. 9. `restore_user(user_id) -> int | null` - Restore `user_id`’s files from the most recent backup for that user. - First, remove all files currently owned by `user_id`. - Then, for each file in the backup, restore it **only if its name is not currently used** by some other user. - Return the number of files actually restored. - If the user exists but has no backup, return `0`. - If the user doesn’t exist, return `null`. ### Notes - Assume up to ~1e5 operations. - You may choose any internal data structures, but must satisfy the behavior above.

Quick Answer: This question evaluates understanding of object-oriented design, stateful data structures, and resource management including user quotas, ownership semantics, and file metadata operations.

You are given a sequence of operations to run on an in-memory cloud file system. Implement `solution(operations)` and return the result of every operation in order. Rules: - Each file has a unique string `name`, a positive integer `size`, and exactly one owner. - Each user has a remaining storage capacity. - The system starts with a built-in user `"admin"` that has infinite capacity. - Adding a file consumes the owner's remaining capacity by its size. - Deleting a file refunds its size to the owner's remaining capacity. - `backup_user` stores only the current set of files owned by that user (`name -> size`). Only the most recent backup per user is kept. - `restore_user` first removes all files currently owned by that user, then restores each file from the latest backup only if that file name is not currently used by someone else. - To keep the built-in admin account always available, `merge_user(x, "admin")` is considered invalid. - When a user is deleted by `merge_user`, that user's backup is also discarded. Return Python values: use `None` for `null`.

Constraints

  • 1 <= len(operations) <= 10^5
  • 0 <= capacity <= 10^9
  • 1 <= size <= 10^9
  • 0 <= n <= 10^5
  • 1 <= len(user_id), len(name) <= 50
  • The sum of lengths of all file names appearing in the input is at most 2 * 10^5
  • `admin` exists from the start, cannot be re-added, and cannot be removed by `merge_user(x, 'admin')`
  • No successful test operation requires returning admin's infinite remaining capacity

Examples

Input: [('add_user', 'alice', 10), ('add_user', 'alice', 5), ('add_file', 'sys.log', 4), ('add_file_by', 'alice', 'a.txt', 3), ('add_file_by', 'alice', 'a.txt', 2), ('add_file_by', 'alice', 'b.txt', 8), ('get_file_size', 'sys.log'), ('get_n_largest', '', 3), ('delete_file', 'a.txt'), ('add_file_by', 'alice', 'b.txt', 8), ('get_n_largest', '', 5)]

Expected Output: [True, False, True, 7, None, None, 4, ['sys.log(4)', 'a.txt(3)'], 3, 2, ['b.txt(8)', 'sys.log(4)']]

Explanation: Covers duplicate users, duplicate file names, insufficient capacity, deleting a file to refund space, and querying the largest files across the whole system with an empty prefix.

Input: [('add_user', 'u1', 5), ('add_user', 'u2', 10), ('add_file_by', 'u1', 'cat', 3), ('add_file_by', 'u2', 'car', 4), ('add_file_by', 'u2', 'cap', 4), ('get_n_largest', 'ca', 5), ('merge_user', 'u1', 'u2'), ('delete_file', 'car'), ('get_n_largest', 'ca', 5), ('merge_user', 'u1', 'u1'), ('merge_user', 'u1', 'u2')]

Expected Output: [True, True, 2, 6, 2, ['cap(4)', 'car(4)', 'cat(3)'], 4, 4, ['cap(4)', 'cat(3)'], None, None]

Explanation: Files with prefix 'ca' are sorted by size descending, then name ascending for ties. After merging, u1 gains u2's remaining capacity and ownership of u2's files.

Hints

  1. Use multiple hash maps: one for `file -> (size, owner)`, one for `user -> remaining capacity`, and one for `user -> owned file names`.
  2. For `get_n_largest(prefix, n)`, avoid scanning every file each time by maintaining a mapping from every prefix to the set of file names currently using that prefix.

Loading coding console...