FastPrepDelete a Filesystem Tree
Problems/Delete a Filesystem Tree

Delete a Filesystem Tree

Datadog logoDatadog● MediumFULLTIMEPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The source leaves child-list scope, failure behavior, depth, and return semantics unspecified. The judged core task matches the visible source at about 85%.

DeleteTree

You are given a mutable filesystem with exactly three fixed APIs:

  • fs.List(path) returns absolute paths below path. In this exercise it returns the live direct children in arbitrary order; on a file it returns an empty list.
  • fs.Delete(path) deletes a file or an empty directory and returns true. It returns false for a nonempty directory.
  • fs.IsDirectory(path) returns true exactly when the live path is a directory.

Every path passed to these APIs is absolute, and the APIs themselves cannot be changed. Implement DeleteTree(path), analogous to rm -rf, so that path and its entire subtree are deleted.

Execution adapter

The function runner represents the initial filesystem with parallel arrays paths and isDirectory. Entry isDirectory[i] describes paths[i]. The virtual root / exists but is not included in paths and is never the target.

Construct the filesystem from that snapshot, perform the logical DeleteTree(targetPath) operation through the three APIs above, and return every path still present after the deletion in lexicographically increasing order. The sorted return value is only the observable judge adapter for the filesystem side effect.

Required behavior

  1. Delete every descendant before attempting to delete its directory.
  2. Delete a file directly because it has no children.
  3. Do not delete any path outside the target subtree.
  4. Do not rely on the order returned by fs.List.

What the interview report shared

The report described the three immutable APIs, stated that all API path arguments are absolute, and asked for a recursive tree deletion with semantics similar to rm -rf.

Memory follow-ups

Discuss why a recursive solution can fail on a deep tree and why an explicit DFS stack or a BFS queue can still use substantial memory. Include the live child list returned by the fixed List API and the lengths of absolute path strings in the analysis.

Also explain a traversal that keeps only a fixed number of traversal variables by deriving the parent from the current absolute path and listing its remaining live children again. Do not describe that as constant bytes: one returned child list can still be large, and repeated listing trades time for less persistent traversal state. The executable result remains the same final filesystem snapshot.

Function

deleteTree(paths: List<String>, isDirectory: boolean[], targetPath: String) → List<String>

Examples

Example 1

paths = ["/data","/data/logs","/data/logs/2026","/data/logs/2026/app.log","/data/tmp","/data/tmp/cache.bin","/keep.txt"]isDirectory = [true,true,true,false,true,false,false]targetPath = "/data/logs"return = ["/data","/data/tmp","/data/tmp/cache.bin","/keep.txt"]

/data/logs/2026/app.log is deleted first, followed by its now-empty parent directories /data/logs/2026 and /data/logs. The sibling subtree rooted at /data/tmp and /keep.txt remain.

Example 2

paths = ["/a","/a/file.txt","/b","/b/keep.txt"]isDirectory = [true,false,true,false]targetPath = "/a/file.txt"return = ["/a","/b","/b/keep.txt"]

The target is already a file, so it is deleted immediately. Its parent directory and the separate /b subtree remain live.

Example 3

paths = ["/empty","/keep","/keep/note.txt"]isDirectory = [true,true,false]targetPath = "/empty"return = ["/keep","/keep/note.txt"]

The target directory has no children, so fs.Delete succeeds on the first deletion attempt.

Constraints

  • 1 <= paths.size() <= 50,000.
  • paths.size() == isDirectory.length.
  • Every listed path is distinct, canonical, absolute, and different from /; no listed path has a trailing slash.
  • The parent of each listed path is either / or another listed path marked as a directory.
  • targetPath is one of the listed paths and is not /.
  • The snapshot is a finite rooted tree with no symbolic links, hard links, cycles, or mount boundaries.
  • fs.List and fs.IsDirectory do not fail, and no concurrent filesystem mutation occurs.
  • A valid deletion fails only while the target directory is nonempty; no other partial or external failure occurs.
  • The sum of all path lengths is at most 5,000,000, and tree depth is at most 2,000. Recursion is not guaranteed to be safe at the maximum depth.
  • A canonical path has no empty, . or .. component, and contains no NUL character. Components may otherwise contain Unicode characters; no ASCII-only restriction applies.
  • Path lengths count Unicode code points. Lexicographic output order compares Unicode code point values, with a prefix before its extensions.

More Datadog problems

  • Query Log MatchPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Grouped-Query Attention Forward PassPHONE SCREEN · Seen Jun 2026
  • Mean Binary Focal LossPHONE SCREEN · Seen Jun 2026
All Datadog interview questionsSee Datadog hiring insights
Saved
public List<String> deleteTree(List<String> paths, boolean[] isDirectory, String targetPath) {
    
}
Checking account…