MANG Problem #42: Design In-Memory File System (Hard)

1. Problem Statement

Design a data structure that simulates an in-memory file system.

Implement the FileSystem class:

• List<String> ls(String path)
• void mkdir(String path)
• void addContentToFile(String filePath, String content)
• String readContentFromFile(String filePath)

Constraints:

• ls should return a list of file/directory names in the given directory in lexicographic order. If it's a file path, return a list containing only the file's name.

2. Approach: N-ary Tree (Trie-like Structure)

A file system is inherently a Tree. We can model it using a Trie-like Node structure where each node represents a directory or a file.

1. Node Structure:
   • boolean isFile: Differentiates files from directories.
   • Map<String, Node> children: Maps a directory/file name to its Node.
   • StringBuilder content: Stores data if isFile is true.
2. Path Parsing: The core utility is splitting the path "/a/b/c" by "/" and traversing the tree layer by layer.

3. Java Implementation

class FileSystem {
    class Node {
        boolean isFile = false;
        Map<String, Node> children = new HashMap<>();
        StringBuilder content = new StringBuilder();
    }

    private Node root;

    public FileSystem() {
        root = new Node();
    }

    public List<String> ls(String path) {
        Node node = traverse(path);
        List<String> res = new ArrayList<>();
        if (node.isFile) {
            String[] parts = path.split("/");
            res.add(parts[parts.length - 1]); // Add filename
        } else {
            res.addAll(node.children.keySet());
            Collections.sort(res); // Return lexicographically
        }
        return res;
    }

    public void mkdir(String path) {
        traverse(path);
    }

    public void addContentToFile(String filePath, String content) {
        Node node = traverse(filePath);
        node.isFile = true;
        node.content.append(content);
    }

    public String readContentFromFile(String filePath) {
        return traverse(filePath).content.toString();
    }

    // Helper method to traverse path and create missing directories
    private Node traverse(String path) {
        Node curr = root;
        String[] parts = path.split("/");
        for (int i = 1; i < parts.length; i++) { // Skip first empty split from "/"
            String p = parts[i];
            curr.children.putIfAbsent(p, new Node());
            curr = curr.children.get(p);
        }
        return curr;
    }
}

4. 5-Minute "Video-Style" Walkthrough

1. The Unified Traverse: The traverse method is the secret sauce. By using putIfAbsent, it acts as both a search function and a creation function. If we call mkdir("/a/b"), it effortlessly creates a and b. If we call addContentToFile("/a/c"), it traverses a and creates c.
2. The Trie Comparison: This is exactly a Trie, but instead of characters driving the edges (Node[26]), full string tokens (directory names) drive the edges via a HashMap.
3. The ls Logic: If the traversed node is a file, we extract its name from the path string. If it's a directory, we dump the HashMap keys into a list and sort them.

5. Interview Discussion

• Interviewer: "What is the time complexity of ls?"
• You: "Traversal takes $O(P)$ where $P$ is path length. Sorting the directory contents takes $O(K \log K)$ where $K$ is the number of items in that directory."
• Interviewer: "How would you optimize ls if it's called very frequently?"
• You: "Instead of a HashMap, we could use a TreeMap in the Node. This maintains lexicographic order automatically during insertions, making ls an $O(K)$ operation to just read the keys, at the cost of $O(\log K)$ insertions."