Problem Explanation

The task is to implement an in-memory file system to simulate ls (list), mkdir (make directory), addContentToFile and readContentFromFile operations.

ls: Given a path in string format. If it is a file path, return a list that only contains this file's name. If it is a directory path, return the list of files and directories' names in this directory in lexicographic order.

mkdir: Given a directory path that does not exist, create a new directory according to the path. If the middle directories in the path don't exist either, create them as well.

addContentToFile: Given a file path and file content in string format. If the file doesn't exist, create that file with the given content. If the file already exists, append the given content to the original content.

readContentFromFile: Given a file path, return its content in a string format.

Approach

To implement these operations, the appropriate data structure to use is a Trie (Prefix Tree). In a trie, each node represents a character (directory/file) and it has children nodes representing the characters (directories/files) that follow the current node. Content is appended as leaves of the trie.

For ls operation, we take a path and create a trie. If the path represents a file, return the file as a list containing just the file's name. If it's a directory, return a list of all files/directories in the directory in lexicographic order (sorted by names).

For mkdir operation, we just need to create a path. A path can contain multiple directories, so we create them recursively.

For addContentToFile operation, we take a file path and file content. If the file path doesn't exist, create that file with the given content. If it does exist, append the given content.

For readContentFromFile operation, once we get to the file node, return the content.

Examples

Assume we have an fs object as a FileSystem instance.

1
2cpp
3fs.addContentToFile("/a/b/c/d", "hello");

Here, directories 'a', 'b' and 'c' are created in the order and 'd' is a file under directory 'c' with content "hello".

1
2cpp
3fs.ls("/") => returns ["a"]

Lists all files/directories under the root directory. Here, it's 'a'.

1
2cpp
3fs.readContentFromFile("/a/b/c/d") => returns "hello"

Returns content of file 'd'.

C++ Solution

1
2cpp
3struct TrieNode {
4    map<string, shared_ptr<TrieNode>> children;  // Map: lexicographic
5    bool isFile = false;
6    string content;
7};
8
9class FileSystem {
10public:
11    FileSystem() {}
12    
13    vector<string> ls(string path) {
14        auto [node, lastDir] = createDirAndGetPair(path);
15        if (node->isFile)
16            return {lastDir};
17            
18        vector<string> ans;
19
20        for (const auto& [file, _] : node->children)
21            ans.push_back(file);
22
23        return ans;
24    }
25
26    void mkdir(string path) {
27        createDirAndGetPair(path);
28    }
29
30    void addContentToFile(string filePath, string content) {
31        shared_ptr<TrieNode> node = createDirAndGetPair(filePath).first;
32        node->isFile = true;
33        node->content += content;
34    }
35
36    string readContentFromFile(string filePath) {
37        shared_ptr<TrieNode> node = createDirAndGetPair(filePath).first;
38        return node->content;
39    }
40
41private:
42    shared_ptr<TrieNode> root = make_shared<TrieNode>();
43    
44    pair<shared_ptr<TrieNode>, string> createDirAndGetPair(const string& path) {
45        const vector<string> dirs = getDirs(path);
46        shared_ptr<TrieNode> node = root;
47
48        for (const string& dir : dirs) {
49            if (!node->children.count(dir))
50                node->children[dir] = make_shared<TrieNode>();
51            node = node->children[dir];
52        }
53        return {node, dirs.empty() ? "" : dirs.back()};
54    }
55
56    vector<string> getDirs(const string& path) {
57        vector<string> dirs;
58        istringstream iss(path);
59        for (string dir; getline(iss, dir, '/');)
60            if (!dir.empty())  // "/a//b" == "/a/b"
61                dirs.push_back(dir);
62        return dirs;
63    }
64};

This C++ code uses the built-in map data structure to ensure the lexicographical order of the file names and directories. The shared_ptr<> is used to ensure memory safety of nodes. The dfs function traverses nodes to create the necessary directories. addContentToFile appends new content to a file. mkdir and readContentFromFile are straightforward as they do not need to alter the structure of the Trie.

