Contain Virus

Contain Virus

What is this problem about?

The Contain Virus interview question is a complex simulation problem. You are given a 2D grid where 1 represents an infected cell, 0 represents an uninfected cell, and 2 represents a firewall. Every day, the virus spreads to all adjacent uninfected cells. However, you can build a firewall around exactly one infected region per day. You must choose the region that, if left alone, would infect the most uninfected cells the next day. The goal is to return the total number of firewalls built.

Why is this asked in interviews?

This is a HARD difficulty problem often asked by Google. The Contain Virus coding problem tests a candidate's ability to coordinate multiple complex algorithms: BFS/DFS for region detection, Simulation for the daily spread, and Greedy logic for choosing which region to quarantine. It’s a test of high-level coding organization and state management.

Algorithmic pattern used

This problem utilizes the Array, Matrix, Breadth-First Search, Depth-First Search, Simulation interview pattern.

1. Use BFS/DFS to identify all disjoint infected regions.
2. For each region, calculate:
   • Its "threat level" (how many unique uninfected cells it will reach).
   • The number of walls needed to surround it.
3. Pick the region with the highest threat. Add its wall count to the total and mark it as "contained" (value 2).
4. For all other regions, simulate their spread to adjacent uninfected cells.
5. Repeat until no more infections can spread.

Example explanation

Imagine a grid with two clusters of virus.

• Cluster A can infect 5 new cells and needs 10 walls.
• Cluster B can infect 8 new cells and needs 12 walls.

1. You pick Cluster B because 8 > 5.
2. Build 12 walls. Cluster B is now blocked.
3. Cluster A spreads, infecting those 5 cells.
4. Next day, repeat the process for Cluster A and any other new clusters.

Common mistakes candidates make

• Miscounting threat: Counting the same uninfected cell multiple times if it is adjacent to multiple infected cells within the same region. You must use a Set to track unique targets.
• Incomplete Containment: Not marking a contained region correctly, allowing it to "spread" in the simulation logic.
• Efficiency: Not being careful with visited sets, leading to redundant BFS calls on the same grid multiple times.

Interview preparation tip

Break large simulation problems into helper functions like getRegions(), buildWall(), and spreadVirus(). This keeps your logic clean and makes it easier to debug during the interview.