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 role is this question designed for?

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

Implement an In-Memory File System | Rippling Coding Question

Implement an In-Memory File System

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Interview Round: Onsite

Implement an in-memory file system directory management tool. Your tool should support the following operations: 1. **Create a file** in a directory. 2. **Create a directory** inside another directory. 3. **Delete** a file or directory. 4. **List contents** of the current directory. Assume paths may refer to nested directories, such as `/a/b/c/file.txt`. Clarify and handle reasonable edge cases, such as: - Creating a file when the parent directory does not exist. - Creating a duplicate file or directory with the same name in the same parent directory. - Deleting a non-empty directory. - Listing an empty directory. - Handling invalid paths. Follow-up questions: - How would your implementation handle very deeply nested directory structures? - How would you efficiently support searching for files or directories by name?

Quick Answer: This question evaluates understanding of file-system abstractions, tree-based data structures, path parsing, and stateful directory and file management operations.

Part 1: Basic In-Memory File System Operations

Implement a small in-memory file system. The file system starts with only the root directory '/'. Process a sequence of operations to create directories, create files, delete files or empty directories, and list directory contents. Paths are absolute, such as '/a/b/file.txt'. A path is invalid if it is not absolute, contains empty components like '/a//b', ends with '/' except for root, or contains '.' or '..'.

Constraints

1 <= len(operations) <= 10^4
Each path length is at most 1000 characters.
Names cannot be empty and cannot be '.' or '..'.
A directory cannot contain two entries with the same name, even if one is a file and one is a directory.
The 'delete' operation only deletes files or empty directories; deleting root is not allowed.

Examples

Input: ([['mkdir', '/a'], ['touch', '/a/file.txt'], ['mkdir', '/a/b'], ['ls', '/a'], ['delete', '/a/file.txt'], ['ls', '/a']],)

Expected Output: [['OK'], ['OK'], ['OK'], ['b', 'file.txt'], ['OK'], ['b']]

Explanation: Creates a directory, a file, and a subdirectory. Listing '/a' returns sorted child names. After deleting the file, only 'b' remains.

Input: ([['touch', '/x/y.txt'], ['mkdir', '/x'], ['mkdir', '/x'], ['touch', '/x'], ['ls', '/x']],)

Expected Output: [['ERROR'], ['OK'], ['ERROR'], ['ERROR'], []]

Explanation: The first file creation fails because '/x' does not exist. Duplicate creation also fails. Listing an empty directory returns an empty list.

Input: ([['mkdir', '/a'], ['mkdir', '/a/b'], ['delete', '/a'], ['delete', '/a/b'], ['delete', '/a'], ['ls', '/']],)

Expected Output: [['OK'], ['OK'], ['ERROR'], ['OK'], ['OK'], []]

Explanation: A non-empty directory cannot be deleted. After deleting '/a/b', '/a' becomes empty and can be deleted.

Input: ([['mkdir', '/bad//path'], ['mkdir', 'relative'], ['touch', '/file'], ['ls', '/file'], ['delete', '/'], ['ls', '/missing']],)

Expected Output: [['ERROR'], ['ERROR'], ['OK'], ['ERROR'], ['ERROR'], ['ERROR']]

Explanation: Invalid paths fail. Listing a file fails. Deleting root is not allowed.

Hints

Represent each directory as a mapping from child name to child node.
Most operations need to find the parent directory of the target path before modifying the tree.

Part 2: Deeply Nested Directory Structure Without Recursion

Adapt an in-memory directory system to handle very deeply nested directory paths. The system starts with only root '/'. You must support creating all directories along a path, checking whether a directory exists, and deleting an entire directory subtree. Hidden tests may include paths deeper than Python's recursion limit, so subtree deletion should be iterative rather than recursive.

Constraints

1 <= len(operations) <= 10^5
The total number of path components across all operations is at most 2 * 10^5.
A valid path is absolute, does not end with '/' except for root, and has no empty, '.', or '..' components.
Directory depth may be greater than 10^4.
Deleting root is not allowed.

Examples

Input: ([['mkdirp', '/a/b/c'], ['exists', '/a/b'], ['rmtree', '/a/b'], ['exists', '/a/b/c'], ['exists', '/a']],)

