Practice/OpenAI/GPU Credit Tracker

GPU Credit Tracker

CodingMust

Problem

Implement a GPU credit tracking system that manages time-based credits with expiration. The system allows adding credits that are valid within specific time windows, subtracting (using) credits, and querying the balance at any given timestamp.

Key Challenge: Operations can arrive out of order -- you might receive operations for timestamp 30, then timestamp 20, then query balance at timestamp 10. Your system must handle this correctly.

Important Requirements

• Out-of-order operations: Methods can be called in any chronological order. get_balance() must reconstruct the correct state at the queried timestamp regardless of call order.
• Expiration is inclusive: A credit with timestamp=10 and expiration=30 is valid during [10, 40].
• Subtraction priority: When subtracting, always consume credits that expire soonest first.
• No exceptions on subtract: The balance is allowed to go negative temporarily.
• Return None for invalid balance: get_balance() returns None if no credits are active at that timestamp OR if the balance would be negative.
• Single event per timestamp: Only one add or subtract occurs at any given timestamp.

Class Specification

` class GPUCredit: def init(self): ...

def add_credit(self, credit_id: str, amount: int,
               timestamp: int, expiration: int) -> None:
    """Add a credit valid during [timestamp, timestamp + expiration]."""

def subtract(self, amount: int, timestamp: int) -> None:
    """Use credits at timestamp. Expire-soonest consumed first."""

def get_balance(self, timestamp: int) -> int | None:
    """Balance at timestamp, or None if no credits / negative."""

`

Examples

Example 1: Basic Credit Lifecycle

` gpu = GPUCredit() gpu.add_credit('microsoft', 10, 10, 30) # Valid from 10 to 40

gpu.get_balance(0) # None (no credits yet) gpu.get_balance(10) # 10 (credit starts) gpu.get_balance(25) # 10 (still valid) gpu.get_balance(40) # 10 (last moment of validity) gpu.get_balance(41) # None (expired) `

Example 2: Credit with Subtraction

` gpu = GPUCredit() gpu.add_credit('amazon', 40, 10, 50) # Valid 10 to 60 gpu.subtract(30, 30)

gpu.get_balance(10) # 40 (before subtraction) gpu.get_balance(30) # 10 (40 - 30) gpu.get_balance(60) # 10 (still valid) gpu.get_balance(61) # None (expired) `

Example 3: Multiple Credits with Expiration Priority

` gpu = GPUCredit() gpu.add_credit('c1', 20, 10, 30) # Valid 10-40 gpu.add_credit('c2', 20, 40, 30) # Valid 40-70 gpu.add_credit('c3', 20, 20, 30) # Valid 20-50 gpu.add_credit('c4', 20, 30, 30) # Valid 30-60 gpu.subtract(45, 30)

At t=30: active credits sorted by expiration:

c1 (exp 40), c3 (exp 50), c4 (exp 60) -- c2 not active yet

Consume: c1=20 used, c3=20 used, c4=5 used (15 remaining)

gpu.get_balance(10) # 20 (only c1 active, no subtract yet) gpu.get_balance(30) # 15 (c1=0 + c3=0 + c4=15) gpu.get_balance(55) # 35 (c4=15 + c2=20; c1 and c3 expired) `

Example 4: Out-of-Order Operations

` gpu = GPUCredit() gpu.subtract(4, 30) # Subtract before any credits added gpu.get_balance(10) # None (no credits exist)

gpu.add_credit('a', 4, 20, 30) # Valid 20-50

gpu.get_balance(10) # None (credit not active at t=10) gpu.get_balance(20) # 4 (credit active, subtract at t=30 is later) gpu.get_balance(30) # 0 (4 - 4 = 0) gpu.get_balance(50) # 0 (still within valid period) gpu.get_balance(51) # None (expired) `

Example 5: Negative Balance Returns None

` gpu = GPUCredit() gpu.add_credit('openai', 10, 10, 30) # Valid 10-40 gpu.subtract(100, 20)

gpu.get_balance(10) # 10 (before subtraction) gpu.get_balance(20) # None (10 - 100 = -90, negative) gpu.get_balance(30) # None (still negative) `

Example 6: Overlapping Credits with Priority

` gpu = GPUCredit() gpu.add_credit('a', 4, 20, 40) # Valid 20-60 gpu.add_credit('b', 3, 30, 10) # Valid 30-40 gpu.subtract(2, 30)

At t=30: 'b' expires at 40 (sooner), 'a' expires at 60

Subtract 2 from 'b' first: b=3->1, a=4 unchanged

gpu.get_balance(30) # 5 (a=4 + b=1) gpu.get_balance(40) # 5 (both still valid) gpu.get_balance(41) # 4 (b expired, only a remains) gpu.get_balance(60) # 4 (a still valid) gpu.get_balance(61) # None (all expired) `

Approach

Key Insight: Store Everything, Recompute on Query

Since operations arrive out of order, the cleanest approach is to store all operations (credits and subtractions) and recompute the balance from scratch on each get_balance() call.

Algorithm for get_balance(t)

1. Copy credit amounts -- start with the original amount for each credit

2. Process subtractions in chronological order up to timestamp t:

   • For each subtraction, find credits active at the subtraction's timestamp
   • Sort active credits by expiration time (ascending)
   • Consume from the earliest-expiring credits first
   • Track any unmet debt (amount that couldn't be subtracted)

3. Sum remaining amounts of credits active at the query timestamp t

4. Return the balance minus unmet debt, or None if negative or no active credits

Why Recompute?

The interviewer may explicitly state that you don't need to optimize for performance. Focus on correctness first. Recomputing from scratch guarantees correctness regardless of operation order.

Test Cases to Consider

• No credits at query time
• Credits added after subtractions (out-of-order)
• Subtraction larger than available balance (negative)
• Multiple subtractions consuming the same credit pool
• Credit that expires between a subtraction and a later query
• Zero balance (should return 0, not None)

Optimization Discussion

If asked to optimize:

• Cache computed balances at specific timestamps and invalidate on new operations
• Use a sorted data structure (e.g., SortedList) for credits by expiration
• Incremental updates rather than full recomputation
• Segment tree for range-based balance queries