In-Memory Unix File System

Problem Overview

Design an in-memory Unix-like file system. This is a multi-part coding exercise with APIs framed around Unix commands, similar in spirit to LeetCode 588: Design In-Memory File System. A five-part version has been described, but the command requirements below cover the first two parts; the later parts are not sufficiently specified to reconstruct here.

The supplied scaffolding varies. Some versions require an execution function, while others provide test files and a basic class framework without requiring a custom command-line run() function. Follow the supplied interfaces and tests for the version you receive.

You should implement a class that supports absolute paths such as /, /tmp, and /tmp/a.txt. [Source: darkinterview.com]

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 only the final directory; its parent must already exist."""

    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 and Reference Conventions

The first two parts require creation/listing commands followed by deletion commands, with creation limited to the final path component. This detailed breakdown has single-account coverage. Path normalization, listing order, return values, and error handling are not fully specified; the reference solution below uses these conventions:

• Paths are absolute and begin with /.
• Treat duplicate slashes and trailing slashes as normalizable, so /a//b/ is equivalent to /a/b.
• Reject relative paths and . or .. path components with ValueError. Current-directory navigation is outside this implementation's scope.
• mkdir(path) creates only the final directory. Its parent must already exist; reject a missing parent or a file in the parent path without creating intermediate directories.
• 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.
• Repeating mkdir on an existing directory (including /) or touch on an existing file is a no-op.
• mkdir and touch return None on success and raise ValueError for missing parents or file/directory conflicts. ls raises ValueError for a missing path.
• For valid absolute paths, rm and rmdir return False when nothing can be removed, including a missing path, the wrong node type, or a non-empty directory. Failed operations leave the tree unchanged.

Part 1: touch, mkdir, ls

Implement:

fs = InMemoryUnixFileSystem()

fs.mkdir("/workspace")
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: [Source: darkinterview.com]

• 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. This example continues from the state created in Part 1.

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: [Source: darkinterview.com]

• removing a missing path
• removing /
• calling touch where a directory already exists
• calling mkdir where a file already exists
• calling mkdir with a missing parent or a file in the parent path, leaving the file system unchanged
• 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")
        parts = [part for part in path.split("/") if part]
        if any(part in (".", "..") for part in parts):
            raise ValueError("'.' and '..' path components are not supported")
        return parts

    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)
             node  :
                 
         node

     () -> [Node | , ]:
        parts = ._parts(path)
          parts:
             , 

        parent = .root
         part  parts[:-]:
            next_node = parent.children.get(part)
             next_node    next_node.is_file:
                 , parts[-]
            parent = next_node

         parent, parts[-]

     () -> :
        parent, name = ._get_parent(path)
          name:
              
         parent  :
             ValueError()

        existing = parent.children.get(name)
         existing   :
             existing.is_file:
                 ValueError()
            

        parent.children[name] = Node()

     () -> :
        parent, name = ._get_parent(path)
          name:
             ValueError()
         parent  :
             ValueError()

        existing = parent.children.get(name)
         existing   :
              existing.is_file:
                 ValueError()
            

        parent.children[name] = Node(is_file=)

     () -> []:
        node = ._get_node(path)
         node  :
             ValueError()

         node.is_file:
            parts = ._parts(path)
             [parts[-]]

         (node.children.keys())

     () -> :
        parent, name = ._get_parent(path)
         parent  :
             

        node = parent.children.get(name)
         node     node.is_file:
             

         parent.children[name]
         

     () -> :
        parent, name = ._get_parent(path)
         parent  :
             

        node = parent.children.get(name)
         node    node.is_file  node.children:
             

         parent.children[name]
         

Complexity

Let L be the length of the input path and k be the number of children in the listed directory. Assume average-case dictionary operations and bounded-length node names for sorting and storage. Using path length accounts for parsing, including repeated slashes.

• touch: O(L) time, at most one new file node
• mkdir: O(L) time, at most one new directory node
• ls(file): O(L) time
• ls(directory): O(L + k log k) time because child names are sorted
• rm: O(L) time
• rmdir: O(L) time

Path splitting uses O(L) temporary space per operation; listing a directory also uses O(k) space for its sorted result. Persistent storage is O(n), where n is the number of files and directories currently stored, including the root.