Design an In-Memory File System

Medium·Tagsllddesignfile-systemtreepath-resolution

Problem Statement

Design an in-memory file system that supports `mkdir`, `createFile`, `write`, `read`, and `ls` over a tree of nested directories rooted at `/`. Path format - Paths are absolute and start with `/`. The root is the path `"/"`. - Components are separated by `/` and cannot themselves contain `/`. - The root directory always exists (you do not create it). API contract ```java class InMemoryFileSystem { public InMemoryFileSystem(); // root directory ready /** Create a directory at `path`. Throws IllegalArgumentException if `path` is invalid * or if any parent directory does not exist. Throws IllegalStateException if a file or directory already exists at `path`. / public void mkdir(String path); /** Create an empty file at `path`. Throws IllegalArgumentException if `path` is invalid * or if the parent directory does not exist. Throws IllegalStateException if `path` already exists. / public void createFile(String path); /** Replace the file's content. Throws IllegalArgumentException if `path` is a directory * or does not exist. */ public void write(String path, String content); /** Return the file's content. Returns the empty string for a freshly-created file. * Throws IllegalArgumentException if `path` is a directory or does not exist. */ public String read(String path); /* Return immediate children of the directory at `path`, in sorted order* (Strings * sorted naturally). Throws IllegalArgumentException if `path` is a file or does not exist. ls("/") returns the top-level entries. / public List<String> ls(String path); public boolean exists(String path); public boolean isDirectory(String path); } ``` The validator runs three checks: 1. mkdir_and_ls — create `/a`, then `/a/b`, then `/a/b/c`. `ls("/")` = `["a"]`; `ls("/a")` = `["b"]`; `ls("/a/b")` = `["c"]`. After also creating `/a/zoo` and `/a/apple`, `ls("/a")` = `["apple", "b", "zoo"]` (sorted). 2. file_create_write_read — `createFile("/note.txt")`; `read("/note.txt")` is `""`. Then `write("/note.txt", "hello")`; `read` returns `"hello"`. Overwriting via `write("/note.txt", "world")` replaces the content. `exists("/note.txt")` is true, `isDirectory("/note.txt")` is false. 3. error_cases — `mkdir("/a")` then `mkdir("/a")` throws `IllegalStateException`. `createFile("/missing/file")` throws `IllegalArgumentException` (parent missing). `read("/a")` (a directory) throws. `ls("/note.txt")` (a file) throws. The stub class throws `UnsupportedOperationException` from every method.

Examples

Example 1

Input

var fs = new InMemoryFileSystem(); fs.mkdir("/a"); fs.mkdir("/a/b"); fs.ls("/a")

Output

"[\"b\"]"

Why

ls returns immediate children of the directory.

Example 2

Input

fs.createFile("/a/note.txt"); fs.write("/a/note.txt", "hi"); fs.read("/a/note.txt")

Output

"\"hi\""

Why

Files store and return their content; write replaces.

Example 3

Input

fs.mkdir("/missing/parent/foo")

Output

"throws IllegalArgumentException"

Why

Parent directories must already exist.

Constraints

•Paths are absolute, starting with /. Root is "/".
•ls returns immediate children in sorted order.
•mkdir / createFile require the parent directory to exist (no auto-create).
•mkdir / createFile throw IllegalStateException if the path already exists; IllegalArgumentException for invalid paths or missing parents.
•read / write require an existing file path; reading or writing a directory throws IllegalArgumentException.
•Empty file reads return the empty string, not null.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

Use a single Node class with a `boolean isFile`, a `Map<String, Node> children` (used only when !isFile), and a `String content` (used only when isFile). Or split into FileNode and DirectoryNode subclasses — both are clean.

Hint 2

Path parsing: split on '/' and discard empty segments. The root path '/' has no segments. '/a/b' has [a, b].

Hint 3

Walk helper: traverse from root following segments. Return null if any segment is missing or if you hit a file before the end. Used by ls, read, write, exists, isDirectory.

Hint 4

mkdir/createFile: walk to the PARENT (all segments except the last). Validate parent exists and is a directory. Validate the last segment doesn't already exist. Then add the new child.

Hint 5

ls of a directory: return new ArrayList<>(node.children.keySet()) and Collections.sort(list). Children iteration order in HashMap is undefined; sort explicitly.

Hint 6

Error types: throw IllegalArgumentException for caller bugs (missing parent, wrong kind, invalid path) and IllegalStateException for 'already exists'. Validator distinguishes the two.