How should I practice Alien Defense Turret Placement?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Bloomberg LP onsite interview problems in FastPrep.

Is Alien Defense Turret Placement associated with Bloomberg LP?

FastPrep tags this as a Bloomberg LP onsite interview coding practice problem when the problem catalog has that company and stage context.

Alien Defense Turret Placement

Bloomberg LP● MediumNEW GRADONSITE INTERVIEW

Learn

Problem statement

The binary matrix grid represents an alien-defense zone. A value of 1 is a house and 0 is an empty cell.

You may place one turret on any cell, including a cell containing a house. A turret at (r, c) protects every house at (hr, hc) whose Manhattan distance satisfies |r - hr| + |c - hc| <= k.

Return the maximum number of houses that one turret can protect.

Function

maxProtectedHouses(grid: int[][], k: int) → int

Examples

Example 1

grid = [[1,0,0],[0,1,0],[0,0,1]]k = 2return = 3

A turret at the center protects all three diagonal houses because each is within Manhattan distance two.

Example 2

grid = [[1,0,1,0,1]]k = 1return = 2

A turret on the empty cell between two neighboring houses is distance one from both, so it protects two houses.

Example 3

grid = [[0,0],[0,0]]k = 5return = 0

The zone contains no houses.

Constraints

1 <= grid.length <= 200.
1 <= grid[i].length <= 200, and all rows have the same length.
grid[i][j] is 0 or 1.
0 <= k <= 400.