Manage GPU Credits with Expiration

Q: Manage GPU Credits with Expiration

This question evaluates data-structure design and algorithmic reasoning for time-based resource accounting, including handling expiring credits and out-of-order operations while maintaining efficient (logarithmic) performance constraints.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Question

Implement a GPU credit manager supporting out-of-order operations:

API

add_credit(id, amount, timestamp, expiration) // adds ‘amount’ credits usable in [timestamp, timestamp+expiration)

charge(amount, timestamp) // consume ‘amount’ credits at ‘timestamp’; always draw from credits that expire soonest first (tie-break by any order)

get_balance(timestamp) // return total unexpired credits available at ‘timestamp’

Constraints

add_credit and charge calls may arrive in arbitrary time order

charge(…) must fail silently or partially apply only if enough total balance exists at that moment

Design an efficient data structure to support ~10^5 operations with O(log n) per call.

Manage GPU Credits with Expiration

Question

Constraints

Comments (0)