Implement a GPU credit management system with the following methods:
add_credit / createGrant(grant_id, amount, start_ts, expiration_ts): Add a credit grant of amount units, valid during the window [start_ts, expiration_ts). At expiration time the credit is no longer usable.
subtract / charge / use_credit(amount, timestamp): Consume amount credits at the given timestamp. When multiple credit grants are active, credits must be consumed from the grant that expires soonest first (earliest-expiring priority). Consumption affects the future remaining balance of those grants.
get_balance(timestamp): Return the total available credit balance at the given timestamp, accounting for all grants that are active at that time minus any prior consumption. Returns None (or throws InsufficientCreditException) if the accumulated usage has caused balance to go negative. Returns 0 if no credits are active at that time but balance is non-negative.
Key constraints and behaviors:
Variant I (simpler): subtract simply reduces a global balance counter without tracking which specific grants were depleted; does not affect future grants individually. Solvable with a sweep-line approach.
Variant II (harder, most commonly tested): subtract deducts from currently active grants starting with earliest-expiring, permanently reducing those grant amounts and affecting future balance calculations.
Sample test cases (Variant II):
gpu.subtract(4, 30)
gpu.get_balance(10) => None # subtract happened before any credit, negative balance
gpu.add('a', 4, 20, 30)
gpu.get_balance(10) => 0 # credit starts at ts=20, not valid at ts=10
gpu.get_balance(20) => 4
gpu.get_balance(30) => 0 # expired at ts=30
gpu.add('a', 4, 20, 60)
gpu.add('b', 3, 30, 40)
gpu.subtract(2, 30)
gpu.get_balance(30) => 5 # 4+3-2=5
gpu.get_balance(40) => 4 # grant 'b' expired, 2 was consumed from 'b' first (earliest expire), so 'a' still has 4
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 if a charge event arrives before the add_credit that covers it — how do you reconcile retroactively?
What is the time and space complexity of your solution?
| 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. Correct but O(n²) in worst case for adjusting expire events; code can be subtle. |
| 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 explicitly endorsed by multiple candidates and interviewers when no complexity requirement is given. |
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 an exception or marking failure at subtract time instead of deferring the negative-balance check to get_balance — this caused candidates to fail test cases where a charge precedes the grant that covers it.; 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.; Spending too much time debugging rather than doing a clean rewrite when the initial data structure was wrong, running out of time before fixing the last test case.; Assuming subtract/add calls always arrive in timestamp order and processing eagerly — fails when out-of-order timestamps appear in test cases; 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 all test cases pass, the interviewer briefly asks about optimization / real-world considerations — this is discussion only, not additional coding.; Interviewer told candidate to find edge cases in the test suite rather than providing direct answers to clarification questions ('look at the test cases'); Interviewer pointed out bugs before the candidate found them (suggesting candidate should have tested more proactively); 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; Interviewer clarified that expiration timestamp is inclusive when candidate asked about boundary
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.; Candidates who passed all 6 test cases did so by storing raw events (add and subtract) without processing them immediately, then doing a full simulation 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 test cases in one submission.; Starting with a clear event-replay simulation approach: store raw events, compute everything lazily at get_balance time; Explicitly clarifying boundary conditions (inclusive/exclusive expiration, None vs exception semantics) before coding; Treating the problem as a pure simulation and avoiding premature optimization
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; Writing too fast (using a memorized solution) and being accused of using LLM by the interviewer; Not communicating the approach clearly before coding, leaving interviewer unable to follow logic; Failing to handle the None propagation edge case (once negative, always None)
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; Once balance is negative at any timestamp, all subsequent get_balance queries return None even after more credits are added; 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); Grant added at ts=X with expiration=X (zero-duration grant — effectively never valid); subtract amount exactly equals total available credit (balance becomes 0, not negative)
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 100 OpenAI questions, refreshed monthly from new candidate reports.