Code Implementation

class FileSystem:
    def __init__(self):
        self.paths = {'/': -1}

    def createPath(self, path: str, value: int) -> bool:
        if path in self.paths or len(path) == 0 or path[0] != '/':
            return False
        parent = path[:path.rfind('/')]
        if parent == '':
            parent = '/'
        if parent not in self.paths:
            return False
        self.paths[path] = value
        return True

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

class FileSystem {
public:
    unordered_map<string, int> paths;
    FileSystem() {
        paths["/"] = -1;
    }
    
    bool createPath(string path, int value) {
        if (paths.count(path) || path.empty() || path[0] != '/') return false;
        int pos = path.find_last_of('/');
        string parent = path.substr(0, pos);
        if (parent.empty()) parent = "/";
        if (!paths.count(parent)) return false;
        paths[path] = value;
        return true;
    }
    
    int get(string path) {
        if (paths.count(path)) return paths[path];
        return -1;
    }
};
      

class FileSystem {
    private Map<String, Integer> paths;

    public FileSystem() {
        paths = new HashMap<>();
        paths.put("/", -1);
    }
    
    public boolean createPath(String path, int value) {
        if (paths.containsKey(path) || path.length() == 0 || path.charAt(0) != '/') return false;
        int idx = path.lastIndexOf('/');
        String parent = path.substring(0, idx);
        if (parent.length() == 0) parent = "/";
        if (!paths.containsKey(parent)) return false;
        paths.put(path, value);
        return true;
    }
    
    public int get(String path) {
        return paths.getOrDefault(path, -1);
    }
}
      

var FileSystem = function() {
    this.paths = {'/': -1};
};

FileSystem.prototype.createPath = function(path, value) {
    if (this.paths.hasOwnProperty(path) || path.length === 0 || path[0] !== '/') return false;
    let idx = path.lastIndexOf('/');
    let parent = path.substring(0, idx);
    if (parent.length === 0) parent = '/';
    if (!this.paths.hasOwnProperty(parent)) return false;
    this.paths[path] = value;
    return true;
};

FileSystem.prototype.get = function(path) {
    if (this.paths.hasOwnProperty(path)) return this.paths[path];
    return -1;
};
      

Problem Description

The "Design File System" problem asks you to implement a simple file system that supports two operations:

• createPath(path, value): Creates a new path in the file system and associates it with the given integer value. Returns True if the path was successfully created, or False if it could not be created (e.g., if the parent path does not exist, or the path already exists).
• get(path): Returns the value associated with the given path, or -1 if the path does not exist.

The constraints are:

• Each path is a string starting with '/' (e.g., "/a", "/a/b").
• Parent directories must exist before creating a path.
• Paths are unique and cannot be reused.
• There is only one valid solution for each operation based on the current state of the file system.

Thought Process

The core challenge is to maintain a mapping of paths to their values, ensuring that:

• When creating a new path, its parent path must already exist.
• Duplicate paths cannot be created.
• Retrieving a value for a path should be efficient.

To optimize, we can use a hash map (dictionary) to store each path and its value. This allows constant-time lookups for both creation and retrieval. The main trick is to correctly identify the parent path and check for its existence before allowing a new path to be created.

Solution Approach

We design the file system using a hash map where:

• The keys are the full path strings (e.g., "/a/b").
• The values are the integers associated with each path.

1. Initialize the hash map with the root path "/" mapped to a dummy value (e.g., -1).
2. For createPath(path, value):
   • Check if the path already exists in the hash map. If so, return False.
   • Extract the parent path by finding the last '/' in the string. For example, the parent of "/a/b" is "/a".
   • If the parent path does not exist, return False.
   • Otherwise, add the new path and value to the hash map and return True.
3. For get(path):
   • Return the value from the hash map if the path exists; otherwise, return -1.

Example Walkthrough

Let's walk through a sample sequence of operations:

1. createPath("/a", 1):
   • Parent path is "/", which exists.
   • Add "/a" with value 1 to the map.
   • Returns True.
2. createPath("/a/b", 2):
   • Parent path is "/a", which exists.
   • Add "/a/b" with value 2 to the map.
   • Returns True.
3. get("/a/b"):
   • Path "/a/b" exists with value 2.
   • Returns 2.
4. createPath("/c/d", 3):
   • Parent path is "/c", which does not exist.
   • Returns False.
5. get("/c"):
   • Path "/c" does not exist.
   • Returns -1.

Each step checks for the parent and path existence, ensuring the file system's integrity.

Time and Space Complexity

Brute-force Approach:

• If using a tree and traversing from root for every operation, time complexity could be O(L) per operation, where L is the length of the path.

• Both createPath and get operations are O(1) on average, since hash map lookups and insertions are constant time.
• Space complexity is O(N), where N is the number of paths stored.

The optimized approach is efficient and scalable, handling large numbers of paths with minimal overhead.

Summary

The "Design File System" problem is elegantly solved with a hash map, mapping each unique path to its value. This approach ensures fast lookups and enforces the parent-existence constraint for new paths. By treating paths as atomic strings and using efficient data structures, we avoid unnecessary traversal and achieve optimal performance for both creation and retrieval operations.