How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Solve Flower Placement and Directory Deletion

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You will solve two independent coding tasks. ### Task 1: Place Flowers on a Grid Given an `N x N` grid: - `'H'` represents a house. - `'0'` represents an empty cell. Place flowers, represented by `'F'`, on empty cells so that all of the following conditions hold: 1. Every row contains exactly one flower. 2. Every column contains exactly one flower. 3. For every house, exactly one of its four orthogonally adjacent cells contains a flower. Orthogonally adjacent means up, down, left, and right within the grid bounds. 4. A flower cannot be placed on a house cell. Return any valid grid configuration. If no valid configuration exists, return an indication that there is no solution. Example grid: ```text H 0 0 0 H 0 0 0 0 0 0 H 0 0 0 0 ``` ### Task 2: Implement Recursive Directory Deletion You are given two filesystem APIs: ```java List<String> getChildrenPaths(String path) void deleteFile(String path) ``` Assumptions: - `getChildrenPaths(path)` returns the immediate child paths of `path` if `path` is a directory. - It returns an empty list if `path` is an empty directory or a file. - `deleteFile(path)` deletes a file or an empty directory, but it cannot delete a non-empty directory. Implement: ```java void deleteDirectory(String path) ``` The function should delete the directory at `path` and all of its descendants. Be prepared to discuss tradeoffs between different implementations, such as recursive DFS versus iterative DFS, preorder versus postorder deletion, stack depth, error handling, and API-call complexity.

Quick Answer: This question evaluates combinatorial constraint-satisfaction and permutation/matching skills for the flower-placement grid alongside filesystem traversal and recursive versus iterative deletion strategies for the directory-deletion task.

Part 1: Place Flowers on a Grid

You are given an N x N grid of characters. Each cell is either 'H' (a house) or '0' (an empty cell). Place flowers, marked as 'F', so that: (1) every row contains exactly one flower, (2) every column contains exactly one flower, (3) no flower is placed on a house, and (4) every house has exactly one orthogonally adjacent flower among its up, down, left, and right neighbors inside the grid. Return the completed grid as a list of strings. If no valid placement exists, return an empty list. If multiple valid placements exist, return the one whose flower-column sequence [c0, c1, ..., cN-1] is lexicographically smallest, where ci is the column of the flower in row i.

Constraints

1 <= N <= 8
grid.length == N
Each row has length N
Each character is either 'H' or '0'

Examples

Input: (['0'],)

Expected Output: ['F']

Explanation: Single-cell grid with one empty cell. The only valid placement is to put the flower there.

Input: (['H'],)

Expected Output: []

Explanation: The only cell is a house, so a flower cannot be placed, but the row and column still need one flower. No solution exists.

Input: (['00', '00'],)

Expected Output: ['F0', '0F']

Explanation: There are multiple perfect row/column placements, but the lexicographically smallest flower-column sequence is [0, 1].

Input: (['H000', 'H000', '000H', '0000'],)

Expected Output: ['HF00', 'H0F0', 'F00H', '000F']

Explanation: The flowers are placed in columns [1, 2, 0, 3], which satisfies the row, column, and house-adjacency rules.

Input: (['H0', '00'],)

Expected Output: []

Explanation: If the flower in row 0 is placed at column 1, the house at (0, 0) becomes adjacent to two flowers: (0, 1) and (1, 0). So no valid grid exists.

Hints

Because each row and each column must contain exactly one flower, a solution corresponds to choosing a permutation of columns.
For each candidate permutation, check two things: no flower lands on a house, and every house sees exactly one adjacent flower.

Part 2: Delete a Directory and All Descendants

You need to simulate recursive directory deletion. A directory can be deleted only after all of its children have already been deleted. You are given the filesystem as two parallel arrays: directories[i] is a directory path, and children_lists[i] is the list of its immediate children in the order returned by getChildrenPaths. Any child path that does not appear in directories is a file. An empty child list means the directory is empty. Implement a function that returns the exact order of deleteFile calls needed to delete the given path and everything below it. If the path is a file, return a one-element list containing that file. If the path does not exist anywhere in the filesystem, return an empty list.

Constraints

0 <= len(directories) == len(children_lists) <= 200000
The total number of child-path entries across all lists is at most 200000
Directory paths in directories are unique
The filesystem structure is acyclic
Each child path has at most one parent

Examples

Input: (['/root', '/root/a', '/root/b'], [['/root/a', '/root/file.txt', '/root/b'], ['/root/a/x'], []], '/root')

Expected Output: ['/root/a/x', '/root/a', '/root/file.txt', '/root/b', '/root']

Explanation: Delete descendants first, preserving child order: subtree /root/a, then /root/file.txt, then /root/b, and finally /root.

Input: (['dir'], [[]], 'dir')

Expected Output: ['dir']

Explanation: An empty directory can be deleted immediately.

Input: (['dir'], [['dir/file.txt']], 'dir/file.txt')

Expected Output: ['dir/file.txt']

Explanation: The target is already a file, so only one delete call is needed.

Input: (['dir'], [['dir/file.txt']], 'missing')

Expected Output: []

Explanation: The path does not appear as a directory or as any listed child, so it does not exist in this filesystem.

Input: (['a', 'a/b', 'a/b/c'], [['a/b'], ['a/b/c', 'a/b/d'], []], 'a/b')

Expected Output: ['a/b/c', 'a/b/d', 'a/b']

Explanation: Delete the empty directory a/b/c, then the file a/b/d, and then delete a/b itself.

Hints

A directory can only be deleted after its contents, so the required order is a postorder DFS traversal.
To avoid recursion-depth issues on deep directory trees, use an explicit stack with a visited/expanded flag.

Quick Overview

This question evaluates combinatorial constraint-satisfaction and permutation/matching skills for the flower-placement grid alongside filesystem traversal and recursive versus iterative deletion strategies for the directory-deletion task.