Design File System
Hash map of full path to value — createPath fails if path exists or parent missing.
3 min read
design hash-map string
Problem#
Design createPath(path, value) and get(path). createPath succeeds iff the path doesn’t exist and its parent path does (root path ”/” always exists). get returns the stored value or -1.
Examples#
createPath("/a", 1)→true;get("/a")→1.createPath("/a/b", 2)→true;createPath("/c/d", 3)→false(parent/cmissing).
Constraints#
2 <= path.length <= 100, up to10^4calls.
Approach#
Flat hash map keyed by full path string. On create: reject if path already exists; reject if parent path (everything up to the last /) is not present. Else insert.
Solution#
class FileSystem { unordered_map<string,int> mp;public: bool createPath(string path, int value) { if (mp.count(path)) return false; int slash = path.find_last_of('/'); if (slash > 0) { string parent = path.substr(0, slash); if (!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; }};import "strings"
type FileSystem struct { mp map[string]int}
func Constructor() FileSystem { return FileSystem{mp: make(map[string]int)}}
func (fs *FileSystem) CreatePath(path string, value int) bool { if _, ok := fs.mp[path]; ok { return false } slash := strings.LastIndex(path, "/") if slash > 0 { parent := path[:slash] if _, ok := fs.mp[parent]; !ok { return false } } fs.mp[path] = value return true}
func (fs *FileSystem) Get(path string) int { if v, ok := fs.mp[path]; ok { return v } return -1}class FileSystem: def __init__(self): self.mp: dict[str, int] = {}
def createPath(self, path: str, value: int) -> bool: if path in self.mp: return False slash = path.rfind('/') if slash > 0: parent = path[:slash] if parent not in self.mp: return False self.mp[path] = value return True
def get(self, path: str) -> int: return self.mp.get(path, -1)var FileSystem = function() { this.mp = new Map();};
FileSystem.prototype.createPath = function(path, value) { if (this.mp.has(path)) return false; const slash = path.lastIndexOf('/'); if (slash > 0) { const parent = path.substring(0, slash); if (!this.mp.has(parent)) return false; } this.mp.set(path, value); return true;};
FileSystem.prototype.get = function(path) { return this.mp.has(path) ? this.mp.get(path) : -1;};class FileSystem { private Map<String, Integer> mp;
public FileSystem() { mp = new HashMap<>(); }
public boolean createPath(String path, int value) { if (mp.containsKey(path)) return false; int slash = path.lastIndexOf('/'); if (slash > 0) { String parent = path.substring(0, slash); if (!mp.containsKey(parent)) return false; } mp.put(path, value); return true; }
public int get(String path) { return mp.getOrDefault(path, -1); }}class FileSystem { private mp: Map<string, number> = new Map();
createPath(path: string, value: number): boolean { if (this.mp.has(path)) return false; const slash = path.lastIndexOf('/'); if (slash > 0) { const parent = path.substring(0, slash); if (!this.mp.has(parent)) return false; } this.mp.set(path, value); return true; }
get(path: string): number { return this.mp.has(path) ? (this.mp.get(path) as number) : -1; }}Editorial#
A flat map sidesteps the entire trie overhead — the lookup is O(1) average and parent-existence is one extra lookup. The root case (/x has parent /, which we treat as implicitly present via the slash > 0 guard) is the only subtle bit.
Complexity#
- Time:
O(L)per op for string hashing. - Space:
O(N).
Concept revision#
Related#