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

Intermediate

Jun 2026

Summary

Amazon OA for a SWE role. One coding problem, greedy/sorting type, not too bad once you see the pattern but easy to overthink.

Questions Asked (1)

Given two arrays of equal length, one representing sizes and one representing costs, make all elements in the size array distinct by only incrementing values. Each increment adds the corresponding cost. Find the minimum total cost to achieve this.

Algorithms & Data Structures

Author's notes

Took me a minute to realize you always want to increment the cheaper element when there's a collision, not just the one that came later.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the elements by cost in ascending order, then greedily assign each element the smallest available size that is at least its original size and not yet used. Use a balanced BST or a disjoint-set union (DSU) with path compression to efficiently find the next available size.

Pro tip: Mention that this problem is a variant of the classic 'minimum cost to make array elements distinct' and that the greedy choice is optimal because costs are independent of the increments. Also, highlight the trade-off between using a balanced BST (O(n log n)) and DSU (near O(n α(n))) depending on the size range.

1. Understand the problem and constraints

Clarify that we can only increment sizes, each increment costs the corresponding cost, and we need all final sizes distinct with minimum total cost. Ask about constraints (e.g., size range, n) to choose the right data structure.

2. Sort by cost

Sort the pairs (size, cost) by cost ascending. This ensures we prioritize cheaper increments first, which is key to minimizing total cost.

3. Greedily assign distinct sizes

For each element in sorted order, find the smallest available size >= original size. If it's larger, add the difference times cost to the total. Mark that size as used.

4. Efficiently find next available size

Use a balanced BST (e.g., TreeSet) or DSU to quickly find and update the next available size. For DSU, map each size to its parent and use path compression to skip used sizes.

5. Analyze complexity and edge cases

Discuss time complexity (O(n log n) for sorting + O(n log n) or O(n α(n)) for assignments) and handle cases like duplicate sizes, large size ranges, and negative costs (if allowed).

Key Points to Mention

Greedy strategy: process elements in increasing order of cost to minimize total increment cost.
Data structures: balanced BST (TreeSet) or disjoint-set union (DSU) for efficient next-available-size queries.
Proof of optimality: exchange argument showing that assigning a cheaper element a larger size cannot reduce total cost.
Time complexity: O(n log n) due to sorting and data structure operations.
Space complexity: O(n) for storing used sizes or DSU parent array.
Edge cases: all sizes already distinct (cost 0), very large size values (use coordinate compression if needed), and negative costs (if allowed, still process by cost).

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