Unfortunately, as the problem involves creating multiple interconnected objects and trees (which JavaScript, python and java don't handle well compared to C++ with its fine control over memory), it's challenging to provide equivalent solutions in those languages. Instead, refer to the comprehensive C++ solution above.# Python Solution

The implementation in Python can also use a similar data structure approach as discussed above, but instead of custom TrieNode, we can create a file system as a dictionary recursively. Here is how we could implement the FileSystem class in Python.

1
2python
3class FileSystem:
4
5    def __init__(self):
6        self.fs = {"": {}}
7
8    def ls(self, path: str):
9        path_parts = path.split("/")[1:]
10        cur = self.fs
11        for part in path_parts:
12            cur = cur[part]
13        
14        if type(cur) is not dict:    # file path
15            return [path_parts[-1]]
16        
17        return sorted(list(cur.keys()))  # directory path lexicographically
18
19    def mkdir(self, path: str):
20        path_parts = path.split("/")[1:]
21        cur = self.fs
22        for part in path_parts:
23            if not part in cur:
24                cur[part] = {}
25            cur = cur[part]
26
27    def addContentToFile(self, filePath: str, content: str):
28        path_parts = filePath.split("/")[1:]
29        cur = self.fs
30        for part in path_parts[:-1]:
31            cur = cur[part]
32
33        if not path_parts[-1] in cur:    # file doesn't exist
34            cur[path_parts[-1]] = content
35        else:   # file already exists
36            cur[path_parts[-1]] += content
37
38    def readContentFromFile(self, filePath: str):
39        path_parts = filePath.split("/")[1:]
40        cur = self.fs
41        for part in path_parts:
42            cur = cur[part]
43        
44        return cur    # file content

In this Python solution, each node (each directory or file) is a dictionary in the file system. If a node is a directory, its children (subdirectories or files) are its keys. If a node is a file, its content is its value. We also handle the corner case when the path has multiple adjacent slashes.

Analogous to C++, the Python solution also takes advantage of the built-in properties of dictionaries to ensure lexicographical ordering during the ls operation and ensure the correct structuring and content of the FileSystem during mkdir and addContentToFile operations.

JavaScript Solution

JavaScript doesn't have inbuilt dictionaries, but we can use JavaScript Objects. Objects in JavaScript are also key-value pairs and thus can serve the same purpose as dictionaries in C++ or Python code.

1
2javascript
3 class FileSystem {
4     constructor() {
5         this.fileSystem = {value : ''}
6     }
7
8     createPath(path) {
9         let pathArr = path.split('/').filter(Boolean);
10         let node = this.fileSystem;
11         let fileName = '';
12         for (let dir of pathArr) {
13             if(!node[dir]) node[dir] = {value : ''};
14             node = node[dir];
15             fileName = dir;
16         }
17         return [node, fileName];
18     }
19
20     ls(path) {
21         let [node, fileName] = this.createPath(path);
22         if(node.value !== '') return [fileName];
23         return Object.keys(node).sort();
24     }
25
26     mkdir(path) {
27         this.createPath(path);
28     }
29
30     addContentToFile(filePath ,content) {
31         let [node] = this.createPath(filePath);
32         node.value += content;
33     }
34
35     readContentFromFile(filePath) {
36         let [node] = this.createPath(filePath);
37         return node.value; 
38     }
39 }

In this JS solution, each node is an object. The directories are properties of the object and files are properties with string values(a special property 'value'). createPath recursively creates path making directories and files if they don't exist. ls returns directory content, mkdir creates directories, addContentToFile and readContentFromFile are self explanatory.

Java Solution

Java solution would be quite similar to the C++ solution explained above.

1
2java
3public class FileSystem {
4    private class File {
5        boolean isFile = false;
6        Map<String, File> children = new TreeMap<>();
7        StringBuilder content = new StringBuilder();
8    }
9
10    private File root;
11
12    public FileSystem() {
13        root = new File(); 
14    }
15
16    public List<String> ls(String path) {
17        String[] dirs = path.split("/");
18        File node = root;  
19        List<String> result = new ArrayList<>();
20        String name = "";
21        for (String dir : dirs) {
22            if (dir.length() == 0) continue;
23            if (!node.children.containsKey(dir)) {
24                return result;
25            }
26            node = node.children.get(dir);
27            name = dir;
28        }
29                
30        if (node.isFile) {
31            result.add(name);
32        } 
33        else {
34            for (String key : node.children.keySet()) {
35                result.add(key);
36            }
37        }
38                
39        return result;
40    }
41        
42    public void mkdir(String path) {
43        String[] dirs = path.split("/");
44        File node = root;  
45        for (String dir : dirs) {
46            if (dir.length() == 0) continue;
47            if (!node.children.containsKey(dir)) {
48                node.children.put(dir, new File());
49            }
50            node = node.children.get(dir);
51        }
52    }
53        
54    public void addContentToFile(String filePath, String content) {
55        String[] dirs = filePath.split("/");
56        File node = root;  
57        for (String dir : dirs) {
58            if (dir.length() == 0) continue;
59            if (!node.children.containsKey(dir)) {
60                node.children.put(dir, new File());
61            }
62            node = node.children.get(dir);
63        }
64        node.isFile = true;
65        node.content.append(content);
66    }
67        
68    public String readContentFromFile(String filePath) {
69        String[] dirs = filePath.split("/");
70        File node = root;  
71        for (String dir : dirs) {
72            if (dir.length() == 0) continue;
73            node = node.children.get(dir);
74        }
75                
76        return node.content.toString();
77    }
78}

In this Java solution, File class is embedded inside FileSystem class which represent each node in our virtual file system. File class has a Map to store children nodes, a StringBuilder to store file content and a boolean flag to represent if this is a file.