GPU Credit System

MediumOpenAI Interview

Priority QueueSortingEvent Replay

You're building a system to track balances for an API credit purchasing system.

API users can purchase credit grants, specified by an ID, that are active at a timestamp and that let them use the API. Unused credit grant balances expire at a certain time.

However, there's a kink in our system: requests can arrive out of order because our system is built on a really unstable network. For example, a request to subtract credits can arrive at the system before the request to add credits, even though the request to add credits has a lower timestamp.

Implement the GPUCredit class, which should support the following operations:

•Granting credits, subtracting credits, and getting the credit balance for a user

•The ability to handle requests that arrive out of order

Rules

•All timestamps are ints and are unique (no two actions at the same timestamp).

•A credit grant is usable for timestamps in [grant_timestamp, grant_timestamp + expiration] (inclusive on both ends).

•Subtract from grants expiring soonest first.

•Balance is never negative. If a use event cannot be fully satisfied, spend as much as possible and ignore the remainder.

•Events are replayed in timestamp order regardless of arrival order.

•getBalance(t) returns None when the total remaining balance at time t is 0 (no active credits with remaining balance).

Class Skeleton

1class GPUCredit:
2    def __init__(self):
3        pass
4
5    def addCredit(self, creditID: str, amount: int,
6                  timestamp: int, expiration: int) -> None:
7        """
8        Add a credit grant usable during
9        [timestamp, timestamp + expiration] inclusive.
10        """
11        pass
12
13    def useCredit(self, timestamp: int, amount: int) -> None:
14        """
15        Record a credit usage event at the given timestamp.
16        """
17        pass
18
19    def getBalance(self, timestamp: int) -> int | None:
20        """
21        Return total remaining balance at time t,
22        or None if balance is 0.
23        """
24        pass

Examples

Example 1 — Single grant, basic queries

1gpu = GPUCredit()
2gpu.addCredit('microsoft', 10, 10, 30)
3gpu.getBalance(0)   # None  (no active grants)
4gpu.getBalance(10)  # 10
5gpu.getBalance(40)  # 10    (still within [10, 40])
6gpu.getBalance(41)  # None  (expired)

Example 2 — Multiple grants, usage, out-of-order

1gpu = GPUCredit()
2gpu.addCredit('amazon', 40, 10, 50)
3gpu.useCredit(30, 30)
4gpu.getBalance(40)  # 10   (40 - 30 = 10)
5gpu.addCredit('google', 20, 60, 10)
6gpu.getBalance(60)  # 30   (10 from amazon + 20 from google)
7gpu.getBalance(61)  # 20   (amazon expired at 60, google still active)
8gpu.getBalance(70)  # 20   (google active through 70)
9gpu.getBalance(71)  # None (google expired at 70)

Mock Interview Prompt

Copy this prompt into ChatGPT to practice with an AI interviewer.

Act as a senior SWE interviewing me for an entry-level to mid-level engineer position.

I have not done interviews in a long time. Do this step by step: start by asking me the question below without giving any hints, then give hints only if I appear stuck. Never directly give me the answer — always end with a question that guides me.

Here is the problem:

You're building a system to track balances for an API credit purchasing system.

API users can purchase credit grants, specified by an ID, that are active at a timestamp and that let them use the API. Unused credit grant balances expire at a certain time.

However, there's a kink in our system: requests can arrive out of order because our system is built on a really unstable network. For example, a request to subtract credits can arrive at the system before the request to add credits, even though the request to add credits has a lower timestamp.

Implement the GPUCredit class with:
- addCredit(creditID, amount, timestamp, expiration)
- useCredit(timestamp, amount)
- getBalance(timestamp) -> int | None

Guidelines:
- Do NOT worry about memory or performance concerns. Write simple, working code.
- All timestamps are ints and are unique.
- Subtract from grants expiring soonest first.
- A credit is usable during [timestamp, timestamp + expiration] inclusive.
- Balance cannot be negative.
- getBalance returns None when balance is 0.

solution.py

class GPUCredit:
    def __init__(self):
        pass

    def addCredit(self, creditID: str, amount: int,
                  timestamp: int, expiration: int) -> None:
        """
        Add a credit grant usable during
        [timestamp, timestamp + expiration] inclusive.
        """
        pass

    def useCredit(self, timestamp: int, amount: int) -> None:
        """
        Record a credit usage event at the given timestamp.
        """
        pass

    def getBalance(self, timestamp: int) -> int | None:
        """
        Return total remaining balance at time t,
        or None if balance is 0.
        """
        pass

class GPUCredit:
    def __init__(self):
        pass

    def addCredit(self, creditID: str, amount: int,
                  timestamp: int, expiration: int) -> None:
        """
        Add a credit grant usable during
        [timestamp, timestamp + expiration] inclusive.
        """
        pass

    def useCredit(self, timestamp: int, amount: int) -> None:
        """
        Record a credit usage event at the given timestamp.
        """
        pass

    def getBalance(self, timestamp: int) -> int | None:
        """
        Return total remaining balance at time t,
        or None if balance is 0.
        """
        pass