Flipkart: Unscanned Ekart AWB Numbers as Ranges per Hub
Each Ekart hub is allotted one block of consecutive AWB (air waybill) numbers, from series_start to series_end inclusive.
- Difficulty: Hard
- Topics: Window Functions, Subqueries, Joins
- Dialect: MySQL
- Problem: #670
Problem statement
Each Ekart hub is allotted one block of consecutive AWB (air waybill) numbers, from series_start to series_end inclusive. Every AWB used on a parcel should appear at least once in the hub's manifest scans; a number of the block that was never scanned means a label was printed and lost, or never used. The hub audit lists them compactly, as ranges.
For every hub, find the numbers of its block with no scan at that hub, and report each run of consecutive missing numbers as one row: hub_code, gap_start, gap_end and missing_awbs (how many numbers the range holds). A single missing number is a range whose start and end are equal; a hub with no scans at all is one range covering its whole block. Scans repeat, and scans of numbers outside the hub's own block are ignored. Order by hub_code, then gap_start.
A practice scenario set at Flipkart: the tables and data are invented, and this is not a question from, or endorsed by, Flipkart.
Tables
Table: AwbAllocation
| Column | Type |
|---|---|
| hub_code | varchar |
| series_start | int |
| series_end | int |
Primary key: hub_code.
One block of AWB numbers per hub; series_end is never below series_start, and blocks of different hubs never overlap.
Table: ManifestScan
| Column | Type |
|---|---|
| scan_id | int |
| hub_code | varchar |
| awb_no | int |
| scanned_at | datetime |
Primary key: scan_id.
One row per scan of a parcel label at a hub. A parcel can be scanned several times, and a misrouted parcel can be scanned at a hub that does not own its number.
Examples
Example 1
AwbAllocation
| hub_code | series_start | series_end |
|---|---|---|
| BLR-E | 1000101 | 1000110 |
| DEL-N | 2000001 | 2000005 |
| MUM-W | 3000001 | 3000003 |
ManifestScan
| scan_id | hub_code | awb_no | scanned_at |
|---|---|---|---|
| 1 | BLR-E | 1000101 | 2024-10-01 09:10:00 |
| 2 | BLR-E | 1000102 | 2024-10-01 09:12:00 |
| 3 | BLR-E | 1000102 | 2024-10-01 18:40:00 |
| 4 | BLR-E | 1000105 | 2024-10-02 10:00:00 |
| 5 | BLR-E | 1000106 | 2024-10-02 10:05:00 |
| 6 | BLR-E | 1000110 | 2024-10-03 08:30:00 |
| 7 | BLR-E | 2000004 | 2024-10-03 08:31:00 |
| 8 | DEL-N | 2000002 | 2024-10-01 11:00:00 |
| 9 | DEL-N | 2000003 | 2024-10-01 11:02:00 |
| 10 | DEL-N | 2000005 | 2024-10-02 15:20:00 |
Output
| hub_code | gap_start | gap_end | missing_awbs |
|---|---|---|---|
| BLR-E | 1000103 | 1000104 | 2 |
| BLR-E | 1000107 | 1000109 | 3 |
| DEL-N | 2000001 | 2000001 | 1 |
| DEL-N | 2000004 | 2000004 | 1 |
| MUM-W | 3000001 | 3000003 | 3 |
How to solve Flipkart: Unscanned Ekart AWB Numbers as Ranges per Hub
Listing missing numbers one by one would need a row for every number of the block; reporting them as ranges needs only the numbers that exist. Sort a hub's scanned numbers and look at each one's successor: if the successor is awb_no + 1 nothing is missing between them, and if it is larger, every number strictly between them is missing — the range awb_no + 1 to next_no - 1, holding next_no - awb_no - 1 numbers. LEAD(awb_no) OVER (PARTITION BY hub_code ORDER BY awb_no) fetches that successor.
Two preparations make it exact. The scans are first cut to distinct numbers inside the hub's own block: a repeated scan would pair a number with itself, and a misrouted label from another block (or just past the end of this one) would look like a scanned neighbour and hide a real gap. And the block's edges get fences — series_start - 1 and series_end + 1 are added as if scanned. Without them a gap at the start of the block has no left neighbour and a gap at the end no right one, and a hub with no scans would produce nothing at all; with them it gets one range covering its whole block. UNION (not UNION ALL) removes duplicates in the same step.
The alternative finds the start of each gap with NOT EXISTS (awb_no + 1 is not among the scanned numbers) and its end with a correlated MIN of the next scanned number. The fence after the block has no successor, so its NULL end is filtered out. The window version is one sort per hub.
Reference solution (MySQL)
WITH seen AS (
SELECT DISTINCT m.hub_code, m.awb_no
FROM ManifestScan m
JOIN AwbAllocation a ON a.hub_code = m.hub_code AND m.awb_no BETWEEN a.series_start AND a.series_end
UNION
SELECT hub_code, series_start - 1 FROM AwbAllocation
UNION
SELECT hub_code, series_end + 1 FROM AwbAllocation
), paired AS (
SELECT hub_code, awb_no,
LEAD(awb_no) OVER (PARTITION BY hub_code ORDER BY awb_no) AS next_no
FROM seen
)
SELECT hub_code, awb_no + 1 AS gap_start, next_no - 1 AS gap_end, next_no - awb_no - 1 AS missing_awbs
FROM paired
WHERE next_no - awb_no > 1
ORDER BY hub_code, gap_startAnother way
WITH seen AS (
SELECT m.hub_code, m.awb_no FROM ManifestScan m
JOIN AwbAllocation a ON a.hub_code = m.hub_code AND m.awb_no >= a.series_start AND m.awb_no <= a.series_end
UNION
SELECT hub_code, series_start - 1 FROM AwbAllocation
UNION
SELECT hub_code, series_end + 1 FROM AwbAllocation
)
SELECT hub_code, gap_start, gap_end, gap_end - gap_start + 1 AS missing_awbs
FROM (
SELECT s.hub_code, s.awb_no + 1 AS gap_start,
(SELECT MIN(t.awb_no) FROM seen t WHERE t.hub_code = s.hub_code AND t.awb_no > s.awb_no) - 1 AS gap_end
FROM seen s
WHERE NOT EXISTS (SELECT 1 FROM seen u WHERE u.hub_code = s.hub_code AND u.awb_no = s.awb_no + 1)
) g
WHERE gap_end IS NOT NULL
ORDER BY hub_code, gap_start← Flipkart: Sale-Acquired Buyers Who Came Back for the Next Sale · Flipkart: First Day a Seller Logged Three Returns in Seven Days →