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.
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
int value = -1;
}
class FileSystem {
TrieNode root;
public FileSystem() {
root = new TrieNode();
}
public boolean createPath(String path, int value) {
TrieNode node = root;
for (int i = 1;
i < path.length();
i++) {
char dir = path.charAt(i);
if (!node.children.containsKey(dir)) {
node.children.put(dir, new TrieNode());
}
node = node.children.get(dir);
}
node.value = value;
return true;
}
public int get(String path) {
TrieNode node = root;
for (int i = 1;
i < path.length();
i++) {
char dir = path.charAt(i);
if (!node.children.containsKey(dir)) {
return -1;
}
node = node.children.get(dir);
}
return node.value;
}
}Follow-up:
How would you optimize the file system to support a large number of operations?
