Implement an expiring GPU credits ledger

Implement an expiring GPU credits ledger for multiple users with three operations:

1. add_credit(user_id, amount, expiry_time): add a lot of credits that expires at expiry_time.
2. subtract(user_id, amount, timestamp): atomically deduct amount at timestamp by consuming unexpired lots in order of earliest expiry first; lots with expiry_time <= timestamp are expired and cannot be used; if total unexpired balance < amount, the operation must fail and make no changes.
3. get_balance(user_id, timestamp): return the total unexpired balance at timestamp and a breakdown by remaining lots (amount, expiry_time). Assumptions: time is integer seconds; amounts are non-negative integers; partial consumption of a lot is allowed; exact expiry boundary uses the rule "valid iff timestamp < expiry_time". Tasks: implement the three functions; include tests for (a) single lot add and spend, (b) spending across multiple lots with different expiries, (c) attempts to spend after a lot expires, (d) insufficient-balance failure leaving state unchanged, (e) edge case at expiry boundary. Follow up: analyze time/space complexity; discuss how to optimize for many operations (e.g., data structures to achieve O(log n) per update) and how to persist/restore state.

Implement an Expiring GPU Credits Ledger

Implement an expiring GPU credits ledger that processes a stream of operations for multiple users and reports the results of every query.

What to implement

Implement:

def solution(operations):
    ...

operations is a list of operation tuples, processed in the given order. Each credit a user adds creates a separate lot with its own expiry time. A lot is valid (unexpired) at a timestamp t if and only if t < expiry_time (so a lot with expiry_time <= t is expired at t).

Return a list containing the result of every non-add operation, in the order the operations were processed. add operations produce no output.

Operations

Each tuple's first element is its type:

• ('add', user_id, amount, expiry_time) — Add a new lot of amount credits to user_id that expires at expiry_time. Produces no result. (An add with amount <= 0 adds nothing.)

• ('subtract', user_id, amount, timestamp) — Atomically deduct amount credits from user_id using only lots that are unexpired at timestamp, spending from the lot with the earliest expiry_time first. Partial consumption of a lot is allowed (a lot may be left with a reduced amount). Returns True on success or False on failure:

  • If the total of user_id's unexpired credits is less than amount, the operation fails: return False and leave the ledger unchanged (no lots are modified).
  • Otherwise it succeeds: deduct exactly amount earliest-expiry-first and return True.
  • A subtract of amount == 0 always succeeds (returns True) and changes nothing, even for a user with no credits.

• ('balance', user_id, timestamp) — Report user_id's credits that are unexpired at timestamp. Returns a tuple (total, breakdown) where:

  • total is the sum of all unexpired lot amounts.
  • breakdown is the list of remaining unexpired lots as (amount, expiry_time) pairs, sorted by expiry_time (ascending).

  A user with no unexpired credits has balance (0, []).

Notes

• Expired lots never count toward a balance, can never be spent, and should be treated as gone once their expiry_time has been reached at the timestamp of a query.
• Users are independent; an operation on one user_id never affects another.

Constraints

• 1 <= len(operations) <= 20000
• 0 <= amount <= 10^9
• 0 <= expiry_time, timestamp <= 10^9
• Operations are processed in the given order.
• A lot is usable exactly when timestamp < expiry_time.
• The timestamp values of the non-add operations (subtract and balance) are non-decreasing in processing order (time only moves forward across queries). add operations carry no timestamp and may specify any expiry_time.

Follow-up

Analyze the time and space complexity of your approach. Discuss how to optimize toward O(log n) updates and queries for heavy workloads, and describe how you would persist and restore the ledger state.

Examples

Example 1

Input: ([('add', 'u1', 50, 10), ('balance', 'u1', 5), ('subtract', 'u1', 20, 6), ('balance', 'u1', 6)],)
Output: [(50, [(50, 10)]), True, (30, [(30, 10)])]

Explanation: At time 5, the lot is still valid, so the balance is 50. Subtracting 20 at time 6 succeeds, leaving 30 in the same lot.

Example 2

Input: ([('add', 'alice', 10, 5), ('add', 'alice', 30, 20), ('subtract', 'alice', 10, 5), ('balance', 'alice', 5)],)
Output: [True, (20, [(20, 20)])]

Explanation: A lot is valid only when timestamp < expiry_time, so the lot expiring at 5 is already invalid at time 5. The subtraction uses the 30-credit lot expiring at 20, leaving 20.

Hints

1. Store each user's credits as separate lots instead of merging everything into one number, because expiry times matter during subtraction.
2. For atomic subtraction, first compute whether enough unexpired balance exists before changing any lot.

Approach

Idea. Each credit "lot" must be spent earliest-expiry-first, so per user we keep a min-heap keyed by [expiry_time, insertion_order, amount]. insertion_order is just a tiebreaker so heap entries never compare on the mutable amount. A parallel totals[user] caches the sum of all live lots so balance/feasibility checks are O(1).

prune(user, t) pops every lot at the heap top with expiry_time <= t, decrementing totals. Because a lot is valid iff t < expiry_time, expiry_time <= t means expired. Pruning only touches the cheapest-expiry lots, which are exactly the ones that die first — so the heap order makes expiry removal correct and cheap.

add pushes [expiry, order, amount] and bumps totals (skipping non-positive amounts, and skipping lots already expired relative to the last seen timestamp as an optimization).

subtract(user, amount, t) first prunes at t. If amount == 0 it trivially succeeds. Otherwise it checks totals[user] >= amount before mutating anything — this is what guarantees atomicity: a request that can't be fully covered returns False and leaves the ledger untouched. When it can succeed, it pops lots earliest-expiry-first, fully consuming each until the last, which is partially consumed and pushed back with its reduced amount.

balance(user, t) prunes then returns (totals[user], sorted lots as (amount, expiry) pairs).

Why correct: earliest-expiry-first is optimal because spending a soon-to-expire credit can never reduce future availability versus spending a longer-lived one; the pre-check makes failure side-effect-free; and pruning at every query keeps reported balances expiry-accurate.

• Space complexity: O(M), where M is the total number of unexpired lots stored across all users at once (one heap entry plus one totals counter per active lot/user).