🔴 Data Structures: Design In-Memory File System

AIVIA Project Engine Coding Challenges
1

Data Structures: Design In-Memory File System

Difficulty: Hard

Problem Statement

Design an in-memory file system to simulate the following functions:

  • ls(path): If path is a file path, return a list containing only the file’s name. If path is a directory path, return the list of file and directory names in that directory. The output should be in lexicographic order.
  • mkdir(path): Make a new directory according to the given path. The given directory path does not exist. If the parent directory does not exist, create it as well.
  • addContentToFile(filePath, content): Write content to the file at filePath. If the file does not exist, create it.
  • readContentFromFile(filePath): Return the content of the file at filePath.

Implementation Details

Implement the following class:

class FileSystem:
    def __init__(self):
        """
        Initializes the file system.
        """
        pass  # Your implementation here

    def ls(self, path: str) -> List[str]:
        """
        List directory contents or file name.

        Args:
            path (str): The path to the file or directory.

        Returns:
            List[str]: List of directory or file names in lexicographic order.
        """
        pass  # Your implementation here

    def mkdir(self, path: str) -> None:
        """
        Creates a directory at the specified path.

        Args:
            path (str): The directory path to create.
        """
        pass  # Your implementation here

    def addContentToFile(self, filePath: str, content: str) -> None:
        """
        Adds content to a file at the specified path.

        Args:
            filePath (str): The file path.
            content (str): The content to add.
        """
        pass  # Your implementation here

    def readContentFromFile(self, filePath: str) -> str:
        """
        Reads content from a file at the specified path.

        Args:
            filePath (str): The file path.

        Returns:
            str: The content of the file.
        """
        pass  # Your implementation here

Constraints

  • File Path Lengths: The length of a path or file name is at most 100.
  • Content Length: The length of content is at most 50.
  • Number of Operations: The number of calls to each function is less than or equal to (10^4).
  • Paths: All paths are absolute starting from '/'.
  • Characters: Paths and file names contain lowercase letters, digits, '/', and '.'.

Example Usage

fs = FileSystem()
print(fs.ls("/"))                       # Expected Output: []
fs.mkdir("/a/b/c")
fs.addContentToFile("/a/b/c/d", "hello")
print(fs.ls("/"))                       # Expected Output: ["a"]
print(fs.readContentFromFile("/a/b/c/d"))  # Expected Output: "hello"

Test Cases

def test_file_system():
    # Test Case 1: Basic directory and file creation
    fs = FileSystem()
    fs.mkdir("/goowmfn")
    print(fs.ls("/goowmfn"))            # Expected Output: []

    # Test Case 2: Add content to file
    fs = FileSystem()
    fs.addContentToFile("/a/b/c/d", "hello")
    assert fs.readContentFromFile("/a/b/c/d") == "hello"

    # Test Case 3: List directory contents
    fs = FileSystem()
    fs.mkdir("/a/b/c")
    fs.addContentToFile("/a/b/c/d", "hello")
    assert fs.ls("/a/b") == ["c"]

    # Test Case 4: Append content to existing file
    fs.addContentToFile("/a/b/c/d", " world")
    assert fs.readContentFromFile("/a/b/c/d") == "hello world"

    # Test Case 5: List root directory
    assert fs.ls("/") == ["a"]

    print("All test cases pass!")

Expected Solution Approach

Implement a hierarchical tree structure to represent directories and files.

Algorithm Steps

  1. Design Data Structures:

    • Use a Trie or nested dictionaries to represent directories and files.
    • Each node represents a directory or a file.
    • A directory node contains a mapping of names to child nodes.
    • A file node contains content.

  2. Implement Functions:

    • ls(path):

      • Traverse to the node at the given path.
      • If it’s a file, return its name in a list.
      • If it’s a directory, return sorted list of its children’s names.

    • mkdir(path):

      • Split the path by '/'.
      • Traverse or create nodes for each directory in the path.

    • addContentToFile(filePath, content):

      • Traverse or create nodes for each directory in the path.
      • For the file node, append content.

    • readContentFromFile(filePath):

      • Traverse to the file node and return its content.

  3. Edge Cases:

    • Handle paths with multiple consecutive '/'.
    • Ensure that file names and directory names are correctly distinguished.

Time Complexity

  • ls: (O(L + K \log K)), where (L) is the length of the path, and (K) is the number of entries in the directory.
  • mkdir and addContentToFile: (O(L)), where (L) is the length of the path.
  • readContentFromFile: (O(L)).

Implementation Hint

Here’s a skeleton to help you start:

class Node:
    def __init__(self):
        self.children = {}
        self.content = ""

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

    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.content:
                return [part]
        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] = Node()
            node = node.children[part]

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self.root
        parts = filePath.split('/')[1:]
        for part in parts[:-1]:
            if part not in node.children:
                node.children[part] = Node()
            node = node.children[part]
        file_name = parts[-1]
        if file_name not in node.children:
            node.children[file_name] = Node()
        node.children[file_name].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

Learning Objectives

  1. Implement Hierarchical Data Structures:

    • Design tree structures to represent file systems.
    • Manage nodes representing both files and directories.

  2. Efficient Path Parsing:

    • Handle absolute paths correctly.
    • Split and process paths efficiently.

  3. Data Encapsulation:

    • Encapsulate data and functionality within classes.
    • Use helper classes or structures when appropriate.

  4. Edge Case Handling:

    • Manage cases where directories or files do not exist.
    • Ensure correct behavior for root and nested paths.

Real-World Applications

  • Operating Systems: Simulate file system operations for testing or embedded systems.
  • Virtual File Systems: Implement file systems over network protocols or in-memory for applications.
  • Cloud Storage Services: Manage user files and directories in services like Dropbox or Google Drive.
  • Educational Tools: Teach concepts of file systems and data structures.