Maximize protected population with one-step guard shifts
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
There are `n` cities in a line (1-indexed). You are given:
- `population[1..n]`: population of each city
- `unit`: a binary string of length `n`, where `unit[i] = '1'` means city `i` initially has a security guard, and `unit[i] = '0'` means it does not.
A guard may be moved **at most once**. A move consists of shifting a guard from city `i` to city `i-1` (one step left), only if:
- `i > 1`, and
- city `i-1` currently has no guard.
You may perform moves in any order.
After all moves, the “protected population” is the sum of populations of the cities that end up with a guard.
Compute the maximum protected population achievable.
Example:
- `population = [10, 5, 8, 9, 6]`
- `unit = "01101"`
Quick Answer: This question evaluates the ability to reason about constrained local moves and optimize a numerical objective over an array, testing skills in array manipulation, combinatorial optimization, and interpretation of binary state representations.
There are n cities in a line. In code, population[i] is the population of city i+1, and unit[i] is either '1' (the city initially has a guard) or '0' (it does not).
Each guard may be moved at most once. A move shifts a guard from city i to city i-1, but only if:
- i > 1, and
- city i-1 is empty at the moment of the move.
You may perform moves in any order.
After all moves, the protected population is the sum of the populations of the cities that end up with a guard.
Return the maximum protected population that can be achieved.
Example: for population = [10, 5, 8, 9, 6] and unit = "01101", the answer is 27.
Constraints
- 0 <= n <= 2 * 10^5
- len(population) == len(unit)
- 0 <= population[i] <= 10^9
- unit contains only '0' and '1'
Examples
Input: ([10, 5, 8, 9, 6], "01101")
Expected Output: 27
Input: ([10, 1, 2, 3], "0111")
Expected Output: 15
Input: ([4, 7, 2], "111")
Expected Output: 13
Input: ([6, 1, 5, 4, 9, 2], "101101")
Expected Output: 24
Input: ([], "")
Expected Output: 0
Input: ([5], "0")
Expected Output: 0
Input: ([5], "1")
Expected Output: 5
Input: ([7, 7, 0, 8, 9], "01111")
Expected Output: 31
Input: ([100, 1, 1], "011")
Expected Output: 101
Hints
- Look at maximal consecutive blocks of '1's. Blocks separated by zeros can be optimized independently.
- If a block of guards is preceded by an empty city, only a prefix of that block can shift left. Think about which single city in that extended segment could be left unguarded.