Design In-Memory File System

Problem Statement

The task is to create a data structure that mimics an in-memory file system. This entails implementing various functionalities typical of a standard file system, such as listing items in directories, creating directories, adding content to files, and retrieving file contents. The FileSystem class should include:

1. Constructor FileSystem() to initialize the file system.
2. Method ls(String path) to list files and directories:
   • If the path leads to a file, the method returns just that file's name.
   • If the path leads to a directory, the method returns all contents in lexicographic order.
3. Method mkdir(String path) to create a new directory, including any necessary parent directories if they don’t exist.
4. Method addContentToFile(String filePath, String content) which:
   • Creates a new file containing the specified content if the file does not exist.
   • Appends content to the existing file without overwriting the original content.
5. Method readContentFromFile(String filePath) that returns the content of the specified file.

Examples

Example 1

Input

["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]

Output

[null, [], null, null, ["a"], "hello"]

Explanation

FileSystem fileSystem = new FileSystem();
fileSystem.ls("/"); // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/"); // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

Constraints

• 1 <= path.length, filePath.length <= 100
• path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just "/".
• You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
• You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist.
• You can assume that the parent directory for the file in addContentToFile will exist.
• 1 <= content.length <= 50
• At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.

Approach and Intuition

1. Data Structures Used:

   • Utilize a composite design pattern where both files and directories can be treated uniformly. This can be achieved by defining a base class or interface (Node), with two subclasses: File and Directory.
   • Each Directory would have a map storing its children nodes (files and sub-directories).
   • The File class would contain a string builder or similar structure to efficiently hold and modify its content.

2. Implementation Walkthrough:

   • Initialization (FileSystem()):
     • Start by creating the root directory.
   • Listing Items (ls(String path)):
     • Parse the path to navigate to the specified directory or file.
     • If a file, return the file name. If a directory, collect the names of its children, sort them, and return.
   • Creating Directories (mkdir(String path)):
     • Split the path to identify all components. Navigate through the existing structure, creating any missing directories.
   • Adding Content to Files (addContentToFile(String filePath, String content)):
     • Follow or create the path to the desired file location, creating the file if it doesn't exist.
     • Append or insert the content into the file's data structure.
   • Reading File Content (readContentFromFile(String filePath)):
     • Navigate to the file’s location and return its content.

3. System Design Considerations:

   • Handle edge cases such as attempting to read a non-existent file or directory.
   • Ensure methods are efficient in terms of both time and space complexity, considering the maximum constraints provided.
   • Implement the system to minimally interact with actual I/O operations, simulating those within the memory using data structures.
   • Leverage sorted data structures where appropriate to reduce complexity, especially for listing directory contents in lexicographic order.

By carefully structuring the file system classes and methods as described, it is possible to simulate an intuitive and efficient in-memory file system. This setup should meet the requirements laid out, handling up to 300 combined operations efficiently.

Solutions

public class VirtualFileSystem {
    class Node {
        boolean isFile = false;
        HashMap < String, Node > children = new HashMap < > ();
        String data = "";
    }
    Node root;
    public VirtualFileSystem() {
        root = new Node();
    }

    public List < String > ls(String path) {
        Node currentNode = root;
        List < String > itemList = new ArrayList < > ();
        if (!path.equals("/")) {
            String[] parts = path.split("/");
            for (int i = 1; i < parts.length; i++) {
                currentNode = currentNode.children.get(parts[i]);
            }
            if (currentNode.isFile) {
                itemList.add(parts[parts.length - 1]);
                return itemList;
            }
        }
        List < String > sortedItems = new ArrayList < > (currentNode.children.keySet());
        Collections.sort(sortedItems);
        return sortedItems;
    }

    public void mkdir(String path) {
        Node currentNode = root;
        String[] parts = path.split("/");
        for (int i = 1; i < parts.length; i++) {
            if (!currentNode.children.containsKey(parts[i]))
                currentNode.children.put(parts[i], new Node());
            currentNode = currentNode.children.get(parts[i]);
        }
    }

    public void addContentToFile(String filePath, String content) {
        Node currentNode = root;
        String[] parts = filePath.split("/");
        for (int i = 1; i < parts.length - 1; i++) {
            currentNode = currentNode.children.get(parts[i]);
        }
        if (!currentNode.children.containsKey(parts[parts.length - 1]))
            currentNode.children.put(parts[parts.length - 1], new Node());
        currentNode = currentNode.children.get(parts[parts.length - 1]);
        currentNode.isFile = true;
        currentNode.data = currentNode.data + content;
    }

    public String readContentFromFile(String filePath) {
        Node currentNode = root;
        String[] parts = filePath.split("/");
        for (int i = 1; i < parts.length - 1; i++) {
            currentNode = currentNode.children.get(parts[i]);
        }
        return currentNode.children.get(parts[parts.length - 1]).data;
    }
}