In-Memory File System: Create, Track Duplicates, and List

Problem Statement

Design an in-memory file system that organizes files and directories in a hierarchical tree structure. The file system should support creating directories, writing files with automatic collision handling for duplicate names, reading file contents, and listing directory entries.

Implement the FileSystem class:

• FileSystem(): Initializes the file system with a root directory /.
• mkdir(path: str) -> None: Creates all directories along the given absolute path if they do not already exist. Intermediate directories are created automatically.
• create_file(path: str, content: str) -> str: Creates a file at the given absolute path with the specified content. Intermediate directories are created if they do not exist.
  • If a file with the same name already exists in the target directory, resolve the collision by appending (k) to the file name, where k is the smallest positive integer (1, 2, ...) such that the new name is not already taken in that directory.
  • If the file has an extension (a . followed by characters, where the dot is not the first character of the filename), insert (k) immediately before the last extension: for example, doc.txt becomes doc(1).txt.
  • If the file has no extension or starts with a dot (e.g., .env), append (k) to the end: file becomes file(1), .env becomes .env(1).
  • Returns the final assigned file name (not the full path).
• read_file(path: str) -> str: Returns the content of the file at the given path. Assumes the file exists.
• ls(path: str) -> list[str]:
  • If path is a directory, returns a list of the names of its immediate children (both subdirectories and files) sorted in lexicographical (alphabetical) order.
  • If path is a file, returns a list containing only that file's name.

Interface

class FileSystem:
    def __init__(self):
        pass

    def mkdir(self, path: str) -> None:
        pass

    def create_file(self, path: str, content: str) -> str:
        pass

    def read_file(self, path: str) -> str:
        pass

    def ls(self, path: str) -> list[str]:
        pass

Examples

Example 1

fs = FileSystem()

fs.mkdir("/a/b")
print(fs.ls("/a"))        # ["b"]

name1 = fs.create_file("/a/b/notes.txt", "first")
print(name1)              # "notes.txt"

name2 = fs.create_file("/a/b/notes.txt", "second")
print(name2)              # "notes(1).txt"

name3 = fs.create_file("/a/b/notes.txt", "third")
print(name3)              # "notes(2).txt"

print(fs.ls("/a/b"))      # ["notes(1).txt", "notes(2).txt", "notes.txt"]
print(fs.read_file("/a/b/notes(1).txt"))  # "second"

Example 2

fs = FileSystem()
fs.create_file("/data", "val1")      # Returns "data"
fs.create_file("/data", "val2")      # Returns "data(1)"
fs.create_file("/.env", "secret")    # Returns ".env"
fs.create_file("/.env", "secret2")   # Returns ".env(1)"
print(fs.ls("/"))                   # [".env", ".env(1)", "data", "data(1)"]

Constraints

• All paths are absolute, starting with /.
• Path components consist of alphanumeric characters, dots (.), and underscores (_).
• Total number of calls across all operations is at most 10^4.
• Directory and file names are case-sensitive.
• It is guaranteed that directory and file paths are valid format and do not end with a trailing / (except the root directory /).