Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

Amazon coding round for a software engineer role. One algorithmic problem, median manipulation with a fixed operation budget. The greedy angle wasn't immediately obvious to me and I spent a bit too long going down the wrong path before things clicked.

Questions Asked (1)

You have an integer array and a budget of k operations. Each operation increments one element by 1 and decrements another by 1, keeping the total sum constant. What is the maximum median you can achieve after exactly k operations?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to just greedily pump up the middle element and call it a day, which is sort of right but not rigorous enough.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and edge cases, then propose a binary search on the median value. For a given candidate median, check if it's achievable within k operations by calculating the minimum increments needed to make at least half the elements >= candidate, and ensure the total sum is preserved.

Pro tip: Emphasize that the total sum is invariant, so the median can only be increased by redistributing values from elements below the median to those above. This shows you understand the core constraint and can avoid unnecessary complexity.

1. Clarify and Restate

Confirm the definition of median (for even length, typically the lower median or average?) and that operations can be applied to any pair of elements. Also confirm that exactly k operations must be used, but extra operations can be wasted by swapping between two elements.

2. Identify Invariant and Goal

Note that the sum of the array is constant. The goal is to maximize the median, which means we want to raise the lower half of the sorted array as much as possible using the surplus from the upper half.

3. Binary Search on Median

Binary search the answer over the range of possible medians (from min to max element). For a candidate median m, check if we can make at least half the elements >= m using at most k operations.

4. Feasibility Check

For a candidate m, sort the array. Compute the minimum increments needed to make the first half (or the lower median position) >= m. This is sum(max(0, m - a[i])) for the relevant elements. If this sum <= k, then m is feasible.

5. Handle Exactly k Operations

If the minimum required operations is less than k, we can waste the remaining operations by incrementing one element and decrementing another (e.g., swapping between two elements) without affecting the median. So feasibility only requires min_ops <= k.

Key Points to Mention

The total sum of the array is invariant under the operations.
The median depends on the sorted order; for even length, clarify which median (lower or average) is considered.
Binary search is efficient because the feasibility condition is monotonic: if a median m is achievable, any smaller median is also achievable.
The minimum operations to achieve a target median m is the sum of deficits of the lower half elements to reach m.
Extra operations beyond the minimum can be wasted by swapping between two elements without changing the median.
Time complexity: O(n log n + n log(max-min)) or O(n log n) if sorting once and binary searching over values.

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