Design File System solution and explanation
Google
6 more videos on this problem
1166 Design File SystemKelvin Chandra · 6:10 · 6K views
Amazon Coding Interview Question | Leetcode 1166 | Design File SystemWorkWithGoogler · 20:05 · 5K views
1166. Design File System (LeetCode)hakunamatasq · 6:13 · 2K views
1166 Design File SystemLeetcode Problems · 16:23 · 1K views
1166. Design File System - Week 3/5 Leetcode August ChallengeProgramming Live with Larry · 8:52 · 787 views
Leetcode 1166. Design File System (hash table)LetsCode · 5:52 · 677 views
1166. Design File SystemMuerde un zombie · 4:52 · 159 views
The problem
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 newpathand associates avalueto it if possible and returnstrue. Returnsfalseif the path already exists or its parent path doesn't exist.int get(string path)Returns the value associated withpathor returns-1if 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 <= 109- Each
pathis valid and consists of lowercase English letters and'/'. - At most
104calls in total will be made tocreatePathandget.
Approach overview
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.
Solution
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 pathwand set its corresponding value tov. If the pathwalready exists or its parent path does not exist, returnfalse, otherwise returntrue. The time complexity isO(|w|), where|w|is the length of the pathw.search(w): Return the value corresponding to the pathw. If the pathwdoes not exist, return-1. The time complexity isO(|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.
class Trie:
def __init__(self, v: int = -1):
self.children = {}
self.v = v
def insert(self, w: str, v: int) -> bool:
node = self
ps = w.split("/")
for p in ps[1:-1]:
if p not in node.children:
return False
node = node.children[p]
if ps[-1] in node.children:
return False
node.children[ps[-1]] = Trie(v)
return True
def search(self, w: str) -> int:
node = self
for p in w.split("/")[1:]:
if p not in node.children:
return -1
node = node.children[p]
return node.v
class FileSystem:
def __init__(self):
self.trie = Trie()
def createPath(self, path: str, value: int) -> bool:
return self.trie.insert(path, value)
def get(self, path: str) -> int:
return self.trie.search(path)
# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.createPath(path,value)
# param_2 = obj.get(path)class Trie {
Map<String, Trie> children = new HashMap<>();
int v;
Trie(int v) {
this.v = v;
}
boolean insert(String w, int v) {
Trie node = this;
var ps = w.split("/");
for (int i = 1; i < ps.length - 1; ++i) {
var p = ps[i];
if (!node.children.containsKey(p)) {
return false;
}
node = node.children.get(p);
}
if (node.children.containsKey(ps[ps.length - 1])) {
return false;
}
node.children.put(ps[ps.length - 1], new Trie(v));
return true;
}
int search(String w) {
Trie node = this;
var ps = w.split("/");
for (int i = 1; i < ps.length; ++i) {
var p = ps[i];
if (!node.children.containsKey(p)) {
return -1;
}
node = node.children.get(p);
}
return node.v;
}
}
class FileSystem {
private Trie trie = new Trie(-1);
public FileSystem() {
}
public boolean createPath(String path, int value) {
return trie.insert(path, value);
}
public int get(String path) {
return trie.search(path);
}
}
/**
* Your FileSystem object will be instantiated and called as such:
* FileSystem obj = new FileSystem();
* boolean param_1 = obj.createPath(path,value);
* int param_2 = obj.get(path);
*/class Trie {
public:
unordered_map<string, Trie*> children;
int v;
Trie(int v) {
this->v = v;
}
bool insert(string& w, int v) {
Trie* node = this;
auto ps = split(w, '/');
for (int i = 1; i < ps.size() - 1; ++i) {
auto p = ps[i];
if (!node->children.count(p)) {
return false;
}
node = node->children[p];
}
if (node->children.count(ps.back())) {
return false;
}
node->children[ps.back()] = new Trie(v);
return true;
}
int search(string& w) {
Trie* node = this;
auto ps = split(w, '/');
for (int i = 1; i < ps.size(); ++i) {
auto p = ps[i];
if (!node->children.count(p)) {
return -1;
}
node = node->children[p];
}
return node->v;
}
private:
vector<string> split(string& s, char delim) {
stringstream ss(s);
string item;
vector<string> res;
while (getline(ss, item, delim)) {
res.emplace_back(item);
}
return res;
}
};
class FileSystem {
public:
FileSystem() {
trie = new Trie(-1);
}
bool createPath(string path, int value) {
return trie->insert(path, value);
}
int get(string path) {
return trie->search(path);
}
private:
Trie* trie;
};
/**
* Your FileSystem object will be instantiated and called as such:
* FileSystem* obj = new FileSystem();
* bool param_1 = obj->createPath(path,value);
* int param_2 = obj->get(path);
*/class Trie {
children: Map<string, Trie>;
v: number;
constructor(v: number) {
this.children = new Map<string, Trie>();
this.v = v;
}
insert(w: string, v: number): boolean {
let node: Trie = this;
const ps = w.split('/').slice(1);
for (let i = 0; i < ps.length - 1; ++i) {
const p = ps[i];
if (!node.children.has(p)) {
return false;
}
node = node.children.get(p)!;
}
if (node.children.has(ps[ps.length - 1])) {
return false;
}
node.children.set(ps[ps.length - 1], new Trie(v));
return true;
}
search(w: string): number {
let node: Trie = this;
const ps = w.split('/').slice(1);
for (const p of ps) {
if (!node.children.has(p)) {
return -1;
}
node = node.children.get(p)!;
}
return node.v;
}
}
class FileSystem {
trie: Trie;
constructor() {
this.trie = new Trie(-1);
}
createPath(path: string, value: number): boolean {
return this.trie.insert(path, value);
}
get(path: string): number {
return this.trie.search(path);
}
}
/**
* Your FileSystem object will be instantiated and called as such:
* var obj = new FileSystem()
* var param_1 = obj.createPath(path,value)
* var param_2 = obj.get(path)
*/type trie struct {
children map[string]*trie
v int
}
func newTrie(v int) *trie {
return &trie{map[string]*trie{}, v}
}
func (t *trie) insert(w string, v int) bool {
node := t
ps := strings.Split(w, "/")
for _, p := range ps[1 : len(ps)-1] {
if _, ok := node.children[p]; !ok {
return false
}
node = node.children[p]
}
if _, ok := node.children[ps[len(ps)-1]]; ok {
return false
}
node.children[ps[len(ps)-1]] = newTrie(v)
return true
}
func (t *trie) search(w string) int {
node := t
ps := strings.Split(w, "/")
for _, p := range ps[1:] {
if _, ok := node.children[p]; !ok {
return -1
}
node = node.children[p]
}
return node.v
}
type FileSystem struct {
trie *trie
}
func Constructor() FileSystem {
return FileSystem{trie: newTrie(-1)}
}
func (this *FileSystem) CreatePath(path string, value int) bool {
return this.trie.insert(path, value)
}
func (this *FileSystem) Get(path string) int {
return this.trie.search(path)
}
/**
* Your FileSystem object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.CreatePath(path,value);
* param_2 := obj.Get(path);
*/Complexity analysis
| 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 |
Frequently asked questions
Is Design File System easy or hard?
The problem is rated Medium because the operations are simple but require careful path validation. Understanding hierarchical structures and implementing a trie or path-based hash map correctly is the main challenge.
How to solve Design File System in O(L)?
Split the path by '/' and process each directory segment sequentially. Using a trie or a hash map with parent validation ensures each operation scans the path only once. Each segment lookup or insertion is O(1), so the total complexity remains O(L).
Design File System Python or Java solution
In Python or Java, the common implementation defines a TrieNode class containing a map of children and a stored value. The createPath method splits the path and inserts nodes only if the parent exists, while get traverses the same segments to return the stored value.
What is the best approach for Design File System?
The trie-based design is the most common approach. Each node represents a directory segment and stores its children in a map. Path creation walks the trie and verifies that the parent exists before inserting the final node. Both createPath and get run in O(L) time where L is the path length.
What data structure is used in Design File System?
A trie is the most natural data structure because file paths form a prefix hierarchy. Each node stores child directories in a hash map and optionally a value for that path. Some implementations also use a flat hash table mapping full paths to values.
What is the time complexity of Design File System?
Both createPath and get operations run in O(L) time where L is the number of characters or segments in the path. The algorithm traverses each directory component once. Space complexity is O(N) to store all created paths or trie nodes.
Is Design File System asked at Google, Amazon, or Meta?
Design-style problems involving hierarchical structures appear frequently in interviews at companies like Google and Amazon. Variants of file system or directory design test a candidate's ability to model real systems using tries, hash maps, and careful path validation.