GPU credit ledger with out-of-order events

The events (grants and charges) can arrive in any timestamp order, so the order we receive them in means nothing. Keep an append-only log and answer every question as if the log had been processed in timestamp order. Two rules decide the outcome:

• A grant is usable on the half-open window [start, end). It is usable at start and not usable at end.
• A charge spends the usable grant that expires soonest first, and moves on to the next one when that grant runs out. A charge is all-or-nothing.

Brute force. Walk time step by step from the earliest timestamp, applying grants, expirations and charges at each tick. That works, but it costs time proportional to the span of timestamps, not the number of events. Interviewers expect you to see that only event timestamps matter.

Replay with a min-heap (what we write). Sort grants by start and charges by (timestamp, arrival order). Sweep the charges in order. Before each charge at time t, push every grant with start <= t onto a heap keyed by end, then pop grants that have expired (end <= t) or are used up. Take from the heap top until the charge is covered. If the heap empties first, the log can't be honored.

• get_balance(t) replays only the charges with timestamp <= t, then sums what is left in the grants usable at t. A charge recorded for time 50 doesn't lower the balance at time 30, even if it arrived first.
• subtract(amount, t) adds the charge to the log and replays the whole log. A late charge stamped in the past can use up credit that a later, already-accepted charge needed. If any charge in the log can no longer be covered, the new charge is rejected, removed from the log, and we return False. Nothing that was accepted is ever undone.
• add_credit never needs a check. Extra supply can't make a coverable log uncoverable. It can change which grant pays for an old charge: a short-lived grant that arrives late pays for an earlier charge, which leaves the long-lived grant for later. Because we replay, that happens on its own.

Why soonest-expiring first is right: when two grants are both usable now, the one that expires later is usable at every future moment the other one is, and possibly more. Spending the soon-to-expire one first never leaves you worse off. This is the same exchange argument as earliest-deadline-first scheduling. So "can every charge be covered?" has a yes answer exactly when the greedy replay finds one.

Invariants:

• Replaying the full log always covers every charge. subtract keeps this true, and add_credit can't break it.
• The log is never edited after it is written. Answers are a pure function of the log, so the arrival order of events can't change them.
• Ties: at the same timestamp, expirations happen before charges (end <= t is popped first), grants that start at t are usable, and charges run in arrival order.

import heapq
from dataclasses import dataclass
from typing import Optional


@dataclass
class Grant:
    grant_id: str
    amount: int
    start: int  # usable at start
    end: int    # not usable at end: window is [start, end)


class CreditSystem:
    """GPU credit ledger that accepts events in any timestamp order.

    The log is the source of truth. Every answer comes from replaying it in
    timestamp order, spending the grant that expires soonest first.
    Invariant: replaying the whole log never finds a charge it can't cover.
    """

    def __init__(self) -> None:
        self._grants: dict[str, Grant] = {}
        self._charges: list[tuple[int, int, int]] = []  # (timestamp, seq, amount)
        self._seq = 0

    def add_credit(self, grant_id: str, amount: int, start: int, end: int) -> None:
        if grant_id in self._grants:
            raise ValueError(f"duplicate grant {grant_id}")
        if amount <= 0 or end <= start:
            raise ValueError("amount must be positive and start < end")
        # Extra supply can't make a feasible log infeasible, so no check needed.
        self._grants[grant_id] = Grant(grant_id, amount, start, end)

    def subtract(self, amount: int, timestamp: int) -> bool:
        if amount <= 0:
            raise ValueError("amount must be positive")
        charge = (timestamp, self._seq, amount)
        self._seq += 1
        self._charges.append(charge)
        if self._replay(until=None) is None:  # breaks this or a later charge
            self._charges.pop()
            return False
        return True

    def get_balance(self, timestamp: int) -> int:
        remaining = self._replay(until=timestamp)
        assert remaining is not None  # guaranteed by the invariant
        return remaining

    def _replay(self, until: Optional[int]) -> Optional[int]:
        """Replay charges with time <= until (all when None).

        Returns the usable balance at `until` (0 when until is None),
        or None if some charge can't be covered.
        """
        grants = sorted(self._grants.values(), key=lambda g: g.start)
        charges = sorted(self._charges)
        left = {g.grant_id: g.amount for g in grants}
        heap: list[tuple[int, str]] = []  # (end, grant_id) of started grants
        gi = 0

        def advance(t: int) -> None:
            nonlocal gi
            while gi < len(grants) and grants[gi].start <= t:
                heapq.heappush(heap, (grants[gi].end, grants[gi].grant_id))
                gi += 1
            while heap and (heap[0][0] <= t or left[heap[0][1]] == 0):
                heapq.heappop(heap)  # expired or used up

        for t, _, need in charges:
            if until is not None and t > until:
                break
            advance(t)
            while need and heap:
                end, gid = heap[0]
                take = min(need, left[gid])
                left[gid] -= take
                need -= take
                if left[gid] == 0:
                    heapq.heappop(heap)
            if need:
                return None
        if until is None:
            return 0
        advance(until)
        return sum(left[gid] for _, gid in heap)

