⚡Flashcard Drill➔
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

  1. 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).
  2. Walking a path means splitting on / and descending, ignoring empty segments from the leading slash.
  3. ls on a directory returns its keys sorted; on a file it returns a single-element list with the file name.
  4. addContentToFile appends, 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's ls returns 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: ls on 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.
🎯 Drill This Card Now➔

🧩 Related Tries Problems