Katkat
Back

Design a CreditTracker with expirations

PerplexitySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates a candidate's ability to design and implement data structures and algorithms for managing time-bound resources with non-monotonic (out-of-order) operations, emphasizing correctness and efficiency within the coding & algorithms domain.

Design a CreditTracker class with three methods: (

  1. add_credit(start_time, end_time, credit), (
  2. subtract_credit(time, credit), and (
  3. check_credit(time). When subtracting credit at a given time, always deduct from the credit that has the earliest expiration time first. The calls to add_credit and subtract_credit may arrive in arbitrary (non-monotonic) time order. Implement these methods and choose data structures that make the operations efficient; explain your approach and analyze time and space complexity.