Frontend School

Top K Most Active Users

DSA
medium

Top K Most Active Users

Medium
Heap
Priority Queue
Hash Map

Overview

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.

What you need to do / Task

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:

  1. Filter activities: Only consider activities that fall within the time window [currentTime - windowDuration + 1, currentTime] (inclusive).
  2. Count activities: Determine the total number of activities for each user within this filtered window.
  3. Identify top k: Return the k user IDs with the highest activity counts.
  4. Tie-breaking: If multiple users have the same activity count, prioritize users with a smaller numerical user ID.
  5. Edge case: If there are fewer than k distinct active users, return all of them.

Input & output

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.

Clarifications

  • Empty activities: If activities is empty or no activities fall within the window, an empty array [] should be returned.
  • Large N: activities can contain up to 10^5 entries. Your solution should be efficient enough to handle this scale.
  • Timestamp range: Timestamps and currentTime can be large, up to 10^9. windowDuration can also be large.
  • User IDs: User IDs are positive integers.

Examples

1

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:

  1. User 1 (2 activities)
  2. User 2 (1 activity - ties with 3 and 4, but has the lowest ID). Output: [1, 2]
2

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]

3

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

Constraints & assumptions

  • 1 <= activities.length <= 10^5
  • 1 <= userId <= 10^9
  • 1 <= timestamp <= 10^9
  • 1 <= currentTime <= 10^9
  • 1 <= windowDuration <= currentTime
  • 1 <= k <= 10^5
  • All timestamps, currentTime, windowDuration, and k are integers.
  • The output array should be sorted as per the tie-breaking rule.

Out of scope

  • Handling negative timestamps or durations.
  • Real-time streaming data processing (assume activities is a snapshot).
  • Persistence or distributed aspects of user activity tracking.

What interviewers evaluate

  • Algorithmic Correctness: Does the solution correctly identify the top K active users considering all constraints and edge cases?
  • Data Structure Choice: Effective use of appropriate data structures (e.g., hash maps, priority queues/heaps) to manage counts and maintain the top K.
  • Time and Space Complexity: Efficiency of the solution, aiming for optimal or near-optimal performance for the given constraints.
  • Code Clarity and Maintainability: Readability, organization, and adherence to good coding practices.

Loading editor...