OpenAI VO Interview Problem: Credits Balance System with Expiring Grants

Credits

Implement the Credits class, which should support the following operations: granting credits, subtracting credits, and getting the balance for a user.

The system must handle requests that arrive out of order. For example, a request to subtract credits may arrive before the request to add credits, even if the add request has a lower timestamp.

Some guidelines:

• Do not worry about memory or performance concerns. Write simple, working code.
• No fancy data structures are needed.
• Timestamps can be represented as ints for simplicity and are unique.
• Subtract from grants expiring soonest first.

Implement:

class Credits:
    def create_grant(self, timestamp: int, grant_id: str, amount: int, expiration_timestamp: int) -> None:
        pass

    def subtract(self, timestamp: int, amount: int) -> None:
        pass

    def get_balance(self, timestamp: int) -> int | None:
        pass

Example usage:

# basic subtraction
credits = Credits()
credits.subtract(30, amount=1)
credits.create_grant(10, grant_id="a", amount=1, expiration_timestamp=100)
assert credits.get_balance(10) == 1
assert credits.get_balance(30) == 0
assert credits.get_balance(20) == 1

# expiration
credits = Credits()
credits.subtract(30, amount=1)
credits.create_grant(10, grant_id="a", amount=2, expiration_timestamp=100)
assert credits.get_balance(10) == 2
assert credits.get_balance(20) == 2
assert credits.get_balance(30) == 1
assert credits.get_balance(100) == 0

# subtracting from soonest expiring grants first
credits = Credits()
credits.create_grant(10, grant_id="a", amount=3, expiration_timestamp=60)
credits.create_grant(20, grant_id="b", amount=2, expiration_timestamp=40)
credits.subtract(30, amount=1)
credits.subtract(50, amount=3)
assert credits.get_balance(10) == 3
assert credits.get_balance(20) == 5
assert credits.get_balance(30) == 4
assert credits.get_balance(40) == 3
assert credits.get_balance(50) == 0

# not enough credit
credits = Credits()
credits.create_grant(10, grant_id="a", amount=3, expiration_timestamp=60)
credits.subtract(20, amount=4)
credits.create_grant(40, grant_id="b", amount=10, expiration_timestamp=60)
assert credits.get_balance(10) == 3
assert credits.get_balance(20) is None
assert credits.get_balance(50) is None

This problem is a simulation of a credit system with expiring grants and out-of-order requests. The main tasks are to track grants by timestamp, subtract credits from the grants that expire soonest first, and answer balance queries at any timestamp. A simple approach is enough: keep the events in time order, recompute the effective balance for a query time, and ignore grants after they expire. If a subtraction ever exceeds the available credits, later balance queries should return None to indicate the account has gone negative.