I recently interviewed with Google for an L4 position. I successfully implemented about 95% of the solution correctly and explained the remaining part to the interviewer. However, some optimization was missing.

Do you know the chances of getting a "Hire" status in the first elimination round?

I’ll share the questions with you all soon.

Here is the question-

Problem Statement:
You are given an N × N matrix, where:

Some cells are occupied by houses (H).
Some cells are empty (.).
Your task is to plant trees (T) adjacent to the houses, following these rules:

A tree (T) can be planted only in an empty cell adjacent (up, down, left, or right) to a house (H).
Each row and column can have at most one tree (T).

You need to maximize the number of trees planted while following the above constraints.
Input:
An N × N grid consisting of H (house) and . (empty cell).
Output:
The updated matrix, where trees (T) are planted following the given rules.