Chronological Points Subtraction

HardPython

Problem

Fetch receives point transactions for users. Positive transactions award points, while negative transactions redeem points. Implement a function that processes every transaction in chronological order and applies redemptions to the user's oldest available point awards first.

Transactions may be provided in any order. If two transactions have the same timestamp, process them in their original input order. A redemption may consume points from multiple awards, and any partially consumed award remains available for future redemptions. Every redemption is guaranteed to be no greater than the user's available balance at that point in chronological processing.

Formal Specification

Implement calculate_balances(transactions), where transactions is a list of dictionaries with:

user: a non-empty string
points: a nonzero integer, positive for an award and negative for a redemption
timestamp: an integer used for chronological ordering

Return a dictionary mapping each user to their final nonnegative integer balance. Do not mutate the input list.

Constraints

1 <= len(transactions) <= 2 * 10^5
Each transaction has user, points, and timestamp fields
1 <= len(user) <= 50
-10^9 <= points <= 10^9, excluding zero
0 <= timestamp <= 10^9
Each redemption is valid at the time it is processed

Function Signature

def calculate_balances(transactions):

Formal Specification

Implement calculate_balances(transactions), where transactions is a list of dictionaries with:

user: a non-empty string
points: a nonzero integer, positive for an award and negative for a redemption
timestamp: an integer used for chronological ordering

Return a dictionary mapping each user to their final nonnegative integer balance. Do not mutate the input list.