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 Medium 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 expiring credit ledger | OpenAI Coding Question

Quick Overview

This question evaluates the ability to design efficient time-based data structures and algorithms for managing expiring credits with ordering and tie-breaking rules, testing competencies in event ordering, interval management, and retroactive update handling; it is in the Coding & Algorithms domain and emphasizes practical application of algorithmic and data-structure reasoning. It is commonly asked to verify correctness under out-of-order inserts and queries, to assess performance and complexity analysis for add/charge/get operations, and to require clear specification of time and space complexity for the proposed approach.

Implement expiring credit ledger

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Implement an expiring-credit ledger that supports out-of-order events. Expose three functions with the following semantics: - add_credit(id, amount, time_stamp, expiration): Add a credit bucket identified by id with amount units that becomes active at time_stamp and expires at time_stamp + expiration (half-open interval [start, end)). - charge(amount, time_stamp): At the given time_stamp, deduct amount from all credits that are active at that time, always consuming from the credit with the earliest expiration first; if multiple credits share the same expiration, break ties by earlier activation time, then by lexicographical id. Return the amount actually charged (do not deduct from inactive or expired credits). - get_balance(time_stamp): Return the total remaining amount across all credits active at time_stamp. Events for add_credit and charge may arrive in arbitrary order of time_stamp, so the data structure must support retroactive inserts and queries correctly. Design for efficiency and specify time/space complexities of your approach. Example: add_credit("c1", 20, 10, 30) // active [10, 40) add_credit("c2", 20, 40, 30) // active [40, 70) add_credit("c3", 20, 20, 30) // active [20, 50) add_credit("c4", 20, 30, 30) // active [30, 60) charge(45, 30) // consume c1->0, c3->0, c4->15 get_balance ( 10) => 20 // c1 get_balance ( 30) => 15 // c4=15 get_balance ( 55) => 35 // c4=15, c2=20

Quick Answer: This question evaluates the ability to design efficient time-based data structures and algorithms for managing expiring credits with ordering and tie-breaking rules, testing competencies in event ordering, interval management, and retroactive update handling; it is in the Coding & Algorithms domain and emphasizes practical application of algorithmic and data-structure reasoning. It is commonly asked to verify correctness under out-of-order inserts and queries, to assess performance and complexity analysis for add/charge/get operations, and to require clear specification of time and space complexity for the proposed approach.

You are given a list of ledger operations, but the operations are not sorted by their time_stamp. Evaluate the ledger on the actual timeline and return the result of every charge and balance query. Each operation is one of: - ("add", id, amount, time_stamp, expiration) Add a credit bucket with `amount` units. It is active on the half-open interval [time_stamp, time_stamp + expiration). - ("charge", amount, time_stamp) At `time_stamp`, deduct up to `amount` from the credits that are active at that time. Always consume from the bucket with the earliest expiration first. If multiple active buckets have the same expiration, consume from the one with the earlier activation time first; if those are also equal, use lexicographically smaller `id` first. Return the amount actually charged. - ("balance", time_stamp) Return the total remaining amount across all credits active at `time_stamp`. Important ordering rule: operations must be evaluated by increasing `time_stamp`, not by their position in the input. If multiple operations share the same `time_stamp`, process all `add` operations first, then all `charge` operations, then all `balance` operations. Within the same type and same timestamp, preserve the original input order. Return a list containing the outputs of every `charge` and `balance` operation, in the same order those output-producing operations appear in the original input.

Constraints

1 <= len(operations) <= 2 * 10^5
0 <= amount, time_stamp, expiration <= 10^9
All `id` values in `add` operations are distinct strings
A credit is active on [start, end), so it is active at `start` but not active at `end`
Use 64-bit integer arithmetic in static languages

Examples

Input: [('charge', 45, 6), ('add', 'A', 50, 5, 10), ('balance', 8), ('charge', 15, 7), ('balance', 6), ('add', 'B', 30, 3, 4)]

