Implement credit ledger with out-of-order timestamps
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
## Problem
You are implementing a **GPU credit ledger** that supports adding credits, charging credits, and querying balances. Requests can arrive in **any timestamp order** (timestamps are not monotonic).
Design a data structure/class that supports these operations:
- `addCredit(timestamp, amount)`
- Records that `amount` credits were added at time `timestamp`.
- `chargeCredit(timestamp, amount)`
- Records that `amount` credits were requested to be charged at time `timestamp`.
- `getBalance(timestamp) -> integer`
- Returns the **effective balance at time `timestamp`**, computed using **all recorded requests whose timestamps are `<= timestamp`**.
### Rules for computing the effective balance
When computing the balance at time `T`, consider all recorded `addCredit` and `chargeCredit` events with timestamp `<= T` and process them in increasing timestamp order.
- Start from balance `0`.
- For an `addCredit`, increase the balance.
- For a `chargeCredit`:
- If current balance is **>= amount**, deduct it (the charge succeeds).
- Otherwise, **do not deduct** it (the charge is declined/ignored).
### Tie-breaking (same timestamp)
If multiple events share the same timestamp, process them in this order:
1. All `addCredit` events at that timestamp (in insertion order)
2. All `chargeCredit` events at that timestamp (in insertion order)
### Notes
- Requests arrive out of order; you are allowed to **cache/store** all requests.
- There is **no strict time complexity requirement**; correctness is the priority.
## Deliverable
Provide the API and implement the logic so that repeated calls to `getBalance(T)` always return the correct value according to the rules above.
Overview: This question evaluates the ability to implement stateful event processing with out-of-order timestamps, correct ledger/accounting semantics including timestamp ordering and explicit tie-breaking between adds and charges.
Read the full OpenAI Software Engineer interview experience this question came from
You are implementing a simple GPU credit ledger. The system receives a stream of requests in the order they arrive, but each request also contains a timestamp, and timestamps are NOT guaranteed to be increasing.
Supported request types:
1) ["GRANT", user, amount, timestamp]
- Adds `amount` credits to `user` at `timestamp`.
2) ["CHARGE", user, amount, timestamp]
- Attempts to subtract `amount` credits from `user` at `timestamp`.
- A charge is applied only if the user's balance at that moment (after processing all earlier/equal timestamps) is >= amount.
- If insufficient credits, the charge is ignored (no change).
3) ["GET", user, timestamp]
- Returns the user's balance at `timestamp`, considering ONLY the GRANT/CHARGE requests that have arrived so far.
Important details:
- Requests arrive over time; a later-arriving request with an earlier timestamp can affect future GET results, but it must not retroactively change past GET outputs.
- When multiple events for the same user have the same timestamp, process them in the order they arrived in the input stream (stable tie-breaker).
Return a list of balances for every GET request, in the order the GET requests appear.
Constraints
- 1 <= len(requests) <= 20000
- user is a non-empty string
- 0 <= amount <= 10^9
- -10^9 <= timestamp <= 10^9
- Timestamps are not guaranteed to be ordered
- If multiple events share the same timestamp for a user, they must be applied in arrival order
Examples
Input: ([["GRANT","alice",10,5],["CHARGE","alice",4,7],["GET","alice",7],["CHARGE","alice",10,6],["GET","alice",7]],)
Expected Output: [6, 0]
Explanation: First GET sees grant@5 then charge4@7 => 6. Second GET also sees a new charge10@6, so at t=7: grant10 -> charge10 succeeds -> balance 0; charge4 then fails => 0.
Input: ([["GRANT","alice",5,10],["GRANT","bob",7,1],["CHARGE","bob",2,3],["GET","bob",2],["GET","bob",3],["GET","alice",9],["GET","alice",10]],)
Expected Output: [7, 5, 0, 5]
Explanation: bob@2 includes only grant7@1 => 7. bob@3 includes charge2@3 => 5. alice@9 excludes grant@10 => 0. alice@10 includes grant5 => 5.
Hints
- Cache all GRANT/CHARGE events seen so far per user; when you get a GET, recompute that user's balance by sorting applicable events by (timestamp, arrival_index).
- To handle equal timestamps correctly, store each event with its position in the input stream and use it as a stable tie-breaker when sorting.
Community answers
Answer by EL
To meet the requirements of your provided test cases—specifically the detailed_example() which inspects internal state like operations, timestamps, and balance_cache—we need to implement a ledger that not only simulates the balance but also manages an optimization layer.
This implementation uses a simulation-with-memoization approach. When a new event is added at time $T$, we invalidate the cache for all times $\ge T$, because a past event can change the validity of every subsequent charge.
The Implementation
from collections import defaultdict
import bisect
class GPUCreditLedger:
def init(self):
# operations[ts] = {"adds": [amount1, ...], "charges": [amount1, ...]}
# Using a dictionary to store adds and charges per timestamp
self.operations = defaultdict(lambda: {"adds": [], "charges": []})
# Unique sorted list of timestamps where events occur
self.timestamps = []
# balance_cache[ts] = balance after all events at that timestamp are processed
self.balance_cache = {}
def _invalidate_cache(self, timestamp: int):
"""Removes cache entries that are affected by an event at 'timestamp'."""
invalid_keys = [ts for ts in self.balance_cache if ts >= timestamp]
for ts in invalid_keys:
del self.balance_cache[ts]
def addCredit(self, timestamp: int, amount: int):
"""Records an add event and invalidates subsequent cache."""
if timestamp not in self.operations:
bisect.insort(self.timestamps, timestamp)
self.operations[timestamp]["adds"].append(amount)
self._invalidate_cache(timestamp)
def cha