Design Twitter — K-Way Merge News Feed Interview

Problem Statement

Design a simplified Twitter:

postTweet(userId, tweetId) — user posts a tweet.
getNewsFeed(userId) — return the 10 most recent tweet IDs from the user and the people they follow.
follow(followerId, followeeId) — user follows another.
unfollow(followerId, followeeId) — user unfollows another.

Constraints:

1 <= userId, followerId, followeeId, tweetId <= 500
All tweetIds distinct.
Up to 3 * 10^4 calls.

Input:
postTweet(1, 5)
getNewsFeed(1)
follow(1, 2)
postTweet(2, 6)
getNewsFeed(1)
unfollow(1, 2)
getNewsFeed(1)
Output: [], [5], [6, 5], [5]

Input:
postTweet(1, 1)
getNewsFeed(1)
Output: [1]

Why This Problem Matters

LeetCode 355 is the canonical mini-system-design interview problem at Meta, Twitter, and Google. It compresses real-world feed building into a single class and tests whether you can apply K-way merge with a max-heap to retrieve the 10 most recent items across many users.

This is a priority queue interview question because the optimal feed retrieval is essentially merging K sorted streams (one per followee) and pulling the top 10. The pattern is exactly what production fanout-on-read systems use.

The Core Insight

Store each user's tweets as a list with a global timestamp. For getNewsFeed, build a max-heap with the latest tweet from each followee plus self. Pop 10 times; after each pop, push the next-newest from that user's list.

Visual Dry Run

User 1 follows 2. Tweets in order: 1 posts 5 (t=1), 2 posts 6 (t=2), 1 posts 7 (t=3).

Step	Heap (t, tweet, user, idx)	Pop	Result
1	(3,7,1,0),(2,6,2,0)	(3,7,1,0)	[7]
2	(2,6,2,0),(1,5,1,1)	(2,6,2,0)	[7,6]
3	(1,5,1,1)	(1,5,1,1)	[7,6,5]

Solution (Optimal)

import heapq
from collections import defaultdict
from typing import List
 
class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)  # user -> list of (time, tweetId)
        self.follows = defaultdict(set)
 
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1
 
    def getNewsFeed(self, userId: int) -> List[int]:
        heap = []
        users = self.follows[userId] | {userId}
        for u in users:
            if self.tweets[u]:
                idx = len(self.tweets[u]) - 1
                t, tid = self.tweets[u][idx]
                heapq.heappush(heap, (-t, tid, u, idx - 1))
        feed = []
        while heap and len(feed) < 10:
            neg_t, tid, u, idx = heapq.heappop(heap)
            feed.append(tid)
            if idx >= 0:
                t2, tid2 = self.tweets[u][idx]
                heapq.heappush(heap, (-t2, tid2, u, idx - 1))
        return feed
 
    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.follows[followerId].add(followeeId)
 
    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].discard(followeeId)

class MaxHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[i][0] > this.h[p][0]) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let m = i;
            if (l < n && this.h[l][0] > this.h[m][0]) m = l;
            if (r < n && this.h[r][0] > this.h[m][0]) m = r;
            if (m === i) break;
            [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
            i = m;
        }
    }
    get size() { return this.h.length; }
}
 
class Twitter {
    constructor() {
        this.time = 0;
        this.tweets = new Map();
        this.follows = new Map();
    }
    postTweet(userId, tweetId) {
        if (!this.tweets.has(userId)) this.tweets.set(userId, []);
        this.tweets.get(userId).push([this.time++, tweetId]);
    }
    getNewsFeed(userId) {
        const heap = new MaxHeap();
        const users = new Set(this.follows.get(userId) || []);
        users.add(userId);
        for (const u of users) {
            const list = this.tweets.get(u);
            if (list && list.length) {
                const idx = list.length - 1;
                heap.push([list[idx][0], list[idx][1], u, idx - 1]);
            }
        }
        const feed = [];
        while (heap.size && feed.length < 10) {
            const [t, tid, u, idx] = heap.pop();
            feed.push(tid);
            if (idx >= 0) {
                const list = this.tweets.get(u);
                heap.push([list[idx][0], list[idx][1], u, idx - 1]);
            }
        }
        return feed;
    }
    follow(followerId, followeeId) {
        if (followerId === followeeId) return;
        if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
        this.follows.get(followerId).add(followeeId);
    }
    unfollow(followerId, followeeId) {
        this.follows.get(followerId)?.delete(followeeId);
    }
}

Time: post O(1), follow/unfollow O(1), getNewsFeed O(K log K + 10 log K) where K is number of followees. Space: O(total tweets + total follow edges).

Common Mistakes

Forgetting that a user follows themself for feed purposes — must add userId to followee set when computing feed.
Pushing all tweets into the heap (O(N)) instead of the K-way merge (O(K)).
Using a global tweet log and filtering — works but slow for large feeds.
Forgetting unfollow on non-existent follow — must guard.
Not preventing self-follow if the spec says so — read carefully.

Interview Tips

Compare fanout-on-read (this approach) vs fanout-on-write (push to followers' inboxes) and discuss trade-offs.
Mention that real Twitter uses hybrid: celebrities are read-time pulled, regular users push to inboxes.
The K-way merge is the production trick; not pulling all tweets into one buffer.
Walk through what a Redis-backed implementation might look like.

Follow-up Questions

Add like(userId, tweetId) and rank by likes plus recency. Hint: weighted heap key.
What if some users have a million tweets? Hint: cap per-user list length or use index pointers.
What if you also need to mute users? Hint: add muted set to filter heap entries.
How would you scale to a billion users? Hint: shard by userId; Redis-backed sorted sets.
Add getMostFollowed() quickly. Hint: maintain a follower-count max-heap.

Key Takeaways

LeetCode 355 Design Twitter combines OOP with a K-way merge max-heap.
Per-user tweet lists keep posts O(1) and feeds efficient.
Get news feed pops 10 from a max-heap seeded with one entry per followee.
Time per feed is O(K log K) where K is the number of followees.
This is the canonical priority queue interview meets system design question.
Real-world systems use a hybrid fanout strategy.
Asked at Meta, Twitter, and Google interviews.

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Solution (Optimal)#

Common Mistakes#

Interview Tips#

Follow-up Questions#

Key Takeaways#

Related reading