Design In-Memory File System


Clarify the problem

The problem is asking us to design an in-memory file system. We need to implement a set of operations such as creating files and directories, reading the contents of a file, and listing the files and directories in a given path.

Analyze the problem

To design an in-memory file system, we can represent it using a tree data structure. Each node in the tree can represent either a file or a directory. Directories can contain other directories and files. We'll also need to keep track of the content of each file.

Design an algorithm

We can start by defining the data structure for our in-memory file system. We'll create a class called FileSystem that has a Directory object as its root. The Directory class will have a dictionary to store the subdirectories and files contained within it.

The main operations we need to implement are:

  • ls(path): List the files and directories at a given path.
  • mkdir(path): Create a directory at the given path.
  • addContentToFile(filePath, content): Add content to the file at the given path.
  • readContentFromFile(filePath): Read and return the content of the file at the given path.

We can implement these operations recursively, starting from the root directory. To implement the ls operation, we'll split the given path into its components and traverse the directory tree accordingly. For the other operations, we'll perform similar traversal logic to reach the target directory or file and perform the necessary actions.

Explain your approach

We'll create a class called FileSystem that has a root directory. The root directory will be an instance of the Directory class, which will have a dictionary to store its subdirectories and files. Each file will be represented by a string of its content.

We'll implement the required operations using recursion, starting from the root directory. The ls operation will use a helper function to perform the recursive traversal and return the list of files and directories at a given path. The other operations will also use recursion to traverse the directory tree and perform the necessary actions.

Write clean and readable code

Let's write the code for our solution:

class File:
    def __init__(self, content):
        self.content = content


class Directory:
    def __init__(self):
        self.subdirectories = {}
        self.files = {}


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

    def ls(self, path):
        components = path.split('/')[1:]  # Ignore the empty string at the start

        # Helper function for recursive traversal
        def traverse(directory, components):
            if not components:
                return sorted(list(directory.subdirectories.keys()) + list(directory.files.keys()))

            next_component = components.pop(0)
            if next_component in directory.subdirectories:
                return traverse(directory.subdirectories[next_component], components)
            else:
                return [next_component] if not components else []

        result = traverse(self.root, components)
        return result

    def mkdir(self, path):
        components = path.split('/')[1:]  # Ignore the empty string at the start

        def traverse(directory, components):
            if not components:
                return

            next_component = components.pop(0)
            if next_component not in directory.subdirectories:
                directory.subdirectories[next_component] = Directory()

            traverse(directory.subdirectories[next_component], components)

        traverse(self.root, components)

    def addContentToFile(self, filePath, content):
        components = filePath.split('/')[1:]  # Ignore the empty string at the start

        def traverse(directory, components):
            if len(components) == 1:
                file_name = components[0]
                if file_name not in directory.files:
                    directory.files[file_name] = File(content)
                else:
                    directory.files[file_name].content += content
                return

            next_component = components.pop(0)
            if next_component not in directory.subdirectories:
                directory.subdirectories[next_component] = Directory()

            traverse(directory.subdirectories[next_component], components)

        traverse(self.root, components)

    def readContentFromFile(self, filePath):
        components = filePath.split('/')[1:]  # Ignore the empty string at the start

        def traverse(directory, components):
            if len(components) == 1:
                file_name = components[0]
                if file_name in directory.files:
                    return directory.files[file_name].content
                else:
                    return ''

            next_component = components.pop(0)
            if next_component in directory.subdirectories:
                return traverse(directory.subdirectories[next_component], components)
            else:
                return ''

        return traverse(self.root, components)

Test your code

Let's test our code with some example test cases to verify its correctness:

# Create a file system instance
fs = FileSystem()

# Create files and directories
fs.mkdir("/a/b/c")
fs.addContentToFile("/a/b/c/d", "Hello")
fs.mkdir("/x/y/z")

# List files and directories
print(fs.ls("/a"))  # Output: ['b']
print(fs.ls("/a/b/c"))  # Output: ['d']
print(fs.ls("/x"))  # Output: ['y']
print(fs.ls("/"))  # Output: ['a', 'x']

# Read content from files
print(fs.readContentFromFile("/a/b/c/d"))  # Output: 'Hello'
print(fs.readContentFromFile("/x/y/z"))  # Output: ''

Optimize if necessary

The provided solution is a straightforward implementation that satisfies the problem requirements. Since we cannot use predefined functions, further optimization may not be applicable.

Handle error cases

The code assumes valid input and does not handle specific error cases. To handle error cases, you can add appropriate checks, such as verifying the path format or ensuring the existence of directories or files before performing operations on them.

Discuss complexity analysis

  • The time complexity of the ls operation is O(k), where k is the length of the given path.
  • The time complexity of the mkdir operation is O(k), where k is the length of the given path.
  • The time complexity of the addContentToFile operation is O(k), where k is the length of the given file path.
  • The time complexity of the readContentFromFile operation is O(k), where k is the length of the given file path.
  • The space complexity is O(n), where n is the total number of directories and files in the file system.

Overall, the provided solution should work efficiently for typical use cases of the in-memory file system.

Next Post Previous Post