1166. Design File System

MediumDesignTrieHash TableString

Problem Description

The challenge is to create a virtual file system that can create new paths and assign values to them. Each path follows a structure similar to file directories in operating systems, beginning with a / (e.g., /path), and can have multiple nested levels (e.g., /path/to/resource). It's important to note that paths like an empty string "" or a single slash / are not considered valid.

The task is split into two parts:

createPath: This method should create a new path with an associated value, returning true if successful. The method can only succeed if the path does not already exist and only if the "parent" path (the path minus the last component) already exists. If these conditions are not met, the method should return false.
get: This method should retrieve the value associated with an existing path. If the path does not exist, the method should return -1.

The primary challenge here is to efficiently manage the creation and retrieval of paths in a way that can quickly determine the existence of a path and its parent paths.

Intuition

To tackle this problem, we use a data structure known as a Trie (prefix tree). The Trie is a tree-like data structure that is typically used to store strings, where each node represents a character of the string, and the path from the root to a node represents the prefix of the string.

In the context of our file system:

Each node in the Trie represents a segment of the path (i.e., the string between two slashes /segment/).
The root node represents the starting point (/) of the file system.
Each complete path from the root to a leaf node represents a full path in the file system, where leaf nodes are paths that have an associated value.

For createPath, we check if the entire path, except the last segment, exists and if the last segment does not exist. If so, we can create the last segment and link it to its parent with the given value.

For get, we simply traverse the Trie starting from the root, following the segments of the path. If at any point the segment doesn't exist, we know the path doesn't exist. If we successfully reach the end of the path, we return the associated value.

The solution code effectively implements this Trie structure with a Trie class that has insert and search methods, which correspond to the createPath and get methods of the file system, encapsulating the logic required for these operations within a clean interface.

Learn more about Trie patterns.

Solution Approach

The implemented solution involves creating a custom [Trie](/problems/trie_intro) class that serves as the backbone of the FileSystem class. The Trie is designed specifically to handle file paths and their associated values. Let us walk through the implementation of each class and the key methods they provide.

Trie Class

The [Trie](/problems/trie_intro) class has two main methods: insert and search, alongside an __init__ method. Here's how they work:

__init__(self, v: int = -1): Initializes a new Trie node with the value v set to -1 by default, indicating that this node does not have an associated value unless explicitly set. Each node also has a children dictionary that will hold references to its child nodes.
insert(self, w: str, v: int) -> bool: Attempts to insert a path w with the associated value v into the Trie. This method splits the input path on slashes to navigate through the nodes. For each segment (except the last one), it checks if the segment exists as a child. If any segment is missing before the final part of the path, it returns False, indicating that the parent path doesn't exist and therefore a new path cannot be created. If the last segment already exists as a child, it also returns False. If it doesn't exist, it creates a new Trie node with the given value v and returns True.
search(self, w: str) -> int: Looks for the path w in the Trie and returns its associated value. Similar to insert, it splits the input path and traverses the Trie. If at any point a segment is not found among the children of the current node, it returns -1, indicating that the path does not exist. If the path is found successfully, it returns the value of the final node.

FileSystem Class

The FileSystem class encapsulates a [Trie](/problems/trie_intro) instance, and it provides the two methods required by the problem statement:

__init__(self): Initializes the FileSystem by creating a Trie instance as its root.
createPath(self, path: str, value: int) -> bool: Public interface to insert a new path with the associated value into the Trie, leveraging the insert method of the Trie instance. It passes the path and value directly to the Trie.
get(self, path: str) -> int: Public interface to retrieve the value for a path from the Trie, using the search method of the Trie instance.

This approach ensures that all path operations are efficiently handled by the Trie structure, taking advantage of its ability to quickly insert and find paths with associated values. The distinction between the FileSystem and Trie classes also helps maintain a clean separation between the file system interface and the underlying data structure that powers it.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

We'll illustrate the solution approach using a simple example. Consider the following sequence of operations on our virtual file system:

createPath("/a", 1)
createPath("/a/b", 2)
createPath("/a/b/c", 3)
get("/a/b")
createPath("/a/b/c", 4)
get("/a/b/c")
get("/d")

