Design In-Memory File System

Naive Solution

A naive solution involves using a HashMap to store the file system structure. Each path can be a key in the HashMap, and the value can be either a string (for files) or another HashMap (for directories). The ls command would involve traversing the HashMap based on the path and returning the contents. mkdir would create a new entry in the HashMap for the directory. addContentToFile would create or append to a file's string value in the HashMap, and readContentFromFile would simply return the string associated with the file path.

Big O Runtime

• ls: O(N) in the worst case, where N is the number of directories and files, as we might have to traverse a long path.
• mkdir: O(N), where N is the length of the path (number of directories in the path).
• addContentToFile: O(N + L), where N is the length of the path and L is the length of the content being added.
• readContentFromFile: O(N + M), where N is the length of the path and M is the size of the file's content.

Big O Space

O(S), where S is the total size of all paths and file contents stored in the system.

Optimal Solution

A more optimal solution involves using a tree-like structure to represent the file system. Each node in the tree represents either a directory or a file. A directory node would contain a HashMap of its children (other directories or files). A file node would contain the file's content.

Data Structure

We can define a Node class:

class Node {
    String name;
    boolean isFile;
    String content;
    HashMap<String, Node> children;

    public Node(String name, boolean isFile) {
        this.name = name;
        this.isFile = isFile;
        this.content = "";
        this.children = new HashMap<>();
    }
}

The FileSystem class would contain a root Node representing the root directory.

Implementation Details

• ls(path): Split the path into directory names. Traverse the tree to the node represented by the path. If it's a file, return a list containing only the file's name. If it's a directory, return a sorted list of the names of its children.
• mkdir(path): Split the path into directory names. Traverse the tree, creating new directory nodes as needed. If a node already exists, move to the next segment of the path.
• addContentToFile(path, content): Split the path into directory names. Traverse the tree, creating new directory nodes as needed. When you reach the final node (file), append the content to the file's content. If the file does not exist, create it.
• readContentFromFile(path): Split the path into directory names. Traverse the tree to the file node and return its content.

Big O Runtime

• ls: O(M + KlogK), where M is the length of the path, and K is the number of files/directories in the directory being listed. The KlogK comes from sorting the result. If we did not require sorting it would be O(M + K).
• mkdir: O(M), where M is the length of the path.
• addContentToFile: O(M + L), where M is the length of the path and L is the length of the content being added.
• readContentFromFile: O(M + N), where M is the length of the path and N is the size of the file's content.

Big O Space

O(T), where T is the total size of all paths and file contents stored in the system. The space is used to store the tree structure and the file contents.

Edge Cases

• Empty path: The root directory.
• Invalid path: Path does not exist. Throw an exception, or return an appropriate error code (depending on the requirements).
• Adding content to a non-file: Should throw an exception or return an error code.
• Reading content from a non-file: Should throw an exception or return an error code.
• Creating a directory with the same name as an existing file: Should throw an exception or return an error code. Vice versa.

Code (Java)

import java.util.*;

class FileSystem {

    class Node {
        String name;
        boolean isFile;
        String content;
        HashMap<String, Node> children;

        public Node(String name, boolean isFile) {
            this.name = name;
            this.isFile = isFile;
            this.content = "";
            this.children = new HashMap<>();
        }
    }

    Node root;

    public FileSystem() {
        root = new Node("", false);
    }

    public List<String> ls(String path) {
        String[] paths = path.split("/");
        Node curr = root;
        for (int i = 1; i < paths.length; i++) {
            String p = paths[i];
            if (!curr.children.containsKey(p)) {
                return new ArrayList<>(); // Path does not exist
            }
            curr = curr.children.get(p);
        }

        if (curr.isFile) {
            return Arrays.asList(curr.name);
        } else {
            List<String> result = new ArrayList<>(curr.children.keySet());
            Collections.sort(result);
            return result;
        }
    }

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

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

        String fileName = paths[paths.length - 1];
        if (!curr.children.containsKey(fileName)) {
            curr.children.put(fileName, new Node(fileName, true));
        }
        curr = curr.children.get(fileName);
        curr.content += content;
    }

    public String readContentFromFile(String filePath) {
        String[] paths = filePath.split("/");
        Node curr = root;
        for (int i = 1; i < paths.length; i++) {
            String p = paths[i];
            if (!curr.children.containsKey(p)) {
                return ""; // Or throw an exception, file not found
            }
            curr = curr.children.get(p);
        }
        return curr.content;
    }

    public static void main(String[] args) {
        FileSystem fs = new FileSystem();
        fs.mkdir("/a/b/c");
        fs.addContentToFile("/a/b/c/d", "hello");
        System.out.println(fs.readContentFromFile("/a/b/c/d")); // Output: hello
        fs.addContentToFile("/a/b/c/d", " world");
        System.out.println(fs.readContentFromFile("/a/b/c/d")); // Output: hello world
        System.out.println(fs.ls("/a/b")); // Output: [c]
    }
}