Solve Two Array Optimization Problems
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
This online assessment included two coding problems.
**Problem 1: Maximize protected city population**
You are given:
- an integer `n`
- an array `population` of length `n`, where `population[i]` is the population of city `i + 1`
- a binary string `unit` of length `n`, where `unit[i] = '1'` means city `i + 1` initially has one security unit, and `unit[i] = '0'` means it does not
For each city `i > 1` that initially has a security unit, you may either keep that unit in city `i` or move it left to city `i - 1`. Each unit can be moved at most once, and moving a unit removes it from its original city. A city is considered protected if it has at least one security unit after all moves. If multiple units end up in the same city, that city's population is still counted only once.
Return the maximum possible sum of populations of all protected cities.
Example:
- `n = 5`
- `population = [10, 5, 8, 9, 6]`
- `unit = "01101"`
One optimal strategy is to move the unit from city 2 to city 1, keep the unit at city 3, and move the unit from city 5 to city 4. The protected cities are 1, 3, and 4, so the answer is `10 + 8 + 9 = 27`.
**Problem 2: Minimize total cost to remove all ones**
You are given a binary array `product` of length `n` and an integer `k`, where `product[i] = 1` represents variant B and `product[i] = 0` represents variant A.
You must turn every `1` into `0` using a sequence of operations. In one operation:
1. Choose a subarray `[l, r]` of length exactly `k`.
2. Pay a cost equal to the sum of the current values in `product[l..r]`.
3. Choose one index `p` in `[l, r]` such that `product[p] = 1`, and set `product[p] = 0`.
The array changes after each operation, so the cost of later operations depends on earlier choices. Find the minimum total cost required to convert all `1`s to `0`s. You may assume `1 <= k <= n`.
Quick Answer: This question evaluates a candidate's competency in array manipulation, combinatorial optimization, and decision-making under constraints, emphasizing skills like interval reasoning, greedy selection, and dynamic planning.
Part 1: Maximize Protected City Population
You are given n cities numbered from 1 to n. City i has population population[i - 1]. You are also given a binary string unit of length n, where unit[i - 1] = '1' means city i initially has one security unit. For every city i > 1 that initially has a unit, you may either keep that unit in city i or move it exactly one city to the left, to city i - 1. Each unit can be moved at most once, and moving it removes it from its original city. After all choices are made, a city is protected if it has at least one unit. If multiple units end up in the same city, that city's population is counted only once. Return the maximum total population of all protected cities.