Implement string-path file system operations
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 1166. Design File System – extended to support Create(path, value), Get(path), Set(path, value) and Delete(path) with validation rules.
https://leetcode.com/problems/design-file-system/description/
Quick Answer: This question evaluates competency in designing data structures for hierarchical string-path file systems, including string parsing, stateful API semantics, validation logic, and efficient lookup/update operations.
Implement a simple path-based file system that supports four operations over UNIX-like paths using strings. You are given a list of operations to process; return a result for each operation in order. Paths must start with '/', use '/' as a separator, have no empty segments, and may not end with '/' unless the path is exactly '/'. The root '/' exists by default and cannot be created, set, or deleted. The operations are: 1) Create(path, value): Create a node at 'path' with integer 'value' only if its parent exists and the path does not already exist. Returns True on success, False otherwise. 2) Get(path): Return the integer value stored at 'path', or -1 if the path does not exist or if 'path' is invalid or is '/'. 3) Set(path, value): Update the value at 'path' to 'value'. Returns True if the path exists and is valid (not '/'), otherwise False. 4) Delete(path): Remove the entire subtree rooted at 'path'. Returns True if the path exists and is not '/', otherwise False. Return for each operation: Create/Set/Delete -> boolean; Get -> integer. Input is a list of operations where each operation is one of: ['Create', path, value], ['Get', path], ['Set', path, value], ['Delete', path].
Constraints
- 1 <= len(ops) <= 50000
- Sum of path lengths across all operations <= 2e6
- Each value is a 32-bit signed integer
- Paths use '/' as separator, start with '/', have no empty segments, and do not end with '/' unless the path is exactly '/'
- Root '/' exists initially and cannot be created, set, or deleted
- Create requires the immediate parent of the path to exist and the path to not already exist
Solution
def file_system(ops):
class Node:
__slots__ = ("val", "children")
def __init__(self, val=None):
self.val = val
self.children = {}
root = Node()
def parse_path(path):
if not isinstance(path, str):
return None
if path == "/":
return []
if not path or path[0] != "/" or (len(path) > 1 and path.endswith("/")):
return None
parts = path.split("/")[1:]
if any(p == "" for p in parts):
return None
return parts
out = []
for op in ops:
t = op[0]
if t == "Create":
if len(op) != 3:
out.append(False)
continue
path, val = op[1], op[2]
segs = parse_path(path)
if segs is None or len(segs) == 0:
out.append(False)
continue
cur = root
for s in segs[:-1]:
nxt = cur.children.get(s)
if nxt is None:
cur = None
break
cur = nxt
if cur is None:
out.append(False)
continue
last = segs[-1]
if last in cur.children:
out.append(False)
else:
cur.children[last] = Node(val)
out.append(True)
elif t == "Get":
if len(op) != 2:
out.append(-1)
continue
path = op[1]
segs = parse_path(path)
if segs is None or len(segs) == 0:
out.append(-1)
continue
cur = root
for s in segs:
cur = cur.children.get(s)
if cur is None:
break
out.append(-1 if cur is None else (cur.val if cur.val is not None else -1))
elif t == "Set":
if len(op) != 3:
out.append(False)
continue
path, val = op[1], op[2]
segs = parse_path(path)
if segs is None or len(segs) == 0:
out.append(False)
continue
cur = root
for s in segs:
cur = cur.children.get(s)
if cur is None:
break
if cur is None:
out.append(False)
else:
cur.val = val
out.append(True)
elif t == "Delete":
if len(op) != 2:
out.append(False)
continue
path = op[1]
segs = parse_path(path)
if segs is None or len(segs) == 0:
out.append(False)
continue
cur = root
for s in segs[:-1]:
cur = cur.children.get(s)
if cur is None:
break
if cur is None:
out.append(False)
else:
last = segs[-1]
if last in cur.children:
del cur.children[last]
out.append(True)
else:
out.append(False)
else:
# Unknown op (not expected by constraints)
out.append(None)
return out
Explanation
Use a trie-like tree where each node holds a value and a hashmap of children. Paths are validated before any operation: they must start with '/', cannot end with '/', and cannot contain empty segments. The root '/' is represented by the initial node and is not creatable, settable, or deletable. For Create, traverse to the parent and insert a new child if it does not already exist. For Get and Set, traverse to the node; Get returns its value or -1 if missing, and Set updates the value if it exists. For Delete, traverse to the parent and remove the child entry; this discards the entire subtree. Each traversal touches at most the number of segments in the path.
Time complexity: O(total path segments processed) overall; O(L) per operation where L is the number of segments in the path. Space complexity: O(N) for N created nodes (sum of path segments created).
Hints
- Store the directory tree as nested hash maps (a trie-like structure).
- Validate path format before performing any operation.
- For Create, traverse to the parent; for Set/Get/Delete, traverse to the exact node.
- Delete can be implemented by removing the child entry from its parent's map.