1166. Design File System
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, returningtrue
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 returnfalse
. -
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 valuev
set to-1
by default, indicating that this node does not have an associated value unless explicitly set. Each node also has achildren
dictionary that will hold references to its child nodes. -
insert(self, w: str, v: int) -> bool
: Attempts to insert a pathw
with the associated valuev
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 returnsFalse
, 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 returnsFalse
. If it doesn't exist, it creates a new Trie node with the given valuev
and returnsTrue
. -
search(self, w: str) -> int
: Looks for the pathw
in the Trie and returns its associated value. Similar toinsert
, 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 theFileSystem
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 theinsert
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 thesearch
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 EvaluatorExample 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 value1
. 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 value1
. This operation returnsTrue
. -
Next, we call
createPath
with the path"/a/b"
and the value2
. The Trie is traversed, and since the path"/a"
exists, the new nodeb
with value2
is created as a child of the nodea
. The operation returnsTrue
as the path is successfully created. -
We now attempt to create the path
"/a/b/c"
with the value3
. The system traverses the Trie - it finds"/a"
and"/a/b"
, so it creates a new nodec
with value3
under the nodeb
. This operation also returnsTrue
. -
The
get
method is invoked with the path"/a/b"
. The Trie is searched, and the node representing"/a/b"
is found, returning the value2
. -
Now we try to create the path
"/a/b/c"
again, but this time with a value4
. However, since the path"/a/b/c"
already exists, thecreatePath
operation must returnFalse
. -
Calling
get
with the path"/a/b/c"
will return the value3
, 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 stringw
. The number of operations is proportional to the number of components in the path, let's denote the number of components in the path asn
. Thus, the time complexity for traversing isO(n)
. - Checking and inserting into the
children
dictionary isO(1)
assuming hash table average case for insertion and search. - Therefore, the overall time complexity for the
insert
method isO(n)
.
search
method (get):
- Similar to
insert
,search
also traverses the trie according to the components in the path obtained after splitting the input stringw
. This operation is alsoO(n)
wheren
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 isO(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 beO(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.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.