Q4 - Stripe Tiered Pricing Problem

As a Backend Engineer at Stripe, you work on Billing, the system that turns metered usage into an invoice. Many of Stripe's customers do not charge a flat price per unit. They use tiered pricing: the first slice of usage costs one rate, the next slice a different rate, and so on. Your job is to build the calculator that turns a usage quantity into an amount owed, in exact cents.

A pricing tier schedule is given as a list of [up_to, unit_amount] pairs, in ascending order. up_to is the largest cumulative quantity that tier covers, and unit_amount is its price per unit in whole cents. The final tier is unbounded, it covers every unit beyond the previous tier, and its up_to is given as -1.

This problem comes in three progressive parts. You will start with volume pricing, then graduated pricing, and finally work backwards from a budget to the number of units it can buy. Each part uses the same tier schedule and builds directly on the previous one.

Throughout the examples we use this schedule:

tiers = [
  [10, 50],   # units 1-10:   50 cents each
  [20, 40],   # units 11-20:  40 cents each
  [-1, 30],   # units 21+:    30 cents each  (the unbounded last tier)
]

Part 1: Volume Pricing (~10 minutes)

In volume pricing, the entire quantity is billed at the unit price of the single tier the quantity lands in. Buy 15 units and the schedule above puts all 15 in tier 2, so every one of them costs 40 cents, not just the units above 10.

Implement volume_price(tiers, quantity). The function should:

• Find the tier that contains quantity: the first tier whose up_to is greater than or equal to quantity, or the final unbounded tier (up_to == -1) if the quantity is larger than every bound.
• Return quantity * unit_amount for that tier, in cents.
• Return 0 when quantity is 0.

Input: tiers = [[10, 50], [20, 40], [-1, 30]], quantity = 8

Output: 400
Explanation: 8 is within the first tier (up to 10), so all 8 units cost 50 cents each.
8 * 50 = 400 cents.

Input: tiers = [[10, 50], [20, 40], [-1, 30]], quantity = 15

Output: 600
Explanation: 15 lands in the second tier (11 to 20), so every unit is priced at 40 cents,
including the first 10. 15 * 40 = 600 cents. That "all units at one rate" is what makes it volume
pricing.

Input: tiers = [[10, 50], [20, 40], [-1, 30]], quantity = 25

Output: 750
Explanation: 25 is past the last finite bound (20), so it falls in the unbounded tier at
30 cents. 25 * 30 = 750 cents.

Solution - Part 1

Scan the tiers in order and stop at the first one that can hold the whole quantity. A finite tier holds it when quantity <= up_to; the unbounded tier (up_to == -1) always holds it, so it acts as the catch-all at the end of the list. Once you have the tier, the price is a single multiplication.

def volume_price(tiers: list, quantity: int) -> int:
    if quantity <= 0:
        return 0
    for up_to, unit_amount in tiers:
        # -1 marks the final, unbounded tier: it holds any quantity
        if up_to == -1 or quantity <= up_to:
            return quantity * unit_amount
    return 0

Complexity Analysis

• Time Complexity: O(t), one scan over the t tiers to find the bracket.
• Space Complexity: O(1), no extra storage.

Part 2: Graduated Pricing (~15 minutes)

Volume pricing charges every unit at one rate. Graduated pricing is what most usage plans actually use: each unit is billed at the rate of the tier it falls into. The first 10 units cost 50 cents each, the next 10 cost 40 cents each, and everything above that costs 30 cents each. You fill the tiers in order.

Implement graduated_price(tiers, quantity). The function should:

• Fill tier 1 first (up to its up_to), then tier 2, and so on, until all quantity units are priced.
• Charge each block of units at its own tier's unit_amount.
• Return the total in cents, and 0 when quantity is 0.

Input: tiers = [[10, 50], [20, 40], [-1, 30]], quantity = 15

Output: 700
Explanation: The first 10 units fill tier 1 at 50 cents (500), the next 5 fall in tier 2 at
40 cents (200). 500 + 200 = 700 cents. Compare with volume pricing, which charged 600 for the
same 15 units: graduated always costs at least as much, because the early units keep their higher
rate.

Input: tiers = [[10, 50], [20, 40], [-1, 30]], quantity = 25

Output: 1050
Explanation: 10 units at 50 (500), 10 units at 40 (400), and the last 5 in the unbounded
tier at 30 (150). 500 + 400 + 150 = 1050 cents.

Input: tiers = [[10, 50], [20, 40], [-1, 30]], quantity = 8

Output: 400
Explanation: All 8 units fit inside tier 1, so graduated and volume pricing agree here:
8 * 50 = 400 cents. They only diverge once the quantity crosses a tier boundary.

Solution - Part 2

Walk the tiers while carrying a running count of how many units you have already priced (covered) and how many are still remaining. For a finite tier, the number of units that fall in it is up_to - covered, but never more than what is left, so take min(remaining, up_to - covered). The unbounded tier simply takes whatever remains. Multiply each block by its rate and add it up.

Here is the walk on quantity = 15:

tiers = [ (up_to 10, 50c), (up_to 20, 40c), (inf, 30c) ],  quantity = 15

tier 1 (up to 10):  take min(15, 10-0)  = 10 units  x 50c = 500c   (5 remaining)
tier 2 (up to 20):  take min(5,  20-10) = 5 units   x 40c = 200c   (0 remaining, stop)
                                                     total = 700c

