Design Twitter
Table of Contents + −
Design Twitter is a design question, not a one-line trick. The interviewer wants to see if you can build a small system from simple parts. The hard part is the feed. You must show the most recent tweets from all the people one user follows. So how do you pull the newest ones without sorting everything? That is the real test here.
🎯 The Problem
You build a tiny version of Twitter that supports a few actions.
The actions:
- Post a tweet.
- Follow another user.
- Unfollow a user.
- Ask for your news feed.
The news feed rules:
- It collects tweets from the user and from everyone the user follows.
- You return only the 10 newest tweets, newest first.
- Each tweet gets a global timestamp when posted. Bigger timestamp means newer.
Input (operation log): postTweet(1, 5) -> user 1 posts tweet 5 getNewsFeed(1) -> [5] follow(1, 2) -> user 1 follows user 2 postTweet(2, 6) -> user 2 posts tweet 6 getNewsFeed(1) -> [6, 5] unfollow(1, 2) -> user 1 unfollows user 2 getNewsFeed(1) -> [5]
Output: [5], [6, 5], [5]Each tweet gets a global timestamp when it is posted. A bigger timestamp means newer. So newest first means largest timestamp first.
The picture below shows what the feed must collect. Each person keeps their own list of tweets. The feed merges the lists of the user and the people they follow.
🐢 Approach 1: Gather All Tweets and Sort (Brute Force)
The idea in one line: collect every tweet you could show, then sort and keep the top 10.
The idea:
- Gather every tweet from the user and from everyone they follow.
- Put them all in one big list.
- Sort that list by timestamp, newest first.
- Take the first 10.
Why it is weak:
- You collect every tweet, even very old ones you will never show.
- A user might follow many people with thousands of tweets each.
- You pull them all just to keep 10, then sort the whole pile.
- That is O(N log N), where N is the total tweets across everyone followed.
Here is the gather-and-sort code:
class Twitter: def __init__(self): self.time = 0 self.tweets = [] self.following = {}
def postTweet(self, userId, tweetId): self.time += 1 self.tweets.append((self.time, userId, tweetId))
def getNewsFeed(self, userId): users = self.following.get(userId, set()) | {userId} feed = [tweet for tweet in self.tweets if tweet[1] in users] feed.sort(reverse=True) return [tweet_id for time, user, tweet_id in feed[:10]]
def follow(self, followerId, followeeId): self.following.setdefault(followerId, set()).add(followeeId)
def unfollow(self, followerId, followeeId): self.following.setdefault(followerId, set()).discard(followeeId)⚡ Approach 2: Heap-Merge the Recent Tweets (Best)
The idea in one line: merge each person’s tweet lists with a heap and stop after 10.
What we set up:
- Keep each user’s tweets in their own list, in post order.
- So each person’s newest tweet sits at the end of their list.
- Use a max-heap, which always hands you the largest item first.
- Here “largest” means the biggest timestamp, which is the newest tweet.
How it works:
- Put each person’s newest tweet into the heap.
- Pop the top. That is the newest tweet overall. Add it to the feed.
- Push the next older tweet from that same person.
- Repeat until the feed has 10 tweets or the heap is empty.
Why it is fast:
- You never touch old tweets you do not need.
- The heap holds at most one tweet per person you follow.
- This is the classic “merge k sorted lists” pattern.
The diagram below shows the heap pulling the newest tweet each step.
Steps to Solve
- Give every tweet a global timestamp that grows by one each post. Bigger means newer.
- Store each user’s tweets in their own list, in post order.
- To build a feed, take the user and everyone they follow. From each, take their newest tweet and push it into a max-heap keyed by timestamp.
- Pop the top of the heap. That tweet is the newest. Add it to the feed.
- From the person whose tweet you just used, push their next older tweet into the heap.
- Repeat until the feed has 10 tweets or the heap is empty. Return the feed.
This Python version uses heapq to build a heap. Python’s heapq is a min-heap, so we push negative timestamps to get max-heap behaviour, newest first.
import heapqfrom collections import defaultdict
class Twitter: def __init__(self): self.time = 0 self.tweets = defaultdict(list) # user -> list of (time, tweetId) self.following = defaultdict(set) # user -> set of followed users
def postTweet(self, userId, tweetId): self.tweets[userId].append((self.time, tweetId)) # newer = bigger time self.time += 1
def getNewsFeed(self, userId): heap = [] # min-heap on negative time = max-heap people = self.following[userId] | {userId} for p in people: if self.tweets[p]: idx = len(self.tweets[p]) - 1 t, tid = self.tweets[p][idx] heapq.heappush(heap, (-t, tid, p, idx)) # newest tweet of p feed = [] while heap and len(feed) < 10: neg_t, tid, p, idx = heapq.heappop(heap) # newest tweet overall feed.append(tid) if idx > 0: # older tweet of same person t2, tid2 = self.tweets[p][idx - 1] heapq.heappush(heap, (-t2, tid2, p, idx - 1)) return feed
def follow(self, a, b): self.following[a].add(b)
def unfollow(self, a, b): self.following[a].discard(b)
t = Twitter()t.postTweet(1, 5)print(t.getNewsFeed(1)) # [5]t.follow(1, 2)t.postTweet(2, 6)print(t.getNewsFeed(1)) # [6, 5]t.unfollow(1, 2)print(t.getNewsFeed(1)) # [5]The output of the above code will be:
[5][6, 5][5]Let us walk through the Python feed line by line, because the heap merge is the heart of this problem.
The line heap = [] makes an empty list. We treat it as a heap with heapq. Python’s heapq is always a min-heap. A min-heap hands you the smallest item first. But we want the newest tweet, which has the largest timestamp. So we store the timestamp as a negative number. The smallest negative is the largest real time. That flips it into a max-heap.
The line people = self.following[userId] | {userId} builds the set of people whose tweets matter. It is everyone the user follows, plus the user themselves.
The first loop pushes one tweet per person: idx = len(self.tweets[p]) - 1 points at that person’s last tweet, which is their newest. We push (-t, tid, p, idx). We keep p and idx so we can find that person’s next older tweet later.
Then while heap and len(feed) < 10: runs until we have 10 tweets or the heap is empty. Each heappop returns the entry with the smallest -t, which means the largest real time. So that is the newest tweet across everyone. We add its id to feed.
The line if idx > 0: checks if that person has an older tweet. If yes, we push it. This is the merge step. We only ever bring in the next tweet when we use one. So the heap stays small. That is what keeps this fast.
⏱️ Time and Space Complexity
The brute force gathers every tweet and sorts the whole pile, so it is O(N log N) where N is the total tweets. The heap-merge only touches the tweets it actually returns. To pull 10 tweets, it does about 10 heap steps. Each heap step costs O(log k), where k is the number of people you follow. So the feed is O(10 log k), which is far less work when people have many old tweets.
| Approach | getNewsFeed Time | Space Complexity |
|---|---|---|
| Gather all tweets and sort | O(N log N) | O(N) |
| Heap-merge newest tweets | O(10 log k) | O(k) |
Tip
In an interview, say out loud that the feed is just “merge k sorted lists”. Each person’s tweets are already sorted by time. The heap merges them. Naming the known pattern shows the interviewer you see the structure under the question.
🧩 Key Takeaways
- ✅ Give each tweet a global timestamp so newest just means largest timestamp.
- ✅ Keep each user’s tweets in their own ordered list, so the newest is at the end.
- ✅ Use a max-heap to merge the newest tweet from each followed person.
- ✅ Only push a person’s next older tweet when you pop one of theirs, so the heap stays small.
- ✅ Recognize the feed as the classic “merge k sorted lists” pattern.
Check Your Knowledge
Test what you learned. Pick an answer for each question, then click Check.
- 1
Why does each tweet get a global timestamp?
Why: A global growing timestamp means a bigger number is always a newer tweet, so the feed just needs the largest timestamps.
- 2
What classic pattern does building the news feed match?
Why: Each person's tweets are already sorted by time, so merging them with a heap is exactly merge k sorted lists.
- 3
Why is the heap kept small during getNewsFeed?
Why: We push one tweet per person, then only add their next older tweet when we pop one of theirs, so the heap stays at about k entries.
- 4
Why does the Python version push negative timestamps into heapq?
Why: heapq is a min-heap. Storing negative timestamps means the smallest negative is the largest real time, giving newest first.