Katkat
Back

Implement expiring credit ledger

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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,
  1. // active [10,

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