Implement credit ledger with out-of-order timestamps

Problem

You are implementing a GPU credit ledger that supports adding credits, charging credits, and querying balances. Requests can arrive in any timestamp order (timestamps are not monotonic).

Design a data structure/class that supports these operations:

• addCredit(timestamp, amount)
  • Records that amount credits were added at time timestamp.
• chargeCredit(timestamp, amount)
  • Records that amount credits were requested to be charged at time timestamp.
• getBalance(timestamp) -> integer
  • Returns the effective balance at time timestamp, computed using all recorded requests whose timestamps are <= timestamp.

Rules for computing the effective balance

When computing the balance at time T, consider all recorded addCredit and chargeCredit events with timestamp <= T and process them in increasing timestamp order.

• Start from balance 0.
• For an addCredit, increase the balance.
• For a chargeCredit:
  • If current balance is >= amount, deduct it (the charge succeeds).
  • Otherwise, do not deduct it (the charge is declined/ignored).

Tie-breaking (same timestamp)

If multiple events share the same timestamp, process them in this order:

1. All addCredit events at that timestamp (in insertion order)
2. All chargeCredit events at that timestamp (in insertion order)

Notes

• Requests arrive out of order; you are allowed to cache/store all requests.
• There is no strict time complexity requirement; correctness is the priority.

Deliverable

Provide the API and implement the logic so that repeated calls to getBalance(T) always return the correct value according to the rules above.

Credit Ledger with Out-of-Order Timestamps

You are implementing a simple GPU credit ledger. The system receives a stream of requests in the order they arrive, but each request also contains a timestamp, and timestamps are NOT guaranteed to be increasing.

Supported request types:

1. ["GRANT", user, amount, timestamp]

   • Adds amount credits to user at timestamp.

2. ["CHARGE", user, amount, timestamp]

   • Attempts to subtract amount credits from user at timestamp.
   • A charge is applied only if the user's balance at that moment (after processing all earlier/equal timestamps) is >= amount.
   • If insufficient credits, the charge is ignored (no change).

3. ["GET", user, timestamp]

   • Returns the user's balance at timestamp, considering ONLY the GRANT/CHARGE requests that have arrived so far.

Important details:

• Requests arrive over time; a later-arriving request with an earlier timestamp can affect future GET results, but it must not retroactively change past GET outputs.
• When multiple events for the same user have the same timestamp, process them in the order they arrived in the input stream (stable tie-breaker).

Return a list of balances for every GET request, in the order the GET requests appear.

Constraints

• 1 <= len(requests) <= 20000
• user is a non-empty string
• 0 <= amount <= 10^9
• -10^9 <= timestamp <= 10^9
• Timestamps are not guaranteed to be ordered
• If multiple events share the same timestamp for a user, they must be applied in arrival order

Examples

Example 1

Input: ([["GRANT","alice",10,5],["CHARGE","alice",4,7],["GET","alice",7],["CHARGE","alice",10,6],["GET","alice",7]],)
Output: [6, 0]

Explanation: First GET sees grant@5 then charge4@7 => 6. Second GET also sees a new charge10@6, so at t=7: grant10 -> charge10 succeeds -> balance 0; charge4 then fails => 0.

Example 2

Input: ([["GRANT","alice",5,10],["GRANT","bob",7,1],["CHARGE","bob",2,3],["GET","bob",2],["GET","bob",3],["GET","alice",9],["GET","alice",10]],)
Output: [7, 5, 0, 5]

Explanation: bob@2 includes only grant7@1 => 7. bob@3 includes charge2@3 => 5. alice@9 excludes grant@10 => 0. alice@10 includes grant5 => 5.

Hints

1. Cache all GRANT/CHARGE events seen so far per user; when you get a GET, recompute that user's balance by sorting applicable events by (timestamp, arrival_index).
2. To handle equal timestamps correctly, store each event with its position in the input stream and use it as a stable tie-breaker when sorting.

Approach

Approach. The tricky requirement is that requests arrive in stream order but carry out-of-order timestamps, and a GET must reflect every GRANT/CHARGE that has arrived so far whose timestamp is <= t — yet must not retroactively rewrite earlier GET outputs. The code handles this by storing events and recomputing the balance from scratch on every GET, using only the events that have arrived up to that point.

Data structure. events is a defaultdict(list) keyed by user. For each GRANT/CHARGE, it appends a tuple (timestamp, idx, op, amount), where idx is the request's position in the input stream — this preserves arrival order as a stable tie-breaker.

Handling a GET (user, t).

• Collect that user's events with ts <= t (applicable).
• Sort by (timestamp, arrival_idx) so same-timestamp events apply in arrival order.
• Replay them: GRANT does bal += amt; CHARGE subtracts only if bal >= amt, otherwise the charge is silently ignored.
• Append bal. If the user has no events yet, append 0.

Why it's correct. Because each GET rebuilds the balance from the current event set in timestamp/arrival order, a later-arriving event with an earlier timestamp naturally affects future GETs (it's now in the set) without altering past results (which were computed before it existed). The bal >= amt guard enforces the "insufficient credits → ignore charge" rule, and re-evaluating it during each replay means a charge that was once skipped can succeed once a backdated grant is added (see test 4: a charge ignored at first becomes effectively reordered behind a grant, yielding [10, 11]).

• Time complexity: O(G · K log K), where G is the number of GET requests and K is the number of stored events for the queried user. Each GET filters and sorts that user's applicable events, costing O(K log K), and replays them in O(K). GRANT/CHARGE are O(1) appends.
• Space complexity: O(E), where E is the total number of GRANT/CHARGE events stored across all users. Each GET additionally builds a temporary applicable list of size up to K, but that is transient per query.