Choose One Blocker Removal for the Fastest Grid Signals
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A rectangular city grid contains sources `S`, blockers `B`, targets `T`, and empty cells `.`. At time zero, every source begins sending a signal. A signal spreads one cell per unit of time in the four orthogonal directions and cannot enter a blocker.
Before propagation begins, you may remove at most one blocker, turning that one cell into an empty cell. Choose the removal, if any, that minimizes the time until every target receives a signal.
### Input
- `grid`: an array of equal-length strings using the four cell symbols above.
### Output
Return `[minimum_time, removed_row, removed_column]` using zero-based coordinates and the following deterministic practice conventions:
- If removing nothing attains the minimum time, prefer that choice and return `-1` for both coordinates.
- Otherwise, among equally good removals, choose the smallest row, then the smallest column.
- If no permitted choice reaches every target, return `[-1, -1, -1]`.
### Constraints and Edge Cases
- For this practice version, the grid has between `1` and `30` rows and between `1` and `30` columns.
- There is at most one removed blocker in the entire grid; different signal paths cannot each remove their own blocker.
- Removal happens before time zero and has no propagation-time cost.
- Signals may pass through sources, targets, and empty cells, including the removed blocker.
- If there are no targets, return `[0, -1, -1]`.
- If targets exist but there are no sources, return `[-1, -1, -1]`.
### Example 1
```text
grid = ["SBT"]
output = [2, 0, 1]
```
Removing the middle blocker allows the signal to reach the target in two steps.
### Example 2
```text
grid = ["SBT", "BBB", "TBS"]
output = [-1, -1, -1]
```
One removal can connect a source to one of the targets, but no single shared removal makes both targets reachable.
Overview: Choose at most one global blocker removal to minimize the time for all grid targets to receive signals, with deterministic tie-breaking.
Read the full Google Software Engineer interview experience this question came from
A rectangular city grid contains sources `S`, blockers `B`, targets `T`, and empty cells `.`. At time zero, every source begins sending a signal. A signal spreads one cell per unit of time in the four orthogonal directions and cannot enter a blocker.
Before propagation begins, you may remove at most one blocker, turning that one cell into an empty cell. Choose the removal, if any, that minimizes the time until every target receives a signal.
### Input
- `grid`: an array of equal-length strings using the four cell symbols above.
### Output
Return `[minimum_time, removed_row, removed_column]` using zero-based coordinates and the following deterministic practice conventions:
- If removing nothing attains the minimum time, prefer that choice and return `-1` for both coordinates.
- Otherwise, among equally good removals, choose the smallest row, then the smallest column.
- If no permitted choice reaches every target, return `[-1, -1, -1]`.
### Constraints and Edge Cases
- For this practice version, the grid has between `1` and `30` rows and between `1` and `30` columns.
- There is at most one removed blocker in the entire grid; different signal paths cannot each remove their own blocker.
- Removal happens before time zero and has no propagation-time cost.
- Signals may pass through sources, targets, and empty cells, including the removed blocker.
- If there are no targets, return `[0, -1, -1]`.
- If targets exist but there are no sources, return `[-1, -1, -1]`.
### Example 1
```text
grid = ["SBT"]
output = [2, 0, 1]
```
Removing the middle blocker allows the signal to reach the target in two steps.
### Example 2
```text
grid = ["SBT", "BBB", "TBS"]
output = [-1, -1, -1]
```
One removal can connect a source to one of the targets, but no single shared removal makes both targets reachable.
Constraints
- The rectangular grid has 1 through 30 rows and columns, with equal-length strings using only S, B, T and period.
- All sources propagate simultaneously at time zero; one orthogonal step costs one unit and every non-blocker cell is traversable.
- At most one blocker is removed globally before propagation, with no removal-time cost; all signal paths share that fixed choice.
- Minimize the maximum target first-arrival time. Prefer no removal on an optimal tie, then the smallest removal row and column.
- No targets returns [0,-1,-1]. No permitted choice reaching all targets returns [-1,-1,-1], including targets with no source.
Examples
Input: (['SBT'],)
Expected Output: [2, 0, 1]
Explanation: Published sample 1: removing the middle blocker creates the two-step route.
Input: (['SBT', 'BBB', 'TBS'],)
Expected Output: [-1, -1, -1]
Explanation: Published sample 2: the two targets require incompatible removals; no single globally shared blocker suffices.
Community answers
Answer by chandanagrawal23
#include
using namespace std;
int m, n;
vector> sources;
vector> targets;
int bfs(vector& grid, int removeR, int removeC)
{
vector> dist(m, vector(n, -1));
queue> q;
for(auto [r, c] : sources)
{
dist[r][c] = 0;
q.push({r, c});
}
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while(!q.empty())
{
auto [r, c] = q.front();
q.pop();
for(int k = 0; k < 4; k++)
{
int nr = r + dr[k];
int nc = c + dc[k];
if(nr < 0 || nr >= m || nc < 0 || nc >= n)
continue;
if(dist[nr][nc] != -1)
continue;
if(grid[nr][nc] == 'B' &&
!(nr == removeR && nc == removeC))
continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
int maxTime = 0;
for(auto [r, c] : targets)
{
if(dist[r][c] == -1)
return INT_MAX;
maxTime = max(maxTime, dist[r][c]);
}
return maxTime;
}
vector solve(vector& grid)
{
m = grid.size();
n = grid[0].size();
vector> blockers;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(grid[i][j] == 'S')
sources.push_back({i, j});
else if(grid[i][j] == 'T')
targets.push_back({i, j});
else if(grid[i][j] == 'B')
blockers.push_back({i, j});
}
}
if(targets.empty())
return {0, -1, -1};
if(sources.empty())
return {-1, -1, -1};
int bestTime = bfs(grid, -1, -1);
int bestR = -1;
int bestC = -1;
for(auto [r, c] : blockers)
{
int time = bfs(grid, r, c);
if(time < bestTime)
{
bestTime = time;
bestR = r;
bestC = c;
}
}
if(bestTime == INT_MAX)
return {-1, -1, -1};
return {bestTime, bestR, bestC};
}
int main()
{
vector grid = {
"SBT"
};
vector ans = solve(grid);
cout << ans[0] << " "
<< ans[