Watch 9 video solutions for Design File System, a medium level problem involving Hash Table, String, Design. This walkthrough by Kelvin Chandra has 6,486 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |