Flipkart: SuperCoins Left in Each Earn Batch After FIFO Burns
SuperCoins expire a year after they are earned, so the loyalty engineers need to know how many coins of each earn batch are still unspent.
- Difficulty: Hard
- Topics: Window Functions, Joins, Subqueries
- Dialect: MySQL
- Problem: #666
Problem statement
SuperCoins expire a year after they are earned, so the loyalty engineers need to know how many coins of each earn batch are still unspent. Burns always consume the oldest coins first: batches in order of earned_on, and by earn_id for batches earned on the same day.
Apply each member's total burned coins to their batches in that order (a member never burns more than they earned). Return earn_id, member_id and coins_left for every batch that still has more than 0 coins left. Order by member_id, then earned_on, then earn_id.
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: SuperCoinEarn
| Column | Type |
|---|---|
| earn_id | int |
| member_id | int |
| earned_on | date |
| coins | int |
Primary key: earn_id.
One row per batch of coins credited for a purchase.
Table: SuperCoinBurn
| Column | Type |
|---|---|
| burn_id | int |
| member_id | int |
| burned_on | date |
| coins | int |
Primary key: burn_id.
One row per redemption. A member's burns never add up to more than their earns.
Examples
Example 1
SuperCoinEarn
| earn_id | member_id | earned_on | coins |
|---|---|---|---|
| 1 | 7 | 2024-06-01 | 100 |
| 2 | 7 | 2024-06-15 | 200 |
| 3 | 7 | 2024-07-02 | 150 |
| 4 | 9 | 2024-06-10 | 80 |
| 5 | 9 | 2024-06-10 | 120 |
| 6 | 12 | 2024-08-01 | 60 |
SuperCoinBurn
| burn_id | member_id | burned_on | coins |
|---|---|---|---|
| 1 | 7 | 2024-07-10 | 150 |
| 2 | 7 | 2024-07-20 | 50 |
| 3 | 9 | 2024-07-01 | 80 |
Output
| earn_id | member_id | coins_left |
|---|---|---|
| 2 | 7 | 100 |
| 3 | 7 | 150 |
| 5 | 9 | 120 |
| 6 | 12 | 60 |
How to solve Flipkart: SuperCoins Left in Each Earn Batch After FIFO Burns
FIFO consumption looks procedural — walk the batches, subtract until the burn is used up — but it has a closed form. Order a member's batches oldest first and take the running total of coins earned, cum_coins. Let B be the member's total burned. All coins up to cumulative B are gone, so a batch whose running total is at most B is fully spent, and a batch whose running total exceeds B keeps cum_coins − B coins — but never more than the batch held, hence LEAST(coins, cum_coins − B). The one batch straddling B is partly spent; every later one is untouched.
The running total is a window SUM(coins) OVER (PARTITION BY member_id ORDER BY earned_on, earn_id). The earn_id in the ORDER BY matters twice: it is the statement's tie-break for batches earned the same day, and it makes every row its own peer group, so the default RANGE frame gives a true running total instead of lumping same-day batches together. A member with no burns has no row in burned; the LEFT JOIN and COALESCE(…, 0) treat that as nothing spent.
The alternative computes the running total with a correlated subquery and clamps with GREATEST/LEAST — quadratic per member but clear. The window version sorts each member's batches once.
Reference solution (MySQL)
WITH burned AS (
SELECT member_id, SUM(coins) AS total_burned FROM SuperCoinBurn GROUP BY member_id
), earned AS (
SELECT earn_id, member_id, earned_on, coins,
SUM(coins) OVER (PARTITION BY member_id ORDER BY earned_on, earn_id) AS cum_coins
FROM SuperCoinEarn
)
SELECT e.earn_id, e.member_id,
LEAST(e.coins, e.cum_coins - COALESCE(b.total_burned, 0)) AS coins_left
FROM earned e
LEFT JOIN burned b ON b.member_id = e.member_id
WHERE e.cum_coins - COALESCE(b.total_burned, 0) > 0
ORDER BY e.member_id, e.earned_on, e.earn_idAnother way
SELECT earn_id, member_id, coins_left FROM (
SELECT e.earn_id, e.member_id, e.earned_on,
GREATEST(0, LEAST(e.coins,
(SELECT SUM(x.coins) FROM SuperCoinEarn x
WHERE x.member_id = e.member_id
AND (x.earned_on < e.earned_on OR (x.earned_on = e.earned_on AND x.earn_id <= e.earn_id)))
- (SELECT IFNULL(SUM(b.coins), 0) FROM SuperCoinBurn b WHERE b.member_id = e.member_id))) AS coins_left
FROM SuperCoinEarn e
) t
WHERE coins_left > 0
ORDER BY member_id, earned_on, earn_id← Flipkart: Running GMV Through the Sale by Category · Flipkart: Big Billion Days GMV by Sale Day Against Last Year →