The Question
Coding

FEFO Credit Management System

Design a resource management system (like GPU credits) that allows users to add credit packs with varying expiration dates. Implement a mechanism to consume credits such that the credits expiring soonest are used first (FEFO). The system must support adding credits, consuming a specific amount at a given timestamp, and querying the current valid balance.
Python
Heap
Priority Queue
Greedy
Questions & Insights

Clarifying Questions

What is the credit consumption policy? (Assumption: We use the First-Expiring-First-Out (FEFO) strategy to maximize user benefit by consuming credits that would expire soonest.)
How are timestamps and expiration handled? (Assumption: All timestamps are integers representing Unix time or sequence numbers. A credit is considered valid at current_time if expiry_time >= current_time.)
What should happen if the consumption amount exceeds the total available credits? (Assumption: The system should deduct as much as possible and return the remaining balance, or throw an error indicating insufficient funds. We will implement it to return the amount actually consumed or raise an exception.)
Are inputs chronological? (Assumption: Credit additions can happen at any time, but consumption requests are typically processed in non-decreasing chronological order.)

Thinking Process

Efficient Retrieval: To always consume the credit pack that expires soonest, a Min-Heap (Priority Queue) is the ideal data structure. It allows O(1) access to the earliest expiration and O(\log N) for insertions and deletions.
Lazy Deletion: Instead of scanning all credits to remove expired ones every second, we only remove expired credits when a consume or get_balance operation is triggered. We pop from the top of the heap until the top pack is still valid.
State Management: We need to track the total balance separately for O(1) balance queries, adjusting it whenever credits are added, consumed, or found to be expired.
Granular Consumption: When a consumption event occurs, a single request might span multiple credit packs. We iterate through the heap, exhausting one pack at a time until the request is satisfied or no valid credits remain.
Implementation Breakdown

Problem Set

Functional Requirements:
add_credits(amount, expiry_time): Add a pack of credits.
consume_credits(amount, current_time): Deduct credits using FEFO logic.
get_balance(current_time): Return total valid credits at a given time.
Constraints:
High frequency of credit additions and balance checks.
Timestamps are non-negative.
Credits are positive numbers.

Approach

Algorithm: FEFO (First-Expiring-First-Out) using a Greedy approach.
Data Structure: Min-Heap (heapq in Python) storing tuples of (expiry_time, amount).
Complexity:
Add: O(\log N) where N is the number of active credit packs.
Consume: O(K \log N) where K is the number of packs exhausted/expired during the call.
Balance: O(K \log N) to clear expired packs.

Implementation

Wrap Up

Advanced Topics

Floating Point Precision: If credits are floating-point values (e.g., 0.005 cents), care must be taken with precision. Using decimal.Decimal or storing everything as integers (micros) is preferred.
Persistence: In a real-world Staff Engineer scenario, this manager would be backed by a database. The heap would represent a cache or an in-memory view of the DB table credit_packs indexed by expiry_date.
Concurrency: To handle simultaneous usage from multiple GPU clusters, the consume_credits logic should be wrapped in an atomic transaction (e.g., using Redis WATCH/MULTI or SQL SELECT FOR UPDATE) to prevent double-spending.
Scalability: If one user has millions of small credit packs, the heap operations might slow down. We could aggregate packs with the same expiration date to reduce heap size.