You are asked to design a file system that allows you to create new paths and associate them with different values.
The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string "" and "/" are not.
Implement the FileSystem class:
bool createPath(string path, int value) Creates a new path and associates a value to it if possible and returns true. Returns false if the path already exists or its parent path doesn't exist.int get(string path) Returns the value associated with path or returns -1 if the path doesn't exist.
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 <= 1001 <= value <= 109path is valid and consists of lowercase English letters and '/'.104 calls in total will be made to createPath and get.Problem Overview: Design a simple file system that supports createPath(path, value) and get(path). A path can only be created if its parent directory already exists, and each path stores an integer value. The main challenge is validating parent paths efficiently while supporting fast lookups.
Approach 1: Hash Map Path Registry (O(L) time, O(N) space)
The simplest design stores every full path in a hash table. When creating a new path, split the string to find its parent path (everything before the last /). If the parent does not exist in the map, creation fails. Otherwise insert the new path with its value. The get operation becomes a direct hash lookup. Each operation takes O(L) time where L is the path length due to string processing, while storage grows to O(N) for all paths. This approach works well because paths are unique strings and lookups are constant time after hashing.
Approach 2: Trie-Based File System (O(L) time, O(N) space)
A more structured design uses a Trie where each node represents a directory segment between slashes. Split the path by / and traverse the trie one component at a time. During createPath, you ensure that all parent nodes already exist before inserting the final segment with its stored value. If the final node already exists, the operation fails. The get operation walks the trie using the same segments and returns the stored value if the node exists.
The key insight is that file paths naturally form a prefix hierarchy. A trie models this structure directly, making parent validation implicit during traversal. Each operation touches at most the number of segments in the path, giving O(L) time complexity where L is the path length. Space complexity is O(N) for all stored nodes. This design also scales better if the system later adds operations like listing directories or nested traversal.
Compared with a flat hash table, the trie avoids repeatedly storing full path strings and keeps directory relationships explicit. The idea appears frequently in system design-style interview problems where hierarchical data must be validated efficiently.
Recommended for interviews: The trie solution is the expected approach. It mirrors how real file systems organize directories and demonstrates comfort with hierarchical data structures. Mentioning the hash map approach first shows you understand the simplest workable design, but implementing the trie highlights stronger modeling and string parsing skills.
We can use a trie to store the paths, where each node stores a value, representing the value of the path corresponding to the node.
The structure of the trie node is defined as follows:
children: Child nodes, stored in a hash table, where the key is the path of the child node, and the value is the reference to the child node.v: The value of the path corresponding to the current node.The methods of the trie are defined as follows:
insert(w, v): Insert the path w and set its corresponding value to v. If the path w already exists or its parent path does not exist, return false, otherwise return true. The time complexity is O(|w|), where |w| is the length of the path w.search(w): Return the value corresponding to the path w. If the path w does not exist, return -1. The time complexity is O(|w|).The total time complexity is O(sum_{w \in W}|w|), and the total space complexity is O(sum_{w \in W}|w|), where W is the set of all inserted paths.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Path Registry | O(L) | O(N) | Simple implementation when only create and lookup operations are required |
| Trie-Based File System | O(L) | O(N) | Best choice for hierarchical paths or when future features like directory traversal may be added |
1166 Design File System • Kelvin Chandra • 6,486 views views
Watch 8 more video solutions →Practice Design File System with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor