Design Twitter — LeetCode 355 Heap Plus HashMap

Problem Statement#

Design a simplified Twitter where users can post tweets, follow and unfollow other users, and see the 10 most recent tweets in their news feed.

• Twitter() — initialize
• postTweet(userId, tweetId) — compose a new tweet by userId
• getNewsFeed(userId) — return the 10 most recent tweet ids in the user's feed, ordered by timestamp descending. Feed includes tweets from the user and from people they follow
• follow(followerId, followeeId)
• unfollow(followerId, followeeId)

Constraints:

• 1 less-equal userId, tweetId less-equal 500
• Up to 10000 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]

Why This Problem Matters#

Design Twitter is a Meta favorite — they literally built the real thing — and Amazon and Uber ask close variants. It tests two skills: composing a hashmap of follows with a per-user tweet log, and merging multiple sorted streams using a heap.

This problem is also the cleanest LeetCode introduction to fan-out architectures. Real Twitter and Instagram feeds are built on a similar pattern at massive scale.

The Core Insight#

Three structures.

• followers: userId to set of followee ids (always include yourself)
• tweets: userId to list of (timestamp, tweetId) appended on every post
• a global timestamp counter that increments on every post

For getNewsFeed, walk every followee, push the tail of their tweet list into a max-heap keyed by timestamp, and pop 10 times. To avoid scanning every tweet, push only the latest tweet per followee and on each pop push the next tweet from that user. This is the k-way merge pattern.

Visual Dry Run#

User 1 follows user 2. user 2 posts tweets 6, 7. user 1 posts tweet 5.

Solution (Optimal)#

import heapq
from collections import defaultdict
 
class Twitter:
    def __init__(self):
        self.timestamp = 0
        self.tweets = defaultdict(list)
        self.followers = defaultdict(set)
 
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.timestamp += 1
        self.tweets[userId].append((self.timestamp, tweetId))
 
    def getNewsFeed(self, userId: int):
        heap = []
        people = self.followers[userId] | {userId}
        for uid in people:
            tweet_list = self.tweets[uid]
            if tweet_list:
                idx = len(tweet_list) - 1
                ts, tid = tweet_list[idx]
                heapq.heappush(heap, (-ts, tid, uid, idx))
        result = []
        while heap and len(result) < 10:
            neg_ts, tid, uid, idx = heapq.heappop(heap)
            result.append(tid)
            if idx > 0:
                ts2, tid2 = self.tweets[uid][idx - 1]
                heapq.heappush(heap, (-ts2, tid2, uid, idx - 1))
        return result
 
    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.followers[followerId].add(followeeId)
 
    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.followers[followerId].discard(followeeId)

var Twitter = function() {
    this.timestamp = 0;
    this.tweets = new Map();
    this.followers = new Map();
};
 
Twitter.prototype.postTweet = function(userId, tweetId) {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push([++this.timestamp, tweetId]);
};
 
Twitter.prototype.getNewsFeed = function(userId) {
    const people = new Set(this.followers.get(userId) || []);
    people.add(userId);
    const all = [];
    for (const uid of people) {
        const list = this.tweets.get(uid) || [];
        for (const [ts, tid] of list) all.push([ts, tid]);
    }
    all.sort((a, b) => b[0] - a[0]);
    return all.slice(0, 10).map(x => x[1]);
};
 
Twitter.prototype.follow = function(followerId, followeeId) {
    if (followerId === followeeId) return;
    if (!this.followers.has(followerId)) this.followers.set(followerId, new Set());
    this.followers.get(followerId).add(followeeId);
};
 
Twitter.prototype.unfollow = function(followerId, followeeId) {
    if (this.followers.has(followerId)) this.followers.get(followerId).delete(followeeId);
};

Time: postTweet, follow, unfollow are O(1). getNewsFeed is O(F log F + 10 log F) with F followees in the heap solution. Space: O(U + T) for users and tweets.

Common Mistakes#

• Forgetting to include the user in their own feed
• Allowing self-follow to inflate counts
• Using a min-heap instead of a max-heap for recency
• Scanning every tweet of every followee instead of pushing one per user into the heap
• Reusing a global tweet list and losing per-user ordering

Interview Tips#

• State the three structures and the global timestamp upfront
• Explain k-way merge — this is the same pattern as Merge K Sorted Lists
• Mention the real-world fan-out tradeoff: push fan-out at write time vs pull fan-out at read time
• Walk one example end to end with timestamps
• Mention that self-follow is a sneaky edge case

Follow-up Questions#

• Scale to a billion users — talk about fan-out on write vs on read
• Add likes and retweets — extend the tweet record
• Implement mute and block lists
• Persist tweets — sketch storage with sharding by userId
• Generate top trending hashtags — Count-Min Sketch plus heap

Key Takeaways#

• Design Twitter is LeetCode 355, frequent at Meta and Amazon
• Three structures: tweets per user, followers per user, global timestamp
• News feed uses k-way merge with a max-heap keyed by timestamp
• Always include the user in their own feed
• Real systems pick between fan-out on write and fan-out on read
• Heap solution is O(F log F) where F is number of followees
• The pattern generalizes to any per-user ordered stream merge