Solve Flower Placement and Directory Deletion

Problem Statement

In this interview session, you are tasked with solving two independent algorithmic problems commonly encountered in system cleanup and spatial layout design.

Task 1: Directory Deletion

You are given a list of all existing directory paths in a filesystem, all_paths, and a subset of paths to remove, to_delete. Deleting a directory automatically deletes all of its subdirectories. You must find the minimum number of directory deletion commands to remove every path in to_delete without deleting any path not in to_delete.

Each path is represented as a string starting with / and separated by / (e.g., "/a/b/c").

def delete_directories(all_paths: list[str], to_delete: list[str]) -> list[str]:

Constraints (Task 1)

• 1 <= len(all_paths) <= 10^4
• 1 <= len(to_delete) <= len(all_paths)
• All paths in to_delete are present in all_paths.
• Path names contain only lowercase English letters and /.

Task 2: Flower Placement Grid

You are designing a garden layout represented by an m x n grid. Each cell is either 0 (empty plantable plot) or -1 (obstacle/rock). You are given k flower species labeled 1 through k. You must assign a flower species to every empty plot such that no two horizontally or vertically adjacent plots have the same species.

Return True if a valid assignment is possible, or False otherwise.

def can_place_flowers(grid: list[list[int]], k: int) -> bool:

Constraints (Task 2)

• 1 <= m, n <= 10
• 1 <= k <= 4
• grid[i][j] is either 0 or -1.

Examples

Example 1: Directory Deletion

all_paths = ["/a/b/c", "/a/b/d", "/a/e"]
to_delete = ["/a/b/c", "/a/b/d"]
# Output: ["/a/b"]

Explanation: Deleting /a/b removes both /a/b/c and /a/b/d in a single command without removing /a/e.

Example 2: Flower Placement

grid = [
  [0, 0],
  [0, -1]
]
k = 2
# Output: True

Explanation: We can place species 1 at (0,0), species 2 at (0,1), and species 2 at (1,0). No adjacent cells share the same species.

Edge Cases

• Task 1: When all existing paths are marked for deletion, the root / (or top-level directories) should be deleted.
• Task 1: A directory where only some children are deleted cannot itself be deleted; deletions must occur deeper in the tree.
• Task 2: Grid with no empty cells (0 count is 0) should return True.
• Task 2: k = 1 with two adjacent empty cells should return False.