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 {
constructor() {
this.children = new Map();
this.value = -1;
}
}
class FileSystem {
constructor() {
this.root = new TrieNode();
}
createPath(path, value) {
let node = this.root;
for (let i = 1; i < path.length; i++) {
const dir = path[i];
if (!node.children.has(dir)) {
node.children.set(dir, new TrieNode());
}
node = node.children.get(dir);
}
node.value = value;
return true;
}
get(path) {
let node = this.root;
for (let i = 1; i < path.length; i++) {
const dir = path[i];
if (!node.children.has(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?
