588. Design In-Memory File System - Leetcode Solution

Code Implementation

class FileNode:
    def __init__(self):
        self.is_file = False
        self.children = {}  # name: FileNode
        self.content = ""

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

    def ls(self, path: str) -> list:
        curr = self.root
        if path == "/":
            return sorted(curr.children.keys())
        parts = path.split("/")[1:]
        for part in parts:
            curr = curr.children[part]
        if curr.is_file:
            return [parts[-1]]
        return sorted(curr.children.keys())

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

    def addContentToFile(self, filePath: str, content: str) -> None:
        curr = self.root
        parts = filePath.split("/")[1:]
        for part in parts[:-1]:
            if part not in curr.children:
                curr.children[part] = FileNode()
            curr = curr.children[part]
        file_name = parts[-1]
        if file_name not in curr.children:
            curr.children[file_name] = FileNode()
        curr = curr.children[file_name]
        curr.is_file = True
        curr.content += content

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

class FileNode {
public:
    bool isFile;
    string content;
    unordered_map<string, FileNode*> children;
    FileNode() : isFile(false), content("") {}
};

class FileSystem {
    FileNode* root;
public:
    FileSystem() {
        root = new FileNode();
    }
    
    vector<string> ls(string path) {
        FileNode* curr = root;
        if (path == "/") {
            vector<string> res;
            for (auto& kv : curr->children)
                res.push_back(kv.first);
            sort(res.begin(), res.end());
            return res;
        }
        vector<string> parts = split(path, '/');
        for (string& part : parts)
            curr = curr->children[part];
        if (curr->isFile)
            return {parts.back()};
        vector<string> res;
        for (auto& kv : curr->children)
            res.push_back(kv.first);
        sort(res.begin(), res.end());
        return res;
    }
    
    void mkdir(string path) {
        FileNode* curr = root;
        vector<string> parts = split(path, '/');
        for (string& part : parts) {
            if (!curr->children.count(part))
                curr->children[part] = new FileNode();
            curr = curr->children[part];
        }
    }
    
    void addContentToFile(string filePath, string content) {
        FileNode* curr = root;
        vector<string> parts = split(filePath, '/');
        for (int i = 0; i < parts.size() - 1; ++i) {
            string part = parts[i];
            if (!curr->children.count(part))
                curr->children[part] = new FileNode();
            curr = curr->children[part];
        }
        string fileName = parts.back();
        if (!curr->children.count(fileName))
            curr->children[fileName] = new FileNode();
        curr = curr->children[fileName];
        curr->isFile = true;
        curr->content += content;
    }
    
    string readContentFromFile(string filePath) {
        FileNode* curr = root;
        vector<string> parts = split(filePath, '/');
        for (string& part : parts)
            curr = curr->children[part];
        return curr->content;
    }
    
private:
    vector<string> split(const string& s, char delim) {
        vector<string> res;
        stringstream ss(s);
        string item;
        while (getline(ss, item, delim)) {
            if (!item.empty())
                res.push_back(item);
        }
        return res;
    }
};

class FileNode {
    boolean isFile = false;
    String content = "";
    Map<String, FileNode> children = new HashMap<>();
}

class FileSystem {
    private FileNode root;
    public FileSystem() {
        root = new FileNode();
    }
    
    public List<String> ls(String path) {
        FileNode curr = root;
        if (path.equals("/")) {
            List<String> res = new ArrayList<>(curr.children.keySet());
            Collections.sort(res);
            return res;
        }
        String[] parts = path.split("/");
        for (int i = 1; i < parts.length; i++)
            curr = curr.children.get(parts[i]);
        if (curr.isFile)
            return Arrays.asList(parts[parts.length - 1]);
        List<String> res = new ArrayList<>(curr.children.keySet());
        Collections.sort(res);
        return res;
    }
    
    public void mkdir(String path) {
        FileNode curr = root;
        String[] parts = path.split("/");
        for (int i = 1; i < parts.length; i++) {
            curr.children.putIfAbsent(parts[i], new FileNode());
            curr = curr.children.get(parts[i]);
        }
    }
    
    public void addContentToFile(String filePath, String content) {
        FileNode curr = root;
        String[] parts = filePath.split("/");
        for (int i = 1; i < parts.length - 1; i++) {
            curr.children.putIfAbsent(parts[i], new FileNode());
            curr = curr.children.get(parts[i]);
        }
        String fileName = parts[parts.length - 1];
        curr.children.putIfAbsent(fileName, new FileNode());
        curr = curr.children.get(fileName);
        curr.isFile = true;
        curr.content += content;
    }
    
    public String readContentFromFile(String filePath) {
        FileNode curr = root;
        String[] parts = filePath.split("/");
        for (int i = 1; i < parts.length; i++)
            curr = curr.children.get(parts[i]);
        return curr.content;
    }
}

class FileNode {
    constructor() {
        this.isFile = false;
        this.content = "";
        this.children = new Map();
    }
}

class FileSystem {
    constructor() {
        this.root = new FileNode();
    }

