Design File System
Problem
Design a file system that supports two operations: createPath(path, value) which creates a new path and associates a value to it iff the parent path exists and the path itself doesn't yet exist; and get(path) which returns the value associated with a path or -1 if none.
createPath("/a", 1), createPath("/a/b", 2), get("/a/b"), createPath("/c/d", 3), get("/c")[true, true, 2, false, -1]class FileSystem:
def __init__(self):
self.paths = {}
def createPath(self, path, value):
if path == "/" or path in self.paths:
return False
parent = path[:path.rfind("/")]
if parent and parent not in self.paths:
return False
self.paths[path] = value
return True
def get(self, path):
return self.paths.get(path, -1)class FileSystem {
constructor() { this.paths = new Map(); }
createPath(path, value) {
if (path === "/" || this.paths.has(path)) return false;
const parent = path.slice(0, path.lastIndexOf("/"));
if (parent && !this.paths.has(parent)) return false;
this.paths.set(path, value);
return true;
}
get(path) {
return this.paths.has(path) ? this.paths.get(path) : -1;
}
}class FileSystem {
private Map<String, Integer> paths = new HashMap<>();
public boolean createPath(String path, int value) {
if (path.equals("/") || paths.containsKey(path)) return false;
String parent = path.substring(0, path.lastIndexOf('/'));
if (!parent.isEmpty() && !paths.containsKey(parent)) return false;
paths.put(path, value);
return true;
}
public int get(String path) {
return paths.getOrDefault(path, -1);
}
}class FileSystem {
unordered_map<string,int> paths;
public:
bool createPath(string path, int value) {
if (path == "/" || paths.count(path)) return false;
string parent = path.substr(0, path.find_last_of('/'));
if (!parent.empty() && !paths.count(parent)) return false;
paths[path] = value;
return true;
}
int get(string path) {
auto it = paths.find(path);
return it == paths.end() ? -1 : it->second;
}
};Explanation
The neat insight here is that we do not need an actual tree of folders. Since every path is a unique string, we can keep one hash map from the full path string to its value. The map acts like a flattened trie of paths.
For createPath(path, value) there are two rules. First, the path must not already exist (and cannot be the root "/"). Second, its parent must exist. We find the parent by chopping off everything after the last /, then check the map for it.
If the parent is present (or the path has no real parent, like a top-level /a), we store the value and return true; otherwise we return false without changing anything. get(path) is then just a map lookup that returns -1 when the key is missing.
Example: createPath("/a", 1) succeeds (top level). createPath("/a/b", 2) succeeds because parent /a exists. createPath("/c/d", 3) fails because parent /c was never created, and get("/c") returns -1.
Each operation only does string slicing and a couple of map lookups, so it costs about the length of the path.