Simulate Orchard Rot Spread
Reported by candidates from ZipRecruiter's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The ZipRecruiter OA reported in September 2024 looks like a grid simulation, but it's really a multi-source BFS wearing a costume. Rotten trees spread to orthogonal neighbors each day, and you return the grid after exactly that many days. Days can hit 100000, so a naive day-by-day rescan will bite you. If you blank on the frontier idea during the live assessment, StealthCoder runs invisibly as a safety net and gives you the approach while you type. Read the pattern first, though. It's short.
The problem
An orchard is a rectangular array of strings using - for empty, T for healthy trees, and R for rotten trees. Each day is synchronous: trees rotten at the start of the day infect orthogonally adjacent healthy trees; newly rotten trees begin spreading the next day. Return the orchard after exactly days days. Function simulateOrchard(orchard: String[], days: int) → String[] Examples Example 1 orchard = ["RT-","TTT"] days = 1 return = ["RR-","RTT"] Only trees adjacent to the original rotten tree change on day one. Example 2 orchard = ["R-T","TTT"] days = 0 return = ["R-T","TTT"] Zero days leaves the orchard unchanged. Constraints 1 <= rows,columns <= 200 0 <= days <= 100000
Reported by candidates. Source: FastPrep
Pattern and pitfall
Treat every starting R as a source and push them all into a queue at distance 0. Run BFS level by level. Each level is one day, and newly rotten trees only spread on the next level, which matches the synchronous rule. Stop after the given number of levels or when the queue empties. The trick is that days up to 100000 is a red herring. The grid is at most 200 by 200, so the spread ends within 40000 steps at most, and BFS ends sooner when the frontier dies. The common pitfall is mutating the grid in place while scanning, so a tree rotten today infects a neighbor today. Process by queue size per level to avoid that. Empty cells block spread, and zero days returns the input unchanged. If the live OA rattles you, StealthCoder is the hedge that covers the level-by-level bookkeeping.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Simulate Orchard Rot Spread cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as rotting oranges. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass ZipRecruiter's OA.
ZipRecruiter reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Simulate Orchard Rot Spread FAQ
What's the real trick in the ZipRecruiter orchard rot problem?+
It's multi-source BFS. Put all initial rotten trees in the queue together, then process one level per day. Each level only infects healthy neighbors, and those new rotten trees wait until the next level to spread. That handles the synchronous rule cleanly.
Do I need to loop 100000 days?+
No. The grid is at most 200 by 200, so the rot stops spreading long before 100000 days. BFS ends when the queue is empty. Cap the loop at the given days and break early if nothing new rots.
Why not just rescan the grid each day?+
You can, but it's slow. Each rescan costs rows times columns, and repeating it for many days adds up. You also risk infecting in place within the same day. BFS touches each cell once and keeps the day boundaries clear.
What edge cases should I test?+
Test days equal to 0, which returns the grid unchanged. Test a grid with no R, so nothing changes. Test empty cells blocking spread, a single-cell grid, and multiple rotten sources reaching the same tree on the same day.
How do I prepare for this in 48 hours?+
Write multi-source BFS on a grid once from scratch, the rotting oranges style. Practice the per-level loop using the queue size at the start of each level. Then test the zero-day and blocked-cell cases. That covers this problem.