Amazon·Software Engineer·Online Assessment (OA)·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

Got an OA from Amazon for a SWE role and the problem was a greedy/DP thing about moving security units left to maximize protected city population. Not the hardest problem I've seen from them but it took me longer than I'd like to admit to nail down the logic.

Questions Asked (1)

Given n cities in a line, each with a population value, and an array indicating which cities start with a security unit, find the maximum total protected population. A unit can either stay in its city or move one step left. Each city only needs one unit to be considered protected, extras don't help.

Algorithms & Data Structures

Author's notes

Spent the first few minutes overcomplicating it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a greedy matching between security units and cities, where each unit can cover its own city or the city immediately to its left. Process cities from left to right, and for each city, if it has a unit, decide whether to use it to protect the current city or save it for the next city based on which gives more benefit. Alternatively, use dynamic programming with states representing whether the current city is protected and whether a unit is available to move right.

Pro tip: Clarify that each city only needs one unit, so extra units are redundant; this simplifies the greedy choice. Also, mention that the problem is equivalent to maximum bipartite matching but can be solved in O(n) with greedy or DP, which is optimal.

1. Understand the problem and constraints

Restate the problem: n cities in a line, each with population, and an array indicating initial security units. A unit can stay or move one step left. Each city needs at most one unit. Goal: maximize total protected population.

2. Identify the greedy choice

Observe that processing from left to right, a unit in city i can protect city i or i-1. If city i-1 is unprotected and has a unit, it's always better to use that unit for i-1 rather than saving it for i, because i can be protected by its own unit or a unit from i+1.

3. Design the algorithm

Use a greedy approach: iterate through cities, keep track of available units. For each city, if it has a unit and the previous city is unprotected, move the unit left to protect the previous city; otherwise, use the unit to protect the current city if unprotected. Alternatively, use DP with states (protected, unit available).

4. Handle edge cases and validate

Consider cases where multiple units are in the same city, no units, or units at the ends. Ensure the algorithm correctly handles moving units left only (not right). Test with small examples to verify.

5. Analyze complexity and optimize

The greedy solution runs in O(n) time and O(1) extra space. Explain why it's optimal and discuss potential DP alternative if needed.

Key Points to Mention

Greedy strategy: process left to right, prioritize protecting the left city if it's unprotected and has a unit.
Each city needs at most one unit, so extra units are redundant.
Units can only move left, not right, which affects the decision order.
Time complexity O(n) and space O(1) for greedy; DP alternative with O(n) space.
Proof of optimality: exchange argument showing that moving a unit left when possible never hurts.
Edge cases: units at first city (can't move left), multiple units in one city, no units.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.