Implement a GPU credit ledger: grant credits, charge usage, report the balance

Implement a GPU credit system. The report names this coding exercise only as "GPU credit", so agree on the interface and the rules with the interviewer before writing code. In its usual form, an account is granted GPU credits, GPU usage is charged against those credits, and the system reports how many credits the account has left. A minimal interface to start from (adjust it to the interviewer's answers): ```python class GpuCredits: def add_credit(self, account: str, amount: int, timestamp: int, expires_at: int | None = None) -> None: ... def charge(self, account: str, amount: int, timestamp: int) -> bool: ... def balance(self, account: str, timestamp: int) -> int: ... ``` ```hint Which grant pays When an account holds several grants, a charge has to draw from some of them first. Work out a small example in which that choice changes the balance the customer sees later. ``` ```hint Time is part of the input If every operation carries a timestamp, check whether your structure still answers correctly when operations arrive out of time order, or when a balance is asked for an earlier time. ``` ### Constraints and Clarifications - Not given: whether grants expire, the order in which grants are consumed, what happens when a charge exceeds the available credits, and whether operations arrive in time order. Ask, or state your assumptions. - Treat amounts and timestamps as integers. ### Clarifying Questions - Do grants expire? If several are live, which one does a charge consume first? - Is a grant usable exactly at its expiry time, or only before it? - What happens when a charge exceeds the available credits: reject it entirely, take what is available, or allow a negative balance? - Can operations arrive out of time order, for example a usage charge stamped earlier than a balance query that was already answered? - Can a balance be asked for a past time? For a future time, counting expirations that have not happened yet? - At the same timestamp, does a grant apply before a charge? ### What a Strong Answer Covers - Settles the expiry rule, consumption order, insufficient-credit policy and ordering assumptions before coding - A per-account structure that answers balances correctly with expiring grants, and the complexity of each operation - A consumption order that is justified from the customer's point of view - Correct handling of out-of-order operations and of queries for earlier times, or an explicit statement that they are excluded - Tests at the boundaries: expiry exactly at the query time, a charge equal to the balance, a charge larger than it, equal timestamps ### Follow-up Questions - Operations can arrive out of time order. A late charge stamped before an already-accepted charge makes that later charge uncoverable. What should happen? - Many accounts each hold thousands of grants and balances are queried constantly. What dominates the cost, and how would you make it cheaper? - Two GPU jobs charge the same account concurrently. How do you keep the balance correct? - Running jobs report usage continuously. How would you stop a job when its account runs out of credits?