Amazon: AWS Promotional Credits Applied Month by Month
Start-ups on a cloud credits programme get one promotional credit grant.
- Difficulty: Hard
- Topics: Window Functions, Joins, Conditional Logic
- Dialect: MySQL
- Problem: #595
Problem statement
Start-ups on a cloud credits programme get one promotional credit grant. Credits are applied to the account's monthly bills oldest month first, as much of each bill as the remaining credit covers, until the credit runs out. Bills for months after the grant's expires_month get no credit, even if some is left. Accounts with no grant get no credit.
For every bill, return account_id, bill_month, credit_applied and amount_due (the bill minus the credit applied). Order the rows by account_id, then bill_month.
A practice scenario set at Amazon: the tables and data are invented, and this is not a question from, or endorsed by, Amazon.
Tables
Table: CreditGrant
| Column | Type |
|---|---|
| account_id | int |
| credit_amount | int |
| expires_month | char |
Primary key: account_id.
At most one grant per account, in dollars; expires_month ('YYYY-MM') is the last month the credit can be used.
Table: MonthlyBill
| Column | Type |
|---|---|
| account_id | int |
| bill_month | char |
| bill_amount | int |
Primary key: account_id, bill_month.
One row per account per billed month ('YYYY-MM'), in dollars; months with no usage have no row.
Examples
Example 1
CreditGrant
| account_id | credit_amount | expires_month |
|---|---|---|
| 201 | 1000 | 2025-06 |
| 202 | 500 | 2025-03 |
MonthlyBill
| account_id | bill_month | bill_amount |
|---|---|---|
| 201 | 2025-02 | 300 |
| 201 | 2025-03 | 450 |
| 201 | 2025-05 | 400 |
| 201 | 2025-07 | 200 |
| 202 | 2025-02 | 120 |
| 202 | 2025-04 | 300 |
| 203 | 2025-02 | 90 |
Output
| account_id | bill_month | credit_applied | amount_due |
|---|---|---|---|
| 201 | 2025-02 | 300 | 0 |
| 201 | 2025-03 | 450 | 0 |
| 201 | 2025-05 | 250 | 150 |
| 201 | 2025-07 | 0 | 200 |
| 202 | 2025-02 | 120 | 0 |
| 202 | 2025-04 | 0 | 300 |
| 203 | 2025-02 | 0 | 90 |
How to solve Amazon: AWS Promotional Credits Applied Month by Month
Burning a balance down looks like it needs a loop, but here it does not. Until the credit is exhausted, it pays every bill in full; so when a month is billed, the credit left is simply the grant minus the total of all earlier bills, floored at 0. That total is a running sum over the earlier rows only — SUM(bill_amount) OVER (PARTITION BY account_id ORDER BY bill_month ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) — which is NULL for the first month, hence the COALESCE.
The credit applied to a month is then LEAST(bill, GREATEST(grant − billed_before, 0)): the whole bill while credit lasts, the remainder in the month it runs out, 0 afterwards. Expiry only cuts the tail: the months up to expires_month are a prefix of the account's months, so the running sum over earlier months is still the right amount spent, and months after expiry are forced to 0 by the CASE. Accounts without a grant come through the LEFT JOIN with a NULL credit and get 0. 'YYYY-MM' strings sort and compare in calendar order.
The first alternative does it the literal way: a recursive CTE walks each account's bills in order, carrying the remaining balance from one month to the next. The second computes the earlier bills' total with a correlated subquery. The window version sorts each account once; the recursive one does a join per month step.
Reference solution (MySQL)
WITH b AS (
SELECT m.account_id, m.bill_month, m.bill_amount, g.credit_amount, g.expires_month,
COALESCE(SUM(m.bill_amount) OVER (PARTITION BY m.account_id ORDER BY m.bill_month
ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING), 0) AS billed_before
FROM MonthlyBill m
LEFT JOIN CreditGrant g ON g.account_id = m.account_id
), c AS (
SELECT account_id, bill_month, bill_amount,
CASE WHEN credit_amount IS NULL OR bill_month > expires_month THEN 0
ELSE LEAST(bill_amount, GREATEST(credit_amount - billed_before, 0)) END AS credit_applied
FROM b
)
SELECT account_id, bill_month, credit_applied, bill_amount - credit_applied AS amount_due
FROM c
ORDER BY account_id, bill_monthAnother way
WITH RECURSIVE ordered AS (
SELECT m.account_id, m.bill_month, m.bill_amount, COALESCE(g.credit_amount, 0) AS credit_amount, g.expires_month,
ROW_NUMBER() OVER (PARTITION BY m.account_id ORDER BY m.bill_month) AS k
FROM MonthlyBill m LEFT JOIN CreditGrant g ON g.account_id = m.account_id
), walk AS (
SELECT account_id, bill_month, bill_amount, k,
CASE WHEN expires_month IS NULL OR bill_month > expires_month THEN 0 ELSE LEAST(bill_amount, credit_amount) END AS applied,
credit_amount - CASE WHEN expires_month IS NULL OR bill_month > expires_month THEN 0 ELSE LEAST(bill_amount, credit_amount) END AS remaining
FROM ordered WHERE k = 1
UNION ALL
SELECT o.account_id, o.bill_month, o.bill_amount, o.k,
CASE WHEN o.expires_month IS NULL OR o.bill_month > o.expires_month THEN 0 ELSE LEAST(o.bill_amount, w.remaining) END,
w.remaining - CASE WHEN o.expires_month IS NULL OR o.bill_month > o.expires_month THEN 0 ELSE LEAST(o.bill_amount, w.remaining) END
FROM walk w JOIN ordered o ON o.account_id = w.account_id AND o.k = w.k + 1
)
SELECT account_id, bill_month, applied AS credit_applied, bill_amount - applied AS amount_due
FROM walk ORDER BY account_id, bill_monthAnother way
SELECT m.account_id, m.bill_month,
IF(g.account_id IS NULL OR m.bill_month > g.expires_month, 0,
LEAST(m.bill_amount, GREATEST(g.credit_amount - COALESCE((SELECT SUM(p.bill_amount) FROM MonthlyBill p
WHERE p.account_id = m.account_id AND p.bill_month < m.bill_month), 0), 0))) AS credit_applied,
m.bill_amount - IF(g.account_id IS NULL OR m.bill_month > g.expires_month, 0,
LEAST(m.bill_amount, GREATEST(g.credit_amount - COALESCE((SELECT SUM(p.bill_amount) FROM MonthlyBill p
WHERE p.account_id = m.account_id AND p.bill_month < m.bill_month), 0), 0))) AS amount_due
FROM MonthlyBill m LEFT JOIN CreditGrant g ON g.account_id = m.account_id
ORDER BY m.account_id, m.bill_month← Amazon: Five-Star Review Bursts From Brand-New Accounts · Amazon: Suggested Subscribe & Save Cadence From Reorder Gaps →