Let's walk through each operation step by step.

The createPath method is called with the path "/a" and the value 1. Since the root exists and "/a" is a direct child of the root, the path "/a" is added successfully to the Trie, which now contains the path "/a" with a value 1. This operation returns True.
Next, we call createPath with the path "/a/b" and the value 2. The Trie is traversed, and since the path "/a" exists, the new node b with value 2 is created as a child of the node a. The operation returns True as the path is successfully created.
We now attempt to create the path "/a/b/c" with the value 3. The system traverses the Trie - it finds "/a" and "/a/b", so it creates a new node c with value 3 under the node b. This operation also returns True.
The get method is invoked with the path "/a/b". The Trie is searched, and the node representing "/a/b" is found, returning the value 2.
Now we try to create the path "/a/b/c" again, but this time with a value 4. However, since the path "/a/b/c" already exists, the createPath operation must return False.
Calling get with the path "/a/b/c" will return the value 3, as assigned during its creation in step 3.
Finally, attempting to get the value for the path "/d" will return -1, as no such path exists in the Trie.

This series of operations showcases how the Trie class effectively handles the insertion and retrieval of paths within the virtual file system. The FileSystem class acts as the interface, using the Trie instance's insert and search methods to facilitate the createPath and get functionalities described in the problem statement.

Solution Implementation

1class TrieNode:
2    def __init__(self, value: int = -1):
3        self.children = {}  # Initialize an empty dictionary for children
4        self.value = value  # Store the value associated with the node
5
6    def insert(self, path: str, value: int) -> bool:
7        """
8        Insert a path with its value into the trie.
9        If path already exists or the parent doesn't exist, return False. Otherwise, insert and return True.
10        """
11        node = self
12        # Split the path by '/' and iterate over the parts, excluding the first empty string and the last part
13        parts = path.split("/")[1:-1]
14        for part in parts:
15            if part not in node.children:
16                # If a part of the path doesn't exist, insertion is not possible
17                return False
18            node = node.children[part]
19        if parts[-1] in node.children:
20            # If the last part of the path already exists, insertion is not possible
21            return False
22        # Otherwise, create the node for the new path and assign the value
23        node.children[parts[-1]] = TrieNode(value)
24        return True
25
26    def search(self, path: str) -> int:
27        """
28        Search for a path and return its associated value.
29        If the path doesn't exist, return -1.
30        """
31        node = self
32        # Split the path by '/' and iterate over the parts, excluding the first empty string
33        for part in path.split("/")[1:]:
34            if part not in node.children:
35                # If a part of the path doesn't exist, the search is unsuccessful
36                return -1
37            node = node.children[part]
38        return node.value  # Return the value of the final node
39
40
41class FileSystem:
42    def __init__(self):
43        self.root = TrieNode()  # Initialize the file system with a root trie node
44
45    def createPath(self, path: str, value: int) -> bool:
46        """
47        Public method to create a path with its value in the file system.
48        Returns True if the path was successfully created, False otherwise.
49        """
50        return self.root.insert(path, value)
51
52    def get(self, path: str) -> int:
53        """
54        Public method to get the value of a path in the file system.
55        Returns the value if the path exists, -1 otherwise.
56        """
57        return self.root.search(path)
58
59# Example usage:
60# fs = FileSystem()
61# creation_success = fs.createPath("/a/b/c", 5)
62# value = fs.get("/a/b/c")
63

