HardCoding

Contain Virus

Asked at

Flipkart

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Find every active infected region.
02For each, collect threatened uninfected cells and wall count.
03Choose the region threatening the most cells.
04Quarantine it and spread all other regions simultaneously.
05Repeat until no region can spread.

Reference answer

Each day, DFS or BFS every uncontained infected component. For a component, collect its distinct adjacent zero cells in a set and count every infected-to-zero edge as one required wall. Select the component with the largest threatened set, mark its cells quarantined, and convert the threatened cells of every other component to infected simultaneously. Repeat until no active region has a threatened cell. Sets matter because several cells in one region can touch the same zero, while wall count deliberately counts each touching edge. Do not spread one region before examining the others, since the specification is a daily simultaneous update. With an R by C grid, repeated simulations are commonly bounded by O((RC) squared) time in the worst case and O(RC) space.

Then expect these follow-ups

Why must threatened cells be a set?
Tests: correctness reasoning
How would you return the walls built per day?
Tests: implementation extension

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question