Leetcode 1166. Design File System

Problem

Design and implement an in-memory directory system that stores integer values at specific path locations. Your system should support two operations:

1. createPath(path, value): Creates a new path in the directory system and associates it with the given integer value. This operation should return true if the path was created successfully, or false if the operation fails.
2. get(path): Retrieves the value associated with the given path. Returns the stored integer value if the path exists, or -1 if the path doesn't exist.

The key challenge is implementing the constraint that a path can only be created if its immediate parent path already exists in the system.

Requirements

1. The createPath operation must fail (return false) if the immediate parent directory doesn't exist
2. The createPath operation must fail (return false) if the path already exists in the system
3. The get operation must return -1 for paths that haven't been created
4. All paths follow the Unix-style format with forward slashes (e.g., /folder/subfolder/file)
5. Path strings are guaranteed to be valid (no trailing slashes except for root, no consecutive slashes)

Constraints

• 1 <= path.length <= 100
• 1 <= value <= 10^9
• Path strings will only contain lowercase English letters, digits, and forward slashes
• At most 10^4 calls will be made to createPath and get combined
• The root path / is implicitly available and doesn't need to be created

Examples

Example 1:

` Operations: createPath("/documents", 100) → true createPath("/documents/reports", 200) → true get("/documents") → 100 get("/documents/reports") → 200

Explanation: We first create "/documents" which succeeds because root exists. Then we create "/documents/reports" which succeeds because "/documents" exists. Both get operations return the stored values. `

Example 2:

` Operations: createPath("/a/b/c", 1) → false createPath("/a", 2) → true createPath("/a/b", 3) → true createPath("/a/b/c", 4) → true get("/a/b/c") → 4

Explanation: The first createPath fails because "/a/b" doesn't exist. After creating "/a" and then "/a/b", we can successfully create "/a/b/c". `

Example 3:

` Operations: createPath("/home", 50) → true createPath("/home", 75) → false get("/home") → 50

Explanation: The second createPath fails because "/home" already exists. The original value remains unchanged. `

Hint 1: Data Structure Choice Consider using a hash map (dictionary) to store paths and their associated values. This allows O(1) lookup time for checking if a path exists and retrieving values.

Hint 2: Parent Path Extraction To check if the parent path exists, you need to extract it from the given path. You can find the last occurrence of "/" in the path string and take everything before it. Remember that the root path "/" is always considered to exist.

Hint 3: Edge Cases Pay special attention to paths at the root level (like "/documents"). These should succeed if the path doesn't already exist, since their parent is the implicit root "/".

Full Solution ` class DirectorySystem: def init(self): # Dictionary to store path -> value mappings self.paths = {}

def createPath(self, path: str, value: int) -> bool:
    # Check if path already exists
    if path in self.paths:
        return False
    
    # Find the parent path by getting everything before the last "/"
    last_slash_index = path.rfind('/')
    parent_path = path[:last_slash_index]
    
    # If parent is empty string, it means this is a root-level path
    # (e.g., "/documents"). Root is implicitly available.
    # Otherwise, check if parent exists in our system
    if parent_path != "" and parent_path not in self.paths:
        return False
    
    # All checks passed - create the path
    self.paths[path] = value
    return True

def get(self, path: str) -> int:
    # Return the value if path exists, otherwise -1
    return self.paths.get(path, -1)

`

Explanation:

The solution uses a hash map to store the mapping between paths and their integer values.

For createPath:

1. First, we check if the path already exists. If it does, we return false immediately.
2. Next, we need to verify that the parent path exists. We extract the parent by finding the last "/" in the path and taking everything before it.
3. Special case: If the parent path is an empty string, it means we're creating a root-level path (like "/folder"). This is always allowed since the root "/" is implicit.
4. For all other cases, we check if the parent path exists in our hash map. If it doesn't, we return false.
5. If all checks pass, we store the path-value pair and return true.

For get: We simply look up the path in our hash map and return the associated value, or -1 if the path doesn't exist.

Time Complexity:

• createPath: O(n) where n is the length of the path string (due to the rfind operation)
• get: O(1) average case for hash map lookup

Space Complexity: O(m × n) where m is the number of paths stored and n is the average length of path strings.