Flag Transaction Windows
MediumSliding Window · Bloomberg
A risk system watches a stream of transactions. Each element of transactions is [id, account, amount, timestamp], and the list is in processing order with timestamps non-decreasing.
When transaction x arrives, compute its window total: the sum of amount over every transaction for the same account that appears at or before x in the list and whose timestamp lies in the inclusive range [x.timestamp - window, x.timestamp]. This includes x itself. Transactions with the same timestamp that appear later in the list are not counted, because they have not arrived yet.
Transaction x is flagged if its window total is strictly greater than limit. Amounts can be negative (refunds and corrections), and they reduce the total.
Return the ids of all flagged transactions in the order they appear in transactions.
Example 1
- Input:
- transactions = [["t1", "acct1", 400, 100], ["t2", "acct2", 900, 105], ["t3", "acct1", 500, 130], ["t4", "acct1", 200, 160], ["t5", "acct1", 300, 200]], window = 60, limit = 1000
- Output:
- ["t4"]
- Explanation
- For t4 the window is 100 to 160, which still includes t1 at exactly 100, so acct1's total is 400 + 500 + 200 = 1100, over the limit. For t5 the window is 140 to 200, which holds only t4 and t5 (500). t2 belongs to another account and never counts toward acct1.
Example 2
- Input:
- transactions = [["a", "x", 700, 1], ["b", "x", -300, 2], ["c", "x", 500, 3]], window = 10, limit = 850
- Output:
- ["c"]
- Explanation
- a alone is 700 and the refund in b lowers the total to 400, so neither exceeds 850. c then brings the total to 400 + 500 = 900, which does.
Example 3
- Input:
- transactions = [["t1", "a", 5, 10], ["t2", "a", 6, 16]], window = 5, limit = 10
- Output:
- []
- Explanation
- t2's window is 11 to 16, and t1 at 10 falls just outside it, so t2's total is only 6.
Constraints
0 <= transactions.length <= 10^50 <= timestamp <= 10^9, non-decreasing through the list0 <= window <= 10^9-10^6 <= amount <= 10^6and-10^9 <= limit <= 10^9- Transaction ids are unique strings; account names are case-sensitive.