class GPUSolution:
Implement a GPU credit tracker, GPUSolution, with three methods:
add(grant_id, amount, timestamp, expire): grant amount credits, usable from timestamp up to but not including expire.subtract(amount, timestamp): consume amount credits at timestamp, taking them from the active grant that expires soonest first. What is taken is gone for every later time.get_balance(timestamp): the credit available at timestamp, the remaining amount of every grant active then.Calls arrive in any order: an add for an earlier time can come after a subtract for a later one, so the balance at a time must reflect every event at or before it, whatever order the calls came in.
If a subtract needs more credit than is active at its time, the balance has gone negative, and get_balance returns None for that time and every later one; a grant that only starts after the shortfall does not undo it. With nothing active and no shortfall, it returns 0.
Performance is not the focus; a brute-force replay is fine. The test cases are given up front and carry rules the prompt does not spell out, so read them all before coding.
Example
gpu = GPUSolution()
gpu.add('a', 3, 10, 60)
gpu.add('b', 2, 20, 40)
gpu.subtract(1, 30) # taken from b, which expires first
gpu.subtract(3, 50)
gpu.get_balance(20) # 5
gpu.get_balance(30) # 4
gpu.get_balance(40) # 3 (b has expired)
gpu.get_balance(50) # 0
gpu = GPUSolution()
gpu.subtract(1, 30)
gpu.get_balance(30) # None: nothing covers the subtract
gpu.add('a', 1, 10, 100)
gpu.get_balance(30) # 0: now it is covered
Reported variations (ask which applies). The tests grade the reading most reports give: the window [start, expire), the active grant that expires soonest drained first, and None from get_balance after a shortfall.
InsufficientCreditException from get_balance instead of returning None.add as a duration rather than an end time, and one was told the end time is inclusive.add_credit or create_grant for add, charge or use_credit for subtract), and one report orders the arguments differently: add_credit(start, expiration, credit) and subtract(timestamp, credit).Standard explanation — no candidate report records what the interviewer accepted here.
Cache intermediate states at processed timestamps; use a sorted structure to binary search for the relevant checkpoint and replay only the delta.
Standard explanation — no candidate report records what the interviewer accepted here.
Discuss locking strategies, optimistic concurrency, or event queuing to serialize mutations.
One candidate answered with per-tier rate limits.
Standard explanation — no candidate report records what the interviewer accepted here.
Event replay: O(n log n) time per get_balance due to sort + heap operations; O(n) space for stored events.
One of the most reported OpenAI coding rounds, in about 50 candidate threads from February 2025 to September 2026, usually a 60-minute phone-screen slot next to a system design round (CI/CD, Slack, payments, Sora). The interviewer pastes the interface and all the test cases, three to six of them, and you run them live; several candidates say the tests carry rules the prompt leaves out, and interviewers often answer clarifying questions with "look at the test cases". Performance is explicitly out of scope. Candidates who passed describe finishing in about 30 minutes, one by recording events and recomputing each get_balance; the failures describe settling subtracts as they arrive, finding the soonest-expiring rule only in the last tests, or getting the shortfall rule backwards. Follow-ups, when there is time: avoid recomputing from time zero (one interviewer pushed a candidate to change their algorithm and switch timestamps to floats), complexity, concurrent calls, rejecting a grant that arrives too late, and per-tier limits in production. Prep sites label this "GPU Credits II"; two candidates say their interview returned None on a shortfall where that version does not, and one got a simpler variant as well.
Also reported as GPU Credit System · GPU Credits II · GPU Credit Audit and Usage Balance
Implement a GPU credit tracker, GPUSolution, with three methods:
add(grant_id, amount, timestamp, expire): grant amount credits, usable from timestamp up to but not including expire.subtract(amount, timestamp): consume amount credits at timestamp, taking them from the active grant that expires soonest first. What is taken is gone for every later time.get_balance(timestamp): the credit available at timestamp, the remaining amount of every grant active then.Calls arrive in any order: an add for an earlier time can come after a subtract for a later one, so the balance at a time must reflect every event at or before it, whatever order the calls came in.
If a subtract needs more credit than is active at its time, the balance has gone negative, and get_balance returns None for that time and every later one; a grant that only starts after the shortfall does not undo it. With nothing active and no shortfall, it returns 0.
Performance is not the focus; a brute-force replay is fine. The test cases are given up front and carry rules the prompt does not spell out, so read them all before coding.
Example
gpu = GPUSolution()
gpu.add('a', 3, 10, 60)
gpu.add('b', 2, 20, 40)
gpu.subtract(1, 30) # taken from b, which expires first
gpu.subtract(3, 50)
gpu.get_balance(20) # 5
gpu.get_balance(30) # 4
gpu.get_balance(40) # 3 (b has expired)
gpu.get_balance(50) # 0
gpu = GPUSolution()
gpu.subtract(1, 30)
gpu.get_balance(30) # None: nothing covers the subtract
gpu.add('a', 1, 10, 100)
gpu.get_balance(30) # 0: now it is covered
Reported variations (ask which applies). The tests grade the reading most reports give: the window [start, expire), the active grant that expires soonest drained first, and None from get_balance after a shortfall.
InsufficientCreditException from get_balance instead of returning None.add as a duration rather than an end time, and one was told the end time is inclusive.add_credit or create_grant for add, charge or use_credit for subtract), and one report orders the arguments differently: add_credit(start, expiration, credit) and subtract(timestamp, credit).How would you handle concurrency if multiple threads are calling add_credit and subtract simultaneously?
How would you improve performance / avoid recomputing from timestamp zero on every get_balance call?
In a real production system, how would you control credit usage per customer tier?
What is the time and space complexity of your solution?
If there are a very large number of credit changes, how would you optimize the system?
| Approach | Notes |
|---|---|
| Simulation with sorted event list | Create explicit (timestamp, amount, type) entries for each add, expire, and subtract event; sort all entries by timestamp; simulate sequentially adjusting expire entries downward when a subtract is processed. A reader's counterexample shows the trap: lowering future expire entries can let a grant that had not started yet pay for an earlier charge, unless each expire entry stays tied to its own grant. |
| Brute-force recompute on each get_balance | On every get_balance call, re-sort and re-process all stored events from scratch using a copy of the grant state. Simple to reason about and acceptable since interviewers explicitly say performance is not required; O(n log n) per query. |
| Two sorted lists + min-heap sweep | Keep one list for credit events, one for subtract events; at get_balance, merge-sort them by timestamp and scan with a min-heap of active grants. Clean separation of concerns; same complexity as brute-force recompute but easier to implement correctly. |
| Timeline entry list with sorted scan | Append (timestamp, amount, type) entries for each add/expire/subtract event; sort and scan at get_balance time. Simpler to implement but O(n log n) per query; correctly handles out-of-order events. Some candidates incorrectly unify expire and subtract entries, leading to double-counting bugs. |
| Eager processing with mutable grant states | Process each subtract immediately against currently known grants sorted by expiration. Fails when operations arrive out of order (a later-timestamped add could retroactively satisfy an earlier subtract). Incorrect for the out-of-order variant. |
| Two-list brute force | Keep a raw list of add events and a raw list of subtract events; at get_balance, filter to relevant time window, apply expired credits first then valid credits. O(n^2) but straightforward and one candidate's write-up says it took about 50 minutes and passed the tests; interviewers say performance does not matter. |
Common mistakes: Assuming subtract/charge operations arrive in monotonically increasing timestamp order — the test cases are deliberately out of order, and solutions built on this assumption fail late test cases.; Throwing at subtract time instead of letting get_balance report the shortfall: one candidate prepared it that way, got tangled, and left one of three tests failing.; Applying subtract by immediately deducting from existing credit entries at call time, rather than storing the event and recomputing during get_balance — this breaks when events arrive out of order.; Conflating Version I (subtract does not affect future credits) with Version II (subtract does affect future credits, draining soonest-expiring first) — candidates who prepared the wrong version wasted significant time.; Not handling the boundary condition correctly: expiry is [start, expiry) — the credit is worth zero at the expiry timestamp itself. Multiple candidates lost points on boundary edge cases.; When adjusting future 'expire' entries after a subtract, not maintaining the correspondence between each expire entry and its originating add_credit grant — leading to incorrectly reducing credits that weren't yet added at the time of the charge.; Discovering a rule in the last test cases after the data structure is built: one candidate rewrote with 20 minutes left and had no time to debug.; Conflating the expiration event with subtract — treating expire as a negative credit causes double-counting; Using earliest-add-time instead of earliest-expiration-time when prioritizing which grants to consume; Not resetting None state: failing to propagate None to all future get_balance calls once balance goes negative; Off-by-one on expiration boundary: treating expiration_ts as inclusive when it is exclusive (or vice versa); Not reading all test cases before coding — missing implicit requirements revealed only in later test cases (e.g., expiration-order deduction appearing only in the last 2 test cases); Over-engineering with complex data structures when brute-force simulation is explicitly acceptable
Interviewer hints: Interviewers explicitly said not to worry about performance / time complexity and that brute-force was fine.; When candidates asked clarifying questions, some interviewers redirected them to read the test cases instead of answering directly: "go find the answer in the test cases yourself" / "you can look at the unit tests".; The interviewer pre-pastes boilerplate code and all test cases at the start; candidates are expected to run them and pass all before time is up.; One interviewer asked the candidate to change the grant timestamp type from integer to float mid-problem and rerun tests, as a way of probing the solution's correctness.; After the tests pass, interviewers usually ask about optimization or production; one had the candidate change the algorithm and switch timestamps to floats, then rerun the tests.; Interviewer told candidate to find edge cases in the test suite rather than providing direct answers to clarification questions ('look at the test cases'); One interviewer pointed out bugs before the candidate found them.; Interviewer helped fix a library import error (heapq vs collections) and told candidate not to worry about it; Interviewer told candidate to discuss approach rather than implement when time was running short
What passers do: Read all test cases before writing any code — the test cases reveal requirements not stated in the problem description, such as the earliest-expiring-first deduction order and the None-on-negative behavior.; Treat all operations as out-of-order / unordered in timestamp, and recompute get_balance from scratch on every call by replaying all stored events up to the requested timestamp.; Use a min-heap ordered by expiration time to track active credits during get_balance computation, so that subtract/charge consumes the soonest-expiring credit first.; Reports that describe a passing method stored the add and subtract events and did the work in get_balance.; Return None from get_balance if a negative balance was ever produced at or before the queried timestamp — not at subtract time, but lazily during get_balance.; Passing candidates finished within ~27–30 minutes, leaving time to discuss follow-ups. One candidate passed all 6 tests just in time; another passed every test on the first run.; Starting with a clear event-replay simulation approach: store raw events, compute everything lazily at get_balance time
Why people fail: Implementing based on a previously-studied version of the problem and not adapting to the specific variant in front of them; Passing most test cases but failing one edge case with no time left to debug; Spending 20+ minutes debugging without identifying the root cause, running out of time; Not accounting for out-of-order timestamps — code worked for ordered inputs but failed on unordered test cases; Finishing very fast: one Java candidate who passed every test says the interviewer suspected LLM use and failed them.; Not communicating the approach clearly before coding, leaving interviewer unable to follow logic; Mishandling the shortfall: get_balance returns None from the shortfall on, unless an earlier-starting grant covers it
Edge cases probed: subtract called before any add_credit exists — balance goes negative, get_balance should return None; get_balance at exactly the expiration timestamp — typically exclusive, credit is NOT valid at expiration_ts; Multiple grants with overlapping validity windows; subtract must consume from earliest-expiring first; Out-of-order operation timestamps: add_credit with an earlier timestamp called after subtract with a later timestamp; After a shortfall, later get_balance queries return None, unless a grant added afterwards starts early enough to cover it (one Java sample shows exactly that); get_balance at a timestamp where no credits are active — return 0, not None; Partial consumption across multiple grants (subtract amount spans two or more grants); subtract amount exactly equals total available credit (balance becomes 0, not negative)
Send them this page. It is free to read, no account needed.
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 91 OpenAI questions, refreshed monthly from new candidate reports.