Cellular Infection Spreading: Interview with a FAANG Engineer

Cellular Infection Spreading

Watch someone solve the cellular infection spreading problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type
Cellular Infection Spreading

Interview question
Given an m×n grid where each cell is either healthy (0) or infected (1), simulate the spread of a disease that propagates simultaneously each day. A healthy plant becomes infected when at least a given threshold of its 8 neighboring cells (including diagonals) are currently infected. Infected plants stay infected forever. Return the number of days until no new infections occur - or 0 if the grid is already stable. The grid can be up to 200×200, and the threshold is guaranteed to be between 1 and 8.

Interview Feedback

Feedback about Winged Unicorn (the interviewee)
Advance this person to the next round? No

How were their technical skills? 3/4

How was their problem solving ability? 3/4

What about their communication ability? 3/4

Strengths & What Went Well

  1. BFS + queue idea. Close to a correct solution.
  2. Good communication. For example, use the whiteboard to explain the candidate’s solution idea. For another example, asked good clarification questions.

Areas for Improvement

  1. This question has two working solutions.

Solution 1: Use a queue to keep track of the infected cells to be processed. Each element in the queue is a tuple (x,y,day). Keep a counter for each cell counting how many neighbors are infected...

Solution 2: Keep the contour of the infected cells. Keep a counter for each cell like solution 1.

Both solutions have O(mn) time and O(mn) space. m=#rows, n=#columns.

  1. Focus on coding speed. Ideally, part 1 is solved within 25 minutes.

Advice for Future Interviews

  1. Use Python. Python saves typing. Good for interviews.
  2. Think over the solution carefully before writing code. Avoid write-erase-rewrite.
  3. Practice these fundamental data structure and algorithm questions on leetcode. Focus on speed and correctness. Use ChatGPT or Gemini to help understand the solutions.
  4. If you have an upcoming interview for a company, look up the leetcode questions under this company’s tag. Or read recent interview experiences for that company people shared online.

Open Notes

Here is the questions I planned to ask:
Part 2: Immunity
Now, immune plants are added to the grid. You are given an m x n grid where each plant can be healthy (0), infected (1), or immune (2).
...

Constraints:

Each cell is 0, 1, or 2

Example 1:

Input:
grid = [[1,0,0],
[0,2,0],
[0,0,0]],
threshold = 1
Output: 3

Example 2:

Input:
grid = [[1,1],[2,0]],
threshold = 2
Output: 1

Example 3:

Input:
grid = [[1,2,0],[2,2,0],[0,0,0]],
threshold = 2
Output: 0

...

Part 3: Recovery

...

Part 4: Death

...

Part 5: Burn nothing, a row, or column

...

Interview Transcript

Winged Unicorn: Hello.
Dapper Stingray: Hello. Can you hear me? Yeah, I can hear you. Great.
...

Dapper Stingray: I'm sure you can get them.
Winged Unicorn: Yeah, well, thank you very much, and thanks for making the time for this interview.
...

Dapper Stingray: I think we can maybe start the questions.
...

Dapper Stingray: Yeah. Can you read over the solution by several passes and to see if everything works fine? If you believe it's working, we can try the test, the sample test cases.