Katkat
Back

Maximize protected population with one-step guard shifts

AmazonSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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