Simulate Rot Spreading Through an Orchard Grid Over a Number of Days
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
An orchard is a grid of characters: `'R'` is a rotten tree, `'H'` is a healthy tree, and `'-'` is empty ground. Every day, each rotten tree turns every healthy tree directly above, below, left or right of it rotten, and all of these changes happen at the same time. Given the orchard and a number of days, return the orchard after that many days.
### Function Signature
```python
def orchard_after_days(orchard: list[str], days: int) -> list[str]:
```
### Rules
- Day 0 is the given orchard. The orchard after day `d + 1` is computed from the orchard after day `d`: every `'H'` cell with at least one `'R'` cell directly above, below, left or right of it becomes `'R'`, and every other cell keeps its character.
- A tree that turns rotten during a day starts spreading rot only on the following day.
- Diagonal cells are not neighbors, and rot does not wrap around the edges of the grid.
- Empty ground never changes and does not pass rot along.
- With `days = 0`, return the orchard unchanged.
- Return a list of strings with the same number of rows, in the same order, each of the same length as in the input.
### Constraints
- `1 <= len(orchard) <= 200`
- `1 <= len(orchard[r]) <= 200`, and all rows have the same length
- every character is `'R'`, `'H'` or `'-'`
- `0 <= days <= 10^9`
### Examples
**Example 1**
```text
Input: orchard = ["RH-",
"HHH",
"-HH"], days = 1
Output: ["RR-",
"RHH",
"-HH"]
```
The rotten tree in the top-left corner rots its right neighbor and the tree below it.
**Example 2**
```text
Input: orchard = ["RH-",
"HHH",
"-HH"], days = 3
Output: ["RR-",
"RRR",
"-RH"]
```
Day 2 rots the center tree. Day 3 rots the right tree of the middle row and the middle tree of the bottom row. The bottom-right tree would rot on day 4.
**Example 3**
```text
Input: orchard = ["H-R"], days = 5
Output: ["H-R"]
```
The empty ground separates the healthy tree from the rotten one, so it never rots.
Overview: A grid simulation question about an orchard of rotten trees, healthy trees and empty ground, where each day rot spreads at once from every rotten tree to the healthy trees directly beside it. It asks for the orchard after a given number of days and tests simultaneous updates, blocked cells and very large day counts.
Read the full Capital One Software Engineer interview experience this question came from
