How do you approach In-Memory File System?

Model the tree as a node with children: Map and content: string (for files).

What is the time complexity of In-Memory File System?

Time complexity: mkdir and addContentToFile are O(L) where L is the number of path components; ls is O(L + k log k) where k is the children count of the target node.. Space complexity: O(total path components + total content).

What are common mistakes on In-Memory File System?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

In-Memory File System

HardObject-Oriented Design

Description

Design an in-memory file system that supports four operations: - `ls(path)`: If `path` is a file path, return a list containing only the file name. If `path` is a directory path, return the lexicographically sorted list of file and sub-directory names directly inside the directory. - `mkdir(path)`: Create a new directory at `path`. If middle directories in the path don't exist, they should be created too. - `addContentToFile(path, content)`: If the file at `path` doesn't exist, create it (along with any necessary parent dirs). If it does, append content to its existing content. - `readContentFromFile(path)`: Return the content of the file at `path`. All paths are absolute (start with `/`) and use `/` as separator. Path components are non-empty, lowercase letters and digits only. **For the auto-grader:** implement `fileSystemOps(operations)` returning the result of each operation in order. Each op is one of: - `["ls", path]` → string[] - `["mkdir", path]` → `null` / `None` - `["addContentToFile", path, content]` → `null` / `None` - `["readContentFromFile", path]` → string

Example 1

Input: operations = [["ls","/"],["mkdir","/a/b/c"],["addContentToFile","/a/b/c/d","hello"],["ls","/"],["readContentFromFile","/a/b/c/d"]]

Output: [[],null,null,["a"],"hello"]

Constraints

- 1 <= operations.length <= 300 - 1 <= path.length <= 500 - 1 <= content.length <= 50 - Paths are valid and absolute.

In-Memory File System: approach, complexity and pitfalls

A hard design problem, graded against 4 test cases (1 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

More Designproblems →

If you are stuck

Show the 3-step hint ladder

Model the tree as a node with `children: Map<name, Node>` and `content: string` (for files).
Distinguish files vs directories by whether `content` was ever written - or use an `isFile` flag.
ls on a file returns just its name; ls on a dir returns sorted child names.

The optimal approach

Show the approach: Tree of Nodes

Each node has:

- `children`: `Map<name, Node>` (sub-directories and files)

- `content`: `string` (only used when this node is a file)

- `isFile`: boolean

Walk the path components from root, creating intermediate dirs in mkdir / addContentToFile if missing.

ls(path): traverse to the node. If it's a file, return `[lastComponent]`. If it's a dir, return its child names sorted.

Edge cases:

- `ls("/")` on an empty fs returns `[]`.

- `addContentToFile` to an existing file appends - don't overwrite.

- The last component on `addContentToFile` is the file name, not a dir.

Time: `mkdir` and `addContentToFile` are O(L) where L is the number of path components; `ls` is O(L + k log k) where k is the children count of the target node.
Space: O(total path components + total content)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.