Skip to main content
Talentd

Design File System - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringDesignTrie12 min readAsked at: Amazon, Microsoft, Meta +9
Practice this problem

Problem Statement

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 <= 100
  • 1 <= value <= 109
  • Each path is valid and consists of lowercase English letters and '/'.
  • At most 104 calls in total will be made to createPath and get.

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 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map Path RegistryO(L)O(N)Simple implementation when only create and lookup operations are required
Trie-Based File SystemO(L)O(N)Best choice for hierarchical paths or when future features like directory traversal may be added

Video Solution

1166 Design File System • Kelvin Chandra • 6,506 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Design File System with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters