0

Cloud usage bill from regional hourly rates

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Cloud usage bill from regional hourly rates

Companies: Stripe

Difficulty: Medium

Problem statement

You are writing the billing step for a cloud platform. A customer's usage report says which region they ran in and how many hours they used each service. A pricing table gives the hourly rate of every service in every region. Compute what the customer owes.

Implement:

def usage_cost(usage_report, pricing_table) -> dict:
    ...

Each argument is either a parsed JSON object (a dict) or a JSON string.

// usage_report
{
  "region": "eu-west-1",
  "usage": [
    {"service": "vm", "hours": 10},
    {"service": "db", "hours": 3.5},
    {"service": "vm", "hours": 2.25}
  ]
}

// pricing_table: region -> service -> hourly rate
{
  "eu-west-1":  {"vm": "0.12", "db": 0.5},
  "ap-south-1": {"vm": "0.10"}
}

Return {"total": "<amount>", "by_service": {"<service>": "<amount>", ...}}. Write amounts as strings with exactly two decimal places.

Part 1: flat hourly rates

  • A service can appear on several usage lines. Add its hours together.
  • Hours and rates can be integers, decimal numbers, or numeric strings. Hours can be fractional and are billed exactly.
  • Money must be exact. Do not do the arithmetic in binary floating point. Round each service's cost half up to the cent, once. The total is the sum of the rounded service lines.
  • Raise ValueError if the region has no prices, a service has no price in that region, or hours are negative or not a number.

Part 2: graduated tiers

A service's price can also be a list of tiers in increasing order, for example:

"egress": [{"up_to": 100, "rate": "0.09"}, {"up_to": null, "rate": "0.05"}]

The first 100 hours of that service, in total across all its usage lines, cost 0.09 each. Every hour after that costs 0.05. up_to: null means no upper limit. If the tiers end with a finite up_to and the usage is larger, raise ValueError.

Constraints

  • Up to 10^6 usage lines and 10^3 services per region.

Examples

For the report and table above:

{"total": "3.22", "by_service": {"db": "1.75", "vm": "1.47"}}

vm is 12.25 hours x 0.12 = 1.47. db is 3.5 hours x 0.5 = 1.75.

With the egress tiers above added to eu-west-1, a report with two egress lines of 60 and 90 hours costs 100 x 0.09 + 50 x 0.05:

{"total": "11.50", "by_service": {"egress": "11.50"}}

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Clarify first. The usage report names one region and lists usage lines, each a service and a number of hours. The pricing table maps each region to the hourly rate of every service sold there. Ask:

  • Can a service appear on several lines? (Yes. Add its hours together.)
  • Are hours fractional? (Yes, and billed exactly, not rounded up to the hour.)
  • What happens if the region or a service has no price? (Fail loudly. A bill with a silent $0 line is worse than no bill.)
  • How is money rounded? (Exact arithmetic, half-up to the cent, once per invoice line.)

Brute force is already the answer for Part 1. Look up the region's rates, then sum hours * rate over the lines. There is no algorithmic trick. The interview grades the money handling and the validation.

Money must be exact. 0.1 + 0.2 != 0.3 in binary floating point, and over many lines the error shows up in the cents. Convert every rate and every hour count to Decimal through str(...), so a JSON float such as 0.12 becomes exactly Decimal("0.12"). Do all the multiplication and addition in Decimal. Round only when a number goes on the invoice. Integer cents work for rates, but fractional hours times a rate in cents is still a fraction, so Decimal is simpler.

Aggregate before pricing. Group the hours by service first, then price each service once. With a flat rate the order does not matter. With graduated tiers (Part 2) it matters a lot: 60 + 90 hours must cross the 100-hour boundary once, not be priced as two lines that each stay in the first tier.

Graduated tiers. A tiered price is a list of {up_to, rate} in increasing order, with up_to: null meaning "and above". Walk the tiers with a running lower bound. Each tier bills min(hours, up_to) - lower hours at its rate. Stop when the hours are used up. If the last tier has a finite cap and hours remain, the pricing table is broken. Raise an error instead of giving the excess away.

Invariants.

  • Every amount is a Decimal. No float touches money.
  • Each invoice line (one per service) is rounded exactly once. The total is the sum of the rounded lines, so the lines always add up to the total a customer sees.
  • Any unknown region, unknown service, or negative or non-numeric hours raises ValueError before a partial bill is returned.

Code

import json
from collections import defaultdict
from decimal import Decimal, ROUND_HALF_UP
from typing import Any

CENT = Decimal("0.01")


def _dec(value: Any, what: str) -> Decimal:
    # str() first so 0.1 (float) becomes Decimal("0.1"), not 0.1000000000000000055...
    try:
        d = Decimal(str(value))
    except Exception:
        raise ValueError(f"{what} is not a number: {value!r}")
    if not d.is_finite() or d < 0:
        raise ValueError(f"{what} must be a non-negative number: {value!r}")
    return d


def _tiered_cost(hours: Decimal, price: Any, service: str) -> Decimal:
    """Price `hours` against a flat rate or a list of graduated tiers."""
    if not isinstance(price, list):
        return hours * _dec(price, f"rate for {service}")
    cost, lower = Decimal(0), Decimal(0)
    for tier in price:
        upper = tier.get("up_to")
        rate = _dec(tier["rate"], f"tier rate for {service}")
        top = hours if upper is None else min(hours, _dec(upper, "up_to"))
        if top > lower:
            cost += (top - lower) * rate
        if upper is None or hours <= top:
            return cost
        lower = top
    raise ValueError(f"tiers for {service} do not cover {hours} hours")


