PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • hard
  • Amazon
  • Coding & Algorithms
  • Software Engineer

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.

Constraints

  • 0 <= n <= 200000
  • len(population) = n
  • len(unit) = n, and each character of unit is '0' or '1'
  • 0 <= population[i] <= 10^9
  • The answer fits in a 64-bit signed integer

Examples

Input: (5, [10, 5, 8, 9, 6], '01101')

Expected Output:

Explanation: 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. Protected cities are 1, 3, and 4, for a total of 10 + 8 + 9 = 27.

Input: (0, [], '')

Expected Output:

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

Input: (1, [7], '1')

Expected Output:

Explanation: The single unit cannot move left, so city 1 stays protected.

Input: (4, [5, 100, 4, 3], '0110')

Expected Output:

Explanation: Move the unit from city 2 to city 1 and move the unit from city 3 to city 2. Protected cities are 1 and 2, giving 5 + 100 = 105.

Input: (6, [10, 1, 7, 2, 9, 3], '010101')

Expected Output:

Explanation: Move the units from cities 2, 4, and 6 to cities 1, 3, and 5. The total is 10 + 7 + 9 = 26.

Hints

  1. Process cities from left to right. Once you decide what happens to the unit at city i, the final status of city i - 1 is fixed.
  2. A small DP state is enough: track whether the current city is already protected by decisions made so far.

Part 2: Minimize Total Cost to Remove All Ones

You are given a binary array product and an integer k. In one operation, you must choose a subarray of length exactly k, pay a cost equal to the current sum of values inside that subarray, then choose one index in that subarray that currently contains 1 and change it to 0. The array changes after every operation, so future costs also change. Return the minimum total cost needed to turn every 1 into 0. This version of the problem guarantees that the number of 1s is small enough for an exact state-compression solution.

Constraints

  • 1 <= len(product) <= 50
  • 1 <= k <= len(product)
  • product[i] is either 0 or 1
  • The number of 1s in product is at most 15

Examples

Input: ([1, 0, 1, 1], 3)

Expected Output:

Explanation: Remove the 1 at index 2 first with cost 2, then the remaining two 1s can each be removed with cost 1.

Input: ([1], 1)

Expected Output:

Explanation: The only valid subarray is the whole array, whose sum is 1.

Input: ([0, 0, 0], 2)

Expected Output:

Explanation: There are no 1s to remove.

Input: ([1, 0, 1, 0, 1], 3)

Expected Output:

Explanation: First remove the middle 1 using the subarray [1, 3] (0-based window [1..3]), which has sum 1. Then the two remaining 1s each cost 1.

Input: ([1, 1, 0, 1], 4)

Expected Output:

Explanation: Since k equals the full array length, every operation uses the entire array. The sums are 3, then 2, then 1.

Hints

  1. Only the positions that currently contain 1 matter. Compress those positions and represent a state by a bitmask of remaining ones.
  2. For a fixed state and a fixed 1, its immediate removal cost is the minimum number of remaining 1s among all length-k windows that contain it.
Last updated: Apr 19, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement Datacenter Router Commands - Amazon (hard)
  • Replace Delimited Tokens in a String - Amazon (medium)
  • Minimize Circular Redistribution Cost - Amazon (medium)
  • Find the Most Common Visit Pattern - Amazon (hard)
  • Maximize Value Under a Budget - Amazon (medium)