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

Intermediate

Jun 2026

Summary

Amazon SWE online assessment with a greedy array problem about relocating security units to maximize protected population. Pretty straightforward once you see the pattern, but the edge cases in the examples took me a minute to work through.

Questions Asked (1)

Given an array of city populations and a binary string indicating which cities have a security unit, you can move any unit one step left (at most once per unit). A city is protected if it has a unit after all moves. Return the maximum total population of protected cities.

Algorithms & Data Structures

Author's notes

My first instinct was greedy from left to right, which was wrong.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a greedy assignment where each city with a unit can either stay or move left to cover an adjacent city. Process cities from left to right, prioritizing covering the highest population city that can be protected without sacrificing future opportunities. Use a dynamic programming or greedy strategy to maximize the sum of populations of covered cities.

Pro tip: Clarify that each unit can move at most once and only left, so a unit at index i can cover i or i-1. Emphasize that you must avoid double-counting and ensure each unit is used at most once, which is a common pitfall.

1. Understand the movement constraints

Each unit can either stay in its original city or move one step left, covering at most two possible cities. No unit can move right or more than one step.

2. Identify coverage options per unit

For each unit at index i, it can protect city i (if it stays) or city i-1 (if it moves left). If i=0, it can only stay.

3. Choose a strategy: greedy or DP

A greedy approach from left to right works: at each city, decide whether to use an available unit to cover it, preferring to cover higher populations when possible. Alternatively, use DP with states tracking whether the current city is covered by a unit from the right.

4. Implement and handle edge cases

Iterate through cities, maintaining a flag for whether a unit is available to move left. Handle cases where multiple units compete for the same city, and ensure each unit is used only once.

5. Verify with examples

Test with small cases like populations [10,20,30] and units '101' to ensure the algorithm picks the optimal set of protected cities.

Key Points to Mention

Greedy choice: prioritize covering the city with the highest population when a unit can cover it without blocking a better future option.
Dynamic programming state: dp[i][covered] where covered indicates if city i is already protected by a unit from i+1.
Time complexity: O(n) with greedy or O(n) with DP using constant states.
Space complexity: O(1) extra space if using greedy, O(n) if using DP array.
Edge cases: no units, all units, units at boundaries, and cities with zero population.
Proof of optimality: exchange argument showing that covering a higher population city earlier never hurts.

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