def graduated_price(tiers: list, quantity: int) -> int:
    if quantity <= 0:
        return 0
    total, covered, remaining = 0, 0, quantity
    for up_to, unit_amount in tiers:
        # units that fall in this tier: the whole remainder for the last
        # tier, otherwise only up to this tier's cap
        tier_units = remaining if up_to == -1 else min(remaining, up_to - covered)
        total += tier_units * unit_amount
        remaining -= tier_units
        if up_to != -1:
            covered = up_to
        if remaining == 0:
            break
    return total

Complexity Analysis

• Time Complexity: O(t), one pass over the t tiers.
• Space Complexity: O(1), a few running counters.

Part 3: What Fits a Budget (~25 minutes)

Now turn the question around. A customer has a fixed budget in cents and asks: under graduated pricing, how many whole units can I buy? Return the largest number of units whose graduated cost does not exceed the budget.

Implement max_units(tiers, budget). The function should:

• Price units with the graduated rules from Part 2.
• Return the largest units such that the graduated cost of units is less than or equal to budget.
• Return 0 when the budget cannot even afford the first unit. You may assume every unit_amount is at least 1 cent.

Input: tiers = [[10, 50], [20, 40], [-1, 30]], budget = 700

Output: 15
Explanation: Graduated cost of 15 units is exactly 700 (500 + 200), and a 16th unit would
add 40 more, going over. So 15 units fit.

Input: tiers = [[10, 50], [20, 40], [-1, 30]], budget = 745

Output: 16
Explanation: 16 units cost 500 + 6*40 = 740, which fits in 745. A 17th unit would cost 40
more (780 total), over budget. The 5 leftover cents are not enough for another unit.

Input: tiers = [[10, 50], [20, 40], [-1, 30]], budget = 30

Output: 0
Explanation: The very first unit costs 50 cents, and the budget is only 30. Nothing is
affordable, so the answer is 0.

Solution - Part 3

The key observation is that graduated cost only ever goes up as you add units, so you can be greedy and fill the tiers in order. At each tier, ask how many units the leftover budget can afford at that tier's rate: affordable = remaining_budget / unit_amount (integer division). Two cases:

• If you cannot even fill the whole tier (affordable is less than the tier's capacity, or you are at the unbounded tier), then the budget runs out right here. Buy affordable units and stop.
• Otherwise the budget covers the whole tier. Buy all of it, subtract its cost, and move to the next tier where units are (usually) cheaper.

The one subtlety is the boundary: only stop when you cannot fill the tier. If the budget affords exactly the whole tier, buy it and continue, because the leftover cents might still buy a unit or two in the next tier.

Here is the walk on budget = 745:

tiers = [ (up_to 10, 50c), (up_to 20, 40c), (inf, 30c) ],  budget = 745c

tier 1 @50c: 745 / 50 = 14 affordable, but the tier holds only 10  ->  buy all 10, spend 500c  (245c left)
tier 2 @40c: 245 / 40 = 6 affordable, the tier holds 10, so 6 fits  ->  buy 6, stop
             units = 10 + 6 = 16     (5c left over, not enough for a 7th unit at 40c)

def max_units(tiers: list, budget: int) -> int:
    if budget <= 0:
        return 0
    units, covered, remaining_budget = 0, 0, budget
    for up_to, unit_amount in tiers:
        affordable = remaining_budget // unit_amount
        # if we cannot fill this whole tier, buy what we can and stop
        if up_to == -1 or affordable < up_to - covered:
            return units + affordable
        # otherwise buy the whole tier and move on to the next
        tier_capacity = up_to - covered
        units += tier_capacity
        remaining_budget -= tier_capacity * unit_amount
        covered = up_to
    return units

Complexity Analysis

• Time Complexity: O(t) for the greedy walk over t tiers. The binary-search alternative is O(t log(budget)).
• Space Complexity: O(1).

Final Notes

Alright, here is the real talk on this one. It is not about a clever algorithm, it is about modeling money precisely and not dropping a unit at a boundary. Here is what actually matters:

1. Volume and graduated are two different things, say which is which: Volume prices the whole quantity at one tier's rate; graduated prices each unit by the tier it falls in. The fastest way to fail this question is to conflate them. Name the mode out loud before you code, and remember that graduated always costs at least as much as volume for the same quantity.

2. Stay in integer cents the whole way: Every amount is a whole number of cents. Do not reach for floats or percentages that could round, this is billing, and a rounding error becomes a customer who was overcharged. There are no fractional units here either: affordable is an integer division on purpose.

3. The unbounded last tier is a real case, not a footnote: The -1 sentinel means "everything above the previous bound." Handle it as its own branch (take all the remaining units, or all the affordable units) so you never do arithmetic on a bound that does not exist. A schedule can even be a single unbounded tier, which is just flat per-unit pricing.

4. Part 3 only works because cost is monotonic: Adding a unit never lowers the bill, so the greedy tier-walk is correct, and binary search on the answer works too. Point that monotonicity out; it is the reason both approaches are valid, and it is the systems instinct Stripe likes to hear.

5. Talk in billing terms: This is exactly how Stripe Billing prices metered usage. Mention that real tiers can also carry a flat_amount charged once per tier on top of the per-unit price, that a tier's rate can be zero (a free allowance), and that usage is often aggregated over a billing period before it is priced. You do not have to implement those, but naming them shows you have seen real pricing systems.

The bottom line: keep every value an integer, decide volume versus graduated before you write anything, and treat the tier boundaries and the unbounded tier with care. Get those right and all three parts fall out of one clean walk over the schedule, the kind of exact billing code Stripe trusts with real invoices.