Walmart: Median Minutes From Shelf Gap to Refill by Department
Walmart's replenishment analytics team measures how fast each department puts stock back once a shelf goes empty.
- Difficulty: Hard
- Topics: Window Functions, Subqueries, Dates
- Dialect: MySQL
- Problem: #1021
Problem statement
Walmart's replenishment analytics team measures how fast each department puts stock back once a shelf goes empty. Handheld scans record each item's shelf as empty or stocked through the day.
For each store and item, take its scans in time order. A gap begins at an empty scan whose previous scan of the same store and item is not empty (or that has no previous scan); later consecutive empty scans belong to the same gap. The gap is refilled at the first stocked scan of that store and item after it began; its length is the minutes from the gap's first scan to that refill. Gaps never refilled are ignored. For each department with at least one refilled gap, return department, refilled_gaps and median_minutes (the median gap length; with an even count, the average of the two middle values). Order by department.
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: ShelfScan
| Column | Type |
|---|---|
| scan_id | int |
| store_id | int |
| item_id | int |
| department | varchar |
| scanned_at | datetime |
| status | enum(empty, stocked) |
Primary key: scan_id.
One row per shelf scan. An item always belongs to the same department, and a store never scans one item twice at the same moment.
Examples
Example 1
ShelfScan
| scan_id | store_id | item_id | department | scanned_at | status |
|---|---|---|---|---|---|
| 1 | 1204 | 501 | Dairy | 2025-08-04 06:00:00 | stocked |
| 2 | 1204 | 501 | Dairy | 2025-08-04 08:00:00 | empty |
| 3 | 1204 | 501 | Dairy | 2025-08-04 09:00:00 | empty |
| 4 | 1204 | 501 | Dairy | 2025-08-04 10:30:00 | stocked |
| 5 | 1204 | 501 | Dairy | 2025-08-04 14:00:00 | empty |
| 6 | 1204 | 501 | Dairy | 2025-08-04 15:00:00 | stocked |
| 7 | 1204 | 502 | Dairy | 2025-08-04 07:00:00 | empty |
| 8 | 1204 | 502 | Dairy | 2025-08-04 11:00:00 | stocked |
| 9 | 1204 | 601 | Produce | 2025-08-04 08:00:00 | empty |
| 10 | 3318 | 602 | Produce | 2025-08-04 09:00:00 | empty |
| 11 | 3318 | 602 | Produce | 2025-08-04 09:45:00 | stocked |
| 12 | 3318 | 602 | Produce | 2025-08-04 12:00:00 | empty |
| 13 | 3318 | 602 | Produce | 2025-08-04 13:30:00 | stocked |
Output
| department | refilled_gaps | median_minutes |
|---|---|---|
| Dairy | 3 | 150 |
| Produce | 2 | 67.5 |
How to solve Walmart: Median Minutes From Shelf Gap to Refill by Department
The scans describe states, not events, so the gaps have to be reconstructed. Ordering each store-item's scans by time, a gap starts where the status turns to empty: an empty scan whose previous status (from LAG) is stocked or missing. A run of several empty scans is one gap, measured from its first scan — counting each empty scan as a new gap would add shorter, overlapping gaps and pull the median down.
Each gap ends at the first stocked scan after it starts, found by a correlated MIN. If the item was never restocked, the subquery returns NULL, the length is NULL, and the gap is dropped — it has no refill time to report. TIMESTAMPDIFF(MINUTE, …) gives the length.
The median uses positions. With cnt lengths per department ranked by ROW_NUMBER, the middle positions are (cnt + 1) DIV 2 and (cnt + 2) DIV 2: the same position for an odd count, the two middle ones for an even count, and AVG of the kept rows is the median either way. Equal lengths can take either rank without changing the answer, because their values are equal.
The alternative finds starts with NOT EXISTS on the latest earlier scan, refills with a grouped join, and takes the median without ranking: a value is a middle value when at least half the lengths are ≤ it and at least half are ≥ it; AVG(DISTINCT …) of those values is the median even when the middle value repeats.
Reference solution (MySQL)
WITH s AS (
SELECT store_id, item_id, department, scanned_at, status,
LAG(status) OVER (PARTITION BY store_id, item_id ORDER BY scanned_at) AS prev_status
FROM ShelfScan
), gaps AS (
SELECT g.department,
TIMESTAMPDIFF(MINUTE, g.scanned_at,
(SELECT MIN(r.scanned_at) FROM ShelfScan r
WHERE r.store_id = g.store_id AND r.item_id = g.item_id
AND r.status = 'stocked' AND r.scanned_at > g.scanned_at)) AS minutes
FROM s g
WHERE g.status = 'empty' AND (g.prev_status IS NULL OR g.prev_status <> 'empty')
), ranked AS (
SELECT department, minutes,
ROW_NUMBER() OVER (PARTITION BY department ORDER BY minutes) AS rn,
COUNT(*) OVER (PARTITION BY department) AS cnt
FROM gaps
WHERE minutes IS NOT NULL
)
SELECT department, MAX(cnt) AS refilled_gaps, AVG(minutes) AS median_minutes
FROM ranked
WHERE rn IN ((cnt + 1) DIV 2, (cnt + 2) DIV 2)
GROUP BY department
ORDER BY departmentAnother way
WITH starts AS (
SELECT g.store_id, g.item_id, g.department, g.scanned_at
FROM ShelfScan g
WHERE g.status = 'empty'
AND NOT EXISTS (
SELECT 1 FROM ShelfScan p
WHERE p.store_id = g.store_id AND p.item_id = g.item_id AND p.status = 'empty'
AND p.scanned_at = (SELECT MAX(q.scanned_at) FROM ShelfScan q
WHERE q.store_id = g.store_id AND q.item_id = g.item_id AND q.scanned_at < g.scanned_at)
)
), gaps AS (
SELECT st.department, TIMESTAMPDIFF(MINUTE, st.scanned_at, MIN(r.scanned_at)) AS minutes
FROM starts st
JOIN ShelfScan r ON r.store_id = st.store_id AND r.item_id = st.item_id
AND r.status = 'stocked' AND r.scanned_at > st.scanned_at
GROUP BY st.store_id, st.item_id, st.department, st.scanned_at
)
SELECT g1.department,
(SELECT COUNT(*) FROM gaps x WHERE x.department = g1.department) AS refilled_gaps,
AVG(DISTINCT g1.minutes) AS median_minutes
FROM gaps g1
WHERE (SELECT COUNT(*) FROM gaps a WHERE a.department = g1.department AND a.minutes <= g1.minutes) * 2
>= (SELECT COUNT(*) FROM gaps x WHERE x.department = g1.department)
AND (SELECT COUNT(*) FROM gaps b WHERE b.department = g1.department AND b.minutes >= g1.minutes) * 2
>= (SELECT COUNT(*) FROM gaps x WHERE x.department = g1.department)
GROUP BY g1.department
ORDER BY g1.department← Walmart: Understaffed Stretches on the Sales Floor · Walmart: Assigning Pallets to Trailers Under a Weight Limit →