Design a CreditTracker with expirations

Quick Overview

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.

Company: Perplexity

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

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

You are given a list of operations to apply to a CreditTracker. Each credit grant is active on the inclusive time interval [start_time, end_time]. Operations are processed in the order given, but the time values inside them are not sorted and may go backward. Each operation is one of: - ('add', start_time, end_time, credit): add a new credit grant. - ('subtract', time, credit): remove up to `credit` units from grants active at `time`, always using the active grant with the earliest `end_time` first. If several active grants expire at the same time, use the one that was added earlier first. If there is less active credit than requested, subtract everything available and stop. - ('check', time): return the total remaining credit that is active at `time`. Return a list containing the answers for all `check` operations in the order they appear.

Constraints

0 <= len(operations) <= 2 * 10^5
0 <= start_time <= end_time <= 10^9
0 <= time <= 10^9
1 <= credit <= 10^9 for add and subtract operations

Examples

Input: ([('add', 10, 20, 100), ('check', 15), ('add', 5, 15, 50), ('check', 12), ('subtract', 12, 70), ('check', 15), ('check', 18)],)

Expected Output: [100, 150, 80, 80]

Explanation: At time 12, both grants are active, so subtract uses the one ending at 15 first for 50, then 20 from the grant ending at 20. The remaining active credit is 80 at both later checks.

Input: ([('check', 5), ('add', 1, 10, 30), ('check', 6), ('subtract', 6, 10), ('check', 6), ('check', 1)],)

Expected Output: [0, 30, 20, 20]

Explanation: The first check happens before the grant is added, so it returns 0. After subtracting 10 at time 6, 20 remains and is still active at time 1 because intervals are inclusive and operation order matters.

Hints

When a grant loses x credit, that change affects every query time inside its whole interval. Think about a data structure that supports interval updates and point queries efficiently.
For subtract(time, ...), you need the active grant with the smallest end_time. After coordinate compression, a segment tree with heaps on nodes along a point's root-to-leaf path can help.

Approach

We keep one flat list grants, where each entry is [start, end, remaining, add_order]. remaining is the live balance left on that grant, and add_order is a strictly increasing counter assigned at insertion — it's the tiebreaker for "added earlier first." Operations are replayed in the exact order given; nothing is pre-sorted, which matters because the problem says the time values can move backward.

add — append [start, end, credit, add_order] and bump add_order. O(1).

subtract(time, credit) — first collect every active grant: one with remaining > 0 and start <= time <= end. For each we store (end, add_order, i) where i is its index in grants. Sorting these tuples orders them by earliest end_time, breaking ties by earliest add_order — exactly the consumption priority required. We then walk this sorted list, taking take = min(need, grants[i][2]) from each grant, decrementing both the grant's remaining and need, until need hits 0 or we run out of active credit (partial subtraction is allowed). A credit <= 0 subtract is a no-op.

check(time) — sum remaining over all grants active at time and append to answers.

Why it's correct

A grant is active iff start <= time <= end and it still has balance, so both check and subtract use the same membership test. Greedily draining the earliest-expiring grant first (with add_order tiebreak) matches the spec precisely, and because we mutate remaining in place, later operations see the depleted state. Only check results are recorded, preserving their relative order.

Time complexity:

O(n^2 log n)

Space complexity:

O(n)