Design In-Memory File System
Design a file system which supports the following functions: createPath(path, value), get(path). createPath(path, value) creates a new path and associates a value to it if possible and returns true. Returns false if the path does not exist. get(path) returns the value associated with the path or returns -1 if the path does not exist.
Constraints:
- The file system should be case-sensitive.
- The file system should support at most 10^4 operations.
- The length of the path should be at most 100.
Examples:
Input: createPath("/a", 1) get("/a")
Output: 1
Explanation: We create a new path "/a" and associate a value 1 to it. Then we get the value associated with the path "/a" which is 1.
Solutions
Hash Map
We use a Trie data structure to represent the file system. Each node in the Trie represents a directory or a file. The createPath function creates a new path and associates a value to it if possible. The get function returns the value associated with the path or returns -1 if the path does not exist.
struct TrieNode {
unordered_map<char, TrieNode*> children;
int value = -1;
}
;
class FileSystem {
TrieNode* root;
public: FileSystem() {
root = new TrieNode();
}
bool createPath(string path, int value) {
TrieNode* node = root;
for (int i = 1;
i < path.size();
i++) {
char dir = path[i];
if (node->children.find(dir) == node->children.end()) {
node->children[dir] = new TrieNode();
}
node = node->children[dir];
}
node->value = value;
return true;
}
int get(string path) {
TrieNode* node = root;
for (int i = 1;
i < path.size();
i++) {
char dir = path[i];
if (node->children.find(dir) == node->children.end()) {
return -1;
}
node = node->children[dir];
}
return node->value;
}
}
;Follow-up:
How would you optimize the file system to support a large number of operations?
