Google - Design In-Memory File System
1. Requirements
-
ls(path): if path is a file return name, else return names inside sorted lexicographically.
-
mkdir(path): create all directories.
-
addContentToFile(path, content)
-
readContentFromFile(path)
2. Ideas
- _traverse(path: str) -> Node
-
Splits path by / and walks the tree.
-
Used by all operations.
-
Time complexity: O(L) where L = number of components.
- ls(path: str) -> List[str>
-
Traverse to node.
-
If file: return [last_component].
-
If directory: return sorted list of keys in node.children.
-
Time: O(L + d log d) (sorting d entries).
- mkdir(path: str)
-
Traverse each component.
-
If directory doesn’t exist, create new Node().
-
Time: O(L).
- addContentToFile(path: str, content: str)
-
Traverse to parent directory.
-
If file doesn’t exist, create Node(is_file=True).
-
Append content to file’s content buffer.
-
Time: O(L + len(content)).
- readContentFromFile(path: str) -> str
-
Traverse directly to the node.
-
Return node.content.
-
Time: O(L + k) where k = content length.
3. Code Walkthrough
class FileSystem:
class Node:
def __init__(self, is_file=False):
self.is_file = is_file
self.content = "" # for files
self.children = {} # for directories
def __init__(self):
self.root = self.Node()
def _traverse(self, path: str) -> 'Node':
node = self.root
if path == "/":
return node
parts = [p for p in path.split("/") if p]
for p in parts:
node = node.children[p]
return node
def ls(self, path: str):
node = self._traverse(path)
if node.is_file:
return [path.split("/")[-1]]
return sorted(node.children.keys())
def mkdir(self, path: str):
node = self.root
for p in [x for x in path.split("/") if x]:
if p not in node.children:
node.children[p] = self.Node()
node = node.children[p]
def addContentToFile(self, path: str, content: str):
parts = [p for p in path.split("/") if p]
node = self.root
for p in parts[:-1]:
if p not in node.children:
node.children[p] = self.Node()
node = node.children[p]
file_name = parts[-1]
if file_name not in node.children:
node.children[file_name] = self.Node(is_file=True)
node.children[file_name].content += content
# Another case
# for p in parts:
# if p not in node.children:
# node.children[p] = Node()
# node = node.children[p]
# node.is_file = True
# node.content += content
def readContentFromFile(self, path: str):
node = self._traverse(path)
return node.content