    ls(path) {
        let curr = this.root;
        if (path === "/") {
            return Array.from(curr.children.keys()).sort();
        }
        let parts = path.split("/").filter(Boolean);
        for (let part of parts) {
            curr = curr.children.get(part);
        }
        if (curr.isFile) {
            return [parts[parts.length - 1]];
        }
        return Array.from(curr.children.keys()).sort();
    }

    mkdir(path) {
        let curr = this.root;
        let parts = path.split("/").filter(Boolean);
        for (let part of parts) {
            if (!curr.children.has(part)) {
                curr.children.set(part, new FileNode());
            }
            curr = curr.children.get(part);
        }
    }

    addContentToFile(filePath, content) {
        let curr = this.root;
        let parts = filePath.split("/").filter(Boolean);
        for (let i = 0; i < parts.length - 1; i++) {
            let part = parts[i];
            if (!curr.children.has(part)) {
                curr.children.set(part, new FileNode());
            }
            curr = curr.children.get(part);
        }
        let fileName = parts[parts.length - 1];
        if (!curr.children.has(fileName)) {
            curr.children.set(fileName, new FileNode());
        }
        curr = curr.children.get(fileName);
        curr.isFile = true;
        curr.content += content;
    }

    readContentFromFile(filePath) {
        let curr = this.root;
        let parts = filePath.split("/").filter(Boolean);
        for (let part of parts) {
            curr = curr.children.get(part);
        }
        return curr.content;
    }
}

Problem Description

You are asked to design an in-memory file system that supports the following operations:

ls(path): If the path is a file, return its name; if it's a directory, return a sorted list of files and directories inside.
mkdir(path): Create a directory at the given path, including any intermediate directories if they do not exist.
addContentToFile(filePath, content): Add content to a file. If the file does not exist, create it.
readContentFromFile(filePath): Return the content of the file at the given path.

The file system starts with an empty root directory '/'. Paths are always absolute (start with '/'). All file and directory names consist of lowercase letters and numbers.
You must implement all operations efficiently, and the structure must be in-memory (no disk or database).

Thought Process

At first glance, the problem resembles building a tree structure, where each node represents either a file or a directory. Since directories can contain files or other directories, a tree (specifically, a trie-like structure) is a natural fit.

A brute-force approach might use a flat hash map from paths to contents, but this would make directory navigation and listing inefficient and error-prone. Instead, representing the file system as a nested hierarchy allows us to efficiently traverse, create, and modify files and directories.

The main challenge is to distinguish files from directories and efficiently walk the path for each operation. We also need to handle cases where intermediate directories/files do not exist, especially for mkdir and addContentToFile.

Solution Approach

We model the file system as a tree, where each node represents either a file or a directory.

Node Structure: Each node stores:
- A flag indicating if it's a file or directory (is_file).
- If it's a directory: a map from names to child nodes.
- If it's a file: the file's content.
Traversing Paths: For every operation, we split the input path by '/' and walk the tree from the root, creating nodes as needed (for mkdir and addContentToFile).
ls(path):
- If the path is a file, return its name in a list.
- If it's a directory, return all child names sorted lexicographically.
mkdir(path): Walk the path, creating directories as needed.
addContentToFile(filePath, content): Walk to the parent directory, create the file node if necessary, append content.
readContentFromFile(filePath): Walk to the file node and return its content.

This approach ensures all operations are efficient and easy to reason about.

Example Walkthrough

Let's walk through an example sequence of operations:

mkdir("/a/b/c"): Creates directories a, b, and c under root. The tree now has a path /a/b/c.
addContentToFile("/a/b/c/d", "hello"): Navigates to /a/b/c, creates file d, and sets its content to "hello".
ls("/a/b/c"): Returns ["d"] because d is the only child of c.
readContentFromFile("/a/b/c/d"): Returns "hello".
ls("/"): Returns ["a"] since a is the only child of root.
ls("/a/b/c/d"): Since this is a file, returns ["d"].

At each step, the file system tree is updated or queried efficiently by splitting and traversing the path.

Time and Space Complexity

Brute-force Approach:

If we stored all paths in a flat hash map, every ls or mkdir could require scanning all keys, which is O(N) in the number of files/directories.

Optimized Tree Approach:

Each operation walks the path from root to the target node. If the path has K components, the time complexity is O(K).
For ls on a directory, we also sort the child names, which is O(M log M) where M is the number of children.
Space complexity is O(N), where N is the total number of files and directories, since each is represented by a node.

This approach avoids scanning unrelated paths and ensures efficient navigation and updates.

Summary

By modeling the in-memory file system as a tree structure with nodes for files and directories, we achieve efficient and intuitive operations for all required commands. Traversing and modifying the tree is straightforward, and the design naturally supports hierarchical file organization. The main insight is to treat the file system as a trie-like structure, enabling O(K) navigation where K is the path length, and to clearly distinguish files from directories in each node.

AlgoMap.io

Want Help Cracking FAANG?