1. The Problem
I recently got a bug ticket about a file upload flow.
The application is deployed on Vercel. When creating an order, users can attach multiple files, and the original implementation bundles all files into a single request.
This caused us to hit Vercel's 4.5 MB request size limit.
For example:
File A: 2.0 MB
File B: 1.5 MB
File C: 1.2 MB
Total: 4.7 MB
Each individual file is already limited to 4 MB, so the easiest solution is to upload the files separately.
However, that would increase the number of HTTP requests.
I also noticed that there are many possible ways to group the files, and some groupings use fewer requests than others. This reminded me of Dynamic Programming problems, so I became curious:
Is there a better way to group the files and reduce the number of upload requests?
If every request can contain multiple files but cannot exceed 4.5 MB, the problem becomes:
Given:
files = [2.0, 1.5, 1.2, ...]
request limit = 4.5 MB
Find:
A grouping of files that uses the minimum number of requests.
After looking into it with ChatGPT, I found that this is basically a variation of the Bin Packing Problem:
File -> Item
Upload request -> Bin
4.5 MB request limit -> Bin capacity
Minimum requests -> Minimum number of bins
I also found a very similar problem on LeetCode:
LeetCode 1986 — Minimum Number of Work Sessions to Finish the Tasks
2. An Exact Solution: Bitmask DP
The LeetCode problem can be solved with Bitmask DP.
Here is the solution I started with:
var minSessions = function(tasks, sessionTime) {
const n = tasks.length
const N = 1 << n
const dp = Array.from(
{ length: N },
() => [Infinity, Infinity]
)
dp[0] = [1, 0]
for (let mask = 0; mask < N; mask++) {
const [count, used] = dp[mask]
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) continue
const nextMask = mask | (1 << i)
const candidate = (used + tasks[i] <= sessionTime)
? [count, used + tasks[i]]
: [count + 1, tasks[i]]
if (
candidate[0] < dp[nextMask][0] ||
(
candidate[0] === dp[nextMask][0] &&
candidate[1] < dp[nextMask][1]
)
) {
dp[nextMask] = candidate
}
}
}
return dp[N - 1][0]
}
If this Bitmask DP looks confusing, I asked ChatGPT to explain it step by step:
LeetCode 1986: An Intuitive Bitmask DP Explanation →
However, that is not enough for my real problem.
The solution only gives me the minimum number of requests, but I also need to know exactly how the files should be grouped.
So I changed the variable names to match my upload problem and added an onUpdate callback:
var minUploadRequests = function(fileSizes, requestLimit, onUpdate) {
const n = fileSizes.length
const N = 1 << n
const dp = Array.from(
{ length: N },
() => [Infinity, Infinity]
)
dp[0] = [1, 0]
for (let mask = 0; mask < N; mask++) {
const [count, used] = dp[mask]
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) continue
const nextMask = mask | (1 << i)
const newRequest = used + fileSizes[i] > requestLimit
const candidate = !newRequest
? [count, used + fileSizes[i]]
: [count + 1, fileSizes[i]]
if (
candidate[0] < dp[nextMask][0] ||
(
candidate[0] === dp[nextMask][0] &&
candidate[1] < dp[nextMask][1]
)
) {
dp[nextMask] = candidate
onUpdate?.({
mask,
nextMask,
fileIndex: i,
newRequest
})
}
}
}
return dp[N - 1][0]
}
Through the onUpdate callback, I can record how each best state was reached and rebuild the final file groups afterward:
function minUploadRequestsWithGroups(fileSizes, requestLimit) {
const parent = []
const requestCount = minUploadRequests(
fileSizes,
requestLimit,
({ mask, nextMask, fileIndex, newRequest }) => {
parent[nextMask] = {
prevMask: mask,
fileIndex,
newRequest
}
}
)
const steps = []
let mask = (1 << fileSizes.length) - 1
while (mask !== 0) {
const step = parent[mask]
steps.push(step)
mask = step.prevMask
}
steps.reverse()
const groups = []
for (const step of steps) {
if (groups.length === 0 || step.newRequest) {
groups.push([])
}
groups[groups.length - 1].push(
fileSizes[step.fileIndex]
)
}
return {
requestCount,
groups
}
}
If the reconstruction part looks confusing, I also asked ChatGPT to explain how the callback, parent, and backward tracing work together:
How Bitmask DP Reconstructs the Actual File Groups →
Test
const fileSizes = [2.0, 2.0, 1.5, 1.5]
const requestLimit = 4.5
const result = minUploadRequestsWithGroups(
fileSizes,
requestLimit
)
console.log(result)
Output:
{
requestCount: 2,
groups: [
[2.0, 2.0],
[1.5, 1.5]
]
}
So now I can get both the minimum number of requests and the actual grouping.
But there is another problem.
3. Do I Really Need the Optimal Solution?
When I checked the time complexity, I found that this solution is much more expensive than I expected.
The Bitmask DP has 2^n possible states, and each state may check up to n files.
So the time complexity is:
O(n * 2^n)
And the space complexity is:
O(2^n)
For a small number of files, this is fine.
But I am using an exponential-time algorithm just to reduce a few HTTP requests.
It started to feel like overengineering for such a small upload problem.
The real requirement is probably not:
Always find the mathematically optimal grouping.
What I really need is:
Group the files reasonably well without creating too many requests.
So I started looking for a simpler solution.
4. A More Practical Approach: First Fit Decreasing
After some research, I found a much more practical solution: First Fit Decreasing.
The algorithm is simple:
- Sort the files from largest to smallest.
- Take each file one by one.
- Put it into the first request where it still fits.
- If it does not fit into any existing request, create a new one.
The idea is that large files are harder to place, while small files are more flexible.
If I place small files first, they may use some space in many requests and leave small gaps everywhere.
Later, a large file may not fit anywhere.
For example:
Limit: 10
Files: [1, 1, 1, 8, 8]
If I use First Fit with the original order:
Request 1: 1 + 1 + 1 = 3
Request 2: 8
Request 3: 8
I need 3 requests.
But First Fit Decreasing sorts the files first:
[8, 8, 1, 1, 1]
Then:
Request 1: 8 + 1 + 1 = 10
Request 2: 8 + 1 = 9
Now I only need 2 requests.
The idea is simple:
Put the difficult items first, then use the smaller items to fill the remaining space.
The implementation is also much simpler:
function firstFitDecreasing(fileSizes, requestLimit) {
const sorted = [...fileSizes].sort((a, b) => b - a)
const groups = []
for (const fileSize of sorted) {
let placed = false
for (const group of groups) {
const used = group.reduce(
(sum, size) => sum + size,
0
)
if (used + fileSize <= requestLimit) {
group.push(fileSize)
placed = true
break
}
}
if (!placed) {
groups.push([fileSize])
}
}
return groups
}
Sorting takes:
O(n log n)
Then each file may need to check the existing groups.
In the worst case:
O(n²)
So the overall time complexity of this implementation is:
O(n²)
Compared with the exact solution:
Bitmask DP: O(n * 2^n)
First Fit Decreasing: O(n²)
First Fit Decreasing does not always give the optimal grouping.
But for my use case, this trade-off feels much more reasonable.
5. Can I Solve the Problem from Another Angle?
At this point, I had another thought:
What if I stop treating each file as something that must stay complete during the upload?
The grouping problem exists because every file has to fit completely inside one request.
If I change that assumption, I can turn the problem into a chunking problem instead.
For example:
File A
File B
File C
↓ combine or serialize
Byte stream
↓ split by request size
Chunk 1 <= 4.5 MB
Chunk 2 <= 4.5 MB
Chunk 3 <= 4.5 MB
Then I can upload each chunk separately and rebuild the original files later.
Now the question changes from:
How should I group these files?
to:
How should I split the data into chunks smaller than the request limit?
This problem is much easier.
However, it also creates other problems:
- how to identify each chunk
- how to retry a failed chunk
- how to handle partial uploads
- how to rebuild the original files
- when to remove temporary data
- how to make retries safe
So this is not always a better solution.
It just moves the complexity to another place.
What I found interesting is that sometimes I do not need a better algorithm.
I can change the assumptions and make the original algorithm problem disappear.
6. Using AI for the Difficult Parts
AI helped me a lot when I tried to understand this problem.
Some parts were new to me, especially Bitmask DP and how to rebuild the actual file groups.
I used AI to help me:
- identify this as a Bin Packing problem
- find a similar LeetCode problem
- understand the Bitmask DP solution
- implement the grouping logic
- check the time complexity
- find simpler solutions
This saved me a lot of time.
I still needed to understand the problem and decide which solution was suitable for the real application.
For example, AI could give me the optimal solution, but I still needed to ask:
Do I really need the optimal result?
Is this solution too complicated for this problem?
Is there another way to solve the problem?
I think this is a useful way for me to use AI.
It helps me explore difficult solutions faster, while I still make the final engineering decision.
7. Conclusion
This started from a simple bug about a request size limit.
But the problem became:
Upload limit
→ File grouping
→ Bin Packing
→ Bitmask DP
→ O(n * 2^n)
→ First Fit Decreasing
→ O(n²)
→ Another way to design the upload flow
The Bitmask DP solution can find the optimal grouping, but it is probably too complicated for my real use case.
First Fit Decreasing is not always optimal, but it is much simpler and faster.
Another possible solution is to change the upload flow and split the data into chunks instead of grouping whole files.
What I learned from this problem is:
The optimal algorithm is not always the best solution for a real application.
Sometimes a simple solution is good enough.
And sometimes it is better to change the problem instead of trying to optimize it.
Top comments (0)