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:
def __init__(self):
self.children = {}
self.value = -1
class FileSystem:
def __init__(self):
self.root = TrieNode()
def createPath(self, path:
str, value:
int) -> bool:
node = self.root
for i in range(1, len(path)):
dir = path[i]
if dir not in node.children:
node.children[dir] = TrieNode()
node = node.children[dir]
node.value = value
return True
def get(self, path:
str) -> int:
node = self.root
for i in range(1, len(path)):
dir = path[i]
if dir not in node.children:
return -1
node = node.children[dir]
return node.valueFollow-up:
How would you optimize the file system to support a large number of operations?
