We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design File System

Number: 1125

Difficulty: Medium

Paid? Yes

Companies: DoorDash, Amazon, Capital One, Microsoft, Atlassian, Oracle, Coinbase, Airbnb

Problem Description

Design a file system that supports creating new paths associated with specific integer values and retrieving the value of a given path. Each path is a string that starts with "/" and contains one or more lowercase English letters for each folder. The creation of a new path fails if the path already exists or if its immediate parent does not exist.

Key Insights

  • Use a data structure (like a hash map) to store paths and associated values.
  • To create a new path, check that the path does not already exist.
  • Ensure the immediate parent path exists before creation.
  • When retrieving a value, simply look it up in the storage structure.
  • Splitting the path by "/" allows easy identification of the parent.

Space and Time Complexity

Time Complexity:

  • createPath: O(n) per call where n is the number of segments in the path (to process and validate parent path).
  • get: O(1) per call if using a hash map. Space Complexity: O(m * L) where m is the number of paths stored and L is the average length of a path.

Solution

The solution uses a hash map (dictionary) to store file paths along with their associated values. For the createPath method, the algorithm:

  1. Checks if the path already exists.
  2. Extracts the parent path by removing the last segment.
  3. Validates the existence of the parent path.
  4. Inserts the new path with its corresponding value if validation passes. For the get method, the algorithm simply returns the stored value if the path exists; otherwise, it returns -1. This approach ensures efficient lookup and validation using string manipulation and hash map operations.

Code Solutions

class FileSystem:
    def __init__(self):
        # Initialize hash map to store paths and their values.
        self.paths = {}

    def createPath(self, path: str, value: int) -> bool:
        # Check if the path already exists.
        if path in self.paths:
            return False
        
        # Find the index of the last '/' to get the parent path.
        last_slash = path.rfind('/')
        # If last_slash is 0, then parent is root level, which is invalid because "" is not a valid path.
        if last_slash == 0:
            parent = ""
        else:
            parent = path[:last_slash]
        
        # For non-root paths, the parent must exist.
        if parent and parent not in self.paths:
            return False
        
        # Store the new path with its value.
        self.paths[path] = value
        return True

    def get(self, path: str) -> int:
        # Return the value associated with the path, or -1 if it doesn't exist.
        return self.paths.get(path, -1)

# Example usage:
# fs = FileSystem()
# print(fs.createPath("/a", 1))  # True
# print(fs.get("/a"))            # 1
← Back to All Questions