Quick 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.

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.

Quick Answer: 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.

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

  1. 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).
  2. 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.

Loading coding console...