AlgoViz
HomeHeap / Priority Queue

Design Twitter

Medium

Merge the followees' feeds with a heap

Problem

Design Twitter: postTweet, getNewsFeed (10 most recent from self + followees), follow, unfollow.

In simple words

Merge each followed user's recent tweets by time using a heap, newest first.

The idea

Store each user's tweets newest-first with a global timestamp, then build a feed by merging the most recent tweet of each followee through a max-heap keyed on that timestamp. Only ten items are ever pulled, so the merge stays cheap regardless of history size.

The trick

  • A global counter gives a total order across users.
  • Push one head per followee, then pop and push the next from the same list.
  • Do not forget the user's own tweets.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — post, follow, getNewsFeed Values: 0.

1/2
Optimal
timeO(F log F)spaceO(N)
1store tweets with timestamps per user; follow sets2getNewsFeed: heap-merge recent tweets of self+followees, take 10

Input

array
[0]

Output

answer
—

Check yourself

2 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
post, follow, getNewsFeed
Output:
recent tweets

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.