Top K Most Active Users
In high-traffic applications like collaboration tools, understanding user engagement in real-time is crucial for monitoring system health, identifying power users, or detecting unusual activity patterns. This problem simulates a core component for such a system, where we need to quickly identify the most active users within a recent time window.
Implement the getTopKActiveUsers function that, given a stream of user activities, identifies and returns the IDs of the top k most active users within a specified sliding time window.
Your implementation must satisfy the following:
[currentTime - windowDuration + 1, currentTime] (inclusive).k: Return the k user IDs with the highest activity counts.k distinct active users, return all of them.Function Signature:
function getTopKActiveUsers(activities: [number, number][], currentTime: number, windowDuration: number, k: number): number[]
Parameters:
activities: An array of [userId, timestamp] pairs, representing user actions. userId is a positive integer, timestamp is a positive integer representing time units (e.g., seconds). The activities array is not necessarily sorted by timestamp.currentTime: An integer representing the current moment in time. The time window ends at currentTime.windowDuration: A positive integer representing the length of the time window. The window is inclusive, from currentTime - windowDuration + 1 to currentTime.k: A positive integer representing the number of top active users to return.Return Value:
An array of number (user IDs), sorted by activity count (descending) then user ID (ascending) according to the tie-breaking rule. The length of the array should be at most k.
activities is empty or no activities fall within the window, an empty array [] should be returned.activities can contain up to 10^5 entries. Your solution should be efficient enough to handle this scale.currentTime can be large, up to 10^9. windowDuration can also be large.Examples
Example 1
Input:
activities = [[1, 10], [2, 12], [1, 15], [3, 18], [2, 20], [1, 22], [4, 25], [3, 28], [1, 29], [2, 30]], currentTime = 30, windowDuration = 10, k = 2
Output:
[1,2]
Note:
The time window is [30 - 10 + 1, 30] = [21, 30]. Activities within this window are: [1, 22], [4, 25], [3, 28], [1, 29], [2, 30]. User activity counts: User 1: 2 activities (at 22, 29) User 2: 1 activity (at 30) User 3: 1 activity (at 28) User 4: 1 activity (at 25)
Top 2 users:
Example 2
Input:
activities = [[101, 50], [102, 55], [101, 58], [103, 60], [102, 62]], currentTime = 65, windowDuration = 10, k = 5
Output:
[101,102,103]
Note:
The time window is [65 - 10 + 1, 65] = [56, 65]. Activities within this window are: [101, 58], [103, 60], [102, 62]. User activity counts: User 101: 1 activity User 102: 1 activity User 103: 1 activity
There are only 3 distinct active users, which is less than k=5. They are returned in order of count (all 1) then user ID (ascending). Output: [101, 102, 103]
Example 3
Input:
activities = [[1, 1], [2, 2]], currentTime = 10, windowDuration = 5, k = 1
Output:
[]
Note:
The time window is [10 - 5 + 1, 10] = [6, 10]. No activities fall within this window. An empty array is returned.
Constraints
1 <= activities.length <= 10^51 <= userId <= 10^91 <= timestamp <= 10^91 <= currentTime <= 10^91 <= windowDuration <= currentTime1 <= k <= 10^5currentTime, windowDuration, and k are integers.activities is a snapshot).Loading editor...