Design In-Memory File System

Naive Solution

A naive approach involves creating a simple file system structure using strings and dictionaries. The root directory can be represented as a dictionary, where keys are file/directory names, and values are either strings (for files) or nested dictionaries (for directories).

• ls(path): Split the path into components. If the path points to a file, return the file name in a list. If it's a directory, return a sorted list of file and directory names in that directory.
• mkdir(path): Split the path into components and create nested dictionaries as needed.
• addContentToFile(filePath, content): Split the file path into components, create directories if they don't exist, and append content to the file.
• readContentFromFile(filePath): Split the path into components and return the file's content.

Example

mkdir("/abc")
addContentToFile("/abc/def", "hello")
readContentFromFile("/abc/def") -> "hello"
ls("/") -> ["abc"]

Big O Analysis (Naive)

• Time Complexity:
  • ls: O(N + KlogK), where N is the length of the path, and K is the number of files/directories in the target directory (for sorting).
  • mkdir: O(N), where N is the length of the path.
  • addContentToFile: O(N + M), where N is the length of the path, and M is the length of the content to add.
  • readContentFromFile: O(N), where N is the length of the path.
• Space Complexity: O(P), where P is the total length of all paths and content stored in the file system.

Optimal Solution

For a more optimal approach, we can use a tree-like structure where each node represents either a directory or a file. Each node stores the file/directory name, its content (if it's a file), and a map of child nodes.

1. Node Class: Create a Node class with attributes: name, isFile, children (a map of name to Node), and content (only if it's a file).
2. File System Class: Maintain a root node. Implement the required methods by traversing the tree.

ls(path)

Split the path by "/". Traverse the tree to reach the desired node. If the node is a file, return [node.name]. If it's a directory, return a sorted list of the names of the children nodes.

mkdir(path)

Split the path. Traverse the tree. If a directory in the path does not exist, create a new node for it and add it to the children map of the current node.

addContentToFile(filePath, content)

Split the path. Traverse the tree, creating directories if they don't exist. When you reach the file node, append the content to the file's content.

readContentFromFile(filePath)

Split the path. Traverse the tree to reach the file node and return its content.

Edge Cases

• Empty path: Handle the root directory correctly.
• Invalid path: Consider throwing an exception or returning an error code.
• Concurrent access: Implement locking mechanisms if concurrent access is required.
• Empty File Name: Handle cases where file or directory names are empty strings.

Big O Analysis (Optimal)

• Time Complexity:
  • ls: O(N + KlogK), where N is the length of the path, and K is the number of entries in the directory (for sorting).
  • mkdir: O(N), where N is the length of the path.
  • addContentToFile: O(N + M), where N is the length of the path, and M is the length of the length of content.
  • readContentFromFile: O(N), where N is the length of the path.
• Space Complexity: O(P), where P is the total size of paths and content stored, similar to the naive solution, but the tree structure provides better organization.

Code (Python)

class Node:
    def __init__(self, name, isFile=False):
        self.name = name
        self.isFile = isFile
        self.children = {}
        self.content = ""

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

    def ls(self, path: str) -> list[str]:
        node = self.getNode(path)
        if node.isFile:
            return [node.name]
        else:
            return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        self.getNode(path, create=True)

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self.getNode(filePath, create=True, isFile=True)
        node.content += content

    def readContentFromFile(self, filePath: str) -> str:
        node = self.getNode(filePath)
        return node.content

    def getNode(self, path, create=False, isFile=False):
        curr = self.root
        if path == "/":
            return curr

        parts = path.split("/")[1:]
        for i, part in enumerate(parts):
            if part not in curr.children:
                if create:
                    curr.children[part] = Node(part, isFile=isFile if i == len(parts) - 1 else False)
                else:
                    return None # Or raise exception: Path not found
            curr = curr.children[part]
        return curr