How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

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.

Input: ([["CHARGE","u1",1,-1],["GET","u1",-1],["GRANT","u1",2,-2],["GET","u1",-1]],)

Expected Output: [0, 1]

Explanation: At first GET, only a charge exists and it fails => 0. After a later-arriving earlier grant@-2, recomputing at t=-1 gives 2 then charge1 succeeds => 1.

Input: ([["CHARGE","a",3,5],["GRANT","a",10,5],["GET","a",5],["GRANT","a",1,4],["GET","a",5]],)

Expected Output: [10, 11]

Explanation: At t=5, same-timestamp events are processed in arrival order: charge then grant, so charge fails and balance becomes 10. After adding grant1@4, at t=5: grant1 -> charge3 fails -> grant10 => 11.

Input: ([],)

Expected Output: []

Explanation: No GET requests, so the output is an empty list.

Solution

from collections import defaultdict


def solution(requests):
    """Simulate an out-of-order timestamp credit ledger.

    requests: List of requests. Each request is:
      - ["GRANT", user, amount, timestamp]
      - ["CHARGE", user, amount, timestamp]
      - ["GET", user, timestamp]

    Returns: list of balances for each GET, in order.
    """

    # user -> list of events (timestamp, arrival_index, type, amount)
    events = defaultdict(list)
    out = []

    for idx, req in enumerate(requests):
        op = req[0]

        if op == "GET":
            user, t = req[1], req[2]
            user_events = events.get(user)
            if not user_events:
                out.append(0)
                continue

            applicable = [e for e in user_events if e[0] <= t]
            applicable.sort(key=lambda x: (x[0], x[1]))  # (timestamp, arrival order)

            bal = 0
            for ts, arrival, typ, amt in applicable:
                if typ == "GRANT":
                    bal += amt
                else:  # CHARGE
                    if bal >= amt:
                        bal -= amt
            out.append(bal)

        elif op == "GRANT" or op == "CHARGE":
            user, amount, t = req[1], req[2], req[3]
            # Store with arrival index for stable tie-breaking.
            events[user].append((t, idx, op, amount))
        else:
            raise ValueError(f"Unknown operation: {op}")

    return out

Time complexity: Worst-case O(G * K log K), where G is the number of GET requests and K is the number of events for the queried user (due to sorting on each GET).. Space complexity: O(E) where E is the number of GRANT/CHARGE events stored..

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.

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.