Design a file system that allows us to create new paths and associate them with different values. A path has one or more concatenated strings of the form / followed by one or more lowercase English letters. For example, valid paths include "/educative" and "/educative/problems", while an empty string "" and "/" are not valid paths.
Implement the FileSystem class with the following functions:
bool createPath(string path, int value): This function creates a new path, associates a value to it if possible, and returns TRUE. It returns FALSE if the path already exists or its parent path doesn’t exist.
int get(string path): This function returns the value associated with the path or returns -
Constraints:
The total number of calls to the two functions are
path.length
A file system is a tree-like structure where directories and files are nodes, and paths define their relationships. This structure inherently has a hierarchical, prefix-based nature. We can use a trie to replicate this hierarchy in our file system. Let’s explore a couple of use cases where using a trie is advantageous:
When creating or searching for a path, we must validate the entire path step by step, ensuring each directory exists before adding or retrieving the next component. A Trie naturally supports this step-by-step validation as we traverse through its nodes.
Many files and directories may share common prefixes, such as /a/b/c and /a/b/d. When creating such paths, a trie stores these common prefixes only once. For instance, the prefix /a/b/ is stored a single time, with different branches handling the unique parts (e.g., c and d). This approach reduces redundancy and conserves memory. Additionally, when searching for any path, each node in the trie represents a part of the path (a directory or file name), and the full path is formed by traversing from the root to the desired node.
Let’s look at how to implement the file ...
Design a file system that allows us to create new paths and associate them with different values. A path has one or more concatenated strings of the form / followed by one or more lowercase English letters. For example, valid paths include "/educative" and "/educative/problems", while an empty string "" and "/" are not valid paths.
Implement the FileSystem class with the following functions:
bool createPath(string path, int value): This function creates a new path, associates a value to it if possible, and returns TRUE. It returns FALSE if the path already exists or its parent path doesn’t exist.
int get(string path): This function returns the value associated with the path or returns -
Constraints:
The total number of calls to the two functions are
path.length
A file system is a tree-like structure where directories and files are nodes, and paths define their relationships. This structure inherently has a hierarchical, prefix-based nature. We can use a trie to replicate this hierarchy in our file system. Let’s explore a couple of use cases where using a trie is advantageous:
When creating or searching for a path, we must validate the entire path step by step, ensuring each directory exists before adding or retrieving the next component. A Trie naturally supports this step-by-step validation as we traverse through its nodes.
Many files and directories may share common prefixes, such as /a/b/c and /a/b/d. When creating such paths, a trie stores these common prefixes only once. For instance, the prefix /a/b/ is stored a single time, with different branches handling the unique parts (e.g., c and d). This approach reduces redundancy and conserves memory. Additionally, when searching for any path, each node in the trie represents a part of the path (a directory or file name), and the full path is formed by traversing from the root to the desired node.
Let’s look at how to implement the file ...