Frontend School

Real-time Top K Engaging Content

DSA
medium

Real-time Top K Engaging Content

Medium
Heap
Priority Queue
Hash Map

Overview

Netflix relies heavily on understanding user engagement with content in real-time to power dynamic recommendations, trending lists, and personalized user experiences. As new engagement data streams in, the 'top' content can shift rapidly. We need an efficient system to identify the most engaging content at any given moment.

This problem challenges you to process a series of engagement updates and identify the top K most engaging content items based on their latest scores. This capability is crucial for keeping our content discovery fresh and relevant.

What you need to do / Task

Implement a function getTopKEngagingContent that takes a list of content engagement updates and an integer k. The function should return the k content IDs that have the highest final engagement scores after all updates have been processed.

Each update is an array [contentId, engagementScore]. If multiple updates for the same contentId occur, only the latest engagementScore for that contentId should be considered for ranking.

Input & output

Function Signature:

function getTopKEngagingContent(updates: number[][], k: number): number[];
  • updates: An array of number[] arrays, where each inner array [contentId, engagementScore] represents an update to a content item's engagement score.
    • contentId: A unique identifier for a content item (positive integer).
    • engagementScore: The new engagement score for the contentId (non-negative integer).
  • k: An integer representing the number of top engaging content items to return.

Return Value:

  • An array of number representing the k contentIds with the highest final engagement scores. The returned contentIds should be sorted:
    1. By engagementScore in descending order.
    2. If engagementScores are equal, then by contentId in ascending order.
  • If there are fewer than k unique content items after all updates, return all unique contentIds sorted according to the rules above.

Clarifications

  • contentIds will be positive integers.
  • engagementScores will be non-negative integers.
  • k will always be a positive integer.
  • If updates is empty, an empty array [] should be returned.
  • If k is larger than the total number of unique content items, return all unique content items sorted as specified.

Examples

1

Example 1

Input:

updates = [[1,10],[2,5],[1,15],[3,20]], k = 2

Output:

[3,1]

Note:

After all updates, content ID 1 has score 15, ID 2 has score 5, and ID 3 has score 20. The top 2 are ID 3 (score 20) and ID 1 (score 15). Sorted by score descending, then ID ascending: [3, 1].

2

Example 2

Input:

updates = [[10,100],[20,50],[30,120],[10,110],[40,90]], k = 3

Output:

[30,10,40]

Note:

Final scores: ID 10: 110, ID 20: 50, ID 30: 120, ID 40: 90. The top 3 are ID 30 (120), ID 10 (110), ID 40 (90). Sorted: [30, 10, 40].

3

Example 3

Input:

updates = [[1,10],[2,5]], k = 5

Output:

[1,2]

Note:

There are only 2 unique content items (ID 1 with score 10, ID 2 with score 5). Since k=5 is greater than the number of unique items, all unique items are returned, sorted by score descending: [1, 2].

4

Example 4

Input:

updates = [], k = 1

Output:

[]

Note:

The updates list is empty, so no content items are available.

Constraints

Constraints & assumptions

  • 1 <= updates.length <= 10^5
  • 1 <= contentId <= 10^9
  • 0 <= engagementScore <= 10^9
  • 1 <= k <= updates.length (Note: k can be up to updates.length, but the actual number of unique content items might be smaller)
  • You should aim for a time complexity of O(N log K) where N is updates.length and K is the input k.
  • You should aim for a space complexity of O(U) where U is the number of unique content IDs.

Out of scope

  • Handling concurrent updates to engagement scores.
  • Network latency or distributed system concerns.
  • Persistent storage of engagement data.

What interviewers evaluate

  • Correctness: The solution accurately identifies the top K content items based on their latest engagement scores and handles sorting requirements.
  • Efficiency: Optimal use of data structures (e.g., hash maps and priority queues/heaps) to meet time and space complexity targets.
  • Edge Cases: Proper handling of scenarios like an empty updates list, k being larger than the number of unique content items, or multiple updates for the same contentId.
  • Code Quality: Clarity, readability, and maintainability of the code, including appropriate variable naming and structure.

Loading editor...