Design an In-Memory File System with Recursive Wildcards

Build an in-memory file system whose only entries are directories. At the start, the sole directory that exists is the root /, and the root is also where the current working directory points.

Your implementation must expose three operations:

mkdir(String name)
pwd()
cd(String path)

Operations

mkdir(name)

Adds a new directory called name as an immediate child of the current directory.

• name never contains a /, and it is never ., .., or *.
• If a child with that name is already present, the operation fails.

pwd()

Reports the absolute path of the current directory.

• For the root, the result is /.
• For any other directory the result looks like /home/user/docs.

cd(path)

Moves the current directory to whichever directory path refers to.

How paths are interpreted:

• When path starts with /, it is absolute and resolution begins at the root; any other path is resolved starting from the current directory.
• A run of consecutive / characters counts as a single separator.
• The component . refers to the current directory.
• The component .. refers to the parent directory. Using .. while at the root leaves you at the root.
• The component * is only allowed as an entire path component, and it stands for zero or more levels of directories. For instance:
  • /a/*/target is satisfied by /a/target, by /a/x/target, and by /a/x/y/target.
  • Because * can cover zero levels, it can resolve to the current directory itself.
• Every component other than * has to match a directory name exactly.
• If resolving the wildcard yields no directory at all, or yields more than one distinct directory, the cd fails and the current directory stays exactly where it was.

Choose suitable data structures and implement these APIs.

Testing uses the following command-line format:

Q
<command 1>
<command 2>
...
<command Q>

Every command is one of mkdir name, pwd, or cd path. What to print:

• OK when a mkdir or cd succeeds.
• ERROR when a mkdir or cd fails.
• The current absolute path when the command is pwd.

Example 1:

Input:
10
mkdir a
mkdir b
cd a
mkdir x
cd /
cd /a/*/x
pwd
cd /a/*
pwd

Output:
OK
OK
OK
OK
OK
OK
/a/x
ERROR
/a/x

Explanation: The pattern /a/* resolves to two different directories, /a and /a/x, so that cd is rejected and the current directory remains /a/x.

Example 2:

Input:
3
pwd
mkdir home
pwd

Output:
/
OK
/

Constraints:

• Only directories exist; there are no files.
• A name passed to mkdir contains no / and is never ., .., or *.
• * appears only as a whole path component and matches zero or more directory levels.
• A failed cd must leave the current directory unchanged.