Design In-Memory File System

This problem requires designing an in-memory file system that simulates the basic operations of a real file system. It involves creating directories and files, reading the content of a file, writing content to a file, and listing the contents of a directory.

Naive Solution

A simple approach is to use a tree-like structure where each node represents either a directory or a file. Each directory node will store a map of names to child nodes. File nodes will store the content of the file as a string.

Data Structures:

• FileSystemNode (Abstract Class):
  • name: Name of the node
  • isFile(): Returns true if the node is a file, false otherwise
• DirectoryNode (Extends FileSystemNode):
  • children: A map of string (name) to FileSystemNode
• FileNode (Extends FileSystemNode):
  • content: String representing the file content

Operations:

• ls(path): Split the path into components. Traverse the tree to the target directory. Return the list of file/directory names in sorted order.
• mkdir(path): Split the path into components. Traverse the tree, creating directories along the way if they don't exist.
• addContentToFile(filePath, content): Split the path into components. Traverse the tree, creating directories along the way if they don't exist. Create the file if it doesn't exist. Append the given content to the file.
• readContentFromFile(filePath): Split the path into components. Traverse the tree to the target file. Return the content of the file.

Code (Python):

class FileSystemNode:
    def __init__(self, name):
        self.name = name

    def isFile(self):
        return False

class DirectoryNode(FileSystemNode):
    def __init__(self, name):
        super().__init__(name)
        self.children = {}

    def isFile(self):
        return False

class FileNode(FileSystemNode):
    def __init__(self, name):
        super().__init__(name)
        self.content = ""

    def isFile(self):
        return True

class FileSystem:
    def __init__(self):
        self.root = DirectoryNode("")

    def ls(self, path: str) -> List[str]:
        node = self.root
        if path != "/":
            parts = path.split("/")[1:]
            for part in parts:
                node = node.children[part]

        if node.isFile():
            return [node.name]
        else:
            return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        node = self.root
        parts = path.split("/")[1:]
        for part in parts:
            if part not in node.children:
                node.children[part] = DirectoryNode(part)
            node = node.children[part]

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self.root
        parts = filePath.split("/")[1:-1]
        filename = filePath.split("/")[-1]

        for part in parts:
            if part not in node.children:
                node.children[part] = DirectoryNode(part)
            node = node.children[part]

        if filename not in node.children:
            node.children[filename] = FileNode(filename)
        node.children[filename].content += content

    def readContentFromFile(self, filePath: str) -> str:
        node = self.root
        parts = filePath.split("/")[1:]
        for part in parts:
            node = node.children[part]
        return node.content

Time Complexity:

• ls: O(m + klogk) where m is the length of the path and k is the number of entries in the directory (due to sorting).
• mkdir: O(m) where m is the length of the path.
• addContentToFile: O(m) where m is the length of the path.
• readContentFromFile: O(m) where m is the length of the path.

Space Complexity:

• O(N) where N is the total number of files and directories created in the file system.

Optimal Solution

The naive solution is already quite efficient for the given operations. However, we can make some small optimizations such as using a single function to handle path traversal, and minor code cleanup.

The core idea remains the same - a tree-like structure with directory and file nodes.

There isn't a significantly "more optimal" solution in terms of asymptotic complexity, but code clarity and reducing redundant code is always beneficial.

Edge Cases:

• Empty path: Handle the root directory case specifically for ls.
• Invalid path: Throw an exception or return an error code (depending on requirements).
• Empty file: Reading an empty file should return an empty string.
• Concurrent access: For a real-world file system, you'd need to consider concurrency and locking.

Revised Code (Python):

class FileSystemNode:
    def __init__(self, name):
        self.name = name

    def isFile(self):
        return False

class DirectoryNode(FileSystemNode):
    def __init__(self, name):
        super().__init__(name)
        self.children = {}

    def isFile(self):
        return False

class FileNode(FileSystemNode):
    def __init__(self, name):
        super().__init__(name)
        self.content = ""

    def isFile(self):
        return True

class FileSystem:
    def __init__(self):
        self.root = DirectoryNode("")

    def _get_node(self, path: str) -> FileSystemNode:
        node = self.root
        if path == "/":
            return node

        parts = path.split("/")[1:]
        for part in parts:
            if part not in node.children:
                return None # Or raise exception if path must exist
            node = node.children[part]
        return node

    def ls(self, path: str) -> List[str]:
        node = self._get_node(path)

        if node is None:
            return [] # Or raise exception if path must exist

        if node.isFile():
            return [node.name]
        else:
            return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        node = self.root
        parts = path.split("/")[1:]
        for part in parts:
            if part not in node.children:
                node.children[part] = DirectoryNode(part)
            node = node.children[part]

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self.root
        parts = filePath.split("/")[1:-1]
        filename = filePath.split("/")[-1]

        for part in parts:
            if part not in node.children:
                node.children[part] = DirectoryNode(part)
            node = node.children[part]

        if filename not in node.children:
            node.children[filename] = FileNode(filename)
        node.children[filename].content += content

    def readContentFromFile(self, filePath: str) -> str:
        node = self._get_node(filePath)
        if node is None:
            return "" # Or raise exception if path must exist
        return node.content

Time Complexity (Optimized):

Same as the naive solution:

• ls: O(m + klogk)
• mkdir: O(m)
• addContentToFile: O(m)
• readContentFromFile: O(m)

Space Complexity (Optimized):

Same as the naive solution: O(N).