eSIM Data Wallet with Expiring Bundles and Late Usage Records

A travel eSIM provider sells prepaid data bundles (for example "50 MB, valid for 10 days"). A customer's wallet can hold several bundles at once. Every bundle has a validity window, and any data left on it when it expires is lost. Usage records come from partner mobile networks in batches, often hours late, so events reach the billing service out of timestamp order.

Part 1: Wallet with expiry-first consumption

Implement:

class DataWallet:
    def add_bundle(self, bundle_id: str, amount: int, start: int, expires: int) -> None
    def consume(self, amount: int, at: int) -> None      # a usage record, in MB
    def balance(self, at: int) -> int                    # MB usable at time `at`
    def overage(self, at: int) -> int                    # total MB used without coverage up to `at`

Rules (treat these as already agreed with the interviewer):

• A bundle is usable on the half-open interval [start, expires).
• Usage draws from the usable bundle that expires soonest, then the next soonest, and so on. Ties go to the earlier start, then the smaller bundle_id.
• If usable data can't cover a usage record, the wallet is drained to zero and the uncovered remainder is added to overage (billed separately). The balance never goes negative.
• At equal timestamps, bundles take effect before usage.
• Calls arrive in any timestamp order. Every answer must equal what you would get by applying all events received so far in timestamp order.

add_bundle("b1", 50, start=0, expires=10)
add_bundle("b2", 30, start=2, expires=6)
consume(20, at=4)                  # taken from b2
balance(4) -> 60     balance(6) -> 50   # b2's last 10 MB expire at 6
consume(15, at=3)                  # arrives late
balance(4) -> 45     balance(6) -> 45   # b2 is now used up before it expires
add_bundle("b0", 10, start=1, expires=3)   # late; expires before the t=3 usage
balance(2) -> 90     balance(4) -> 45
consume(100, at=8)
balance(8) -> 0      overage(8) -> 55     balance(7) -> 45

Part 2: Don't replay from the beginning every time

A heavy user's wallet accumulates hundreds of thousands of usage records, and almost all late records are only a little late. Replaying the whole history for every balance call is too slow. Make reads cheap when new events land near the end of the timeline, while keeping answers exactly correct for arbitrarily late events.

Constraints

• Integer amounts and timestamps. expires > start, and bundle ids are unique.
• Up to 10^5 events per wallet. Wallets are independent.