In-Memory File System
Composite pattern for hierarchical file/directory structure with path resolution. Files and directories share a common interface, so recursive operations like size calculation and deletion work uniformly across the tree.
Key Abstractions
Facade with root directory and path resolution. All operations go through here.
Abstract base for File and Directory. Enables uniform treatment across the tree.
Leaf node holding a name and string content
Composite node with a children map for O(1) child lookup by name
Class Diagram
The Key Insight
A file system is a tree. That sounds obvious, but the design implications run deep. You have two fundamentally different types of nodes: files that hold data and directories that hold other nodes. The naive approach treats them as completely separate types and checks which one you have before every operation. This works until you need to compute the total size of a directory, recursively delete a subtree, or search for files matching a pattern. Suddenly every operation needs its own tree-walking code with type checks at every level.
Composite pattern eliminates this entirely. File and Directory both extend a common FileSystemEntry. When you call size() on a directory, it sums up the sizes of its children. Some children are files that return their content length. Others are directories that recurse further. The caller never needs to know the difference. One method call, uniform behavior, regardless of tree depth.
The other critical decision is how directories store their children. A list forces you to scan every entry when looking up a name. That is O(n) per lookup and it compounds fast in deep paths. A HashMap gives O(1) lookups by name, which means path resolution is O(depth) rather than O(depth * breadth).
Requirements
Functional
- Create directories (mkdir) and files (touch) at any valid path
- Write content to files and read it back (write, cat)
- List directory contents (ls) sorted alphabetically
- Remove files and directories (rm), with directory removal being recursive
- Compute size of any entry: files return content length, directories return recursive total
- Search for entries by name across the tree (find)
Non-Functional
- O(1) child lookup within a directory using HashMap
- Path resolution fails fast with clear error messages for missing segments
- Adding new entry types (symlinks, mount points) should not require modifying existing operations
Design Decisions
Why Composite pattern instead of a type flag?
A type flag means every operation has if entry.type == FILE ... else if entry.type == DIRECTORY ... branching. That works for two types but breaks open/closed principle hard. Want to add symbolic links? Touch every method. Composite uses polymorphism. Each subclass implements its own behavior. Directory's size() recurses. File's size() returns content length. Client code calls entry.size() and the runtime dispatches correctly.
Why HashMap for children instead of a List?
Looking up a child by name in a list means scanning every entry. A directory with 10 files? No problem. A directory with 10,000 log files? Every ls, cat, and mkdir operation inside that directory takes linear time. HashMap gives O(1) lookups by name. The sorted output for ls is a one-time sort on the keys, and that only happens when someone actually asks for a listing.
Why split path resolution into resolve() and resolveParent()?
Most operations need either the entry itself (cat, ls, size) or the parent directory plus the child name (mkdir, touch, rm). Having both methods avoids duplicating the tree-walking logic. resolveParent() is the workhorse for mutations because you need the parent to add or remove a child. resolve() handles reads. Clean separation.
Why a facade instead of exposing Entry directly?
Without a facade, callers need to understand path parsing, tree traversal, and entry types. They would manually split paths, walk directories, cast entries to the right type. The FileSystem facade absorbs all that complexity. Callers pass a path string and get a result. Path validation, traversal, and error handling happen in one place.
Interview Follow-ups
- "How would you add symbolic links?" Create a SymLink class extending FileSystemEntry that stores a target path string. On any operation, resolve the symlink by following the target path. Keep a visited set during resolution to detect circular references.
- "How would you support file permissions?" Add a Permissions object to FileSystemEntry with read, write, and execute flags plus an owner identifier. Check permissions at the FileSystem facade layer before every operation.
- "What about undo support for delete?" Command pattern. Wrap each rm operation in a command object that captures the deleted subtree. Push commands onto a stack. Undo pops and re-attaches the subtree to its former parent.
- "How would you handle concurrent access safely?" Add a ReadWriteLock at the FileSystem level. Read operations (cat, ls, size, find) take a read lock. Write operations (mkdir, touch, write, rm) take a write lock. This allows concurrent reads while serializing writes.
Code Implementation
1 from abc import ABC, abstractmethod
2 from datetime import datetime
3 from typing import Optional
4
5
6 class FileSystemEntry(ABC):
7 """Abstract base for files and directories. Composite pattern root.
8 Both leaf (File) and composite (Directory) extend this."""
9
10 def __init__(self, name: str):
11 self._name = name
12 self._created_at = datetime.now()
13
14 @property
15 def name(self) -> str:
16 return self._name
17
18 @abstractmethod
19 def is_directory(self) -> bool: ...
20
21 @abstractmethod
22 def size(self) -> int:
23 """Files return content length. Directories return recursive total."""
24 ...
25
26
27 class File(FileSystemEntry):
28 """Leaf node. Holds a name and string content."""
29
30 def __init__(self, name: str, content: str = ""):
31 super().__init__(name)
32 self._content = content
33
34 def is_directory(self) -> bool:
35 return False
36
37 @property
38 def content(self) -> str:
39 return self._content
40
41 @content.setter
42 def content(self, value: str) -> None:
43 self._content = value
44
45 def size(self) -> int:
46 return len(self._content)
47
48
49 class Directory(FileSystemEntry):
50 """Composite node. Children stored in a dict for O(1) lookup by name."""
51
52 def __init__(self, name: str):
53 super().__init__(name)
54 self._children: dict[str, FileSystemEntry] = {}
55
56 def is_directory(self) -> bool:
57 return True
58
59 def add_child(self, entry: FileSystemEntry) -> None:
60 if entry.name in self._children:
61 raise FileExistsError(f"'{entry.name}' already exists in '{self._name}'")
62 self._children[entry.name] = entry
63
64 def remove_child(self, name: str) -> FileSystemEntry:
65 if name not in self._children:
66 raise FileNotFoundError(f"'{name}' not found in '{self._name}'")
67 return self._children.pop(name)
68
69 def get_child(self, name: str) -> Optional[FileSystemEntry]:
70 return self._children.get(name)
71
72 def list_children(self) -> list[str]:
73 return sorted(self._children.keys())
74
75 def get_all_children(self) -> dict[str, "FileSystemEntry"]:
76 return dict(self._children)
77
78 def size(self) -> int:
79 """Recursive size. Composite pattern makes this clean."""
80 return sum(child.size() for child in self._children.values())
81
82
83 class FileSystem:
84 """Facade for all file system operations. Parses paths,
85 walks the tree, delegates to the right entry."""
86
87 def __init__(self):
88 self._root = Directory("/")
89
90 def _split_path(self, path: str) -> list[str]:
91 return [p for p in path.strip("/").split("/") if p]
92
93 def _resolve(self, path: str) -> FileSystemEntry:
94 """Walks the full path and returns the entry at the end."""
95 if path == "/":
96 return self._root
97 parts = self._split_path(path)
98 current: FileSystemEntry = self._root
99 for part in parts:
100 if not current.is_directory():
101 raise FileNotFoundError(f"'{current.name}' is not a directory")
102 child = current.get_child(part)
103 if child is None:
104 raise FileNotFoundError(f"'{part}' not found")
105 current = child
106 return current
107
108 def _resolve_parent(self, path: str) -> tuple[Directory, str]:
109 """Returns the parent directory and the final name component."""
110 parts = self._split_path(path)
111 if not parts:
112 raise ValueError("Cannot operate on root directly")
113 current = self._root
114 for part in parts[:-1]:
115 child = current.get_child(part)
116 if child is None or not child.is_directory():
117 raise FileNotFoundError(f"Directory '{part}' not found in path '{path}'")
118 current = child
119 return current, parts[-1]
120
121 def mkdir(self, path: str) -> None:
122 parent, name = self._resolve_parent(path)
123 parent.add_child(Directory(name))
124
125 def touch(self, path: str) -> None:
126 parent, name = self._resolve_parent(path)
127 if parent.get_child(name) is None:
128 parent.add_child(File(name))
129
130 def write(self, path: str, content: str) -> None:
131 entry = self._resolve(path)
132 if entry.is_directory():
133 raise IsADirectoryError(f"'{path}' is a directory")
134 entry.content = content
135
136 def cat(self, path: str) -> str:
137 entry = self._resolve(path)
138 if entry.is_directory():
139 raise IsADirectoryError(f"'{path}' is a directory")
140 return entry.content
141
142 def ls(self, path: str = "/") -> list[str]:
143 entry = self._resolve(path)
144 if entry.is_directory():
145 return entry.list_children()
146 return [entry.name]
147
148 def rm(self, path: str) -> None:
149 parent, name = self._resolve_parent(path)
150 parent.remove_child(name)
151
152 def size(self, path: str = "/") -> int:
153 return self._resolve(path).size()
154
155 def find(self, path: str, name: str) -> list[str]:
156 """Recursive search for entries matching a name. Iterator pattern
157 over the tree structure."""
158 results: list[str] = []
159 entry = self._resolve(path)
160 self._find_recursive(entry, path.rstrip("/"), name, results)
161 return results
162
163 def _find_recursive(self, entry: FileSystemEntry, current_path: str,
164 target: str, results: list[str]) -> None:
165 if entry.name == target:
166 results.append(current_path)
167 if entry.is_directory():
168 for child_name, child in entry.get_all_children().items():
169 child_path = f"{current_path}/{child_name}"
170 self._find_recursive(child, child_path, target, results)
171
172
173 if __name__ == "__main__":
174 fs = FileSystem()
175
176 # Build directory structure
177 fs.mkdir("/home")
178 fs.mkdir("/home/alice")
179 fs.mkdir("/home/alice/docs")
180 fs.mkdir("/home/alice/projects")
181 fs.mkdir("/home/bob")
182
183 # Create and write files
184 fs.touch("/home/alice/docs/notes.txt")
185 fs.write("/home/alice/docs/notes.txt", "Meeting at 3pm. Bring laptop.")
186 fs.touch("/home/alice/docs/todo.txt")
187 fs.write("/home/alice/docs/todo.txt", "Buy groceries\nFinish report")
188 fs.touch("/home/alice/projects/readme.txt")
189 fs.write("/home/alice/projects/readme.txt", "Project Alpha")
190 fs.touch("/home/bob/readme.txt")
191 fs.write("/home/bob/readme.txt", "Hello from Bob")
192
193 # List directories
194 print("ls /:", fs.ls("/"))
195 print("ls /home:", fs.ls("/home"))
196 print("ls /home/alice:", fs.ls("/home/alice"))
197 print("ls /home/alice/docs:", fs.ls("/home/alice/docs"))
198
199 # Read files
200 print("\ncat /home/alice/docs/notes.txt:")
201 print(f" {fs.cat('/home/alice/docs/notes.txt')}")
202 print("cat /home/bob/readme.txt:")
203 print(f" {fs.cat('/home/bob/readme.txt')}")
204
205 # Check sizes
206 print(f"\nSize of /home/alice/docs: {fs.size('/home/alice/docs')} chars")
207 print(f"Size of entire fs: {fs.size('/')} chars")
208
209 # Find files by name
210 print(f"\nfind / readme.txt: {fs.find('/', 'readme.txt')}")
211
212 # Remove a file and verify
213 fs.rm("/home/bob/readme.txt")
214 print(f"\nAfter rm /home/bob/readme.txt, ls /home/bob: {fs.ls('/home/bob')}")
215
216 # Remove a directory with children
217 fs.rm("/home/alice/docs")
218 print(f"After rm /home/alice/docs, ls /home/alice: {fs.ls('/home/alice')}")
219
220 # Verify error handling
221 try:
222 fs.cat("/nonexistent")
223 except FileNotFoundError as e:
224 print(f"\nExpected error: {e}")
225
226 try:
227 fs.write("/home", "data")
228 except IsADirectoryError as e:
229 print(f"Expected error: {e}")
230
231 assert fs.ls("/home/bob") == []
232 assert fs.ls("/home/alice") == ["projects"]
233 assert fs.size("/") > 0
234 print("\nAll assertions passed.")Common Mistakes
- ✗Using isinstance/instanceof checks everywhere instead of polymorphism. Adding a new entry type means touching every operation.
- ✗Storing children in a list. Linear scan for every lookup is fine for 10 files, painful for 10,000.
- ✗Forgetting that rm on a directory should be recursive. Leaving orphaned children is a silent resource leak.
- ✗Not validating paths. Operations on '/foo/bar' should fail cleanly when '/foo' does not exist.
Key Points
- ✓Composite pattern lets files and directories share a common interface. Recursive operations like size() work without type-checking.
- ✓Children stored as HashMap, not a list. Name-based lookups are O(1) instead of scanning every entry.
- ✓Path resolution walks the tree from root by splitting on '/'. Missing segments fail fast with clear errors.
- ✓FileSystemEntry is abstract with polymorphic behavior. No instanceof calls in client code.