Leetcode 1166. Design File System

Problem Explanation:

In this problem, we are asked to design a file system that supports two operations:

1. creating a new path and associating a value to it,
2. getting the value associated with a specific path.

To clarify the concept, here is an explanation with an example:

createPath(path, value): Creates a new path and associates a value to it if the path does not already exist and has a valid parent path; otherwise, it returns False. For instance, if we have a path "/a" and we want to create a new path "/a/b" with a value 2, the operation will be successful and return True, because "/a/b" does not exist and its parent "/a" exists. But if we want to create a path "/c/d" when there is no parent path "/c", it will return False.

get(path): Returns the value associated with a path or -1 if the path does not exist. For instance, if we have a path "/a/b" with a value 2 and we call get("/a/b"), it will return 2. But if we call get("/a/c"), it will return -1 because this path does not exist.

Solution Approach:

The solution uses a Trie data structure. Trie is an efficient information retrieval data structure. Each node of the Trie is a symbol associated with a value, and its children are symbols that follow the parent in the paths. The root node is a special case that has a symbol of an empty string and a value of 0 (since any value here is meaningless). By using a Trie, we can check the existence of a path or its parent path in O(M) time where M is the size of the path.

Using a shared_ptr for the TrieNode is for the memory management convenience, since we do not need to delete a node explicitly when it is not used anymore.

In the "createPath" function, it separates the path into subpaths and tries to create a new node for the last subpath. If its parent node does not exist or the path itself already exists, it will return false.

In the "get" function, it travels through the Trie and returns the value of the corresponding node if exists.

Here is a walk-through to demonstrate the process:

If we call createPath("/a", 1), it will create a new node "a" at the root and set its value to 1. Then if we call createPath("/a/b", 2), it will create a new node "b" as a child of node "a" and set its value to 2. If we call createPath("/a/b", 3) again, it will return False since the path "/a/b" already exists. If we call get("/a/b"), it will return 2, as node "b" has a value of 2. If we call get("/a/c"), it will return -1 since node "c" under "a" does not exist.Solution in Python:

1
2python
3class TrieNode:
4    def __init__(self):
5        self.value = None
6        self.children = {}
7
8class FileSystem:
9    def __init__(self):
10        self.root = TrieNode()
11
12    def createPath(self, path: str, value: int) -> bool:
13        node = self.root
14        dirs = path.split("/")[1:]
15        
16        for i in range(len(dirs) - 1):
17            if dirs[i] not in node.children:
18                return False
19            node = node.children[dirs[i]]
20        
21        if dirs[-1] in node.children:
22            return False
23        else:
24            node.children[dirs[-1]] = TrieNode()
25            node.children[dirs[-1]].value = value
26            return True
27
28    def get(self, path: str) -> int:
29        node = self.root
30        dirs = path.split("/")[1:]
31        
32        for dir in dirs:
33            if dir not in node.children:
34                return -1
35            node = node.children[dir]
36        
37        return node.value

Solution in JavaScript:

1
2javascript
3class TrieNode {
4    constructor() {
5        this.value = null;
6        this.children = {};
7    }
8}
9
10class FileSystem {
11    constructor() {
12        this.root = new TrieNode();
13    }
14
15    createPath(path, value) {
16        let node = this.root;
17        const dirs = path.split("/").slice(1);
18        
19        for (let i = 0; i < dirs.length - 1; i++) {
20            if (!(dirs[i] in node.children)) {
21                return false;
22            }
23            node = node.children[dirs[i]];
24        }
25        
26        if (dirs[dirs.length - 1] in node.children) {
27            return false;
28        } else {
29            node.children[dirs[dirs.length - 1]] = new TrieNode();
30            node.children[dirs[dirs.length - 1]].value = value;
31            return true;
32        }
33    }
34
35    get(path) {
36        let node = this.root;
37        const dirs = path.split("/").slice(1);
38        
39        for (let dir of dirs) {
40            if (!(dir in node.children)) {
41                return -1;
42            }
43            node = node.children[dir];
44        }
45        
46        return node.value;
47    }
48}

Solution in Java:

1
2java
3import java.util.*;
4
5class TrieNode {
6    Integer value;
7    Map<String, TrieNode> children = new TreeMap<>();
8
9    public TrieNode() {
10    }
11}
12
13class FileSystem {
14    TrieNode root;
15
16    public FileSystem() {
17        root = new TrieNode();
18    }
19
20    public boolean createPath(String path, int value) {
21        String[] dirs = path.split("/");
22        TrieNode node = root;
23        
24        for (int i = 1; i < dirs.length - 1; i++) {
25            if (!node.children.containsKey(dirs[i])) {
26                return false;
27            }
28            node = node.children.get(dirs[i]);
29        }
30        
31        if (node.children.containsKey(dirs[dirs.length - 1])) {
32            return false;
33        } 
34        else {
35            TrieNode newNode = new TrieNode();
36            newNode.value = value;
37            node.children.put(dirs[dirs.length - 1], newNode);
38            return true;
39        }
40    }
41
42    public Integer get(String path) {
43        String[] dirs = path.split("/");
44        TrieNode node = root;
45        
46        for (int i = 1; i < dirs.length; i++) {
47            if (!node.children.containsKey(dirs[i])) {
48                return -1;
49            }
50            node = node.children.get(dirs[i]);
51        }
52        
53        return node.value;
54    }
55}

The presented code snippets are the solution to the problem using a Trie-like data structure in Python, JavaScript, and Java. The solution generally runs in O(M) time, where M is the size of the path, and uses O(N) space, where N is the total number of paths created.