Expected Output: [['3'], ['true'], ['2'], ['false'], ['true']]

Explanation: Creates '/a', '/a/b', and '/a/b/c'. Deleting '/a/b' removes both '/a/b' and '/a/b/c'.

Input: ([['mkdirp', '/d0/d1/d2/d3/d4'], ['mkdirp', '/d0/d1/d2/d3/d4'], ['rmtree', '/d0/d1/d2'], ['exists', '/d0/d1'], ['exists', '/d0/d1/d2']],)

Expected Output: [['5'], ['0'], ['3'], ['true'], ['false']]

Explanation: The second mkdirp creates nothing because the full path already exists. Removing '/d0/d1/d2' deletes three directories.

Input: ([['mkdirp', '/'], ['exists', '/'], ['rmtree', '/'], ['mkdirp', '/a//b'], ['exists', '/a//b']],)

Expected Output: [['0'], ['true'], ['0'], ['ERROR'], ['false']]

Explanation: Root already exists and cannot be removed. The path '/a//b' is invalid.

Input: ([['mkdirp', '/a/b'], ['mkdirp', '/a/c/d'], ['rmtree', '/a/c'], ['exists', '/a/b'], ['exists', '/a/c/d']],)

Expected Output: [['2'], ['2'], ['2'], ['true'], ['false']]

Explanation: Deleting one subtree does not affect sibling directories.

Hints

Use an explicit stack for subtree deletion instead of recursive DFS.
Storing nodes in arrays by integer ID can avoid recursive object traversal and can be efficient for very deep trees.

Part 3: In-Memory File System with Efficient Name Search

Extend an in-memory file system so that files or directories can be searched efficiently by name. The system starts with only root '/'. Support creating directories, creating files, deleting a file or directory subtree, and searching for all paths whose final component equals a given name. Search should not scan the entire file system each time.

Constraints

1 <= len(operations) <= 10^5
Each path length is at most 2000 characters.
A valid path is absolute, does not end with '/' except for root, and has no empty, '.', or '..' components.
A search name is valid if it is a single non-empty component and is not '.' or '..'.
The total number of created file-system entries is at most 10^5.

Examples

Input: ([['mkdir', '/src'], ['touch', '/src/readme.md'], ['mkdir', '/docs'], ['touch', '/docs/readme.md'], ['search', 'readme.md'], ['search', 'src']],)

Expected Output: [['OK'], ['OK'], ['OK'], ['OK'], ['/docs/readme.md', '/src/readme.md'], ['/src']]

Explanation: The search index returns all paths with the requested final name in sorted order.

Input: ([['touch', '/missing/a.txt'], ['mkdir', '/a'], ['touch', '/a'], ['mkdir', '/a'], ['search', 'a']],)

Expected Output: [['ERROR'], ['OK'], ['ERROR'], ['ERROR'], ['/a']]

Explanation: Creating inside a missing parent fails. A file cannot be created with the same path as an existing directory.

Input: ([['mkdir', '/a'], ['mkdir', '/a/x'], ['touch', '/a/x/file'], ['mkdir', '/b'], ['touch', '/b/file'], ['search', 'file'], ['delete', '/a'], ['search', 'file'], ['search', 'x']],)

Expected Output: [['OK'], ['OK'], ['OK'], ['OK'], ['OK'], ['/a/x/file', '/b/file'], ['3'], ['/b/file'], []]

Explanation: Deleting '/a' removes '/a', '/a/x', and '/a/x/file' from both the file system and the search index.

Input: ([['search', 'none'], ['mkdir', '/'], ['mkdir', '/bad//x'], ['search', 'bad/name'], ['delete', '/'], ['delete', '/missing']],)

Expected Output: [[], ['ERROR'], ['ERROR'], [], ['0'], ['0']]

Explanation: Searching for a missing name returns an empty list. Invalid paths fail. Deleting root is not allowed.

Hints

Maintain a dictionary from base name to a set of full paths.
When deleting a directory subtree, remove every deleted path from both the tree and the search index.

Quick Overview

This question evaluates understanding of file-system abstractions, tree-based data structures, path parsing, and stateful directory and file management operations.