Walmart: Assigning Pallets to Trailers Under a Weight Limit

Hard
1022.

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 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

ColumnType
pallet_idint
dc_idint
load_seqint
weight_kgint

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.

Example

The rows must come back in the order shown.

OutboundPallet

pallet_iddc_idload_seqweight_kg
1601134000
2601173500
36011102500
46011123000
56011156000
66011201500
7609419500
860942800
960945700

Output

dc_idtrailer_nopalletstotal_kg
60111310000
6011229000
6011311500
6094119500
6094221500
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

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

ColumnType
pallet_idint
dc_idint
load_seqint
weight_kgint

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_iddc_idload_seqweight_kg
1601134000
2601173500
36011102500
46011123000
56011156000
66011201500
7609419500
860942800
960945700

Output

dc_idtrailer_nopalletstotal_kg
60111310000
6011229000
6011311500
6094119500
6094221500

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_no

Another 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 →