Credit Tracker with Expiring Credits

Design a `CreditTracker` class that adds credits over time ranges, subtracts credits at a point in time using earliest-expiration-first order, and checks available credit at a timestamp. Problem Statement We need to create a CreditTracker class. This class manages credits that are only valid for a specific time window. When we spend (subtract) credits, we must use the credits that expire soonest first. Methods to Implement: class CreditTracker: def add_credit(self, start_time: int, end_time: int, credit: int) -> None: """Add credit that works from start_time until end_time.""" def subtract_credit(self, time: int, credit: int) -> None: """Subtract credit at a specific time. Use the earliest expiring credit first.""" def check_credit(self, time: int) -> int: """Return the total credit left at a specific time.""" Rules: Credits work during the time range [start_time, end_time). When subtracting, always use the credit that is about to expire first. Commands can happen in any order. The time does not always move forward. Usage Example: tracker = CreditTracker() tracker.add_credit(0, 10, 50) # 50 credits. Works from t=0 to t=10 tracker.add_credit(3, 7, 30) # 30 credits. Works from t=3 to t=7 tracker.check_credit(5) # → 80 (Both credits work at t=5) tracker.subtract_credit(5, 40) # Spend 40 at t=5 # The credit (3,7) expires first. We take 30 from it. It is now empty. # The credit (0,10) expires next. We take the remaining 10 from it. It has 40 left. tracker.check_credit(5) # → 40 (Only the (0,10) credit has money left) tracker.check_credit(8) # → 40 (The (3,7) credit expired, so we don't count it) Part 1: Implementation Main Logic The hardest part is the subtract_credit method. Here is the plan: Find all credits that work at the current time. Sort them by their expiration time (earliest first). Take credit from the one that expires soonest. If we need more, go to the next one. This is called a "greedy" approach. It is the best way because we save the longer-lasting credits for later. Python Solution import heapq from typing import List class CreditTracker: def __init__(self): self.credits: List[List] = [] # [[start_time, end_time, remaining_credit], ...] def add_credit(self, start_time: int, end_time: int, credit: int) -> None: """Add a credit valid in [start_time, end_time).""" self.credits.append([start_time, end_time, credit]) def check_credit(self, time: int) -> int: """Return total available credit at the given time.""" total = 0 for start, end, credit in self.credits: if start <= time < end and credit > 0: total += credit return total def subtract_credit(self, time: int, credit: int) -> None: """ Subtract credit at the given time. Use the credit that expires earliest first. Raises ValueError if there is not enough credit. """ # Find credits that work at this time: (end_time, index) valid = [] for i, (start, end, cred) in enumerate(self.credits): if start <= time < end and cred > 0: valid.append((end, i)) # Check if we have enough credit before changing anything total_available = sum(self.credits[i][2] for _, i in valid) if total_available < credit: raise ValueError( f"Insufficient credit: needed {credit}, only {total_available} available" ) # Make a min-heap based on end_time (earliest expiration first) heapq.heapify(valid) remaining = credit while remaining > 0 and valid: end_time, idx = heapq.heappop(valid) available = self.credits[idx][2] deducted = min(remaining, available) self.credits[idx][2] -= deducted remaining -= deducted Step-by-Step Tracing Let's look at how the code runs with an example: Start: credits = [] 1. add_credit(0, 10, 50) List is: [[0, 10, 50]] 2. add_credit(3, 7, 30) List is: [[0, 10, 50], [3, 7, 30]] 3. check_credit(5) At time 5: - [0,10,50] works (0 <= 5 < 10) - [3,7,30] works (3 <= 5 < 7) Total = 50 + 30 = 80 4. subtract_credit(5, 40) Valid credits at time 5, sorted by end_time: 1. (ends at 7, index 1) -> Amount: 30 2. (ends at 10, index 0) -> Amount: 50 - Take from index 1 (ends first): We need 40. It has 30. Take all 30. Remaining needed = 10. Credit index 1 is now 0. - Take from index 0 (ends next): We need 10. It has 50. Take 10. Remaining needed = 0. Credit index 0 is now 40. List is now: [[0, 10, 40], [3, 7, 0]] 5. check_credit(5) At time 5: - [0,10,40] works. - [3,7,0] has 0 balance, so ignore. Total = 40 6. check_credit(8) At time 8: - [0,10,40] works. - [3,7,0] expired (8 >= 7). Total = 40 Testing def test_credit_tracker(): # Test 1: Simple add and check tracker = CreditTracker() tracker.add_credit(0, 10, 50) assert tracker.check_credit(5) == 50 assert tracker.check_credit(10) == 0 # end_time is not included assert tracker.check_credit(-1) == 0 # before start_time print("✓ Test 1: Basic add and check") # Test 2: Two credits at the same time tracker = CreditTracker() tracker.add_credit(0, 10, 50) tracker.add_credit(3, 7, 30) assert tracker.check_credit(5) == 80 assert tracker.check_credit(8) == 50 # only the first one is valid here assert tracker.check_credit(2) == 50 # only the first one is valid here print("✓ Test 2: Overlapping credits") # Test 3: Subtract from the one that expires first tracker = CreditTracker() tracker.add_credit(0, 10, 50) tracker.add_credit(3, 7, 30) tracker.subtract_credit(5, 40) # Took 30 from (3,7) and 10 from (0,10) assert tracker.check_credit(5) == 40 assert tracker.check_credit(8) == 40 # (3,7) is totally empty print("✓ Test 3: Earliest expiration subtraction") # Test 4: Not enough money tracker = CreditTracker() tracker.add_credit(0, 10, 20) try: tracker.subtract_credit(5, 30) assert False, "Should raise ValueError" except ValueError: pass print("✓ Test 4: Insufficient credit raises error") # Test 5: Times are not in order tracker = CreditTracker() tracker.add_credit(5, 15, 100) tracker.add_credit(0, 10, 50) # added second, but starts earlier tracker.subtract_credit(7, 60) # At t=7: (0,10) expires at 10, (5,15) expires at 15 # Take 50 from (0,10). Remaining needed = 10. # Take 10 from (5,15). assert tracker.check_credit(7) == 90 # 0 + 90 assert tracker.check_credit(11) == 90 # only (5,15,90) works here print("✓ Test 5: Non-monotonic time operations") # Test 6: Subtract multiple times tracker = CreditTracker() tracker.add_credit(0, 10, 100) tracker.subtract_credit(5, 30) tracker.subtract_credit(5, 30) tracker.subtract_credit(5, 30) assert tracker.check_credit(5) == 10 print("✓ Test 6: Multiple subtractions") # Test 7: Subtract when one credit expired tracker = CreditTracker() tracker.add_credit(0, 5, 20) tracker.add_credit(0, 10, 30) tracker.subtract_credit(6, 25) # At t=6: only (0,10,30) works. (0,5,20) is expired. assert tracker.check_credit(6) == 5 assert tracker.check_credit(3) == 25 # (0,5,20) is still full + (0,10,5) left print("✓ Test 7: Boundary validity check") print("All tests passed!") # test_credit_tracker() Part 2: Follow-Up — Optimizations Current Issues The simple solution has problems if we have too many credits: check_credit looks at every single credit. This takes O(n) time. subtract_credit also looks at every single credit to find the right ones. Credits that are empty or expired stay in the list forever. This wastes memory. Idea 1: Lazy Cleanup We can delete empty credits occasionally to keep the list short. def _cleanup(self) -> None: """Remove credits that are used up.""" self.credits = [entry for entry in self.credits if entry[2] > 0] We can run this every 100 operations. We can also remove expired credits if we know the current time. Idea 2: Sorted List We can use a sorted list so we don't have to scan everything. from sortedcontainers import SortedList class CreditTrackerOptimized: def __init__(self): # Keep list sorted by end_time automatically self.by_end = SortedList(key=lambda x: x[1]) self.credit_map = {} self.next_id = 0 def add_credit(self, start_time: int, end_time: int, credit: int) -> None: entry = [start_time, end_time, credit, self.next_id] self.credit_map[self.next_id] = entry self.by_end.add(entry) self.next_id += 1 This makes adding items faster (O(log n)), but checking validity is still tricky because we also need to check start_time. Idea 3: Interval Tree If we do check_credit very often, an Interval Tree is the best tool. It allows us to find all overlapping time ranges in O(log n) time. Pros: Very fast for checking and subtracting. Cons: Harder to write code for. Only worth it if you have thousands of credits. Time and Space Complexity Analysis n = total number of credits. k = number of valid credits at the specific time we are checking. Operation Time Space add_credit O(1) O(1) check_credit O(n) O(1) subtract_credit O(n + k log k) O(k) Why is subtract O(n + k log k)? We scan all n items to find the k valid ones: O(n). We turn the k items into a heap: O(k). We pop items from the heap to subtract: O(k log k). Space Complexity O(n): We must store every credit added. O(k): Temporary space used by the heap during subtraction. Interview Questions How would you handle many users doing this at the same time? Use "locks" so two people don't spend the same credit at once. Use a database that handles "transactions". How do we save this if the computer restarts? Save the credits in a database (SQL table). Columns: id, start_time, end_time, amount_left. What if we need to refund (undo) a subtraction? Keep a log (history) of every subtraction. Record exactly which credits were used and by how much. To refund, put that amount back into those specific credits. How do we handle millions of credits? Use an Interval Tree so we don't scan the whole list. Run a background job to delete old, expired data.