Design File System

Hash map of full path to value — createPath fails if path exists or parent missing.

Medium
Time O(L) per op Space O(N)
LeetCode
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 /c missing).

Constraints#

  • 2 <= path.length <= 100, up to 10^4 calls.

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#

Design File System
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.