def usage_cost(usage_report: Any, pricing_table: Any) -> dict[str, Any]:
    """Return {"total": "12.34", "by_service": {service: "x.yy"}}.

    Both inputs may be dicts or JSON strings. Amounts are exact Decimals,
    rounded half-up to the cent once per service; total = sum of the lines.
    """
    if isinstance(usage_report, str):
        usage_report = json.loads(usage_report)
    if isinstance(pricing_table, str):
        pricing_table = json.loads(pricing_table)

    region = usage_report.get("region")
    if region not in pricing_table:
        raise ValueError(f"no prices for region {region!r}")
    rates = pricing_table[region]

    # Aggregate first: graduated tiers apply to a service's total hours.
    hours_by_service: dict[str, Decimal] = defaultdict(Decimal)
    for item in usage_report.get("usage", []):
        service = item.get("service")
        if service not in rates:
            raise ValueError(f"service {service!r} is not priced in {region}")
        hours_by_service[service] += _dec(item.get("hours"), f"hours for {service}")

    by_service: dict[str, Decimal] = {}
    for service in sorted(hours_by_service):
        raw = _tiered_cost(hours_by_service[service], rates[service], service)
        by_service[service] = raw.quantize(CENT, rounding=ROUND_HALF_UP)

    total = sum(by_service.values(), Decimal(0))
    return {
        "total": f"{total:.2f}",
        "by_service": {s: f"{c:.2f}" for s, c in by_service.items()},
    }

Complexity

  • Let n be the number of usage lines, s the number of distinct services, and t the number of tiers for a service.
  • Aggregation: O(n) time, O(s) space.
  • Pricing: O(s log s + sum of t) time for the sort and the tier walks. The sort is only there to give a stable breakdown order.
  • Overall: O(n + s log s + T) time and O(s) extra space, where T is the total tier count. Parsing JSON is linear in the input size.

Test cases

With eu-west-1 priced at vm: "0.12", db: 0.5, and egress tiered [{up_to: 100, rate: "0.09"}, {up_to: null, rate: "0.05"}]:

  • vm 10 h + vm 2.25 h + db 3.5 h -> vm 12.25 x 0.12 = 1.47, db 3.5 x 0.5 = 1.75, total "3.22". This is a repeated service and a float rate.
  • egress 60 h + egress 90 h -> 100 x 0.09 + 50 x 0.05 = total "11.50". Aggregating first matters here: pricing each line on its own would give 13.50.
  • Usage list empty -> {"total": "0.00", "by_service": {}}.
  • vm 0.05 h at "0.10" -> 0.005, rounds half up to "0.01".
  • Both inputs given as JSON strings -> same result as dicts.
  • Region "mars" not in the table -> ValueError.
  • Service db not priced in ap-south-1 -> ValueError.
  • Hours -1 or "x" -> ValueError.
  • A single capped tier [{up_to: 100, rate: 1}] with 100 h -> "100.00". With 200 h -> ValueError (tiers do not cover the usage).

Follow-ups

  • Several regions in one report. Make each usage line carry its own region (falling back to the report's). Key the aggregation by (region, service). Tier boundaries are usually per region, so they stay per key.
  • Timestamps instead of hours. Lines arrive as start/end times. Compute the duration, then decide the billing granularity with the interviewer: exact seconds, per started minute, or per started hour (ceil). Overlapping intervals for the same resource ID should be merged first (sort by start and sweep) so the customer is not billed twice for the same instance.
  • Free tier and discounts. A free allowance per service is a first tier with rate: 0, so the tier walk already handles it. A percentage discount or credit applies to the rounded line or the total. Say which one, because the cents differ.
  • Currency. Rates can be in each region's currency. Convert with a given FX table at a fixed point (per line or on the total), and round with the currency's minor unit (JPY has none). Never add amounts in different currencies.
  • Streaming and scale. For millions of lines, read the report as a stream and keep only the per-service running totals (O(s) memory). To bill many customers, partition by customer ID and run the same function per partition.

Interviewer expectations

Mid-level (L4)

  • Gets a correct total with lookups by region and service, including a service that appears twice.
  • Notices floating-point money is a problem, or fixes it when prompted, by using Decimal or integer cents.
  • Handles a missing region or service with a clear error instead of a KeyError or a silent zero.

Senior (L5)

  • Asks the clarifying questions about rounding, partial hours and unknown keys before writing code.
  • Converts floats through str into Decimal, rounds once per line, and makes the lines add up to the total.
  • Adds graduated tiers cleanly, and explains why hours must be aggregated per service before tiering.
  • Writes tests for the boundaries: exactly on a tier edge, half-cent rounding, empty usage.

Staff (L6+)

  • Treats the pricing table as untrusted config: validates tier order and coverage, and rejects bad tables when they load, not only when a bill is computed.
  • Designs for the follow-ups without rewriting: a (region, service) key, a pricing strategy per service (flat, tiered, volume), and an itemized output that an invoice and an audit log can both use.
  • Talks about idempotent re-runs, versioned price tables (the price at usage time, not at billing time), and how a correction to past usage produces an adjustment line instead of a changed invoice.

Sign in to comment, vote or remix.