In-Memory File System

Prompt

"Implement an in-memory file system. I want mkdir(path), ls(path), write(path, content) that appends, and read(path). Paths are absolute, like /a/b/c. Tell me how you would structure it, then code it."

Clarifying questions

• Does mkdir create intermediate directories? Yes, like mkdir -p. Existing directories along the way are not an error.
• What does ls return? If the path is a directory, the sorted names of its direct children (files and directories mixed). If it is a file, a one-element list containing the file's own name.
• Does write create the file if it does not exist? Yes, and its parent directories too. Content is appended, not replaced.
• Can a file and a directory share a name in the same parent? No. Names are unique within a directory regardless of kind.
• Valid path format? Absolute, /-separated, no . or .., no trailing slash except the root / itself. Names are non-empty and contain no /.
• Concurrency? Not for the first version, but the interviewer will ask what breaks if two threads write.

Requirements

Functional

• mkdir(path): create the directory and any missing ancestors.
• ls(path): list a directory's children in lexicographic order, or the file itself.
• write(path, content): append to a file, creating it and ancestors on demand.
• read(path): return the full content of a file. Reading a directory is an error.

Non-functional

• Each operation should cost O(depth) for path resolution plus O(1) per component; ls additionally pays for sorting the children.
• Path parsing must be in one place. Most bugs in this problem are inconsistent handling of the root and of empty components.
• The structure should extend to rm, mv, and permissions without rewriting resolution.

Numbers

• A workspace-scale tree: 10^5 nodes, depth rarely above 20, names ~20 bytes. That is a few megabytes of dict overhead plus the content. Nothing here needs to be clever about memory; the design question is entirely about shape and invariants.