NeetCode #485LC-588HardTriesNC Algo100
← Back to All Problems#485 · #588 · Design In-Memory File System(设计内存文件系统)
📌 Problem Statement & Constraints
Design an in-memory file system with
ls(path), mkdir(path), addContentToFile(filePath, content) and readContentFromFile(filePath). ls on a directory returns its entries sorted; on a file it returns the file name. Constraints: paths are absolute and start with /; at most 300 calls.💡 Core Algorithmic Approaches
- Model directories as nested dictionaries: a key is a name, and a value is either another dictionary (a directory) or a string (a file's content).
- Walking a path means splitting on
/and descending, ignoring empty segments from the leading slash. lson a directory returns its keys sorted; on a file it returns a single-element list with the file name.addContentToFileappends, creating the file if needed -- the problem requires append semantics.
💻 Benchmark Python3 Implementation
class FileSystem:
def __init__(self):
self.root = {} # name -> dict (dir) or str (file)
def _walk(self, path: str):
node = self.root
for part in path.split("/"):
if part:
node = node[part]
return node
def ls(self, path: str):
node = self._walk(path)
if isinstance(node, str): # it is a file
return [path.split("/")[-1]]
return sorted(node.keys()) # directory entries, sorted
def mkdir(self, path: str) -> None:
node = self.root
for part in path.split("/"):
if part:
node = node.setdefault(part, {})
def addContentToFile(self, filePath: str, content: str) -> None:
parts = [p for p in filePath.split("/") if p]
node = self.root
for p in parts[:-1]:
node = node.setdefault(p, {})
name = parts[-1]
node[name] = node.get(name, "") + content # append semantics
def readContentFromFile(self, filePath: str) -> str:
return self._walk(filePath)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(path length) per operation, plus O(k log k) for sorting a directory's entries.
💾 Space Complexity
O(total names and content).
⚠️ Interview Pitfalls & Follow-ups
- Overwriting instead of appending in
addContentToFile: the problem requires accumulating content. - Returning
sorted(node)for a file: a file'slsreturns the file name, not its content's characters. - Splitting the path without filtering empty segments: the leading
/produces an empty first element. - Using a flat map from full path to content:
lson a directory would require scanning all paths.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.