Design Twitter
Design a mini Twitter: post tweets, follow and unfollow, and return the 10 most recent tweets in a user's news feed with a k-way merge on a heap.
Problem Understanding
Design Twitter: implement postTweet(userId, tweetId), follow(followerId, followeeId), unfollow(followerId, followeeId) and getNewsFeed(userId), which returns the ids of the 10 most recent tweets posted by the user or anyone they follow, newest first.
Example: postTweet(1, 5), getNewsFeed(1) → [5]; follow(1, 2), postTweet(2, 6), getNewsFeed(1) → [6, 5]; unfollow(1, 2), getNewsFeed(1) → [5].
The Intuition: Merge Sorted Lists, Stop at 10
The design follows from what each call needs:
- A global clock gives every tweet a position in time, so "most recent" is well defined.
- Per-user lists come out sorted for free, since tweets are appended in time order.
- The feed merges a few sorted lists and only needs the first 10 results, which is exactly what a heap is for: keep one candidate per user, always take the newest.
It is the same k-way merge as Merge k Sorted Lists, and the heap works like the one in Kth Largest Element in an Array. More problems like this are in the heap / priority queue pattern.
Interactive Walkthrough
t = POSTING TIME · OLDEST LEFT
EMPTY
user 1
→ none
no tweets
user 2
→ none
no tweets
call
:
max-heap (time · id)
Only during a feed
feed
Only during a feed
Start empty: a global clock, a tweet list per user, a follow set per user
Next
postTweet(1, 5): time = 1; append (1, 5) to user 1's list
calls
Each row is one user's tweets, oldest on the left, with the posting time underneath; who they follow is written by their name. During getNewsFeed, tweets in the heap are tinted, the one just popped is solid and tweets already in the feed are green. Try Interleaved to watch two users' tweets merge.
Dry Run Table
Calls: follow(1,2), follow(1,3), postTweet(2,11), postTweet(3,12), postTweet(2,13), postTweet(3,14), getNewsFeed(1).
| Step | Heap (time, id) | Popped | Pushed | Feed |
|---|---|---|---|---|
| seed | (4,14), (3,13) | |||
| 1 | (3,13), (2,12) | 14 | (2,12) from user 3 | 14 |
| 2 | (2,12), (1,11) | 13 | (1,11) from user 2 | 14, 13 |
| 3 | (1,11) | 12 | nothing older | 14, 13, 12 |
| 4 | empty | 11 | nothing older | 14, 13, 12, 11 |
Answer: [14, 13, 12, 11]. User 1 has no tweets, so it adds nothing to the heap.
The Solution Template
Python, Java, C++, JavaScript and TypeScript merge with a heap; the C version keeps one global tweet list and scans it newest-first, which is simpler without a library heap and fits LeetCode's limits.
Design Twitter Code
1class Heap {2 constructor(before) {3 this.items = [];4 this.before = before;5 }67 size() {8 return this.items.length;9 }1011 peek() {12 return this.items[0];13 }1415 push(item) {16 const a = this.items;17 a.push(item);18 let i = a.length - 1;19 while (i > 0 && this.before(a[i], a[(i - 1) >> 1])) {20 const parent = (i - 1) >> 1;21 [a[i], a[parent]] = [a[parent], a[i]];22 i = parent;23 }24 }2526 pop() {27 const a = this.items;28 const top = a[0];29 const last = a.pop();30 if (a.length > 0) {31 a[0] = last;32 let i = 0;33 while (true) {34 const left = 2 * i + 1, right = 2 * i + 2;35 let first = i;36 if (left < a.length && this.before(a[left], a[first])) first = left;37 if (right < a.length && this.before(a[right], a[first])) first = right;38 if (first === i) break;39 [a[i], a[first]] = [a[first], a[i]];40 i = first;41 }42 }43 return top;44 }45}4647var Twitter = function() {48 this.time = 0;49 this.tweets = new Map();50 this.following = new Map();51};5253Twitter.prototype.postTweet = function(userId, tweetId) {54 if (!this.tweets.has(userId)) this.tweets.set(userId, []);55 this.tweets.get(userId).push([++this.time, tweetId]);56};5758Twitter.prototype.getNewsFeed = function(userId) {59 const heap = new Heap((a, b) => a[0] > b[0]);60 const users = new Set(this.following.get(userId) || []);61 users.add(userId);62 for (const u of users) {63 const list = this.tweets.get(u) || [];64 if (list.length) {65 const i = list.length - 1;66 heap.push([list[i][0], list[i][1], u, i]);67 }68 }69 const feed = [];70 while (heap.size() > 0 && feed.length < 10) {71 const [, id, u, i] = heap.pop();72 feed.push(id);73 if (i > 0) {74 const [t, prev] = this.tweets.get(u)[i - 1];75 heap.push([t, prev, u, i - 1]);76 }77 }78 return feed;79};8081Twitter.prototype.follow = function(followerId, followeeId) {82 if (followerId === followeeId) return;83 if (!this.following.has(followerId)) this.following.set(followerId, new Set());84 this.following.get(followerId).add(followeeId);85};8687Twitter.prototype.unfollow = function(followerId, followeeId) {88 this.following.get(followerId)?.delete(followeeId);89};
Edge Cases & Common Mistakes
- Forgetting your own tweets: the feed includes the user's own posts, so add the user to the set being merged.
- Following yourself: ignore
follow(u, u), or your tweets can appear twice. - Unfollowing someone you never followed: must be a no-op, not an error.
- Ordering by tweet id: ids are not times; order by the global counter.
- Fewer than 10 tweets: stop when the heap runs out.
Summary
Stamp each tweet with a global time and append it to its author's list; keep a follow set per user. For the feed, seed a max-heap with each followed user's newest tweet (plus your own), then pop the newest and push that user's next-older tweet until you have 10. Posting and following are O(1); a feed is O(f + 10 log f).
More practice: DSA interview questions with answers · patterns cheat sheet