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