Design Twitter

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

AmazonMicrosoftMeta

Problem Description

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and retrieve the 10 most recent tweets in the user’s news feed.

Implement the Twitter class:

Twitter() Initializes your Twitter object.
void postTweet(int userId, int tweetId) Posts a new tweet with tweetId by user userId.
List<Integer> getNewsFeed(int userId) Returns the 10 most recent tweet IDs in the user’s news feed. The feed includes tweets posted by the user themselves and by users they follow.
void follow(int followerId, int followeeId) The user with followerId follows the user with followeeId.
void unfollow(int followerId, int followeeId) The user with followerId unfollows the user with followeeId.

Examples

Example 1:

Input: [“Twitter”,“postTweet”,“getNewsFeed”,“follow”,“postTweet”,“getNewsFeed”,“unfollow”,“getNewsFeed”] [[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]] Output: [null,null,[5],null,null,[6,5],null,[5]]

Constraints

1 ≤ userId, followerId, followeeId ≤ 500
0 ≤ tweetId ≤ 10⁴
All tweets have unique IDs
At most 3 * 10⁴ calls will be made

Merge K Sorted Lists With a Heap

Each user has a list of tweets ordered by time (most recent first). The news feed is the 10 most recent tweets across all followed users. This is a k-way merge problem, exactly like Merge K Sorted Lists.

Store tweets as (timestamp, tweetId) pairs per user. For getNewsFeed, collect the latest tweet from each followed user into a max-heap, pop 10 times (or until the heap is empty), then pull the next tweet from that user.

A global timestamp counter keeps tweets globally ordered without a real clock.

Solution

import java.util.*;

class Twitter {
    private int timestamp = 0;
    private Map<Integer, List<int[]>> tweets = new HashMap<>(); // userId -> [(time, tweetId)]
    private Map<Integer, Set<Integer>> following = new HashMap<>(); // userId -> set of followees

    public Twitter() {}

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{timestamp++, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        // max-heap: [time, tweetId, userId, tweetIndex]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);

        // seed with this user's latest tweet
        Set<Integer> feedSources = new HashSet<>();
        feedSources.add(userId);
        if (following.containsKey(userId)) feedSources.addAll(following.get(userId));

        for (int uid : feedSources) {
            List<int[]> userTweets = tweets.get(uid);
            if (userTweets != null && !userTweets.isEmpty()) {
                int idx = userTweets.size() - 1;
                heap.offer(new int[]{userTweets.get(idx)[0], userTweets.get(idx)[1], uid, idx});
            }
        }

        List<Integer> feed = new ArrayList<>();
        while (!heap.isEmpty() && feed.size() < 10) {
            int[] top = heap.poll();
            feed.add(top[1]); // tweetId
            int uid = top[2], idx = top[3] - 1;
            if (idx >= 0) {
                List<int[]> userTweets = tweets.get(uid);
                heap.offer(new int[]{userTweets.get(idx)[0], userTweets.get(idx)[1], uid, idx});
            }
        }
        return feed;
    }

    public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        if (following.containsKey(followerId)) following.get(followerId).remove(followeeId);
    }
}

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.timestamp = 0
        self.tweets = defaultdict(list)   # userId -> [(time, tweetId)]
        self.following = defaultdict(set) # userId -> set of followees

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.timestamp, tweetId))
        self.timestamp += 1

    def getNewsFeed(self, userId: int) -> list[int]:
        feed_sources = {userId} | self.following[userId]
        heap = []

        for uid in feed_sources:
            user_tweets = self.tweets[uid]
            if user_tweets:
                idx = len(user_tweets) - 1
                time, tweet_id = user_tweets[idx]
                # negate time for max-heap behavior
                heapq.heappush(heap, (-time, tweet_id, uid, idx))

        feed = []
        while heap and len(feed) < 10:
            neg_time, tweet_id, uid, idx = heapq.heappop(heap)
            feed.append(tweet_id)
            idx -= 1
            if idx >= 0:
                time, next_tweet = self.tweets[uid][idx]
                heapq.heappush(heap, (-time, next_tweet, uid, idx))

        return feed

    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

class Twitter {
    int timestamp = 0;
    std::unordered_map<int, std::vector<std::pair<int,int>>> tweets; // userId->{time, tweetId}
    std::unordered_map<int, std::unordered_set<int>> following;

public:
    Twitter() {}

    void postTweet(int userId, int tweetId) {
        tweets[userId].push_back({timestamp++, tweetId});
    }

    std::vector<int> getNewsFeed(int userId) {
        // {time, tweetId, userId, index}
        auto cmp = [](auto& a, auto& b){ return std::get<0>(a) < std::get<0>(b); };
        std::priority_queue<std::tuple<int,int,int,int>,
                            std::vector<std::tuple<int,int,int,int>>, decltype(cmp)> heap(cmp);

        auto seed = [&](int uid) {
            if (tweets.count(uid) && !tweets[uid].empty()) {
                int idx = tweets[uid].size() - 1;
                heap.push({tweets[uid][idx].first, tweets[uid][idx].second, uid, idx});
            }
        };
        seed(userId);
        if (following.count(userId))
            for (int uid : following[userId]) seed(uid);

        std::vector<int> feed;
        while (!heap.empty() && (int)feed.size() < 10) {
            auto [t, tid, uid, idx] = heap.top(); heap.pop();
            feed.push_back(tid);
            if (--idx >= 0)
                heap.push({tweets[uid][idx].first, tweets[uid][idx].second, uid, idx});
        }
        return feed;
    }

    void follow(int followerId, int followeeId) {
        following[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        following[followerId].erase(followeeId);
    }
};

Complexity Analysis:

postTweet: O(1).
getNewsFeed: O(F log F + 10 log F) where F is the number of followed users. F log F to seed the heap, 10 log F for 10 pops.
follow/unfollow: O(1) with hash sets.
Space: O(total tweets + total follow relationships).

Where it breaks: each user could follow up to 500 others (per constraints). If F = 500, seeding the heap takes O(500 log 500) per getNewsFeed call. With 3×10⁴ calls this is manageable, but grows linearly with the number of followed users per call.

Common Mistakes

Including the user themselves in follow/unfollow operations. The user always sees their own tweets in the feed, so you include userId in the feed sources but never let them “follow themselves” as a separate relationship.
Not tracking the tweet index during heap processing. After popping a user’s latest tweet, you need to push their second-latest tweet into the heap. Storing the index makes this O(1).
Returning more than 10 tweets. The problem specifies at most 10. The feed.size() < 10 guard is required.

Frequently Asked Questions

Why not just collect all tweets and sort? For a user following 500 others who each have thousands of tweets, collecting and sorting all of them for each getNewsFeed call would be too slow. The k-way merge with a heap only processes as many tweets as you need (10).

What does the timestamp accomplish? Since tweets are stored in insertion order per user (oldest first), the index already implies order. The timestamp makes cross-user ordering unambiguous without having to compare arrays across users.