How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Instacart.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Instacart during technical interviews.

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.

Input: [('addUser', 'bob', 25), ('addFileByUser', 'bob', '/p/a.txt', 10), ('addFileByUser', 'bob', '/p/b.txt', 10), ('addFileByUser', 'bob', '/p/c.txt', 5), ('updateUserCapacity', 'bob', 10), ('getFileSize', '/p/a.txt'), ('getFileSize', '/p/b.txt'), ('getFileSize', '/p/c.txt'), ('findFiles', '/p', '.txt')]

Expected Output: [True, 15, 5, 0, 2, -1, -1, 5, ['/p/c.txt(5)']]

Explanation: Bob uses 25 total. Reducing capacity to 10 removes the largest files first. Between the two size-10 files, '/p/b.txt' is removed before '/p/a.txt' because it is lexicographically larger.

Input: [('findFiles', '/nothing', '.zip'), ('addUser', 'admin', 100), ('addUser', 'anna', 5), ('addUser', 'anna', 7), ('addFileByUser', 'missing', '/m.txt', 1), ('updateUserCapacity', 'missing', 0), ('getFileSize', '/missing.txt')]

Expected Output: [[], False, True, False, -1, -1, -1]

Explanation: This covers edge cases: no matches for findFiles, reserved admin user, duplicate user creation, missing user, and missing file.

Input: [('addUser', 'eve', 20), ('addFileByUser', 'eve', '/e/a.log', 7), ('copyFile', '/e/a.log', '/e/b.log'), ('updateUserCapacity', 'eve', 14), ('findFiles', '/e', '.log')]

Expected Output: [True, 13, True, 0, ['/e/a.log(7)', '/e/b.log(7)']]

Explanation: The copy succeeds because Eve's usage becomes 14, which still fits within capacity 20. Updating capacity to 14 removes nothing.

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.

Quick Overview

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.