Design an In-Memory File System With Search & Size Visitors
In a 45-minute LLD interview, the interviewer tests two classic structural/behavioral patterns: Composite (treating files and directories uniformly in a tree) and Visitor (adding arbitrary tree traversals like size calculation or extension search without polluting node classes). Scope the solution to Unix-style path resolution (/a/b/c), mkdir -p, file creation/writing, alphabetical listing, and double-dispatch visitors. Mention permissions (chmod), soft/symbolic links, and file system locking as follow-up extensions.
Problem statement & clarifying requirements
Design an in-memory file system supporting files, hierarchical directories, nested path creation (mkdir -p), reading, writing, and directory listing (ls). New tree-walking operations—such as recursive size calculation and search by extension—must be added without modifying the node classes, adhering strictly to the Open-Closed Principle.
Paths use Unix-style forward slashes (e.g. /home/user/src/main.cpp). Path segments are resolved iteratively from the root directory.
The operation aborts and returns false, preventing files from acting as directories.
Via the Visitor pattern, keeping tree structure classes (FileNode, DirectoryNode) closed for modification.
Yes, using the Composite pattern, directories store polymorphic std::unique_ptr<FsNode> children.
First, sketch the design yourself
Spend 5 minutes listing the classes, who owns whom, and which interface hides the part that changes.
- 1.
Treat files and directories uniformly: A common base class
FsNodeallows directories to store collections ofFsNode*without caring whether each child is a leaf or a subtree. - 2.
Separate algorithms from tree structure: Hardcoding
calculateTotalSize()orsearchByExtension()insideFsNodepollutes the data model with every new reporting requirement. Use the Visitor pattern. - 3.
Clean memory ownership: Let parent directories own child nodes exclusively through
std::unique_ptr<FsNode>, while child nodes hold a non-owning raw back-pointerDirectoryNode* parent_to build absolute paths.
How to think through this problem (5-step walkthrough)
In a 45-minute LLD interview, the interviewer tests two classic structural/behavioral patterns: Composite (treating files and directories uniformly in a tree) and Visitor (adding arbitrary tree traversals like size calculation or extension search without polluting node classes). Scope the solution to Unix-style path resolution (/a/b/c), mkdir -p, file creation/writing, alphabetical listing, and double-dispatch visitors. Mention permissions (chmod), soft/symbolic links, and file system locking as follow-up extensions.
Not every noun in the prompt deserves its own class. Separate dumb data structs from stateful managers, and turn trivial nouns into fields or enums.
FsNodeAbstract Composite base class declaring common node attributes (name, parent pointer, isDirectory(), size()) and the accept(FsVisitor&) hook.
FileNodeLeaf Composite node storing binary/text content and file size. Dispatches visitor.visitFile(*this).
DirectoryNodeComposite container node owning child nodes (std::map<std::string, std::unique_ptr<FsNode>>). Dispatches visitor.visitDirectory(*this) and propagates traversal.
FsVisitorDouble-dispatch Visitor interface declaring visitFile(const FileNode&) and visitDirectory(const DirectoryNode&).
TotalSizeVisitor / ExtensionSearchVisitorConcrete visitors encapsulating traversal operations: accumulating byte size across subtrees or filtering files by suffix.
FilePath / FileExtensionTrap noun — beginners often create separate FilePath, PathTokenizer, or FileExtension classes. Path splitting is easily handled by std::string_view iteration, and an extension is a simple string substring check (endsWith), not a heavyweight class.
A naive implementation adds recursive methods (calculateSize(), searchExtension(), printTree()) directly to DirectoryNode and FileNode, using dynamic_cast<FileNode*> to inspect children. Every new feature (e.g. disk usage analysis, checksum calculation, backup serialization) forces modifying the core node hierarchy, violating the Open-Closed Principle and cluttering domain classes with traversal state.
Having separate collections for files_ and directories_ inside every directory requires branching logic for every lookup and listing operation.
Hardcoding operations like recursive size calculation or file extension search inside node classes violates OCP and bloats core data structures.
- ✓
Strict hierarchical tree ownership:
DirectoryNodeexclusively owns its children viastd::map<std::string, std::unique_ptr<FsNode>>, while children hold a non-owning raw back-pointerDirectoryNode* parent_to build absolute paths without circular references. - ✓
Collision prevention invariant: A directory cannot contain both a file and a subdirectory with the exact same name under the same parent directory.
- ✓
Double-dispatch traversal invariant: When
DirectoryNode::accept(visitor)is invoked, it visits the directory itself and recursively forwardschild->accept(visitor)to all owned children.
Entities & design patterns used
Unlock Full UML Diagram & C++23 Solution
The complete UML diagram, production-ready C++23 code, follow-up extensions, and design pitfall analysis are part of Brute2Best Pro. All 7 foundation chapters are 100% free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.