Extend cloud file system with copy and compression
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## In-Memory Cloud File System V2: Copy, Capacity Updates, Compress/Decompress
Design an in-memory file system with per-user quotas and additional operations.
### Data model / rules
- Each file has:
- `name` (unique string)
- `size` (positive int)
- `owner` (user id)
- Each user has:
- `capacity`
- `used`
- A user may only own files such that `used <= capacity`.
### API
1. `add_user(user_id, capacity) -> bool`
- Create a user with `used = 0`.
2. `add_file_by(user_id, name, size) -> bool`
- Add a new file owned by `user_id`.
- Fail if user missing, name exists, or would exceed capacity.
3. `add_file(name, size) -> bool`
- Add a file owned by a special `admin` user with effectively unlimited capacity (or explicitly create admin with very large capacity).
4. `copy_file(from_name, to_name) -> bool`
- Duplicate an existing file to a new name.
- The copy has the same size and owner as the source.
- Fail if `from_name` missing, `to_name` already exists, or the owner’s capacity would be exceeded.
5. `get_file_size(name) -> int | null`
- Return size or `null` if missing.
6. `get_n_largest(prefix, suffix, n) -> list<string>`
- Filter files with `name` starting with `prefix` and ending with `suffix`.
- Return up to `n` formatted: `"name(size)"`.
- Sort by size desc, then name asc.
7. `update_capacity(user_id, new_capacity) -> bool`
- Update the user’s capacity.
- If `used > new_capacity`, repeatedly delete the user’s largest files (tie-break by name asc/desc—state your tie-break clearly) until `used <= new_capacity`.
- Return `false` if user missing.
8. `compress_file(name) -> bool`
- Convert a file into a compressed version:
- Only if `name` exists and does **not** already represent a compressed file.
- New file name becomes `name + "compress"` (or another fixed suffix; be consistent).
- New size becomes `floor(old_size / 2)`.
- Ownership stays the same.
- Replace the original (remove old name, add new name).
- Update the owner’s `used` accordingly.
9. `decompress_file(name) -> bool`
- Only valid if `name` ends with the compression suffix.
- New name removes the suffix; new size becomes `old_size * 2`.
- Fail if the decompressed name already exists or if the owner would exceed capacity.
- Replace the compressed file with the decompressed one.
### Notes
- Aim for correct bookkeeping of `used` and efficient deletion of largest files (e.g., heap + lazy deletion).
- Assume up to ~1e5 operations.
Quick Answer: This question evaluates understanding of data structures and algorithms for stateful resource management, covering bookkeeping of per-user quotas, file metadata operations (copy, compress/decompress), string filtering and sorting, and efficient selection and deletion of largest elements.
You are given a list of queries to execute against an in-memory cloud file system.
Each live file has a unique name, a size, and an owner. Each user has a capacity and currently used space. A reserved user named "admin" exists from the start with capacity 10^18.
Process every query and return the result of that API call in order.
Use the fixed compression suffix ".cmp". A file is considered compressed if and only if its name ends with this suffix.
Operations:
- add_user(user_id, capacity) -> bool
Create a new user with used = 0. Return false if the user already exists.
- add_file_by(user_id, name, size) -> bool
Add a new file owned by user_id. Return false if the user does not exist, the name already exists, or adding it would exceed the user's capacity.
- add_file(name, size) -> bool
Same as add_file_by, but the owner is admin.
- copy_file(from_name, to_name) -> bool
Duplicate an existing file. The copy keeps the same size and owner. Return false if the source does not exist, the destination already exists, or the owner's capacity would be exceeded.
- get_file_size(name) -> int | None
Return the file's size, or None if it does not exist.
- get_n_largest(prefix, suffix, n) -> list[str]
Consider only files whose names start with prefix and end with suffix. Return up to n strings formatted as "name(size)", sorted by size descending, then name ascending.
- update_capacity(user_id, new_capacity) -> bool
Update the user's capacity. If used space becomes too large, repeatedly delete that user's largest file until used <= capacity. If multiple files have the same largest size, delete the lexicographically smaller name first. Return false only if the user does not exist.
- compress_file(name) -> bool
Only valid if the file exists and its name does not already end with ".cmp". Replace it with a file named name + ".cmp" and size floor(old_size / 2). Ownership stays the same. Return false if the target name already exists.
- decompress_file(name) -> bool
Only valid if the file exists and its name ends with ".cmp". Replace it with the name obtained by removing the suffix, and size old_size * 2. Return false if the target name already exists or the owner's capacity would be exceeded.
All sizes given in add operations are positive integers. Compression may produce size 0 if a size-1 file is compressed.
Constraints
- 0 <= len(queries) <= 10^5
- User capacities and file sizes in add operations are integers in the range [0, 10^9], and file names are unique among live files
- Use lexicographically smaller name first when update_capacity must delete among files with equal size
Examples
Input: [('add_user', 'u1', 15), ('add_file_by', 'u1', 'fileA', 4), ('add_file_by', 'u1', 'fileB', 5), ('copy_file', 'fileA', 'fileA_copy'), ('get_file_size', 'fileA_copy'), ('get_n_largest', 'file', '', 3)]
Expected Output: [True, True, True, True, 4, ['fileB(5)', 'fileA(4)', 'fileA_copy(4)']]
Explanation: The copy succeeds because u1 still has enough remaining capacity. The largest matching files are ordered by size descending, then name ascending.
Input: [('add_user', 'u1', 10), ('add_file_by', 'u1', 'alpha', 4), ('add_file_by', 'u1', 'beta', 4), ('add_file_by', 'u1', 'gamma', 2), ('update_capacity', 'u1', 6), ('get_file_size', 'alpha'), ('get_n_largest', '', '', 5), ('add_file_by', 'u1', 'delta', 1)]
Expected Output: [True, True, True, True, True, None, ['beta(4)', 'gamma(2)'], False]
Explanation: After lowering capacity to 6, one size-4 file must be deleted. alpha and beta tie in size, so alpha is removed first because its name is lexicographically smaller.
Hints
- Use hash maps for users and files so that existence checks, ownership lookups, and size lookups are O(1).
- For update_capacity, keep a max-heap per user keyed by (-size, name). Because files can be deleted or renamed, use lazy deletion when popping from the heap.