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

Senior

Jun 2026

Summary

Amazon SWE coding round with a DP problem on batching documents across GPUs to minimize padding. Pretty niche problem, not your typical LeetCode grind.

Questions Asked (1)

Given K documents with various lengths and G GPUs, partition all documents into exactly G batches (one per GPU) to minimize total padding cost, where padding cost per batch is batch_size times the max length in that batch minus the sum of actual lengths. Output the minimum total padding cost and one valid batching.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The key insight I kept second-guessing myself on was whether sorting first was actually valid.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, sort the documents by length and recognize that in an optimal partition, each batch consists of a contiguous segment of the sorted list. Then, use dynamic programming to compute the minimum total padding cost for partitioning the sorted documents into exactly G batches, and reconstruct one valid batching.

Pro tip: Mention that the problem is equivalent to partitioning a sorted array into G contiguous segments, and that the DP can be optimized to O(K^2 G) or even O(K G) with convex hull trick if needed. Also, clarify that the padding cost for a batch is (batch_size * max_length) - sum_of_lengths, which simplifies to (number_of_docs_in_batch - 1) * max_length - sum_of_other_lengths, but stick to the original formula for clarity.

1. Sort and justify contiguity

Sort the documents by length in non-decreasing order. Explain that any optimal solution can be transformed into one where each batch is a contiguous segment of this sorted order without increasing the cost.

2. Define DP state and transition

Let dp[i][g] be the minimum padding cost for partitioning the first i documents (in sorted order) into g batches. The transition is dp[i][g] = min_{j < i} (dp[j][g-1] + cost(j+1, i)), where cost(a, b) = (b-a+1) * len[b] - sum_{t=a}^b len[t].

3. Compute and reconstruct

Initialize dp[0][0] = 0 and fill the DP table for g from 1 to G and i from 1 to K. Keep track of the split points to reconstruct one valid batching. The answer is dp[K][G].

4. Analyze complexity and trade-offs

State the time complexity O(G * K^2) and space O(G * K). Mention that this can be optimized to O(G * K) using divide-and-conquer DP optimization or convex hull trick if the cost function satisfies the quadrangle inequality.

Key Points to Mention

Sorting documents by length and proving that an optimal partition uses contiguous segments in sorted order.
Dynamic programming formulation with state dp[i][g] and transition using prefix sums for efficient cost calculation.
Cost function: padding cost = (batch_size * max_length) - sum_of_lengths, and its computation in O(1) with prefix sums.
Reconstruction of one valid batching using parent pointers or by backtracking through the DP table.
Time and space complexity: O(G * K^2) time, O(G * K) space, and possible optimizations.
Edge cases: K < G (impossible to have exactly G non-empty batches), K = G (each document in its own batch), and handling large K efficiently.

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