1import java.util.HashMap;
2import java.util.Map;
3
4class TrieNode {
5    // Map to hold child nodes.
6    Map<String, TrieNode> children = new HashMap<>();
7    // Variable to hold the value associated with a path.
8    int value;
9
10    // Constructor for the TrieNode.
11    TrieNode(int value) {
12        this.value = value;
13    }
14
15    // Method to insert a path with its value into the trie.
16    boolean insert(String path, int value) {
17        TrieNode node = this;
18        // Split the path by "/" to get individual parts.
19        String[] parts = path.split("/");
20        // Iterate over parts of the path (excluding the first empty part and the last part).
21        for (int i = 1; i < parts.length - 1; ++i) {
22            String part = parts[i];
23            // If the current part is not in the children map, the path cannot be created.
24            if (!node.children.containsKey(part)) {
25                return false;
26            }
27            // Move to the corresponding child node.
28            node = node.children.get(part);
29        }
30        // Check if the last part of the path already exists, which means the path cannot be created.
31        if (node.children.containsKey(parts[parts.length - 1])) {
32            return false;
33        }
34        // Insert the new TrieNode with the given value into the children map.
35        node.children.put(parts[parts.length - 1], new TrieNode(value));
36        return true;
37    }
38
39    // Method to search for the value associated with a given path.
40    int search(String path) {
41        TrieNode node = this;
42        // Split the path by "/" to get individual parts.
43        String[] parts = path.split("/");
44        // Iterate over the parts of the path.
45        for (int i = 1; i < parts.length; ++i) {
46            String part = parts[i];
47            // If the current part is not in the children map, return -1 indicating the path does not exist.
48            if (!node.children.containsKey(part)) {
49                return -1;
50            }
51            // Move to the corresponding child node.
52            node = node.children.get(part);
53        }
54        // Return the value associated with the path.
55        return node.value;
56    }
57}
58
59class FileSystem {
60    private TrieNode root = new TrieNode(-1);
61
62    // Constructor for the FileSystem class.
63    public FileSystem() {
64    }
65
66    // Method to create a path in the file system with the given value.
67    public boolean createPath(String path, int value) {
68        return root.insert(path, value);
69    }
70
71    // Method to get the value of a given path in the file system.
72    public int get(String path) {
73        return root.search(path);
74    }
75}
76
77// Usage example of the FileSystem class.
78/*
79FileSystem obj = new FileSystem();
80boolean param_1 = obj.createPath("/a/b/c", 10);
81int param_2 = obj.get("/a/b/c");
82*/
83

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <sstream>
5
6// Class representing a node in the Trie
7class TrieNode {
8public:
9    std::unordered_map<std::string, TrieNode*> children; // Children of the current node
10    int value; // Value associated with the node
11
12    // Constructor initializing TrieNode with a given value
13    TrieNode(int v) : value(v) {}
14
15    // Inserts a path with a value into the Trie
16    bool insert(const std::string& w, int v) {
17        TrieNode* node = this; // Starting at the root
18        std::vector<std::string> parts = split(w, '/'); // Split the path
19        // Traverse the parts of the path excluding the first and last
20        for (size_t i = 1; i < parts.size() - 1; ++i) {
21            const std::string& p = parts[i];
22            // If the part is not found in children, return false (cannot insert)
23            if (!node->children.count(p)) {
24                return false;
25            }
26            node = node->children[p]; // Move to the next part
27        }
28        // If the last part is already in children, return false (path exists)
29        if (node->children.count(parts.back())) {
30            return false;
31        }
32        // Create a new node for the last part with the given value
33        node->children[parts.back()] = new TrieNode(v);
34        return true; // Successfully inserted
35    }
36
37    // Searches for a value by the given path in the Trie
38    int search(const std::string& w) {
39        TrieNode* node = this; // Starting at the root
40        std::vector<std::string> parts = split(w, '/'); // Split the path
41        // Traverse the parts of the path
42        for (size_t i = 1; i < parts.size(); ++i) {
43            const std::string& p = parts[i];
44            // If the part is not found in children, return -1 (path does not exist)
45            if (!node->children.count(p)) {
46                return -1;
47            }
48            node = node->children[p]; // Move to the next part
49        }
50        // Return the value of the found node
51        return node->value;
52    }
53
54private:
55    // Helper method to split a string by a delimiter into a vector of strings.
56    std::vector<std::string> split(const std::string& s, char delim) {
57        std::stringstream ss(s);
58        std::string item;
59        std::vector<std::string> res;
60        while (std::getline(ss, item, delim)) {
61            if (!item.empty()) { // Ignore empty strings from multiple '/' in a row
62                res.push_back(item);
63            }
64        }
65        return res;
66    }
67};
68
69// Class representing a file system interface
70class FileSystem {
71public:
72    // Constructor initializing FileSystem with a fake root node with value -1
73    FileSystem() : trieRoot(new TrieNode(-1)) {}
74
75    // Creates a path in the trie with the given value
76    bool createPath(const std::string& path, int value) {
77        return trieRoot->insert(path, value);
78    }
79
80    // Gets the value of the node associated with the path
81    int get(const std::string& path) {
82        return trieRoot->search(path);
83    }
84
85private:
86    TrieNode* trieRoot; // The root of the Trie
87};
88
89/* Usage example:
90FileSystem* obj = new FileSystem();
91bool isCreated = obj->createPath("/a", 5); // true if path was created successfully
92int value = obj->get("/a"); // Should be 5 if "/a" was created successfully, or -1 if the path does not exist
93delete obj; // Don't forget to deallocate the allocated memory
94*/
95

