⚡Flashcard Drill➔
NeetCode #481LC-1166MediumTries
← Back to All Problems

#481 · #1166 · Design File System(设计文件系统)

📌 Problem Statement & Constraints

Design a file system with createPath(path, value) (returns false if the path exists or its parent does not) and get(path) (returns the value or -1). Paths are of the form /a/b/c. Constraints: 1 <= path.length <= 100; at most 10^4 calls.

💡 Core Algorithmic Approaches

  1. Keep a dictionary from full path to value.
  2. createPath checks for existence, then verifies that the parent path exists (unless the path is a top-level one).
  3. The parent is obtained by stripping the last /-separated segment.
  4. get is a single dictionary lookup with a -1 default.

💻 Benchmark Python3 Implementation

class FileSystem:
    def __init__(self):
        self.paths = {}                    # full path -> value

    def createPath(self, path: str, value: int) -> bool:
        if not path or path in self.paths:
            return False                   # empty or already exists
        parent = path[:path.rfind("/")]    # everything before the last '/'
        if parent and parent not in self.paths:
            return False                   # the parent must already exist
        self.paths[path] = value
        return True

    def get(self, path: str) -> int:
        return self.paths.get(path, -1)    # -1 when absent

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(path length) per operation.
💾 Space Complexity
O(number of paths).

⚠️ Interview Pitfalls & Follow-ups

  • Using rfind('/') incorrectly: the parent is the prefix before the last slash, so path[:path.rfind('/')].
  • Allowing creation when the parent is missing: the problem requires the parent to exist, except for top-level paths where the prefix is empty.
  • Using a trie of segments: workable but unnecessary, since the full path is a natural key here.
  • Returning None from get: the contract requires -1.
⚡
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