Design File System

Problem Statement

In this task, you are required to design a filesystem structure within a class named FileSystem. This filesystem allows the user to create new paths and associate specific values with each path. The paths should follow a specific format: they are strings composed of one or more sections prefixed by a forward slash (/) and followed by lowercase English letters. Valid examples of such paths include /leetcode and /leetcode/problems, while "" (an empty string) and "/" alone are considered invalid.

The FileSystem class should support two primary operations:

1. createPath(string path, int value): This method should create a new path and associate an integer value with it. The function returns true if the path is successfully created and associated with the specified value. It will return false if the path already exists or if the intended parent path of the new path does not exist. This ensures that each new path created has a valid hierarchical structure.

2. get(string path): This function should return the integer value associated with the provided path. If the path does not exist, this function returns -1.

The class design should efficiently support these operations adhering to the constraints and ensure that the operations on the path and value associations are performed correctly.

Examples

Example 1

Input:

["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]

Output:

[null,true,1]

Explanation:

FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

Example 2

Input:

["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]

Output:

[null,true,true,2,false,-1]

Explanation:

FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/leet", 1); // return true
fileSystem.createPath("/leet/code", 2); // return true
fileSystem.get("/leet/code"); // return 2
fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist.
fileSystem.get("/c"); // return -1 because this path doesn't exist.

Constraints

• 2 <= path.length <= 100
• 1 <= value <= 109
• Each path is valid and consists of lowercase English letters and '/'.
• At most 104 calls in total will be made to createPath and get.

Approach and Intuition

Given the examples and the problem constraints, consider how you would implement the filesystem class utilizing data structures like hashmaps for efficient lookups and inserts.

• Each path can be visualized as a node in a tree structure where every unique path segment prefixed by / represents a child in the hierarchical structure of files and directories.
• For efficient operations:
  • You should use a hashmap (or dictionary in Python) to store each path as a key and its associated value as the map's value.
  • For efficient checking of path existence and the validation of parent paths, each path can be checked against keys in the hashmap.

Creating a Path (createPath)

1. Firstly, extract the parent path from the given path string and check if this parent path exists in the hashmap (except for the root, /).
2. If the parent exists and the given path does not exist in the hashmap, you can create the path by adding it to the hashmap with the associated value, and return true.
3. If the path already exists or the parent path does not exist, return false.

Fetching a Path Value (get)

1. Check if the requested path exists in the hashmap.
2. If it exists, return the associated value.
3. If it does not exist, return -1.

The given constraints ensure the solutions are scalable, limiting path length and the number of operations, making a dictionary-based approach suitable for managing the createPath and get functions without performance concerns.

Solutions

class FileSystem {
    
    class Node {
            
        String nodeName;
        int value = -1;
        Map<String, Node> children = new HashMap<>();
            
        Node (String nodeName) {
            this.nodeName = nodeName;
        }
    }
        
    Node rootNode;
        
    public FileSystem() {
        this.rootNode = new Node("");
    }
        
    public boolean createPath(String path, int value) {
            
        String[] parts = path.split("/");
            
        Node currentNode = rootNode;
            
        for (int i = 1; i < parts.length; i++) {
                
            String part = parts[i];
                
            if (!currentNode.children.containsKey(part)) {
                    
                if (i == parts.length - 1) {
                    currentNode.children.put(part, new Node(part));
                } else {
                    return false;
                }    
            }
                
            currentNode = currentNode.children.get(part);
        }
            
        if (currentNode.value != -1) {
            return false;
        }
            
        currentNode.value = value;
        return true;
    }
        
    public int get(String path) {
            
        String[] parts = path.split("/");
            
        Node currentNode = rootNode;
            
        for (int i = 1; i < parts.length; i++) {
                
            String part = parts[i];
                
            if (!currentNode.children.containsKey(part)) {
                return -1;   
            }
                
            currentNode = currentNode.children.get(part);
        }
            
        return currentNode.value;
    }
}