Flipkart: SuperCoins Left in Each Earn Batch After FIFO Burns

Hard
666.

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

ColumnType
earn_idint
member_idint
earned_ondate
coinsint

Primary key: earn_id.

One row per batch of coins credited for a purchase.

Table: SuperCoinBurn

ColumnType
burn_idint
member_idint
burned_ondate
coinsint

Primary key: burn_id.

One row per redemption. A member's burns never add up to more than their earns.

Example

The rows must come back in the order shown.

SuperCoinEarn

earn_idmember_idearned_oncoins
172024-06-01100
272024-06-15200
372024-07-02150
492024-06-1080
592024-06-10120
6122024-08-0160

SuperCoinBurn

burn_idmember_idburned_oncoins
172024-07-10150
272024-07-2050
392024-07-0180

Output

earn_idmember_idcoins_left
27100
37150
59120
61260
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.

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

ColumnType
earn_idint
member_idint
earned_ondate
coinsint

Primary key: earn_id.

One row per batch of coins credited for a purchase.

Table: SuperCoinBurn

ColumnType
burn_idint
member_idint
burned_ondate
coinsint

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_idmember_idearned_oncoins
172024-06-01100
272024-06-15200
372024-07-02150
492024-06-1080
592024-06-10120
6122024-08-0160

SuperCoinBurn

burn_idmember_idburned_oncoins
172024-07-10150
272024-07-2050
392024-07-0180

Output

earn_idmember_idcoins_left
27100
37150
59120
61260

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_id

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