Expected Output: [45, 20, 15, 35]

Explanation: Evaluate by time: add B at 3, add A at 5, charge 45 at 6 consumes B=30 then A=15, so the balance at time 6 is 35. At time 7, B is expired and charge 15 consumes from A, leaving 20 for the balance at time 8. Outputs are returned in original input order.

Input: [('balance', 1), ('charge', 5, 4), ('charge', 4, 2), ('balance', 3), ('add', 'C', 4, 2, 1)]

Expected Output: [0, 0, 4, 0]

Explanation: At time 1 there is no credit, so balance is 0. At time 2, the add happens before the charge, so the charge gets 4. The bucket is active on [2, 3), so by time 3 it is no longer active, and the later charge at time 4 also returns 0.

Input: [('balance', 5), ('charge', 3, 5), ('add', 'Z', 10, 5, 0)]

Expected Output: [0, 0]

Explanation: A bucket with expiration 0 is active on the empty interval [5, 5), so it is never usable. At timestamp 5, add is considered first, then charge, then balance, but both output-producing operations still see 0.

Input: [('balance', 10), ('add', 'x', 10, 5, 5), ('charge', 10, 11), ('add', 'y', 8, 1, 10), ('charge', 12, 6)]

Expected Output: [6, 0, 12]

Explanation: At time 6, charge 12 uses x first because it expires earlier, then uses part of y, leaving 6 in y. At time 10, x is expired so balance is 6. At time 11, y is also expired, so the charge returns 0.

Input: []

Expected Output: []

Explanation: No operations means no outputs.

Solution

def solution(operations):
    import heapq

    events = []
    output_index = {}
    next_output = 0

    for idx, op in enumerate(operations):
        kind = op[0]
        if kind == 'add':
            _, bucket_id, amount, time_stamp, expiration = op
            events.append((time_stamp, 0, idx, bucket_id, amount, expiration))
        elif kind == 'charge':
            _, amount, time_stamp = op
            events.append((time_stamp, 1, idx, amount))
            output_index[idx] = next_output
            next_output += 1
        elif kind == 'balance':
            _, time_stamp = op
            events.append((time_stamp, 2, idx))
            output_index[idx] = next_output
            next_output += 1
        else:
            raise ValueError('Unknown operation type')

    events.sort()
    results = [0] * next_output

    # Heap item: [expiration_time, activation_time, id, serial, remaining]
    heap = []
    total = 0
    serial = 0

    def clean(current_time):
        nonlocal total
        while heap and (heap[0][0] <= current_time or heap[0][4] == 0):
            expiration, activation, bucket_id, order, remaining = heapq.heappop(heap)
            if expiration <= current_time and remaining > 0:
                total -= remaining

    for event in events:
        time_stamp = event[0]
        kind_order = event[1]
        original_idx = event[2]

        if kind_order == 0:
            bucket_id, amount, expiration = event[3], event[4], event[5]
            if amount <= 0 or expiration <= 0:
                continue
            item = [time_stamp + expiration, time_stamp, bucket_id, serial, amount]
            serial += 1
            heapq.heappush(heap, item)
            total += amount
        elif kind_order == 1:
            need = event[3]
            if need < 0:
                need = 0
            clean(time_stamp)
            charged = 0
            while need > 0 and heap:
                bucket = heap[0]
                take = min(need, bucket[4])
                bucket[4] -= take
                need -= take
                charged += take
                total -= take
                if bucket[4] == 0:
                    heapq.heappop(heap)
            results[output_index[original_idx]] = charged
        else:
            clean(time_stamp)
            results[output_index[original_idx]] = total

    return results

Time complexity: O(n log n). Space complexity: O(n).

Hints

Think of this as a sweep-line problem: sort all operations by effective execution order on the timeline.
Maintain the currently active credit buckets in a min-heap keyed by (expiration_end, activation_time, id), and keep a running sum of active remaining credit.

Last updated: May 27, 2026

Loading coding console...