AlgoMaster Logo

Design In-Memory File System

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We need to build a file system that supports four operations: listing directory contents, creating directories, writing to files, and reading files. The file system is hierarchical, like a real one. Paths like /a/b/c indicate a nested structure where c is inside b, which is inside a, which is inside the root /.

One detail matters for the design: ls behaves differently depending on whether the path points to a file or a directory. If it points to a file, we return only the file name (not the full path). If it points to a directory, we return all its children sorted lexicographically.

The main design decision is which data structure represents this hierarchy. Paths are sequences of names separated by /, and we traverse them one component at a time, so a tree where each node represents a directory or file fits the structure directly.

Key Constraints:

  • 1 <= path.length <= 200: paths are short, so the cost of splitting a path is negligible per call.
  • At most 300 calls: the total number of nodes stays small, so memory is not a concern and we can sort children on every ls.
  • Paths contain only letters, digits, /, ., and spaces: there are no special characters to escape and no . or .. relative-path components to resolve.

Approach 1: Hash Map of Full Paths

Intuition

Store everything in two hash maps. One maps a directory path to a set of its children names, and another maps a file path to its content string.

When we mkdir("/a/b/c"), we add "a" to the children of "/", add "b" to the children of "/a", and add "c" to the children of "/a/b". When we ls("/a"), we look up "/a" in the directory map and return its children sorted.

The downside is that the keys are full path strings, so every operation rebuilds intermediate path prefixes (/, /a, /a/b) by string concatenation, and deep paths store the same prefixes repeatedly across keys.

Algorithm

  1. Initialize two hash maps: dirContents (maps directory path to a sorted set of child names) and fileContents (maps file path to its content string).
  2. For ls(path): Check if path is a file (exists in fileContents). If yes, return only the file name. Otherwise, return the sorted set of children from dirContents.
  3. For mkdir(path): Split the path by /. For each prefix, add the next component as a child of that prefix in dirContents.
  4. For addContentToFile(filePath, content): Create parent directories. Add the file name to the parent's children. Append content to fileContents[filePath].
  5. For readContentFromFile(filePath): Return fileContents[filePath].

Example Walkthrough

dirContents
1FileSystem(): initialize root directory
/
:
[]
fileContents
1No files yet
1/7

Code

This approach stores redundant full path strings as map keys. The next approach removes that redundancy by representing the file system as a tree, where moving from a parent to a child is following a pointer instead of building a new key.

Approach 2: Trie (File System Tree)

Intuition

A file system is a tree. The root directory / is the root node, and each subdirectory or file is a child node. Instead of flattening paths into hash map keys, we represent the file system as a tree where each node stores a map of its children (keyed by name) and an optional file content.

This is a Trie, except each level represents a path component rather than a single character. Given a path like /a/b/c, we start at the root, follow the edge labeled "a" to reach node a, then follow "b" to reach node b, then follow "c" to reach node c.

Navigating to any path is a walk down the tree, and mkdir creates the intermediate nodes it passes through. There is no string concatenation and no duplicate prefix storage, because each node holds only its own children.

To distinguish files from directories, each node has an optional content field. A node with non-null content is a file; otherwise it is a directory.

Algorithm

  1. Define a TrieNode class with a children map (name to child node) and a content string (null for directories).
  2. Create a root node representing /.
  3. For any path, split by / and traverse from root, following child pointers for each component.
  4. ls(path): Navigate to the node. If it's a file, return its name. Otherwise, return sorted keys of its children map.
  5. mkdir(path): Navigate the path, creating child nodes as needed.
  6. addContentToFile(filePath, content): Navigate to the node (creating nodes along the way), then append content.
  7. readContentFromFile(filePath): Navigate to the node and return its content.

Example Walkthrough

1FileSystem(): create root node with empty children
/ (root)
:
children={}
1/7

Code