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
Explanation: Move the guard from city 2 to city 1, and move the guard from city 5 to city 4. The guarded cities become 1, 3, and 4, so the protected population is 10 + 8 + 9 = 27.
Input: ([10, 1, 2, 3], "0111")
Expected Output: 15
Explanation: The block of guards at cities 2..4 is preceded by city 1 with population 10. The best choice is to leave city 2 (population 1) unguarded by moving the guard from city 2 to city 1. Total protected population is 10 + 2 + 3 = 15.
Input: ([4, 7, 2], "111")