Delete a Directory Tree

DatadogPhone screenMedium

You work through delete_tree(entries, undeletable, path), which builds a file system object fs from entries (strings like "D /a" for a directory and "F /a/b.txt" for a file) and undeletable (paths whose delete is always refused). All paths are absolute and start with /. The object exposes exactly three calls:

fs.list(path) returns the absolute paths of the direct children of the directory path. For a file it returns an empty list.
fs.delete(path) deletes a file or an empty directory and returns True. It returns False and changes nothing for a directory that still has children, and for an entry the system refuses to remove.
fs.is_directory(path) returns True for a directory and False for a file.

The starter already ends with return [deleted, fs.remaining()], where fs.remaining() lists the entries still present, sorted as plain strings in the same "D /p" / "F /p" format as entries.

Part 1: Delete the whole subtree

Fill in the deletion in delete_tree: remove path and everything under it using only fs.list, fs.delete and fs.is_directory, children before parents. A directory can only be deleted after all of its children are gone; a file is deleted with a single call.

A refused delete does not stop the work. Delete every entry that can be deleted. deleted is True only when every entry of the subtree, including path itself, is gone, and False otherwise. Keep the provided return line, which reports [deleted, fs.remaining()].

Example 1
path
"/a"
entries
["D /a","D /a/b","F /a/b/c.txt","F /a/d.txt","D /x"]
undeletable
[]
Output
[true,["D /x"]]
Why: The files under /a are removed first, then the emptied /a/b, then /a itself. /x lies outside the subtree and stays.

Constraints

1 <= len(entries) <= 10^6
1 <= len(path) <= 4096
every path in entries has a parent directory that is also in entries, or is /
path names an existing entry other than /
the subtree of path can be deeper than 1000 levels
a directory in entries can have more than 10^5 direct children

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question