Amazon·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jul 2026

Summary

Amazon SWE coding round, one algorithmic problem for the whole session. The problem looked deceptively simple at first glance but there's a subtle constraint on guard movement that makes it easy to miss edge cases.

Questions Asked (1)

You have n cities in a row, each with a population value. Some cities start with a security guard. Each guard can move at most one step to the left, but only if the destination city is unoccupied. You can perform moves in any order. After all moves are done, the protected population is the sum of populations of cities that have a guard. Find the maximum protected population you can achieve.

Algorithms & Data Structures

Author's notes

Spent way too long convincing myself this was a greedy problem before actually verifying it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a matching or greedy assignment where each guard can either stay or move left if the left city is empty. Use a greedy strategy from left to right, prioritizing moving guards to cities with higher populations when beneficial, or use dynamic programming to consider all possibilities. Prove that the greedy choice is optimal by exchange argument.

Pro tip: Clarify that guards can only move left and only into unoccupied cities, and that moves are sequential but order doesn't affect the final set of occupied cities. Emphasize that the problem reduces to selecting a set of cities to protect such that each selected city either originally had a guard or has a guard that can move into it from the right, with no two guards competing for the same city.

1. Understand the problem and constraints

Restate the problem: n cities in a row, each with population, some have guards. Each guard can move at most one step left into an empty city. Maximize sum of populations of cities with guards after moves.

2. Identify the decision for each guard

For each guard, decide whether to stay or move left. Moving left is only possible if the left city is empty and not occupied by another guard. This creates dependencies between adjacent cities.

3. Formulate as a matching or DP problem

Consider dynamic programming with states representing whether the current city is occupied and whether a guard from the right can move in. Alternatively, model as a maximum weight matching in a path graph where each guard can match to itself or its left neighbor.

4. Design a greedy or DP algorithm

For a greedy approach: scan from left to right, and for each city, if it has a guard and the left city is empty and has higher population, move the guard left. For DP: define dp[i][0/1] as max protected population up to city i, with 0/1 indicating if city i is occupied. Transition based on guard presence and movement.

5. Analyze complexity and prove correctness

The DP solution runs in O(n) time and O(1) or O(n) space. Prove correctness by induction or exchange argument, showing that the optimal solution can be transformed into the greedy/DP choice without decreasing the total population.

Key Points to Mention

The problem can be modeled as a maximum weight matching on a path graph where each guard can match to itself or its left neighbor.
Dynamic programming with states tracking occupancy of the current city and whether a guard is available from the right.
Greedy approach: process cities left to right, and if a guard can move left to a higher-population city, do so, but be careful about blocking other guards.
Time complexity should be O(n) and space O(1) or O(n).
Edge cases: no guards, all cities have guards, guards at the first city cannot move left.
Proof of optimality using exchange argument: if an optimal solution doesn't make a beneficial move, swapping assignments doesn't reduce total population.

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