The real-world analogy: Russian nesting boxes and drawer folders
Imagine organizing a physical filing cabinet:
- The Nesting Boxes (Composite Pattern): You have wooden storage containers. A container can hold single paper documents (Files), or it can hold smaller wooden storage containers (Directories), which in turn hold more documents and folders.
- Both files and directories sit in the same drawer layout and can be moved, labeled, and sized.
- When calculating the total weight of a container, you sum the weights of its contents. If a content item is a folder, you recursively open that folder and sum its items. The folder and the document share the same base trait—they are physical nodes on the shelf.
If you don't use this Composite structure in code, you end up writing separate, duplicate traversal systems for folders and files, resulting in messy if (is_file) { ... } else { ... } branching nested inside every search, print, and calculation logic.
The ask
Build an in-memory file system supporting mkdir, ls, addContentToFile, and readContentFromFile, with arbitrarily nested directories. Paths are absolute (/a/b/file.txt). (This is LeetCode 588 in disguise.)
The insight — files and directories are the same shape
The naive design has two unrelated classes and if (isDirectory) checks smeared through every operation. The Composite pattern unifies them: a Node is either a file (leaf: has content) or a directory (composite: has named children). Both live in one tree, so traversal is uniform and you stop special-casing at every step.
UML Class Diagram
Think it through like the interview
Think it through: In-Memory File SystemLLD / Hard — LeetCode 5880/3 stages
PROBLEMSupport mkdir, ls, addContentToFile, readContentFromFile with nested directories and absolute paths.
- 1
Spec → the tree
“What's the data structure under all four operations?”
- 2
Composite: one Node type
“Two classes (File, Directory) or one Node with both roles?”
unlocks after the stage above - 3
Path traversal is the core helper
“How do I avoid rewriting path-walking in every method?”
unlocks after the stage above
Implementation
Below are complete implementations utilizing the Composite pattern and fine-grained, thread-safe node locks.
Python
Python
import threading
from typing import Dict, List
class Node:
def __init__(self, name: str, is_file: bool = False):
self.name = name
self.is_file = is_file
self.content = ""
self.children: Dict[str, Node] = {}
self.lock = threading.Lock() # Per-node lock for thread-safety
class FileSystem:
def __init__(self):
self.root = Node("/")
def _split_path(self, path: str) -> List[str]:
return [p for p in path.split("/") if p]
def _traverse(self, path: str, create: bool = False) -> Node:
parts = self._split_path(path)
curr = self.root
for part in parts:
with curr.lock:
if part not in curr.children:
if not create:
raise ValueError(f"Path not found: {path}")
curr.children[part] = Node(part)
curr = curr.children[part]
return curr
def mkdir(self, path: str) -> None:
self._traverse(path, create=True)
def add_content_to_file(self, path: str, content: str) -> None:
node = self._traverse(path, create=True)
with node.lock:
node.is_file = True
node.content += content
def read_content_from_file(self, path: str) -> str:
node = self._traverse(path, create=False)
with node.lock:
if not node.is_file:
raise ValueError("Path is a directory, not a file")
return node.content
def ls(self, path: str) -> List[str]:
node = self._traverse(path, create=False)
with node.lock:
if node.is_file:
return [node.name]
return sorted(node.children.keys())
Java
Java
import java.util.*;
import java.util.concurrent.locks.ReentrantLock;
class Node {
String name;
boolean isFile;
String content = "";
final Map<String, Node> children = new HashMap<>();
final ReentrantLock lock = new ReentrantLock();
Node(String name) { this.name = name; }
Node(String name, boolean isFile) {
this.name = name;
this.isFile = isFile;
}
}
public class FileSystem {
private final Node root = new Node("/");
private List<String> splitPath(String path) {
List<String> list = new ArrayList<>();
for (String s : path.split("/")) {
if (!s.isEmpty()) list.add(s);
}
return list;
}
private Node traverse(String path, boolean create) {
List<String> parts = splitPath(path);
Node curr = root;
for (String part : parts) {
curr.lock.lock();
try {
if (!curr.children.containsKey(part)) {
if (!create) throw new IllegalArgumentException("Path not found: " + path);
curr.children.put(part, new Node(part));
}
curr = curr.children.get(part);
} finally {
curr.lock.unlock();
}
}
return curr;
}
public void mkdir(String path) {
traverse(path, true);
}
public void addContentToFile(String path, String content) {
Node node = traverse(path, true);
node.lock.lock();
try {
node.isFile = true;
node.content += content;
} finally {
node.lock.unlock();
}
}
public String readContentFromFile(String path) {
Node node = traverse(path, false);
node.lock.lock();
try {
if (!node.isFile) throw new IllegalArgumentException("Path is a directory, not a file");
return node.content;
} finally {
node.lock.unlock();
}
}
public List<String> ls(String path) {
Node node = traverse(path, false);
node.lock.lock();
try {
if (node.isFile) return Collections.singletonList(node.name);
List<String> sortedNames = new ArrayList<>(node.children.keySet());
Collections.sort(sortedNames);
return sortedNames;
} finally {
node.lock.unlock();
}
}
}
C++
C++
#include <string>
#include <vector>
#include <unordered_map>
#include <mutex>
#include <algorithm>
#include <sstream>
#include <stdexcept>
#include <memory>
class Node {
public:
std::string name;
bool isFile = false;
std::string content = "";
std::unordered_map<std::string, std::shared_ptr<Node>> children;
std::mutex mtx;
Node(std::string n) : name(n) {}
};
class FileSystem {
private:
std::shared_ptr<Node> root;
std::vector<std::string> splitPath(const std::string& path) {
std::vector<std::string> parts;
std::stringstream ss(path);
std::string item;
while (std::getline(ss, item, '/')) {
if (!item.empty()) parts.push_back(item);
}
return parts;
}
std::shared_ptr<Node> traverse(const std::string& path, bool create) {
std::vector<std::string> parts = splitPath(path);
std::shared_ptr<Node> curr = root;
for (const auto& part : parts) {
std::lock_guard<std::mutex> lock(curr->mtx);
if (curr->children.find(part) == curr->children.end()) {
if (!create) throw std::invalid_argument("Path not found: " + path);
curr->children[part] = std::make_shared<Node>(part);
}
curr = curr->children[part];
}
return curr;
}
public:
FileSystem() { root = std::make_shared<Node>("/"); }
void mkdir(const std::string& path) {
traverse(path, true);
}
void addContentToFile(const std::string& path, const std::string& content) {
auto node = traverse(path, true);
std::lock_guard<std::mutex> lock(node->mtx);
node->isFile = true;
node->content += content;
}
std::string readContentFromFile(const std::string& path) {
auto node = traverse(path, false);
std::lock_guard<std::mutex> lock(node->mtx);
if (!node->isFile) throw std::runtime_error("Path is a directory, not a file");
return node->content;
}
std::vector<std::string> ls(const std::string& path) {
auto node = traverse(path, false);
std::lock_guard<std::mutex> lock(node->mtx);
if (node->isFile) return {node->name};
std::vector<std::string> sortedNames;
for (const auto& entry : node->children) {
sortedNames.push_back(entry.first);
}
std::sort(sortedNames.begin(), sortedNames.end());
return sortedNames;
}
};
Interactive Quiz
Check yourself0/3 answered
1.
2.
3.
Complexity & follow-ups
- Complexity: each op is O(path length) traversal;
lson a directory is O(children log children) for the sort. - Search / glob: DFS the subtree matching a pattern (
*.txt) — naturally recursive on the Composite tree. - Permissions: add owner + rwx bits per node; check on traverse.
- Symlinks: a node that points to another path — watch for cycles when traversing.
- Thread-safety: concurrent
mkdir/write on the same parent races on the children map — guard with a lock per directory, or a read-write lock (many readers, one writer). - Real FS: swap content strings for block pointers + an LRU page cache; this is where in-memory meets storage.
Design drills
Design drills: In-Memory File System0/3 done
Whiteboard each one out loud for 5–10 minutes before you reveal what a strong answer covers — the gap between your sketch and the checklist is your study list. Progress is saved on this device.
Core
Add search: find all files matching a glob like /a/**/*.log.
Stretch
Make concurrent mkdir and writes on the same directory safe.
Core
Add Unix-style permissions and ownership.