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

Intermediate

Jun 2026

Summary

Amazon OA for a SWE role, one algorithmic problem about guard placement and maximizing protected population. Pretty niche greedy/simulation problem, not your typical LeetCode fare.

Questions Asked (1)

Given n cities with population values and a binary string indicating which cities have a guard unit, find the maximum total population you can protect. Each guard can move at most one step to the left (or stay), and a city is protected if it has at least one guard after all moves.

Algorithms & Data Structures

Author's notes

Took me a while to even parse what they were asking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a greedy assignment where each guard can cover itself or the city to its left. Process cities from left to right, and whenever a city is unprotected, use the nearest available guard to its right to cover it, ensuring maximum population protection.

Pro tip: Clarify that guards can only move left, so a guard at position i can protect city i or i-1. This constraint simplifies the problem to a linear scan with a greedy choice, avoiding complex DP.

1. Understand the problem constraints

Restate that each guard can move at most one step left or stay, and a city is protected if at least one guard ends there. Confirm that guards cannot move right.

2. Identify the greedy strategy

Process cities from left to right. For each city, if it has a guard, it's protected; if not, check if the next city has a guard that can move left to protect it.

3. Simulate the assignment

Iterate through the cities, keeping track of available guards. When a city is unprotected, use a guard from the immediate right if available, and mark both cities as handled.

4. Sum the protected populations

Accumulate the population of each city that ends up with a guard. Ensure no city is double-counted and guards are not reused.

5. Analyze complexity and edge cases

State that the solution runs in O(n) time and O(1) extra space. Discuss edge cases like guards at the last city, consecutive guards, and no guards.

Key Points to Mention

Greedy choice: always protect the leftmost unprotected city using the nearest guard to its right.
Linear scan with O(n) time complexity and O(1) space.
Handling of guards that can stay or move left, and the impossibility of moving right.
Edge cases: guard at index 0 (can only protect itself), guard at last index (can protect last or second-last), multiple guards in a row.
Proof of optimality: exchanging arguments show that using a guard for the leftmost city never reduces total protected population.
Comparison with dynamic programming: DP is possible but greedy is simpler and more efficient.

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