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: ```python 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.