Trending Feed Manager
LinkedIn's feed algorithm constantly identifies trending content to keep users engaged. Imagine you're building a component for this system that tracks the top k most engaged posts in real-time. Engagement scores for posts can change frequently due to likes, shares, and comments, and your system needs to reflect these changes promptly to always display the most relevant content.
Implement the TrendingFeedManager class with the following methods:
constructor(k: number): Initializes the manager with a maximum capacity k for trending posts.updateEngagement(postId: number, engagementScore: number): Updates the engagement score for a given postId. If the post is new, it's added. If its score changes, the system should reflect this change.getTopKPosts(): number[]: Returns a list of postIds representing the top k most engaged posts. The list should be sorted by engagement score in descending order. If two posts have the same engagement score, they should be sorted by postId in ascending order.TrendingFeedManager(k: number)
k: A positive integer representing the maximum number of trending posts to track.updateEngagement(postId: number, engagementScore: number)
postId: A unique integer identifier for a post.engagementScore: A non-negative integer representing the current engagement score of the post.voidgetTopKPosts(): number[]
postIds, representing the top k most engaged posts, sorted as specified in the task. If fewer than k unique posts exist in the system, return all of them.postIds are unique positive integers.engagementScores are non-negative integers.getTopKPosts method must return postIds sorted by score descending, with postId ascending as a tie-breaker.k posts.Examples
Example 1
Input:
operations = ["TrendingFeedManager","updateEngagement","updateEngagement","getTopKPosts","updateEngagement","getTopKPosts"] params = [[2],[1,10],[2,20],[],[3,15],[]]
Output:
[null,null,null,[2,1],null,[2,3]]
Note:
Example 2
Input:
operations = ["TrendingFeedManager","updateEngagement","updateEngagement","updateEngagement","getTopKPosts","updateEngagement","getTopKPosts","updateEngagement","getTopKPosts"] params = [[3],[1,10],[2,20],[3,30],[],[1,25],[],[4,25],[]]
Output:
[null,null,null,null,[3,2,1],null,[3,1,2],null,[3,1,4]]
Note:
Example 3
Input:
operations = ["TrendingFeedManager","updateEngagement","updateEngagement","getTopKPosts"] params = [[3],[100,50],[200,80],[]]
Output:
[null,null,null,[200,100]]
Note:
Constraints
1 <= k <= 10^51 <= postId <= 10^90 <= engagementScore <= 10^9updateEngagement calls: N <= 10^5getTopKPosts calls: M <= 10^4updateEngagement calls.updateEngagement and getTopKPosts operations in terms of time and space complexity.k posts, and score updates (increase/decrease).Loading editor...