Walmart: Assigning Pallets to Trailers Under a Weight Limit
A Walmart distribution centre loads outbound pallets onto trailers strictly in loading order, and the transport planners want to know how the pallets will…
- Difficulty: Hard
- Topics: Subqueries, Aggregation
- Dialect: MySQL
- Problem: #1022
Problem statement
A Walmart distribution centre loads outbound pallets onto trailers strictly in loading order, and the transport planners want to know how the pallets will split across trailers before the trucks are booked. A trailer may carry at most 10,000 kg in this exercise.
Within each DC, pallets are loaded in load_seq order. The first pallet goes on trailer 1. Each following pallet goes on the current trailer if the trailer's weight plus the pallet's stays at most 10,000 kg; otherwise the current trailer leaves and the pallet starts the next trailer. Trailers are numbered from 1 in each DC. Return dc_id, trailer_no, pallets and total_kg for every trailer, ordered by dc_id, then trailer_no.
A practice scenario set at Walmart: the tables and data are invented, and this is not a question from, or endorsed by, Walmart.
Tables
Table: OutboundPallet
| Column | Type |
|---|---|
| pallet_id | int |
| dc_id | int |
| load_seq | int |
| weight_kg | int |
Primary key: pallet_id.
One row per pallet staged at a DC's dock. load_seq is unique within a DC but has gaps; every pallet weighs at most 10,000 kg.
Examples
Example 1
OutboundPallet
| pallet_id | dc_id | load_seq | weight_kg |
|---|---|---|---|
| 1 | 6011 | 3 | 4000 |
| 2 | 6011 | 7 | 3500 |
| 3 | 6011 | 10 | 2500 |
| 4 | 6011 | 12 | 3000 |
| 5 | 6011 | 15 | 6000 |
| 6 | 6011 | 20 | 1500 |
| 7 | 6094 | 1 | 9500 |
| 8 | 6094 | 2 | 800 |
| 9 | 6094 | 5 | 700 |
Output
| dc_id | trailer_no | pallets | total_kg |
|---|---|---|---|
| 6011 | 1 | 3 | 10000 |
| 6011 | 2 | 2 | 9000 |
| 6011 | 3 | 1 | 1500 |
| 6094 | 1 | 1 | 9500 |
| 6094 | 2 | 2 | 1500 |
How to solve Walmart: Assigning Pallets to Trailers Under a Weight Limit
It is tempting to use a running SUM and divide by 10,000, but that answers a different question: it would split pallets across trailer boundaries as if weight were liquid. Here a trailer leaves before it would go over the limit, so the next trailer starts with the leftover space unused, and every later boundary depends on where the earlier ones fell. That chain of decisions needs state carried from row to row, which is what a recursive CTE does.
First, ROW_NUMBER() numbers each DC's pallets 1, 2, 3 … in load_seq order, because the sequence has gaps. The anchor of the recursion is pallet 1 on trailer 1, carrying its own weight as the trailer's load. Each recursive step joins the previous pallet's state to the next pallet (rn + 1, same DC) and decides: if the load plus this pallet exceeds 10,000 kg, start trailer trailer_no + 1 with this pallet's weight; otherwise stay on the trailer and add the weight. A load of exactly 10,000 kg still fits. The recursion runs per DC in parallel because the anchor has one row per DC.
With a trailer number on every pallet, GROUP BY dc_id, trailer_no gives the pallet count and total weight. The alternative walks load_seq directly, finding each next pallet with a correlated MIN, and tracks the same state with IF. Both visit each pallet once, so the work is linear in the number of pallets per DC.
Reference solution (MySQL)
WITH RECURSIVE ordered AS (
SELECT dc_id, weight_kg,
ROW_NUMBER() OVER (PARTITION BY dc_id ORDER BY load_seq) AS rn
FROM OutboundPallet
), fill AS (
SELECT dc_id, rn, weight_kg, 1 AS trailer_no, weight_kg AS load_kg
FROM ordered
WHERE rn = 1
UNION ALL
SELECT o.dc_id, o.rn, o.weight_kg,
CASE WHEN f.load_kg + o.weight_kg > 10000 THEN f.trailer_no + 1 ELSE f.trailer_no END,
CASE WHEN f.load_kg + o.weight_kg > 10000 THEN o.weight_kg ELSE f.load_kg + o.weight_kg END
FROM fill f
JOIN ordered o ON o.dc_id = f.dc_id AND o.rn = f.rn + 1
)
SELECT dc_id, trailer_no, COUNT(*) AS pallets, SUM(weight_kg) AS total_kg
FROM fill
GROUP BY dc_id, trailer_no
ORDER BY dc_id, trailer_noAnother way
WITH RECURSIVE walk AS (
SELECT p.dc_id, p.load_seq, p.weight_kg, 1 AS trailer_no, p.weight_kg AS room_used
FROM OutboundPallet p
WHERE p.load_seq = (SELECT MIN(q.load_seq) FROM OutboundPallet q WHERE q.dc_id = p.dc_id)
UNION ALL
SELECT n.dc_id, n.load_seq, n.weight_kg,
w.trailer_no + IF(w.room_used + n.weight_kg <= 10000, 0, 1),
IF(w.room_used + n.weight_kg <= 10000, w.room_used + n.weight_kg, n.weight_kg)
FROM walk w
JOIN OutboundPallet n
ON n.dc_id = w.dc_id
AND n.load_seq = (SELECT MIN(q.load_seq) FROM OutboundPallet q WHERE q.dc_id = w.dc_id AND q.load_seq > w.load_seq)
)
SELECT dc_id, trailer_no, COUNT(*) AS pallets, SUM(weight_kg) AS total_kg
FROM walk
GROUP BY dc_id, trailer_no
ORDER BY dc_id, trailer_no← Walmart: Median Minutes From Shelf Gap to Refill by Department · Zomato: Hygiene Certificates Expiring in July →