Design a credit tracking service for user token balances

Late June, 2026

6 test cases

Late June, 2026

Mid May, 2026

GPU credit tracking system. API consists of 3 operations: - createCredit(id, amount, timestamp, expiresAt) - subtract(amount, timestamp) - getBalance(timestamp) The caveat here is that operations may be executed at random timestamps, so it's not strictly increasing. And that makes the balance calculation much harder. The solution idea: 1. Don't try to calculate the balance on the fly - it's impossible to do correctly as timestamps are not given sequentially. Rather, store all the mutations (create/subtract) as events in a data structure. As timestamps can be random, a min heap sorted by their timestamps really helps to enforce the events' order later. 2. When adding a CREATE event into the heap, also add an EXPIRE event at the right timestamp, too. This will help you to process it correctly when calculating the balance, instead of trying to manage a CREATE event only along with its expiration. Add a type property to your events' structure to easily distinguish them. 3. Balance calculation will be the most complex operation in this task. You need to process your entire min heap of events that have been stored so far. And you need to do that every time getBalance() is called to ensure correctness, as again, the mutations may happen at random timestamps. 4. Make a deep copy of your heap within getBalance(), as you'll be processing all the events and popping them out of the heap. So, you need a copy to preserve the original history of events. Yes, it'll require O(n) memory. But you need to sacrifice something here to ensure the correctness of your system. 5. Also, create a HashMap within getBalance() where you'll add all the ids of CREATE events that you popped out of the heap, along with their amounts. So, id -> amount. Why? Because if multiple CREATE events follow, and then there's a SUBTRACT, you potentially need to spend credits from multiple CREATE events, not just from the last one. So, you need to track those that you've already consumed from the heap. Example: CREATE 10 CREATE 5 CREATE 7 SUBTRACT 20 In this case, the SUBTRACT operation is valid because you had multiple CREATE ones before, and the balance is sufficient. So, you need to track the ones you've already seen, not just consider the last one. You can say: "Why would I have a HashMap, if I just track the total balance that all the CREATE operations add up to? I could just execute that SUBTRACT against that total value!" That would have worked if you hadn't had the EXPIRE events too. If you just aggregate the total balance, and then you have an EXPIRE event, you need to know exactly which one you should remove from the total balance now. And for that, you need that HashMap AND the total balance. 6. When you get an EXPIRE event, remove it from the HashMap and from the total balance - the amount that was in the HashMap for that ID. 7. When you get a SUBTRACT event, you need to take available grants from your HashMap and try to subtract from them first, as they can be less than the total amount you need to subtract. So, potentially, you'll be subtracting from multiple active grants in your HashMap. But there's a caveat, too: if you go over your HashMap and do subtractions, those events will be unordered. That may work, but ideally, you want to subtract from those grants that have the closest expiration time, so the system doesn't waste any credits. For that, except the HashMap, you might also create a min heap sorted by the expiration time of those CREATE events. Then, when subtracting, you get an event from that heap, get its current amount from the HashMap, subtract, and update your state. Poll it from the heap and remove it from the HashMap if the amount gets to 0. 8. When you implemented the backbone of your logic, mention the validation for all the methods and edge cases (negative balance, negative amounts, etc.). Also, if you can proactively tell about potentially caching balance, with invalidating it, when any mutation happens - that's great. If the system is read-heavy, the cache would really make a difference here. But you don't need to implement it. Just say about it at the end. That this is something you'd consider in a real system. # P.S. This solution is a bit complex, but it's a correct one that passes the interview and deals with multiple edge cases. I literally passed the on-site with this one. A piece of advice: try to write the code for it in your spare time and review it with ChatGPT or Claude prompting it to take a role of OpenAI interviewer. This way, you'll catch all the bugs you might have before the actual interview and make sure that you understand why certain choices are made. This HashMap + heap by expiresAt wasn't clear for me at first. Only practice made the difference.