GPU Credit Ledgers And Schedulers
Asked of: Software Engineer
Last updated
What's being tested
This tests concurrent resource accounting: maintaining a correct GPU-credit ledger under reservations, usage commits, refunds, expirations, and duplicate requests. The core skill is combining hash maps, heaps, ordered maps, and atomic state transitions to support balance checks, top-K queries, and fair scheduling with clear complexity guarantees.
Patterns & templates
-
Ledger-as-events, balance-as-index — append immutable events, maintain per-user cached balance;
O(1)updates, rebuildable from log after crash. -
Idempotency-key table — store
request_id -> resultforreserve,commit,refund; return prior result on retry, not double-apply credits. -
Expiration min-heap — keep
(expires_at, grant_id, user_id, amount); lazily pop expired grants before reads/writes,O(log n)per grant. -
Per-user grant buckets — consume credits FIFO by expiration using
dequeor min-heap; prevents spending long-lived credits before soon-expiring credits. -
Atomic check-and-decrement — implement
try_reserve(user, cost)under a mutex, CAS loop, or transaction; never split balance check from mutation. -
Scheduler priority queue — rank runnable jobs by
priority,submit_time,credit_balance, or fairness score; use stable tie-breakers to avoid nondeterminism. -
Top-K users/jobs — maintain heap or balanced tree keyed by balance/usage; heap is cheaper for approximate/top query, tree supports deletes/updates cleanly.
Common pitfalls
Pitfall: Treating balance as a single integer fails when credits have different expirations, grant sources, or refund semantics.
Pitfall: Retrying
reserve()without an idempotency key can double-charge users during client timeouts or scheduler failover.
Pitfall: Using a heap for mutable priorities without lazy invalidation creates stale entries; store version numbers and discard obsolete heap nodes.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Practice questions
- Implement credit ledger with out-of-order timestampsOpenAI · Software Engineer · Technical Screen · hard
- Implement GPU credit ledgerOpenAI · Software Engineer · Technical Screen · Medium
- Implement expiring credit ledgerOpenAI · Software Engineer · Technical Screen · Medium
- Implement an expiring GPU-credit managerOpenAI · Software Engineer · Technical Screen · Medium
- Design credit balance with vector-clock expirationsOpenAI · Software Engineer · Technical Screen · hard
- Design a GPU credit system and schedulerOpenAI · Software Engineer · Technical Screen · hard
- Implement a GPU credit managerOpenAI · Software Engineer · Technical Screen · Medium
- Manage GPU Credits with ExpirationOpenAI · Software Engineer · Technical Screen · Medium
- Design GPU credit allocatorOpenAI · Software Engineer · Technical Screen · hard
- Design a GPU credit allocation serviceOpenAI · Software Engineer · Technical Screen · hard
- Implement an expiring GPU credits ledgerOpenAI · Software Engineer · Technical Screen · Medium
Related concepts
- GPU Credit Ledgers And Resource AccountingSystem Design
- ML Inference APIs And GPU BatchingML System Design
- GPU Programming, Graphics APIs, And Shader CompilersSystem Design
- Distributed System Design For Ledgers And CountersSystem Design
- Greedy, Heaps, And Scheduling OptimizationCoding & Algorithms
- Distributed Job Scheduler SystemsSystem Design