Implement an In-Memory File Storage System
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Implement an in-memory file storage service.
You need to support files identified by a unique full path string, such as `"/docs/a.txt"`. Each file has an integer `size` and is owned either by the built-in admin user or by a normal user. Directories do not need to be stored separately; treat paths as plain strings.
Design a class that supports the following operations:
1. `addFile(name: string, size: int) -> bool`
- Adds a new admin-owned file with path `name` and file size `size`.
- Return `true` if the file did not already exist and was added.
- Return `false` if a file with the same name already exists.
2. `copyFile(source: string, destination: string) -> bool`
- Copies the file at `source` to a new path `destination`.
- The copied file has the same size and owner as the source file.
- Return `true` if `source` exists and `destination` does not already exist.
- Return `false` otherwise.
3. `getFileSize(name: string) -> int`
- Return the size of the file named `name`.
- Return `-1` if the file does not exist.
4. `findFiles(prefix: string, suffix: string) -> list[string]`
- Return all files whose names start with `prefix` and end with `suffix`.
- Each result should be formatted as `"<name>(<size>)"`, for example `"/docs/a.txt(120)"`.
- Sort results by size in descending order. If two files have the same size, sort by file name in lexicographical order.
5. `addUser(userId: string, capacity: int) -> bool`
- Adds a new user with maximum storage capacity `capacity`.
- Return `true` if the user did not already exist.
- Return `false` otherwise.
6. `addFileByUser(userId: string, name: string, size: int) -> int`
- Adds a new file owned by `userId`.
- The file can be added only if the user exists, the file name does not already exist, and the user's used storage plus `size` does not exceed their capacity.
- Return the user's remaining capacity after the file is added.
- Return `-1` if the operation fails.
7. `updateUserCapacity(userId: string, newCapacity: int) -> int`
- Updates the capacity of an existing user.
- If the user's current used storage exceeds `newCapacity`, remove that user's files until their used storage is at most `newCapacity`.
- When removing files, remove the largest files first; if there is a tie, remove the lexicographically largest file name first.
- Return the number of files removed.
- Return `-1` if the user does not exist.
Assume all operations are performed in memory. Choose appropriate data structures and implement the APIs efficiently.
Quick Answer: This question evaluates the ability to design and implement efficient in-memory data structures and algorithms for stateful file management, covering string-keyed storage, size accounting, querying and sorting, and user quota enforcement.
Implement a function that simulates an in-memory file storage service.
Files are identified by a unique full path string such as '/docs/a.txt'. Directories do not need to be stored separately; treat paths as plain strings. Every file has an integer size and an owner: either the built-in admin user or a normal user.
Your function receives a list of operations and must return the result of each operation in order.
Supported operations:
1. ('addFile', name, size) -> bool
Add a new admin-owned file.
Return True if the file did not already exist, otherwise False.
2. ('copyFile', source, destination) -> bool
Copy the file at source to destination.
The new file keeps the same size and owner as the source.
Return True only if source exists, destination does not exist, and if the file is user-owned, the owner's storage capacity is not exceeded by the copy.
Otherwise return False.
3. ('getFileSize', name) -> int
Return the file's size, or -1 if it does not exist.
4. ('findFiles', prefix, suffix) -> list[str]
Return all file names that start with prefix and end with suffix.
Format each result as '<name>(<size>)'.
Sort by size descending; if sizes are equal, sort by file name in lexicographical order.
5. ('addUser', userId, capacity) -> bool
Add a new normal user with maximum storage capacity.
Return True if the user did not already exist, otherwise False.
6. ('addFileByUser', userId, name, size) -> int
Add a new file owned by userId.
Succeeds only if the user exists, the file name does not already exist, and the user's used storage plus size does not exceed capacity.
Return the user's remaining capacity after adding the file.
Return -1 if the operation fails.
7. ('updateUserCapacity', userId, newCapacity) -> int
Update an existing user's capacity.
If the user's used storage is greater than newCapacity, remove that user's files until usage is at most newCapacity.
Remove the largest files first; if there is a tie, remove the lexicographically largest file name first.
Return the number of files removed.
Return -1 if the user does not exist.
The built-in admin user is always available and has no storage limit.
Constraints
- 1 <= len(operations) <= 2 * 10^4
- 0 <= size, capacity, newCapacity <= 10^9
- Path names and user IDs are non-empty strings of length at most 100
- 'admin' is a reserved built-in user and should not be added with addUser
- At most 2 * 10^4 files exist at any time
Examples
Input: [('addFile', '/docs/a.txt', 120), ('addFile', '/docs/b.txt', 80), ('addFile', '/docs/a.txt', 50), ('getFileSize', '/docs/a.txt'), ('copyFile', '/docs/a.txt', '/backup/a.txt'), ('findFiles', '/', 'a.txt'), ('findFiles', '/docs', '.txt')]
Expected Output: [True, True, False, 120, True, ['/backup/a.txt(120)', '/docs/a.txt(120)'], ['/docs/a.txt(120)', '/docs/b.txt(80)']]
Explanation: The duplicate addFile fails. The copy succeeds. findFiles returns matching files sorted by size descending, then by name.
Input: [('addUser', 'alice', 10), ('addFileByUser', 'alice', '/u/x.txt', 6), ('copyFile', '/u/x.txt', '/u/x_copy.txt'), ('addFileByUser', 'alice', '/u/y.txt', 4), ('copyFile', '/u/y.txt', '/u/y_copy.txt'), ('getFileSize', '/u/y.txt'), ('findFiles', '/u', '.txt')]
Expected Output: [True, 4, False, 0, False, 4, ['/u/x.txt(6)', '/u/y.txt(4)']]
Explanation: Alice can store x.txt and y.txt exactly up to capacity 10. Both copy attempts fail because each copy would exceed her capacity.
Hints
- Use one hash map from file path to its metadata so existence checks, copies, and size lookups are O(1) on average.
- For each user, track used space and the set of files they own. During updateUserCapacity, sort only that user's files in the required removal order.