Design File System
Design File System is a medium design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (hash map of full paths), runs in O(L) per call time and O(k · L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list of created paths) up.
Problem
Build a class FileSystem that stores paths, each carrying an integer value. A path looks like /docs/reports/q1: a slash followed by one or more lowercase segments separated by slashes. FileSystem() starts empty, with only the root present.
createPath(String path, int value) creates path with the given value and returns true. It does nothing and returns false if path already exists, or if its parent path (everything before the last slash) does not exist yet. A top-level path such as /docs has the root as its parent, so it can always be created if it is new.
get(String path) returns the value stored at path, or -1 if that path was never created.
Examples
Example 1
- Input
FileSystem(), createPath("/app", 7), createPath("/app/logs", 12), get("/app/logs"), createPath("/app/logs", 30), get("/app")- Output
true, true, 12, false, 7- Why
- Both paths are created in order. The second attempt to create /app/logs fails because that path already exists, so its value stays 12.
Example 2
- Input
FileSystem(), createPath("/home/user", 5), get("/home/user"), createPath("/home", 3), createPath("/home/user", 5), get("/home/user")- Output
false, -1, true, true, 5- Why
- /home/user cannot be created while /home is missing. Once /home exists, the same call succeeds.
Constraints
2 <= path.length <= 100- Every path starts with
/and is made of one or more segments of lowercase English letters separated by single slashes (no trailing slash). 1 <= value <= 10^9- At most
10^4calls tocreatePathandgetin total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (list of created paths) | O(k · L) per call | O(k · L) |
| Optimal (hash map of full paths) | O(L) per call | O(k · L) |
1Brute force (list of created paths)
O(k · L) per callEach call compares the path against all k stored paths, each comparison costing up to L characters.O(k · L)All k created paths of length up to L are stored.Keep every created path with its value in a plain list. Each existence check scans the whole list and compares strings.
- createPath(path, value): if some stored entry equals path, return false.
- Compute parent = path up to its last
/. If parent is non-empty and no stored entry equals it, return false. - Otherwise append (path, value) and return true.
- get(path): scan the list; return the value of the matching entry, or -1.
class FileSystem {
private final List<String> paths = new ArrayList<>();
private final List<Integer> values = new ArrayList<>();
public FileSystem() {}
private int find(String p) {
for (int i = 0; i < paths.size(); i++) {
if (paths.get(i).equals(p)) return i;
}
return -1;
}
public boolean createPath(String path, int value) {
if (find(path) != -1) return false;
String parent = path.substring(0, path.lastIndexOf('/'));
if (!parent.isEmpty() && find(parent) == -1) return false;
paths.add(path);
values.add(value);
return true;
}
public int get(String path) {
int i = find(path);
return i == -1 ? -1 : values.get(i);
}
}class FileSystem:
def __init__(self):
self.paths: List[str] = []
self.values: List[int] = []
def _find(self, p: str) -> int:
for i, q in enumerate(self.paths):
if q == p:
return i
return -1
def createPath(self, path: str, value: int) -> bool:
if self._find(path) != -1:
return False
parent = path[:path.rfind("/")]
if parent and self._find(parent) == -1:
return False
self.paths.append(path)
self.values.append(value)
return True
def get(self, path: str) -> int:
i = self._find(path)
return -1 if i == -1 else self.values[i]class FileSystem {
vector<string> paths;
vector<int> values;
int find(const string& p) {
for (int i = 0; i < (int)paths.size(); i++) {
if (paths[i] == p) return i;
}
return -1;
}
public:
FileSystem() {}
bool createPath(string path, int value) {
if (find(path) != -1) return false;
string parent = path.substr(0, path.rfind('/'));
if (!parent.empty() && find(parent) == -1) return false;
paths.push_back(path);
values.push_back(value);
return true;
}
int get(string path) {
int i = find(path);
return i == -1 ? -1 : values[i];
}
};class FileSystem {
constructor() {
this.paths = [];
this.values = [];
}
find(p) {
for (let i = 0; i < this.paths.length; i++) {
if (this.paths[i] === p) return i;
}
return -1;
}
createPath(path, value) {
if (this.find(path) !== -1) return false;
const parent = path.substring(0, path.lastIndexOf('/'));
if (parent.length > 0 && this.find(parent) === -1) return false;
this.paths.push(path);
this.values.push(value);
return true;
}
get(path) {
const i = this.find(path);
return i === -1 ? -1 : this.values[i];
}
}2Optimal (hash map of full paths)
O(L) per callBuilding the parent string and hashing a key both take time proportional to the path length L.O(k · L)The map stores each of the k created paths once.Use a hash map from full path to value. Checking whether the path or its parent exists is one hash lookup each, so every call costs only the time to hash a string of length L.
- createPath(path, value): if the map already has path, return false.
- parent = path up to its last
/. If parent is non-empty and not in the map, return false. - Put path -> value and return true.
- get(path): return the mapped value, or -1 if absent.
class FileSystem {
private final Map<String, Integer> map = new HashMap<>();
public FileSystem() {}
public boolean createPath(String path, int value) {
if (map.containsKey(path)) return false;
String parent = path.substring(0, path.lastIndexOf('/'));
if (!parent.isEmpty() && !map.containsKey(parent)) return false;
map.put(path, value);
return true;
}
public int get(String path) {
return map.getOrDefault(path, -1);
}
}class FileSystem:
def __init__(self):
self.map: Dict[str, int] = {}
def createPath(self, path: str, value: int) -> bool:
if path in self.map:
return False
parent = path[:path.rfind("/")]
if parent and parent not in self.map:
return False
self.map[path] = value
return True
def get(self, path: str) -> int:
return self.map.get(path, -1)class FileSystem {
unordered_map<string, int> mp;
public:
FileSystem() {}
bool createPath(string path, int value) {
if (mp.count(path)) return false;
string parent = path.substr(0, path.rfind('/'));
if (!parent.empty() && !mp.count(parent)) return false;
mp[path] = value;
return true;
}
int get(string path) {
auto it = mp.find(path);
return it == mp.end() ? -1 : it->second;
}
};class FileSystem {
constructor() {
this.map = new Map();
}
createPath(path, value) {
if (this.map.has(path)) return false;
const parent = path.substring(0, path.lastIndexOf('/'));
if (parent.length > 0 && !this.map.has(parent)) return false;
this.map.set(path, value);
return true;
}
get(path) {
return this.map.has(path) ? this.map.get(path) : -1;
}
}Edge cases to test
- Creating a top-level path like
/a: its parent is the root, which always exists - Creating a path whose parent is missing returns false and changes nothing
- Creating a path that already exists returns false and keeps the old value
geton a path that was never created returns -1- Segment names that are prefixes of each other, like
/aband/a, are different paths
Hints
Hint 1
The parent of a path is everything before its last /. For /a/b/c it is /a/b; for /a it is the empty string, meaning the root.
Hint 2
A path can be created only if it is new and its parent already exists. What structure answers "does this full path exist?" in about O(length) time?
Hint 3
Store every created full path as a key in a hash map with its value. The root is always present.
FAQ
What is the best time complexity for Design File System?
Optimal (hash map of full paths) runs in O(L) per call time and O(k · L) extra space. Building the parent string and hashing a key both take time proportional to the path length L.
Which pattern does Design File System use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design HashMap.
Is there a brute force solution for Design File System?
Yes. Brute force (list of created paths) takes O(k · L) per call time and O(k · L) space. Keep every created path with its value in a plain list.
Which edge cases should I test for Design File System?
Creating a top-level path like /a: its parent is the root, which always exists; Creating a path whose parent is missing returns false and changes nothing; Creating a path that already exists returns false and keeps the old value; get on a path that was never created returns -1; Segment names that are prefixes of each other, like /ab and /a, are different paths.