How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Perplexity AI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Perplexity AI during technical interviews.

Design a CreditTracker with expirations | Perplexity AI Coding Question

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.

Design a CreditTracker with expirations

Company: Perplexity AI

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.

Quick Answer: 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.

Input: ([('add', 0, 5, 40), ('add', 0, 5, 30), ('subtract', 3, 50), ('check', 3), ('check', 5)],)

Expected Output: [20, 20]

Explanation: Both grants expire at the same time, so subtraction breaks the tie by add order: the first grant loses 40, then the second loses 10, leaving 20 total.

Input: ([('add', -2, 1, 20), ('add', 0, 0, 15), ('subtract', 0, 50), ('check', 0), ('check', -1)],)

Expected Output: [0, 0]

Explanation: At time 0 there are only 35 active credits total, so subtract removes all of them. Both later checks return 0.

Input: ([],)

Expected Output: []

Explanation: With no operations, there are no check results.

Solution

def solution(operations):
    grants = []  # [start, end, remaining, add_order]
    answers = []
    add_order = 0

    for op in operations:
        kind = op[0]

        if kind == 'add':
            _, start, end, credit = op
            grants.append([start, end, credit, add_order])
            add_order += 1

        elif kind == 'subtract':
            _, time, credit = op
            if credit <= 0:
                continue

            active = []
            for i, grant in enumerate(grants):
                start, end, remaining, order = grant
                if remaining > 0 and start <= time <= end:
                    active.append((end, order, i))

            active.sort()
            need = credit

            for _, _, i in active:
                if need == 0:
                    break
                take = min(need, grants[i][2])
                grants[i][2] -= take
                need -= take

        elif kind == 'check':
            _, time = op
            total = 0
            for start, end, remaining, _ in grants:
                if remaining > 0 and start <= time <= end:
                    total += remaining
            answers.append(total)

        else:
            raise ValueError('Unknown operation type: {}'.format(kind))

    return answers

Time complexity: O(n^2 log n) in the worst case, where n is the number of operations. Space complexity: O(n).

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.

Quick Overview