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
- Keep a dictionary from full path to value.
createPathchecks for existence, then verifies that the parent path exists (unless the path is a top-level one).- The parent is obtained by stripping the last
/-separated segment. getis 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, sopath[: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
Nonefromget: 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.