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

Intermediate

Jun 2026

Summary

Amazon SWE coding round with a greedy/sorting problem around minimizing total packaging effort across fulfillment centers. The problem had a neat twist with the free item bonus mechanic that made it less obvious than it first looked.

Questions Asked (1)

Given a list of item packaging efforts and a list of fulfillment center thresholds, where paying to package at least a threshold number of items at a center gives you 2 free items (each with effort at most the minimum paid effort at that center), return the minimum total packaging effort to package all items. Each center can be used at most once.

Algorithms & Data Structures

Author's notes

The free items mechanic is what makes this tricky.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

This is a combinatorial optimization problem where each center can be used at most once to cover two items with effort at most the minimum paid effort. Sort items by effort and centers by threshold, then use dynamic programming to decide which centers to use and which items to assign as paid or free, minimizing total paid effort. The DP state should track the number of items covered and the maximum allowed effort for free items.

Pro tip: Clarify that the free items must have effort ≤ the minimum paid effort at that center, so the paid items determine the cap. Mention that sorting both lists and using DP with binary search or two pointers can optimize transitions.

1. Understand the problem and constraints

Restate the problem: each center can be used once, requires paying for at least threshold items, and gives 2 free items with effort ≤ the minimum paid effort at that center. Goal: minimize total paid effort to cover all items.

2. Sort and preprocess

Sort items by effort ascending and centers by threshold ascending. This helps in efficiently determining which items can be free for a given center based on the minimum paid effort.

3. Define DP state and transitions

Let dp[i][j] be the minimum total paid effort to cover the first i items using j centers. For each center, consider using it: choose a set of paid items (at least threshold) from the remaining items, and then up to 2 free items with effort ≤ min paid effort. Use binary search to find eligible free items.

4. Optimize and handle base cases

Initialize dp[0][0] = 0. For each center, iterate over possible numbers of paid items and update DP. Ensure all items are covered; if not, return -1 or infinity. Consider that centers can be skipped.

5. Return the minimum effort

After processing all centers, the answer is the minimum dp[n][j] over all j, where n is the total number of items. If no valid assignment, return -1.

Key Points to Mention

Sorting items and centers to enable efficient matching.
Dynamic programming state definition and transition.
Binary search to find free items given a minimum paid effort.
Handling the constraint that each center can be used at most once.
Time and space complexity analysis (e.g., O(n^2 * m) or optimized with greedy).
Edge cases: insufficient centers, items with equal effort, threshold larger than available items.

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