How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Anthropic.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anthropic during technical interviews.

Account Balance with Expiring Grants | Anthropic Coding Question

Quick Overview

This question evaluates the ability to design a data structure that tracks time-limited credit grants, prioritizing expiration order during spending and querying. It tests simulation and greedy-ordering skills within a coding and algorithms context, commonly used to assess practical handling of stateful, timestamp-driven systems under efficiency constraints.

Account Balance with Expiring Grants

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Account Balance with Expiring Grants You are modeling a prepaid-credit ledger. Credits are added as time-limited **grants**; a grant can only be spent while it is active, and any unspent portion is forfeited when it expires. Spending always draws from the credits that will expire soonest, so the customer keeps their longest-lived credit as long as possible. The ledger is driven by a list of operations applied in **non-decreasing timestamp order**. Implement a function that receives `ops: List[List[str]]` and returns `List[str]` containing one entry for each `GET_BALANCE` operation, in order. Other operations produce no output. Operations (all numeric arguments are integers): - `["ADD_GRANT", timestamp, amount, expire]` — add a grant of `amount` credits that is active during the half-open interval `[timestamp, expire)`. You may assume `expire > timestamp` and `amount > 0`. - `["SPEND", timestamp, amount]` — spend `amount` credits at `timestamp`. First drop any grant whose `expire <= timestamp`. Then deduct `amount` from the active grants, taking from the grant with the **earliest `expire` first** (break ties arbitrarily). If the total active balance is less than `amount`, deduct everything down to zero and ignore the unfunded remainder. - `["GET_BALANCE", timestamp]` — first drop any grant whose `expire <= timestamp`, then return the total remaining (unspent, unexpired) credit at `timestamp` as a string. ## Constraints - `1 <= len(ops) <= 10^5`. - Timestamps are non-decreasing integers in `[0, 10^15]`. - `amount` and `expire` are integers; `amount` in `[1, 10^9]`. - `SPEND` and `GET_BALANCE` must collectively run efficiently even when many small grants accumulate (favor a structure ordered by expiry over rescanning all grants each call). ## Example Input: ``` [ ["ADD_GRANT", "0", "100", "10"], ["ADD_GRANT", "1", "50", "5"], ["GET_BALANCE", "2"], ["SPEND", "3", "60"], ["GET_BALANCE", "4"], ["GET_BALANCE", "6"] ] ``` Output: ``` ["150", "90", "90"] ``` Explanation: at t=2 both grants are active (`100 + 50 = 150`). The `SPEND` of 60 at t=3 takes from the grant expiring at 5 first (50 credits), then 10 from the grant expiring at 10, leaving `90`. At t=4 the balance is `90`. At t=6 the second grant has expired but it was already fully consumed, so the balance is still `90` (the 90 remaining all live in the grant expiring at 10).

Quick Answer: This question evaluates the ability to design a data structure that tracks time-limited credit grants, prioritizing expiration order during spending and querying. It tests simulation and greedy-ordering skills within a coding and algorithms context, commonly used to assess practical handling of stateful, timestamp-driven systems under efficiency constraints.

You are modeling a prepaid-credit ledger. Credits are added as time-limited **grants**; a grant can only be spent while it is active, and any unspent portion is forfeited when it expires. Spending always draws from the credits that will expire soonest, so the customer keeps their longest-lived credit as long as possible. The ledger is driven by a list of operations applied in **non-decreasing timestamp order**. Implement `solution(ops)` that receives `ops: List[List[str]]` and returns `List[str]` containing one entry for each `GET_BALANCE` operation, in order. Other operations produce no output. All numeric arguments arrive as strings. Operations: - `["ADD_GRANT", timestamp, amount, expire]` — add a grant of `amount` credits active during the half-open interval `[timestamp, expire)`. Assume `expire > timestamp` and `amount > 0`. - `["SPEND", timestamp, amount]` — first drop any grant whose `expire <= timestamp`, then deduct `amount` from the active grants, taking from the grant with the **earliest `expire` first** (ties broken arbitrarily). If the total active balance is less than `amount`, deduct everything down to zero and ignore the unfunded remainder. - `["GET_BALANCE", timestamp]` — first drop any grant whose `expire <= timestamp`, then return the total remaining unspent, unexpired credit as a string. ## Example Input: ``` [["ADD_GRANT","0","100","10"],["ADD_GRANT","1","50","5"],["GET_BALANCE","2"],["SPEND","3","60"],["GET_BALANCE","4"],["GET_BALANCE","6"]] ``` Output: ``` ["150","90","90"] ``` At t=2 both grants are active (100+50). The SPEND of 60 at t=3 takes 50 from the grant expiring at 5, then 10 from the grant expiring at 10, leaving 90.

Constraints

1 <= len(ops) <= 10^5
Timestamps are non-decreasing integers in [0, 10^15]
amount is an integer in [1, 10^9]; expire > timestamp
SPEND and GET_BALANCE must run efficiently even with many small grants (use a structure ordered by expiry, not a rescan)

Examples

Input: [["ADD_GRANT","0","100","10"],["ADD_GRANT","1","50","5"],["GET_BALANCE","2"],["SPEND","3","60"],["GET_BALANCE","4"],["GET_BALANCE","6"]]

Expected Output: ["150","90","90"]

Explanation: At t=2 both grants live: 100+50=150. SPEND 60 takes 50 from the grant expiring at 5, then 10 from the grant expiring at 10, leaving 90. The already-emptied grant expiring at 5 contributes nothing later, so t=4 and t=6 both read 90.

Input: [["ADD_GRANT","0","100","10"],["GET_BALANCE","10"]]

Expected Output: ["0"]

Explanation: The interval is half-open [0,10); at t=10 the grant has expired (expire <= timestamp), so it is dropped and the balance is 0.

Input: [["ADD_GRANT","0","30","100"],["SPEND","5","50"],["GET_BALANCE","6"]]

Expected Output: ["0"]

Explanation: Only 30 credits exist; spending 50 drains everything to 0 and ignores the unfunded 20.

Input: [["GET_BALANCE","0"]]

Expected Output: ["0"]

Explanation: No grants have been added, so the balance is 0.

Input: [["ADD_GRANT","0","100","10"],["ADD_GRANT","0","50","5"],["GET_BALANCE","6"],["SPEND","7","30"],["GET_BALANCE","8"]]

Expected Output: ["100","70"]

Explanation: The 50-credit grant expiring at 5 is never spent and is forfeited by t=6, leaving 100. SPEND 30 at t=7 draws from the remaining grant (expiring at 10), leaving 70.

Input: [["ADD_GRANT","0","10","100"],["ADD_GRANT","0","20","50"],["ADD_GRANT","0","30","20"],["SPEND","5","45"],["GET_BALANCE","6"]]

Expected Output: ["15"]

Explanation: SPEND 45 goes earliest-expiry first: 30 from the grant expiring at 20, then 15 from the grant expiring at 50 (leaving 5 there), leaving the grant expiring at 100 untouched at 10. Total 5+10=15.

Hints

Keep grants in a min-heap keyed by expire time so the credit that expires soonest is always at the top — that is exactly what SPEND must consume first.
Both SPEND and GET_BALANCE begin the same way: lazily pop every grant at the top whose expire <= timestamp before doing anything else (the interval is half-open, so a grant expiring at t is inactive at t).
Maintain a running total that you decrement whenever you evict an expired grant or spend from one, so GET_BALANCE is O(1) instead of re-summing the whole heap.
If a SPEND asks for more than the live balance, drain every grant to zero and silently drop the shortfall — do not go negative.

Quick Overview