Transaction Window Count
At Stripe, efficiently processing and querying transaction data is crucial for analytics, reporting, and fraud detection. A common requirement is to quickly determine the volume of transactions occurring within specific timeframes. This problem challenges you to implement an efficient solution for counting transactions that fall into a given set of time windows.
Implement the countTransactionsInWindows function that takes a list of Transaction objects and a list of Window objects. For each specified Window, you must determine and return the total count of transactions whose timestamps fall inclusively within that window's start and end times.
Input:
transactions: An array of Transaction objects. Each Transaction has two properties:
timestamp: A number representing the transaction's occurrence time (e.g., Unix epoch seconds).amount: A number representing the transaction's value.windows: An array of Window objects. Each Window has two properties:
start: A number representing the inclusive start timestamp of the window.end: A number representing the inclusive end timestamp of the window.Output:
numbers. The i-th element of the output array should be the count of transactions for the i-th window in the input windows array.t is considered to be within a window [start, end] if start <= t <= end.transactions array is not guaranteed to be sorted by timestamp.transactions or windows arrays can be empty. Handle these cases gracefully (e.g., an empty transactions list should result in all counts being 0; an empty windows list should result in an empty output array).Examples
Example 1
Input:
transactions = [{ timestamp: 10, amount: 100 }, { timestamp: 5, amount: 50 }, { timestamp: 15, amount: 150 }, { timestamp: 10, amount: 75 }], windows = [{ start: 0, end: 7 }, { start: 9, end: 11 }, { start: 12, end: 20 }]
Output:
[1,2,1]
Note:
Sorted transactions by timestamp: [{5, 50}, {10, 100}, {10, 75}, {15, 150}]. Window [0, 7]: Contains {5, 50}. Count = 1. Window [9, 11]: Contains {10, 100} and {10, 75}. Count = 2. Window [12, 20]: Contains {15, 150}. Count = 1.
Example 2
Input:
transactions = [{ timestamp: 1, amount: 10 }, { timestamp: 2, amount: 20 }, { timestamp: 3, amount: 30 }], windows = [{ start: 0, end: 0 }, { start: 4, end: 5 }, { start: 1, end: 3 }]
Output:
[0,0,3]
Note:
Window [0, 0]: No transactions. Count = 0. Window [4, 5]: No transactions. Count = 0. Window [1, 3]: Contains {1, 10}, {2, 20}, {3, 30}. Count = 3.
Example 3
Input:
transactions = [], windows = [{ start: 100, end: 200 }, { start: 0, end: 1000 }]
Output:
[0,0]
Note:
With no transactions, all window counts should be 0.
Example 4
Input:
transactions = [{ timestamp: 50, amount: 100 }], windows = []
Output:
[]
Note:
With no query windows, the output array should be empty.
Constraints
0 <= transactions.length <= 10^50 <= windows.length <= 10^50 <= transaction.timestamp <= 10^90 <= window.start <= window.end <= 10^90 <= transaction.amount <= 10^6O(N log N + M log N), where N is the number of transactions and M is the number of windows.O(N) for storing timestamps or O(1) if sorting in-place (depending on language's sort implementation).timestamp, amount, start, end properties exist and are numbers).Loading editor...