Amazon: AWS Promotional Credits Applied Month by Month

Hard
595.

Amazon: AWS Promotional Credits Applied Month by Month

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

ColumnType
account_idint
credit_amountint
expires_monthchar

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

ColumnType
account_idint
bill_monthchar
bill_amountint

Primary key (together): account_id, bill_month.

One row per account per billed month ('YYYY-MM'), in dollars; months with no usage have no row.

Example

The rows must come back in the order shown.

CreditGrant

account_idcredit_amountexpires_month
20110002025-06
2025002025-03

MonthlyBill

account_idbill_monthbill_amount
2012025-02300
2012025-03450
2012025-05400
2012025-07200
2022025-02120
2022025-04300
2032025-0290

Output

account_idbill_monthcredit_appliedamount_due
2012025-023000
2012025-034500
2012025-05250150
2012025-070200
2022025-021200
2022025-040300
2032025-02090
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.

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

ColumnType
account_idint
credit_amountint
expires_monthchar

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

ColumnType
account_idint
bill_monthchar
bill_amountint

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_idcredit_amountexpires_month
20110002025-06
2025002025-03

MonthlyBill

account_idbill_monthbill_amount
2012025-02300
2012025-03450
2012025-05400
2012025-07200
2022025-02120
2022025-04300
2032025-0290

Output

account_idbill_monthcredit_appliedamount_due
2012025-023000
2012025-034500
2012025-05250150
2012025-070200
2022025-021200
2022025-040300
2032025-02090

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_month

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

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