Design an In-Memory File System
Directories, files, paths, and a Composite tree with ls/mkdir/read/write operations.
Problem Statement
Design an in-memory file system that supports directories and files organized as a tree. Clients should be able to create directories, create files, read and write file contents, list paths, delete nodes, and ask for the aggregate size of any subtree.
The heart of the interview is the Composite pattern: files and directories share a common FileSystemNode base, so traversal, deletion, listing, and size aggregation can treat a subtree uniformly.
Business context
This problem appears in storage, developer tooling, and cloud-drive interviews because it exposes how well a candidate models hierarchy. A strong solution keeps path parsing at the facade boundary, keeps node behavior inside the node classes, and uses recursive traversal instead of scattering directory-specific checks through every operation. The in-memory constraint removes persistence and permissions so the conversation can focus on object design, invariants, and extensibility.
Functional Requirements
Create nested directories with mkdir using absolute paths such as /docs/projects.
Create a file at an existing directory path with initial content.
Read and replace file content through readFile and writeFile.
List a directory's immediate children in deterministic order; listing a file returns that file name.
Delete a file or an entire directory subtree by path, while rejecting deletion of the root.
Resolve absolute paths recursively from the root and fail clearly when a component is missing or a file is used as a directory.
Return the aggregate size of any path, where a file size is its content length and a directory size is the sum of descendant file sizes.
Non-Functional Requirements
Correct tree invariants
A directory owns unique child names, every child has exactly one parent, and the root has no parent. Operations must preserve those invariants.
Low latency for interview scale
Path operations should be proportional to path depth plus work on the touched subtree, which is acceptable for an in-memory design.
Encapsulation
File content changes live on FileNode and child management lives on DirectoryNode; the facade coordinates but does not mutate raw maps directly.
Extensibility
Adding metadata, search, permissions, or alternate storage should be possible without rewriting the path traversal algorithm.
Deterministic output
List results are sorted so demos, tests, and interview dry runs are repeatable regardless of insertion order.
Requirement Clarification
QAre paths absolute or relative?
Assume absolute Unix-style paths beginning with /. Relative path support can be layered later by keeping a current working directory in a session object.
QShould **writeFile** create a missing file?
In the base design, createFile creates and writeFile updates an existing file. This keeps error handling explicit and mirrors many real file APIs.
QDoes deleting a directory require it to be empty?
For the base design, deleting a directory removes its whole subtree. A safer empty-directory-only delete is an easy policy change in the facade.
QDo we need persistence, permissions, symbolic links, or quotas?
No for the core model. The design is in-memory and single-process; production concerns document where repositories, ACLs, and quotas plug in.
QHow is file size measured?
Use content length in characters for the interview implementation. A production system would choose bytes and store size as metadata.
UML Class Diagram
Sequence Diagram
Entity Identification
FileSystem
Facade over the tree. Validates absolute paths, resolves components recursively, exposes the API, and centralizes node creation through factory methods.
FileSystemNode
Abstract Component in the Composite. Stores name and parent, computes full path, and defines the common operations size, isDirectory, and accept.
DirectoryNode
Composite node. Owns uniquely named child nodes, supports iteration over children, delegates aggregate size to descendants, and performs pre-order visitor traversal.
FileNode
Leaf node. Stores mutable file content, implements read/write, and reports size as content length.
NodeVisitor
Behavior extension seam. Lets clients add traversal behavior such as printing, indexing, auditing, or statistics without adding methods to every node class.
Path components
The normalized tokens produced from an absolute path. They drive the recursive descent from root to target and keep parsing outside the domain nodes.
Design Patterns Used
FileSystemNode is the common component, FileNode is the leaf, and DirectoryNode is the composite that owns child nodes. This makes size and visitor traversal recursive and uniform.
FileSystem.createDirectoryNode and createFileNode centralize node construction. Subclasses can override them to attach metadata, quotas, or instrumented nodes without changing path operations.
DirectoryNode implements Iterable<FileSystemNode>, so callers can traverse children without seeing the internal map. It preserves encapsulation while supporting listing and visitors.
NodeVisitor separates traversal actions from the node classes. A printer, indexer, or metrics collector can visit files and directories without bloating the core model.
Step-by-Step Design
1Start with a shared node abstraction
Both files and directories need a name, parent link, path calculation, size, and visitor hook. Put that common contract in FileSystemNode so every public operation can resolve to one type.
public abstract class FileSystemNode { public abstract boolean isDirectory(); public abstract int size(); public abstract void accept(NodeVisitor visitor); }2Make directory the Composite
DirectoryNode stores children as FileSystemNode, not as separate file and directory collections. Aggregate size becomes a simple recursive sum.
public int size() { int total = 0; for (FileSystemNode child : children.values()) { total += child.size(); } return total; }3Keep path parsing in the facade
FileSystem is responsible for absolute paths. It splits a path into components and recursively descends from the root, creating directories only for mkdir.
private FileSystemNode resolveFrom(DirectoryNode current, List<String> parts, int index, boolean createMissing) { String name = parts.get(index); FileSystemNode child = current.child(name).orElse(null); if (child == null && createMissing) { child = createDirectoryNode(name); current.add(child); } return index == parts.size() - 1 ? child : resolveFrom((DirectoryNode) child, parts, index + 1, createMissing); }4Separate create and write semantics
createFile fails when the name already exists and writeFile fails when the path is not an existing file. This avoids ambiguous upsert behavior during an interview.
5Expose iteration without exposing storage
DirectoryNode.iterator returns an unmodifiable iterator over children. The facade can list names and visitors can traverse, but no caller can mutate the backing map.
6Add visitor traversal as an extension seam
accept performs pre-order traversal: visit the directory, then recursively visit descendants. That gives future features like search indexing and audit logging a clean hook.
public void accept(NodeVisitor visitor) { visitor.visit(this); for (FileSystemNode child : children.values()) { child.accept(visitor); } }
Complete Java Implementation
Explanation of Every Class
FileSystemNode
The abstract Component. It owns the common identity fields, parent wiring, full-path calculation, and the shared contract that both files and directories implement.
FileNode
The leaf in the Composite. It stores content, exposes read/write, returns content length as size, and accepts a visitor by dispatching to visit(FileNode).
DirectoryNode
The Composite node. It owns a name-to-child map, rejects duplicate child names, exposes an iterator instead of the map, recursively sums sizes, and performs pre-order visitor traversal.
NodeVisitor
The Visitor interface. It provides separate hooks for FileNode and DirectoryNode, allowing clients to add traversal behavior without modifying node classes.
FileSystem
The facade and path resolver. Public methods parse absolute paths, recursively resolve nodes from root, enforce create/write/delete semantics, and use factory methods for node creation.
Main
A compact demonstration that creates directories and files, lists a directory, reads and writes a file, computes subtree size, traverses with a visitor, and deletes a file.
Dry Run
Sample input
Actions: mkdir(/docs/projects), createFile(/docs/readme.txt, hello), createFile(/docs/projects/plan.txt, draft), writeFile(/docs/readme.txt, hello world), size(/docs), delete(/docs/projects/plan.txt).
| Step | Operation | Resolved target | Tree effect | Result |
|---|---|---|---|---|
| 1 | mkdir /docs/projects | root then docs | Create docs and projects directories | No output |
| 2 | createFile /docs/readme.txt | parent /docs | Add readme.txt with length 5 | File created |
| 3 | createFile /docs/projects/plan.txt | parent /docs/projects | Add plan.txt with length 5 | File created |
| 4 | writeFile /docs/readme.txt | file readme.txt | Replace content with length 11 | File updated |
| 5 | size /docs | directory docs | Sum readme 11 + plan 5 recursively | 16 |
| 6 | delete /docs/projects/plan.txt | parent /docs/projects | Remove plan.txt from children | true |
| 7 | size /docs | directory docs | Sum remaining readme 11 | 11 |
The important moment is Step 5: FileSystem only resolves /docs. The recursive DirectoryNode.size method performs the aggregate calculation by treating every child as a FileSystemNode.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| mkdir | O(D) | O(D) | D is the number of path components. Missing directory nodes may be allocated along the path. |
| createFile | O(D) | O(1) | Resolve the parent directory recursively, then insert one child into a map. |
| readFile / writeFile | O(D) | O(1) | Resolve the file path. Replacing content stores the new string reference in this simplified model. |
| ls | O(D + C log C) | O(C) | Resolve the path, copy C child names, and sort them for deterministic output. |
| delete | O(D) | O(1) | Resolve the parent and remove the target child; garbage collection reclaims the detached subtree. |
| size | O(D + N) | O(H) | Resolve the starting node, then recursively visit N nodes in that subtree. H is recursion height. |
The design optimizes for clarity. If size becomes a hot path, cache subtree sizes on directories and update ancestors on file writes, creates, and deletes; that trades simpler reads for stricter mutation bookkeeping.
Extensibility
Metadata and permissions
Add owner, timestamps, permissions, or ACLs to FileSystemNode. Keep authorization checks in FileSystem before mutation so nodes remain focused on tree behavior.
Cached directory sizes
Store cachedSize on DirectoryNode and update ancestors during create, write, and delete. This changes size from subtree traversal to O(D).
Search and indexing
Implement a NodeVisitor that indexes file names, content, or metadata. Traversal stays unchanged and the node classes do not gain search-specific methods.
Persistence
Override factory methods to create repository-backed node types or add a Repository layer behind FileSystem for snapshots and recovery.
Relative paths
Introduce a session object with a current directory and normalize relative paths before calling the existing absolute-path facade.
Alternative Designs
Flat path map
Store every absolute path in a Map<String, Node> and make each operation a direct key lookup.
Tradeoffs
Simple and fast for point lookups, but rename, delete subtree, and aggregate size become path-prefix operations. It also hides the Composite relationship interviewers expect.
Trie without node polymorphism
Use one trie node class with a boolean flag for file versus directory and optional content.
Tradeoffs
Fewer classes, but behavior fills with conditionals. The design is less extensible than separate FileNode and DirectoryNode subclasses.
Size-cached Composite
Keep the same tree, but each directory stores aggregate size and mutations update the ancestor chain.
Tradeoffs
Makes size cheap but complicates every write, create, and delete. A missed update causes silent inconsistency.
Common Mistakes
- ×
Representing paths as raw strings everywhere and never building a real tree.
- ×
Putting content fields on directories or child maps on files, which blurs leaf and composite responsibilities.
- ×
Letting external callers mutate the directory child map directly.
- ×
Making writeFile silently create parent directories and files without clarifying upsert semantics.
- ×
Calculating directory size in FileSystem with type checks instead of letting nodes implement size polymorphically.
- ×
Forgetting to reject deletion of the root, leaving the facade with no stable aggregate root.
- ×
Skipping deterministic sort in ls, causing flaky demos and tests.
Follow-up Interview Questions
QHow would you support **move** and **rename**?
Resolve the source parent and destination parent, remove the source child, validate the new name is free, then add it to the destination. Guard against moving a directory into its own descendant.
QHow do you make **size** O(1) for directories?
Cache aggregate size on each directory. On file content changes, create, and delete, propagate the size delta up the parent chain to root.
QHow would you add **find by name**?
Add a NodeVisitor that records nodes whose names match a predicate. The traversal can start at any resolved directory and does not require changing node classes.
QWhat changes for concurrent access?
Use a read-write lock around the facade or finer-grained locks per directory. Mutations must make path resolution plus child update atomic for the touched parent.
QHow would symbolic links affect this design?
Add a new SymlinkNode leaf with a target path and detect cycles during resolution. This is a deliberate extension because symlinks complicate traversal and deletion semantics.
Production Considerations
Durability
An in-memory tree disappears on restart. Persist snapshots or append a write-ahead log of operations so the tree can be rebuilt safely.
Concurrency
Multiple clients require locking. Start with a facade-level read-write lock, then move to directory-level locks if contention appears.
Memory limits
Large file contents should not live as Java strings inside nodes. Store blocks externally and keep metadata plus block references in FileNode.
Path normalization
Production code must handle repeated slashes, ., .., Unicode normalization, reserved names, and maximum path length consistently.
Observability
Track operation counts, latency by operation, tree size, file count, and failed path resolutions to diagnose misuse and growth patterns.
What Interviewers Look For
Did the candidate identify Composite early and use it to remove type-check-heavy traversal?
Are path parsing and recursive resolution isolated inside the facade?
Do files and directories have crisp, separate responsibilities?
Are edge cases clear: root path, missing component, duplicate name, file used as directory, delete root?
Can the design evolve toward permissions, search, cached sizes, and persistence without rewriting the core tree?
Quiz
0/5 answered
1.Why is **FileSystemNode** the base type for both files and directories?
2.Where should recursive path traversal live in this design?
3.What does the Iterator pattern protect here?
4.Why is **writeFile** separate from **createFile**?
5.Which extension is a natural use of **NodeVisitor**?
Practice Variants
Add rename and move
IntermediateImplement rename(path, newName) and move(source, destinationDirectory) while preventing duplicate names and cycles.
Cache subtree sizes
AdvancedMake directory size queries O(1) by maintaining aggregate size deltas through parent links on every mutation.
Implement find
BeginnerUse NodeVisitor to find files by name suffix, minimum size, or content predicate under a chosen directory.
Flashcards
Cheat Sheet
Core model: FileSystem facade owns the root. FileSystemNode is the abstract component. FileNode is the leaf. DirectoryNode is the composite.
Path flow: validate absolute path → split into components → recursively resolve from root → apply operation to the resolved node or parent.
Operations: mkdir creates missing directories; createFile inserts a leaf under an existing directory; writeFile updates an existing leaf; ls returns sorted child names; delete detaches a subtree; size recursively aggregates file content length.
Patterns: Composite for the tree, Factory Method for node creation, Iterator for directory children, Visitor for traversal extensions.
Invariants: root is stable, directory child names are unique, parent links are maintained, files have no children, external callers never mutate the child map directly.
Complexity: path operations are O(D); ls adds O(C log C); size adds O(N) for subtree traversal unless cached.
References
- BookDesign Patterns: Elements of Reusable Object-Oriented Software — Gamma, Helm, Johnson, Vlissides
- BookEffective Java — Item 18 and Item 52 — Joshua Bloch
- DocsRefactoring Guru — Composite Pattern
- DocsOracle Java Tutorials — Interfaces and Inheritance