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

Intermediate

May 2026Remote

Summary

Amazon SWE online assessment, one coding problem about greedy placement of security units across cities. Pretty clean problem statement but the edge cases took me longer than I'd like to admit.

Questions Asked (1)

You have n cities in a row, each with a population value and a binary string indicating whether a security unit is present. Each unit can optionally move one step to the left. A city is protected if it ends up with at least one unit. Find the maximum total population of protected cities.

Algorithms & Data Structures

Author's notes

Spent the first few minutes just re-reading the problem because I wasn't sure if units could stack or if each city just needed one.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a greedy assignment where each security unit can protect its own city or the city to its left. Process cities from left to right, prioritizing protection for the city with the larger population when a unit can cover both. Use a simple rule: if a unit is present at city i, compare populations of city i and i-1, and assign the unit to the city with higher population, ensuring no city gets more than one unit.

Pro tip: Clarify that the greedy choice is optimal because each unit's decision only affects two adjacent cities and choosing the higher population never reduces future options. Also, mention that the solution runs in O(n) time and O(1) space, which is optimal for this problem.

1. Understand the problem and constraints

Restate the problem: n cities in a row, each with a population and a binary string indicating security units. Each unit can move left by one or stay. Maximize total population of cities with at least one unit. Note that units are indistinguishable and each city can have at most one unit effectively.

2. Identify the greedy choice

For each unit at city i, it can protect city i or city i-1. If both are unprotected, assign the unit to the one with larger population. If one is already protected, assign to the other if possible. This local decision is optimal because it maximizes immediate gain without affecting other units.

3. Design an algorithm

Iterate through cities from left to right. Keep track of whether the previous city is protected. For each city i with a unit, if city i-1 is unprotected and its population is greater than city i's population, assign the unit to i-1; otherwise assign to i. Mark the chosen city as protected. Sum populations of protected cities.

4. Handle edge cases and validate

Consider cases with no units, units at the first city (cannot move left), multiple units in a row, and cities with equal populations. Walk through a small example to verify the greedy choice yields the maximum sum.

5. Analyze complexity and conclude

State that the algorithm runs in O(n) time and O(1) extra space (besides input). Explain why greedy is optimal: each unit's decision is independent and choosing the higher population never prevents a better assignment later.

Key Points to Mention

Greedy approach: each unit independently chooses between its current city and the left neighbor.
Comparison of populations to decide assignment when both cities are unprotected.
Tracking protected status to avoid double-counting and to handle already protected cities.
Edge cases: units at index 0, consecutive units, no units, equal populations.
Time and space complexity: O(n) time, O(1) extra space.
Proof of optimality: exchange argument showing greedy choice is safe.

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