89. Design GPU Credit Calculator

Design GPU Credit Calculator
Build a GPU credit calculator for a single account. Credits are added over time, can be partially consumed, and expire after a fixed lifetime.

The calculator must support adding credit grants, spending credits, and querying the remaining balance at any timestamp.

Critical constraint: all operations that record a ledger event happen at the current timestamp, and these timestamps are non-decreasing (monotonically increasing) across such calls.

Specifically:
  • addCredit(...) records an ADD event at the current timestamp.
  • useCredit(...) records a USE event at the current timestamp (if successful).
  • getBalance(timestamp) is a read-only query and may be called for any timestamp (past or future).

Because grants expire, you must treat credits as a time-ordered ledger (events that you replay up to a timestamp), not as a single evolving “current balance”.

Key Definitions

  • Credit Grant: a bucket of credits added by creditId, with a start time and an expiry time.
  • Active Credit: a grant is active at time t if startTimestamp ≤ t ≤ endTimestamp.
  • Expiry Rule: if a grant is added at timestamp with expiration time units, then:
    • It is usable for all timestamps in [timestamp, timestamp + expiration-1] (inclusive).
    • It becomes expired starting at timestamp + expiration.
  • Earliest-Expiry-First Spending: when spending, consume credits from the active grants that expire sooner first (to minimize waste).
    If there are multiple such grants then spend from the grant with lexicographically smaller creditId.
  • Current Timestamp: an integer time value supplied by the caller. For all calls that record ledger events, the provided timestamp is the current time and is non-decreasing across those calls.

Method Signatures

1) Add credit

boolean addCredit(String creditId, int amount, int timestamp, int expiration)
  • timestamp is the current timestamp of this event.
  • creditId uniquely identifies a single credit grant.
  • amount credits become usable starting at timestamp.
  • The grant expires after expiration time units (see Expiry Rule).
  • Return false if a grant with the same creditId already exists; otherwise store it and return true.

2) Spend credit

boolean useCredit(int timestamp, int amount)
  • timestamp is the current timestamp of this event.
  • Spend amount credits at the given timestamp.
  • Only credits that are active at timestamp can be spent.
  • Spending must follow earliest-expiry-first. If multiple active grants have the same expiry time, break ties by creditId lexicographically.
  • If there is insufficient active credit at timestamp, return false and do not record this spend.
  • If successful, record the spend and return true.

3) Query balance

Integer getBalance(int timestamp)
  • Return the total remaining credits usable at the given timestamp, after applying all recorded adds and successful spends with time ≤ timestamp.
  • getBalance does not have to be monotonic and can query any timestamp.
  • Return 0 if no balance has been added or all balance has been spent or expired.

Constraints

  • 1 ≤ amount ≤ 10000
  • 0 ≤ timestamp ≤ 10^9
  • 0 ≤ expiration ≤ 10^9
  • creditId is a non-empty string.

Example 1: Multiple grants (expiry + earliest-expiry-first + lexicographic tie-break) + duplicate add + failed spend + 0 balance

GPUCreditCalculator gpuCredit = new GPUCreditCalculator();

gpuCredit.addCredit(creditId="b", amount=5, timestamp=10, expiration=5) → true
"b" usable in [10, 14], expires starting at 15.

gpuCredit.addCredit(creditId="a", amount=7, timestamp=11, expiration=4) → true
"a" usable in [11, 14], expires starting at 15. (Same expiry as "b"; tie-break by creditId.)

gpuCredit.addCredit(creditId="c", amount=10, timestamp=12, expiration=10) → true
"c" usable in [12, 21], expires starting at 22.

gpuCredit.addCredit(creditId="a", amount=1, timestamp=13, expiration=10) → false
Duplicate creditId "a" is rejected.

gpuCredit.getBalance(timestamp=9) → 0
At time 9, no grants have started yet, so balance is 0 .

gpuCredit.useCredit(timestamp=14, amount=21) → true
At time 14, active credits total 22 ("a" 7, "b" 5, "c" 10). Spend earliest-expiry-first: "a" (lexicographically smaller than "b") then "b" then "c". Consume 7 from "a", 5 from "b", and 9 from "c" → remaining: "c" has 1.

gpuCredit.getBalance(timestamp=14) → 1
Only "c" has 1 remaining at time 14.

gpuCredit.useCredit(timestamp=15, amount=2) → false
At time 15, "a" and "b" are expired; only "c" has 1 active credit, so spending 2 fails and is not recorded.

gpuCredit.getBalance(timestamp=15) → 1
Failed spend at time 15 did not change the ledger; "c" still has 1.

gpuCredit.getBalance(timestamp=21) → 1
At time 21, "c" is still active and still has 1 remaining.

gpuCredit.getBalance(timestamp=22) → 0
At time 22, "c" is expired (usable only through 21), so balance is 0 → 0.

Example 2: Time-travel queries (past/future) + spend affects only timestamps ≥ spend time + expiration=0 edge

GPUCreditCalculator gpuCredit = new GPUCreditCalculator();

gpuCredit.addCredit(creditId="x", amount=10, timestamp=50, expiration=60) → true
"x" usable in [50, 109], expires starting at 110.

gpuCredit.getBalance(timestamp=40) → 0
At time 40, "x" hasn't started yet, so balance is 0 .

gpuCredit.getBalance(timestamp=100) → 10
At time 100, "x" is active and unspent.

gpuCredit.useCredit(timestamp=105, amount=5) → true
At time 105, "x" is active; spend 5, leaving 5.

gpuCredit.getBalance(timestamp=100) → 10
Spend at 105 is after 100, so it does not affect the balance at time 100.

gpuCredit.getBalance(timestamp=106) → 5
At time 106, the spend at 105 applies; remaining is 5.

gpuCredit.addCredit(creditId="zero", amount=7, timestamp=110, expiration=0) → true
Expiration=0 means usable window is empty ([110, 109]), so "zero" is never active.

gpuCredit.getBalance(timestamp=109) → 5
At time 109, "x" is still active and has 5 remaining; the add at time 110 is after 109 so it doesn't apply.

gpuCredit.getBalance(timestamp=110) → 0
At time 110, "x" is expired (starting at 110) and "zero" is never active, so balance is 0 .

gpuCredit.useCredit(timestamp=111, amount=1) → false
At time 111, there is no active credit, so the spend fails and is not recorded.




Please use Laptop/Desktop or any other large screen to add/edit code.