Problem Statement

Design Twitter

We are building a tiny version of Twitter. People can post tweets, follow and unfollow each other, and ask for their news feed. The news feed is the 10 newest tweets, counting your own tweets plus tweets from everyone you follow, with the newest one first. The tricky part is the feed. You might follow many people, and each person has their own list of tweets in time order. You need to pick the 10 newest across all of those lists. The neat tool for this is a min-heap, also called a priority queue. A heap is like a bucket that always keeps the single most important item ready at the top. Here, "most important" means "newest tweet," so the heap hands us tweets newest first without us sorting everything.

mediumDesignHeapHeap / Priority QueueTime: O(k log n) · Space: O(n)

Signals to notice

design simplified Twittermerge k sorted tweet streamsOOP + heap

Brute force first

For each getNewsFeed, collect all tweets from followed users and sort — O(total tweets).

The key insight

Each user has a linked list of tweets (newest first). getNewsFeed: put heads of all followed users' lists in a max-heap (by time). Pop 10 times, pushing each popped user's next tweet. O(k log k).

Trace it on `ops: postTweet(1,5); follow(1,2); postTweet(2,6); getNewsFeed(1)`

postTweet(1,5): tweets[1]=[(0,5)], timestamp->1
follow(1,2): following[1]={2}
postTweet(2,6): tweets[2]=[(1,6)], timestamp->2
getNewsFeed(1): add self -> following[1]={1,2}; seed heap with each user's newest tweet: user1 push (-0,5,1,0), user2 push (-1,6,2,0)
pop: heap top is (-1,6,2,0) [most recent], feed=[6]; idx=0 so nothing re-pushed
pop: heap top is (-0,5,1,0), feed=[6,5]; idx=0 so nothing re-pushed
heap empty -> return feed=[6,5] (most recent first)

What must stay true

The max-heap merges k sorted streams to find the 10 most recent tweets across all followed users — same as merge-k-sorted-lists.

Shape of the loop

getNewsFeed(user):
  heap = []; follow set includes self
  for each followee with tweets: push (-newestTime, tweetId, fid, lastIdx)
  while heap and len(feed) < 10:
    pop newest -> append tweetId to feed
    if idx > 0: push that user's previous tweet (-time, tid, fid, idx-1)
  return feed

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Storing tweets globally — keeping tweets per-user makes follow/unfollow independent of tweet data and avoids cleanup on unfollow.

Heap / Priority Queue Pattern