Implement FileSystem, a tree of directories and files kept in memory. All paths are absolute, like "/a/b/c"; names use lowercase letters and digits; the root is "/".
ls(path) -> list[str]: ifpathis a file, return a list containing just its name. If it's a directory, return the names of its direct children (files and directories) in lexicographic order.mkdir(path): create the directory, creating any missing parent directories along the way (likemkdir -p). Creating one that exists is a no-op.add_content_to_file(path, content): if the file doesn't exist, create it (and any missing parent directories) withcontent; otherwise appendcontentto it.read_content_from_file(path) -> str: return the file's full content.
You may assume calls are valid: ls targets an existing path, read_content_from_file targets an existing file, and nobody tries to create a file where a directory is (or vice versa).
fs = FileSystem()
fs.ls("/") # []
fs.mkdir("/docs/notes")
fs.add_content_to_file("/docs/todo", "buy")
fs.add_content_to_file("/docs/todo", " milk")
fs.ls("/") # ["docs"]
fs.ls("/docs") # ["notes", "todo"]
fs.ls("/docs/todo") # ["todo"]
fs.read_content_from_file("/docs/todo") # "buy milk"
Each call should cost time proportional to the path length (plus sorting the listing for ls), not to the total number of files.
Show hint
Model it as a trie of path components: each node is either a directory (dict of children) or a file (content).