Medium

Amazon-styleMicrosoft-style

Minimum Time for Contamination to Spread DSA Interview

Given a grid where each cell is empty, clean, or already contaminated, find the minimum time for all clean cells to become contaminated, spreading one step per unit time to adjacent cells, or report it is impossible.

Mock Interview with AI

1. Problem Statement

You are given a grid where each cell is empty (0), clean (1), or contaminated (2). Every minute, contamination spreads to horizontally or vertically adjacent clean cells. Return the minimum number of minutes for every clean cell to become contaminated, or -1 if some clean cell can never be reached.

2. Live Coding Format

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

3. Key Focus Areas

1
Problem clarification and contract
2
Approach exploration and optimality
3
Think-aloud communication and pacing
4
Implementation correctness
5
Code quality and language fluency
6
Handwritten tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

✓Clarify cell states, spread direction rules, and impossible-case behavior before coding.
✓Explain a naive round-by-round full-grid rescan baseline and improve to a multi-source BFS.
✓Think aloud while implementing careful level-by-level traversal.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and handle a bounded follow-up modification.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies that spread is 4-directional, confirms empty cells block spread and do not need to be contaminated, and asks what to return when there are no clean cells at all.
✓Confirms whether multiple initially contaminated cells can exist simultaneously.

Staff-level signals

◆Raises whether the grid could be very large and whether early termination once all clean cells are contaminated matters for performance.

Common red flags

×Codes immediately while assuming only one initial contamination source without confirming.

Approach exploration and optimality

20%

Senior signals

✓Explains a naive baseline that rescans the entire grid each simulated minute looking for newly adjacent clean cells, identifies its repeated-full-scan bottleneck, and improves to a multi-source BFS seeded with all initially contaminated cells simultaneously.
✓Explains why processing the BFS level by level directly yields the minute count, rather than tracking time some other way.

Staff-level signals

◆Discusses how to detect the impossible case efficiently by comparing the total clean-cell count against the number actually reached.

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.
×Proposes running a separate BFS from each contaminated source independently, missing that simultaneous multi-source BFS is needed for correct timing.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates the level-by-level BFS timing while implementing.
✓Paces the core solution to leave time for validation and the follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.

Implementation correctness

25%

Senior signals

✓Implements a correct multi-source BFS that seeds the queue with all initially contaminated cells, tracks elapsed minutes per level, and verifies every clean cell was reached before returning the elapsed time.
✓Handles no clean cells (0 minutes), no initial contamination with clean cells present (-1), and clean cells isolated by empty cells (-1).
✓Provides a convincing invariant argument for why BFS level count equals elapsed minutes.

Common red flags

×Uses single-source BFS or DFS in a way that miscounts simultaneous spread timing.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with a clear queue structure, boundary checks, and a defined remaining-clean-cell counter.

Common red flags

×Contains off-by-one errors in minute counting or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom, including a drawn grid with minute annotations.
✓Covers no clean cells, isolated clean cells, multiple simultaneous sources, and empty cells acting as barriers.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States time complexity proportional to the number of cells and auxiliary space for the queue, comparing it with the repeated-full-scan baseline.

Staff-level signals

◆Discusses memory usage for very large grids and whether the queue size could be bounded more tightly.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

Rescanning the entire grid each simulated minute is simple to reason about but costs time proportional to cells times minutes elapsed.
Multi-source BFS seeded with all initial contamination simultaneously achieves linear time in the number of cells.
Running independent single-source BFS per source and combining results is more complex and does not directly give correct simultaneous-spread timing without extra merging logic.

Practice follow-up questions

1.Coding follow-up: modify the solution so that certain cells act as permanent barriers that block spread even though they are not empty, and recompute the minimum time under this new constraint.
2.Verbal extension: how would the approach change if new contamination sources could appear at fixed later minutes during the simulation?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

Grid TraversalMulti-Source BFSQueuesComplexity Analysis