AO
AceOffer
·
Back

GPU Credit Management System

CodingPhone, OnsiteSoftware Engineer, Machine Learning EngineerLast reported April 2026High Frequency

Problem Overview

Implement a GPU credit management system class with three methods: (1) add_credit(credit_id, amount, start_ts, expiration_ts) — register a grant of 'amount' credits identified by 'credit_id', valid during the half-open interval [start_ts, expiration_ts); (2) subtract(amount, timestamp) — schedule a deduction of 'amount' credits at the given timestamp, consuming from the earliest-expiring valid grants first; (3) get_balance(timestamp) — compute and return the remaining balance at the given timestamp, or return None (some versions throw InsufficientCreditException) if the effective balance would be negative.
What you must implement
  1. add_credit(credit_id, amount, start_ts, expiration_ts) — register a grant of 'amount' credits identified by 'credit_id', valid during the half-open interval [start_ts, expiration_ts)
  2. subtract(amount, timestamp) — schedule a deduction of 'amount' credits at the given timestamp, consuming from the earliest-expiring valid grants first
  3. get_balance(timestamp) — compute and return the remaining balance at the given timestamp, or return None (some versions throw InsufficientCreditException) if the effective balance would be negative.
Full problem statement
Implement a GPU credit management system class with three methods: (1) add_credit(credit_id, amount, start_ts, expiration_ts) — register a grant of 'amount' credits identified by 'credit_id', valid during the half-open interval [start_ts, expiration_ts); (2) subtract(amount, timestamp) — schedule a deduction of 'amount' credits at the given timestamp, consuming from the earliest-expiring valid grants first; (3) get_balance(timestamp) — compute and return the remaining balance at the given timestamp, or return None (some versions throw InsufficientCreditException) if the effective balance would be negative. Key constraints: add_credit and subtract calls may arrive with out-of-order timestamps, so all computation must be deferred to get_balance time; only credits whose [start_ts, expiration_ts) window covers the query timestamp are valid; subtract permanently consumes from the earliest-expiring grants (Version II), affecting future balance queries; once get_balance returns None, all subsequent queries also return None regardless of later credit additions. Sample test cases: [subtract(4,30), get_balance(10)→None, add('a',4,20,30), get_balance(10)→0, get_balance(20)→4, get_balance(30)→0] and [add('a',4,20,60), add('b',3,30,40), subtract(2,30), get_balance(30)→5, get_balance(40)→4]. The interviewer provides ~6 test cases; reading them before coding reveals implicit requirements (e.g., expiration boundary semantics, None vs. 0 vs. positive return) not stated in the written description. Two documented variants exist — Version I (subtract is a snapshot deduction not affecting future credits, solvable with sweep-line) and Version II (subtract permanently reduces earliest-expiring grants, requiring event-replay simulation; more commonly seen in interviews).

Follow-up Arc

Interviewers escalate through these phases. The order varies, but most candidates see at least one from each bucket.
Concurrency · 1Distributed scale · 1Trade-off discussion · 2
Concurrency
How would you handle concurrent add_credit and subtract operations?
Probes for: Candidate completes the implementation cleanly
Distributed scale
What if the credit dataset is very large (millions of grants)?
Probes for: Candidate mentions or is asked about scale
Trade-off discussion
How would you optimize the performance of your solution?
Probes for: Candidate finishes passing all test cases with a brute-force replay
What if the timestamp type needs to change from integer to float?
Probes for: Candidate has all test cases passing

Approach Trade-offs

Approaches actually attempted in reports — including ones that lost candidates time. Pick deliberately.
ApproachNotes
Sweep-line (Version I only)For the simpler variant where subtract does not reduce future credits: build a timeline of +amount events at start_ts and -amount events at expiration_ts for each grant, plus subtract events at their timestamps; scan up to the query timestamp to compute balance in O(n log n). Does not correctly model Version II where subtract permanently depletes specific grants.
Two-entry event log with future-expire adjustmentFor each add_credit, append both an 'add' entry at start_ts and an 'expire' entry at expiration_ts. For each subtract, append a 'cost' entry. At get_balance, sort all entries and replay; when processing a cost entry, walk future 'expire' entries in expiration order and reduce their amounts to reflect permanent depletion. Correct for Version II and handles out-of-order inputs. Described by a passing candidate as the cleanest simulation approach.
Two-list brute force (expired-first, then valid)At get_balance(ts), partition credits into expired_list (expiration < ts) and valid_list (covering ts), and collect usage_list (subtract events ≤ ts). Apply usage against expired credits first (they expire soonest), then against valid credits. Build balance from remaining valid credits. Simple to reason about; O(n²) per query; passing candidates report ~50 lines of code.

Practice

Open the editor to write a solution against test cases, then return here to compare against the follow-ups.
Open Editor →
OpenAI · Coding · Reported 40× across candidate reports