Frontend School

Trending Feed Manager

DSA
medium

Trending Feed Manager

Medium
Heap
Priority Queue
Data Structure Design
Hash Map

Overview

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.

What you need to do / Task

Implement the TrendingFeedManager class with the following methods:

  1. constructor(k: number): Initializes the manager with a maximum capacity k for trending posts.
  2. 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.
  3. 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.

Input & output

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.
  • Returns: void

getTopKPosts(): number[]

  • Returns: An array of 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.

Clarifications

  • postIds are unique positive integers.
  • engagementScores are non-negative integers.
  • The getTopKPosts method must return postIds sorted by score descending, with postId ascending as a tie-breaker.
  • A post's score can increase or decrease. The system must always reflect the latest score for each post.
  • The internal data structures should be optimized for frequent updates and efficient retrieval of the top k posts.

Examples

1

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:

  1. Initialize with k=2.
  2. Update post 1 with score 10.
  3. Update post 2 with score 20.
  4. getTopKPosts: Current posts are [2 (score 20), 1 (score 10)]. Returns [2, 1].
  5. Update post 3 with score 15. Now we have posts [2 (20), 3 (15), 1 (10)].
  6. getTopKPosts: Top 2 posts are [2 (20), 3 (15)]. Returns [2, 3].
2

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:

  1. Initialize with k=3.
  2. Update posts 1, 2, 3 with scores 10, 20, 30.
  3. getTopKPosts: Returns [3 (30), 2 (20), 1 (10)].
  4. Update post 1 with new score 25. Scores are now: 3 (30), 1 (25), 2 (20).
  5. getTopKPosts: Returns [3 (30), 1 (25), 2 (20)].
  6. Update post 4 with score 25. Scores are now: 3 (30), 1 (25), 4 (25), 2 (20). For scores 25, post 1 (ID=1) comes before post 4 (ID=4) due to tie-breaker (smaller postId).
  7. getTopKPosts: Top 3 are [3 (30), 1 (25), 4 (25)].
3

Example 3

Input:

operations = ["TrendingFeedManager","updateEngagement","updateEngagement","getTopKPosts"] params = [[3],[100,50],[200,80],[]]

Output:

[null,null,null,[200,100]]

Note:

  1. Initialize with k=3.
  2. Update post 100 (score 50), post 200 (score 80).
  3. getTopKPosts: Only 2 posts exist, so both are returned. Sorted: [200 (80), 100 (50)].

Constraints

Constraints & assumptions

  • 1 <= k <= 10^5
  • 1 <= postId <= 10^9
  • 0 <= engagementScore <= 10^9
  • Total updateEngagement calls: N <= 10^5
  • Total getTopKPosts calls: M <= 10^4
  • Time limit: ~40 minutes for implementation and testing.
  • Space complexity: Should be efficient enough for the given constraints.

Out of scope

  • Persistence of data across application restarts.
  • Handling concurrent updateEngagement calls.
  • Distributed system concerns or fault tolerance.

What interviewers evaluate

  • Correctness of data structure selection and implementation (Heaps, Hash Maps).
  • Efficiency of updateEngagement and getTopKPosts operations in terms of time and space complexity.
  • Handling of edge cases such as empty input, fewer than k posts, and score updates (increase/decrease).
  • Code clarity, organization, and adherence to best practices.

Loading editor...