Let G be the number of grants and S the number of charges.

• add_credit: O(1).
• subtract: O((G + S) log(G + S)) to sort and replay the full log.
• get_balance: O((G + S) log(G + S)), the same replay stopped at t.
• Space: O(G + S) for the log, plus O(G) scratch space per replay.

Every call replays from scratch. That's the right first version in an interview: it's obviously correct whatever the arrival order. The follow-ups cover how to avoid the replay.

• Grant a = 10 on [0, 100), grant b = 5 on [10, 40). get_balance(5) → 10. get_balance(20) → 15.
• Then subtract(7, 30) → True. It takes all 5 from b (expires first) and 2 from a. get_balance(30) → 8, get_balance(25) → 15 (the charge hasn't happened yet), get_balance(50) → 8, get_balance(100) → 0.
• Late charge in the past: grant 10 on [0, 100), subtract(8, 50) → True, then subtract(5, 20) → False, because it would leave only 5 for the charge at 50. get_balance(60) → 2. subtract(2, 20) → True, after which get_balance(60) → 0.
• Charge before any grant: subtract(3, 10) on an empty ledger → False. After grant x = 5 on [0, 20) arrives, subtract(3, 10) → True.
• A grant that hasn't started can't pay: with x as above (2 left at t=12) and y = 4 on [15, 30), subtract(4, 12) → False. get_balance(15) → 6. get_balance(20) → 4 (x expired).
• A late grant changes who pays: long = 5 on [0, 100), subtract(5, 10) → True. Then short = 5 on [0, 20) arrives. Replay now charges short at t=10, so subtract(5, 50) → True and get_balance(50) → 0. A ledger that locked in its choices when events arrived would wrongly reject this.
• Boundaries: grant 3 on [5, 10). Balance at 4 → 0, at 5 → 3, at 9 → 3, at 10 → 0. subtract(1, 10) → False.
• Bad input: a duplicate grant id, amount <= 0, or end <= start raises ValueError.

1. Make it faster when most events arrive in order. Keep a checkpoint: the heap and remaining amounts after replaying up to the latest timestamp seen. An event at or after the checkpoint is applied incrementally in O(log G). Only an event older than the checkpoint forces a replay, and only from the newest snapshot before its timestamp. Keep snapshots every k events to bound that replay.
2. Multiple users or accounts. Shard the log by user_id (dict[str, CreditSystem]). Replays are per user, so one busy user doesn't slow the rest. Ask whether grants can be shared across a team, because that changes the key.
3. Report the breakdown. Return, for a charge or a time, how much came from each grant. Record (grant_id, taken) pairs during the replay. Ask the interviewer whether the breakdown of an old charge is allowed to change when a late grant arrives (it does under replay semantics). If billing has already been reported, you need a cutoff after which history is frozen.
4. Many balance queries. Charges never undo grants, so the balance over time is a step function. After a replay, store (timestamp, balance) at every event and answer get_balance(t) with a binary search in O(log n) until the next write invalidates it.
5. Refunds or cancellations. cancel_grant(id) can make accepted charges uncoverable, unlike add_credit. Decide whether it's refused, or allowed and the uncovered charges are reported as debt. Either way, replay and check the invariant before you commit.

Mid-level (L4)

• Asks how the window boundaries work and what a failed charge does. Uses [start, end) and all-or-nothing consistently.
• Writes a correct replay with soonest-expiring first, including grants that haven't started and grants that have expired.
• Makes get_balance(t) ignore charges stamped after t.

Senior (L5)

• Spots that a late charge in the past can break a charge that was already accepted, and rejects it without editing history.
• Explains why soonest-expiring first is optimal and why add_credit needs no check.
• Covers ties at a single timestamp and tests them, then states the replay cost and proposes the checkpoint optimization.

Staff (L6+)

• Frames the ledger as an event log with derived state. Talks about idempotent event ids, how late events are allowed to be, and when history freezes for billing.
• Discusses per-user sharding, snapshots, and what changes when the log is durable and events come from several producers.
• Weighs how the product should behave. Rejecting a late charge, recording it as debt, and reordering history each have a different cost.