In-Memory File System

Build an in-memory Unix-style file system backed by a tree of directory and file nodes, implemented incrementally across parts. Supports creating, listing, reading/writing, and removing files and directories by path. Problem Overview Design an in-memory Unix-like file system. This is a two-part coding question and is the canonical design-in-memory-file-system problem, but the API is framed around Unix commands. You should implement a class that supports absolute paths such as /, /tmp, and /tmp/a.txt. class InMemoryUnixFileSystem: def touch(self, path: str) -> None: """Create an empty file if it does not already exist.""" def mkdir(self, path: str) -> None: """Create a directory.""" def ls(self, path: str) -> list[str]: """List a directory, or return the file name if path is a file.""" def rm(self, path: str) -> bool: """Remove a file. Return True if a file was removed.""" def rmdir(self, path: str) -> bool: """Remove an empty directory. Return True if a directory was removed.""" Clarifications Paths are absolute and begin with /. Treat duplicate slashes and trailing slashes as normalizable, so /a//b/ is equivalent to /a/b. mkdir(path) behaves like mkdir -p: missing intermediate directories are created. touch(path) creates a file only if the parent directory exists. A file and directory cannot share the same name under the same parent. ls("/") returns the root's children in lexicographic order. ls(file_path) returns a one-element list containing the file name. rm(path) removes files only; it should not remove directories. rmdir(path) removes empty directories only; it should not remove / or non-empty directories. touch("/") is invalid because / is the root directory, not a file path. Part 1: touch, mkdir, ls Implement: fs = InMemoryUnixFileSystem() fs.mkdir("/workspace/src") fs.touch("/workspace/src/app.py") fs.touch("/workspace/README.md") fs.ls("/") # ["workspace"] fs.ls("/workspace") # ["README.md", "src"] fs.ls("/workspace/src") # ["app.py"] fs.ls("/workspace/src/app.py") # ["app.py"] The clean data model is a tree. Each node represents either a directory or a file: directory nodes store child names file nodes store no children for this problem traversal follows normalized path segments from the root You can solve Part 1 with nested dictionaries, but it is better to introduce an explicit node type from the beginning because Part 2 needs to distinguish files, directories, empty directories, and non-empty directories. Part 2: rm, rmdir Extend the file system with deletion commands. fs.rm("/workspace/src/app.py") # True fs.ls("/workspace/src") # [] fs.rmdir("/workspace/src") # True fs.ls("/workspace") # ["README.md"] fs.rmdir("/workspace") # False, still contains README.md fs.rm("/workspace") # False, path is a directory fs.rm("/workspace/README.md") # True fs.rmdir("/workspace") # True Edge cases worth testing: removing a missing path removing / calling touch where a directory already exists calling mkdir where a file already exists calling rmdir on a non-empty directory listing a file path versus a directory path Reference Solution from __future__ import annotations from dataclasses import dataclass, field @dataclass class Node: is_file: bool = False children: dict[str, "Node"] = field(default_factory=dict) class InMemoryUnixFileSystem: def __init__(self): self.root = Node() def _parts(self, path: str) -> list[str]: if not path.startswith("/"): raise ValueError("path must be absolute") return [part for part in path.split("/") if part] def _get_node(self, path: str) -> Node | None: node = self.root for part in self._parts(path): if node.is_file: return None node = node.children.get(part) if node is None: return None return node def _get_parent(self, path: str) -> tuple[Node | None, str]: parts = self._parts(path) if not parts: return None, "" parent = self.root for part in parts[:-1]: next_node = parent.children.get(part) if next_node is None or next_node.is_file: return None, parts[-1] parent = next_node return parent, parts[-1] def mkdir(self, path: str) -> None: node = self.root for part in self._parts(path): child = node.children.get(part) if child is None: child = Node() node.children[part] = child elif child.is_file: raise ValueError(f"{path} conflicts with an existing file") node = child def touch(self, path: str) -> None: parent, name = self._get_parent(path) if not name: raise ValueError("cannot touch root directory") if parent is None: raise ValueError("parent directory does not exist") existing = parent.children.get(name) if existing is not None: if not existing.is_file: raise ValueError(f"{path} is a directory") return parent.children[name] = Node(is_file=True) def ls(self, path: str) -> list[str]: node = self._get_node(path) if node is None: raise ValueError("path does not exist") if node.is_file: parts = self._parts(path) return [parts[-1]] return sorted(node.children.keys()) def rm(self, path: str) -> bool: parent, name = self._get_parent(path) if parent is None: return False node = parent.children.get(name) if node is None or not node.is_file: return False del parent.children[name] return True def rmdir(self, path: str) -> bool: parent, name = self._get_parent(path) if parent is None: return False node = parent.children.get(name) if node is None or node.is_file or node.children: return False del parent.children[name] return True Complexity Let d be the number of path segments and k be the number of children in the listed directory. touch: O(d) time, O(1) extra space mkdir: O(d) time, O(d) new nodes in the worst case ls(file): O(d) time ls(directory): O(d + k log k) time because child names are sorted rm: O(d) time rmdir: O(d) time The total space usage is O(n), where n is the number of files and directories created. Notes A three-part variant adds cd() after creation, listing, and deletion. Another command-oriented variant receives raw Unix-style command lines rather than direct method calls, so the implementation must parse each command, dispatch it, and execute it against the same tree. Clarify current-directory behavior, relative versus absolute paths, tokenization rules, and invalid-command handling before coding.