How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

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")

Expected Output: 13

Explanation: All cities already have guards, and the first city has no left neighbor. No move can improve the result, so the answer is 4 + 7 + 2 = 13.

Input: ([6, 1, 5, 4, 9, 2], "101101")

Expected Output: 24

Explanation: City 1 stays guarded. For the block at cities 3..4, it is best to leave city 2 unguarded, so cities 3 and 4 remain guarded. For city 6, moving its guard to city 5 is better. Total = 6 + 5 + 4 + 9 = 24.

Input: ([], "")

Expected Output: 0

Explanation: There are no cities, so the protected population is 0.

Input: ([5], "0")

Expected Output: 0

Explanation: There is one city but no guard, so no population is protected.

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.

Quick Overview

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.