Coding questions · OpenAI

Implement expiring credit ledger

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

Implement Expiring Credit Ledger

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

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.