1// The TrieNode represents a node in our Trie structure.
2interface TrieNode {
3    children: Map<string, TrieNode>;
4    value: number;
5}
6
7// Creates and initializes a new Trie node.
8function createTrieNode(value: number): TrieNode {
9    return {
10        children: new Map<string, TrieNode>(),
11        value: value,
12    };
13}
14
15// Global Trie root node.
16const rootTrieNode: TrieNode = createTrieNode(-1);
17
18// Inserts a path with a value into the Trie.
19// Returns true if inserted successfully, false if the path already exists.
20function insertIntoTrie(w: string, v: number): boolean {
21    let node: TrieNode = rootTrieNode;
22    const parts = w.split('/').slice(1);
23    for (let i = 0; i < parts.length - 1; ++i) {
24        const part = parts[i];
25        if (!node.children.has(part)) {
26            return false;
27        }
28        node = node.children.get(part)!;
29    }
30    if (node.children.has(parts[parts.length - 1])) {
31        return false;
32    }
33    node.children.set(parts[parts.length - 1], createTrieNode(v));
34    return true;
35}
36
37// Searches for a path in the Trie and returns its associated value.
38// Returns -1 if the path does not exist.
39function searchInTrie(w: string): number {
40    let node: TrieNode = rootTrieNode;
41    const parts = w.split('/').slice(1);
42    for (const part of parts) {
43        if (!node.children.has(part)) {
44            return -1;
45        }
46        node = node.children.get(part)!;
47    }
48    return node.value;
49}
50
51// Creates a new path in the file system with the given value.
52// Returns true if the path is created successfully, false otherwise.
53function createPath(path: string, value: number): boolean {
54    return insertIntoTrie(path, value);
55}
56
57// Retrieves the value associated with the given path in the file system.
58// Returns -1 if the path does not exist.
59function get(path: string): number {
60    return searchInTrie(path);
61}
62
63// Example usage:
64// var createdSuccessfully = createPath("/a/b/c", 10);
65// var value = get("/a/b/c");
66

Time and Space Complexity

Time Complexity:

`insert` method (createPath):

The insert method traverses the trie according to the components in the path, which are obtained by splitting the input string w. The number of operations is proportional to the number of components in the path, let's denote the number of components in the path as n. Thus, the time complexity for traversing is O(n).
Checking and inserting into the children dictionary is O(1) assuming hash table average case for insertion and search.
Therefore, the overall time complexity for the insert method is O(n).

`search` method (get):

Similar to insert, search also traverses the trie according to the components in the path obtained after splitting the input string w. This operation is also O(n) where n is the number of components in the path.
Accessing each of the child nodes in the traversal is constant time O(1).
Hence, the overall time complexity for the search method is O(n).

Space Complexity:

The space complexity is dependent on the number of unique paths inserted into the file system.
Each unique path component can potentially be a node in the trie. If we denote m as the total number of unique path components across all paths, the space complexity would be O(m).
Each node stores a dictionary of children, which can be variable in size but is bounded by the number of unique path components that follow the current one. However, this does not change the overall space complexity, which remains O(m).

Overall, the time complexity for the insert and search operations is O(n), where n is the number of components in a given path, and the space complexity is O(m) where m is the total number of unique path components in all paths stored in the trie.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems