355. Design Twitter - Solution & Explanation

Q: Is Design Twitter easy or hard?

Design Twitter is considered a medium difficulty problem. The API methods themselves are simple, but selecting the correct data structures to efficiently merge tweets from multiple users requires careful design thinking.

Q: Design Twitter Python or Java solution

Python solutions typically use defaultdict with heapq for the priority queue, while Java implementations rely on HashMap, HashSet, and PriorityQueue. Both follow the same design: store tweets per user with timestamps and merge them using a heap during feed retrieval.

Q: What is the best approach for Design Twitter?

The most efficient approach uses a HashMap to store follow relationships and tweet lists, combined with a Priority Queue (max heap) to merge recent tweets from followed users. This allows retrieving the 10 most recent tweets efficiently. Feed generation runs in O((F + 10) log F) time where F is the number of followed users.

Q: What data structure is used in Design Twitter?

Typical implementations use HashMap for storing users and follow relationships, a list or linked structure for each user's tweets, and a Priority Queue (heap) to efficiently retrieve the most recent tweets across multiple users.

Q: What is the time complexity of Design Twitter?

Posting a tweet and follow/unfollow operations run in O(1) time with hash maps. Retrieving the news feed using a heap-based merge costs O((F + 10) log F), where F is the number of users the person follows. Space complexity is O(T) for storing all tweets.

Q: How to solve Design Twitter in O((F+10) log F)?

Store tweets per user with timestamps and track follow relationships using hash maps. When generating the feed, push the latest tweet from each followed user into a max heap ordered by timestamp. Pop the newest tweet, add it to the feed, and push the next tweet from that user until 10 tweets are collected.

Q: Is Design Twitter asked at Google Amazon or Meta?

Design Twitter is a common object-oriented design problem asked in interviews at companies like Amazon, Meta, and Google. It tests data structure selection, API design, and efficient merging of sorted data streams.

The problem

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see 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) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.
List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

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]]

Explanation
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5]. return [5]
twitter.follow(1, 2);    // User 1 follows user 2.
twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.unfollow(1, 2);  // User 1 unfollows user 2.
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

Constraints:

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10⁴
All the tweets have unique IDs.
At most 3 * 10⁴ calls will be made to postTweet, getNewsFeed, follow, and unfollow.
A user cannot follow himself.

Approach overview

Problem Overview: Design a simplified Twitter system that supports posting tweets, following/unfollowing users, and retrieving the 10 most recent tweets in a user's news feed. The feed must include tweets from the user and the people they follow, ordered by recency.

Approach 1: HashMap with Priority Queue (O((F + 10) log F) time for feed, O(T) space)

This approach models users and tweets using hash-based lookups. Maintain a HashMap that maps each user to the list of their tweets, each tagged with an increasing timestamp. Another HashMap stores the set of users they follow. When generating the news feed, push the most recent tweet from each followed user into a Priority Queue (max heap ordered by timestamp). Repeatedly pop the newest tweet and push the next tweet from that same user until you collect 10 tweets. Posting a tweet is O(1), while feed generation costs O((F + 10) log F), where F is the number of followed users. This approach relies heavily on efficient lookups with a hash table and ordering with a heap (priority queue). It scales well when users follow many accounts but only need the most recent tweets.

Approach 2: Multiset for Tweets and Followers (O(N) feed time, O(N) space)

Instead of storing tweets per user, maintain a global ordered structure such as a multiset sorted by timestamp. Each entry stores (timestamp, userId, tweetId). A separate map tracks follow relationships. When retrieving the news feed, iterate through the multiset from most recent to oldest and collect tweets posted by the user or anyone they follow until 10 tweets are found. Insertions remain O(log N) due to ordered structure maintenance, and feed retrieval is O(N) in the worst case since you may scan many tweets before finding 10 valid ones. This approach is simpler conceptually but less efficient when the system contains many tweets. It fits scenarios where tweet volume is small or where maintaining per-user lists is unnecessary.

Recommended for interviews: The HashMap + Priority Queue design is the expected solution. It demonstrates strong understanding of system design patterns, efficient feed merging, and heap-based selection of the most recent elements. Interviewers look for the insight that you only need the latest tweets from each followee and can merge them using a heap, similar to merging sorted lists. The multiset approach shows a valid baseline but does not scale well for large datasets.

Approach 1: Approach 1: HashMap with Priority Queue

This approach uses a HashMap to keep track of follow relationships and a priority queue to fetch the top 10 tweets efficiently for the news feed.

We will use a map where the key is user ID and the value is a set of user IDs representing the followers. Another map will store the tweets where the key is the user ID, and the value is a list of tweet IDs. For the news feed, a min-heap (priority queue) will help us extract the most recent tweets.

Python

import heapq

class Twitter:
    def __init__(self):
        self.timestamp = 0
        self.tweets = {}
        self.following = {}

    def postTweet(self, userId, tweetId):
        self.timestamp += 1
        if userId not in self.tweets:
            self.tweets[userId] = []
        self.tweets[userId].append((self.timestamp, tweetId))

    def getNewsFeed(self, userId):
        min_heap = []
        if userId in self.tweets:
            for tweet in self.tweets[userId]:
                heapq.heappush(min_heap, tweet)
        if userId in self.following:
            for followed in self.following[userId]:
                if followed in self.tweets:
                    for tweet in self.tweets[followed]:
                        heapq.heappush(min_heap, tweet)
        # Fetch the 10 most recent tweets
        news_feed = [heapq.heappop(min_heap)[1] for _ in range(min(len(min_heap), 10))]
        return news_feed[::-1]

    def follow(self, followerId, followeeId):
        if followerId == followeeId:
            return
        if followerId not in self.following:
            self.following[followerId] = set()
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        if followerId in self.following and followeeId in self.following[followerId]:
            self.following[followerId].remove(followeeId)

Java

import java.util.*;

class Twitter {
    private static int timestamp = 0;
    private Map<Integer, List<Tweet>> tweets;
    private Map<Integer, Set<Integer>> following;

    public Twitter() {
        this.tweets = new HashMap<>();
        this.following = new HashMap<>();
    }

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

    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<Tweet> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a.timestamp));
        if (tweets.containsKey(userId)) {
            for (Tweet tweet : tweets.get(userId))
                minHeap.offer(tweet);
        }
        if (following.containsKey(userId)) {
            for (int followeeId : following.get(userId)) {
                if (tweets.containsKey(followeeId)) {
                    for (Tweet tweet : tweets.get(followeeId))
                        minHeap.offer(tweet);
                }
            }
        }

        List<Integer> recentTweets = new ArrayList<>();
        while (!minHeap.isEmpty() && recentTweets.size() < 10)
            recentTweets.add(minHeap.poll().tweetId);

        Collections.reverse(recentTweets);
        return recentTweets;
    }

    public void follow(int followerId, int followeeId) {
        if (followerId != 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);
    }

    private static class Tweet {
        int timestamp;
        int tweetId;

        Tweet(int timestamp, int tweetId) {
            this.timestamp = timestamp;
            this.tweetId = tweetId;
        }
    }
}

C++

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

class Twitter {
private:
    int timestamp;
    std::unordered_map<int, std::vector<std::pair<int, int>>> tweets;
    std::unordered_map<int, std::unordered_set<int>> following;

public:
    Twitter() : timestamp(0) {}

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

    std::vector<int> getNewsFeed(int userId) {
        std::priority_queue<std::pair<int, int>> feed;
        for (const auto& tweet : tweets[userId])
            feed.push(tweet);
        if (following.count(userId)) {
            for (const int& followeeId : following[userId]) {
                for (const auto& tweet : tweets[followeeId])
                    feed.push(tweet);
            }
        }
        std::vector<int> recentTweets;
        for (int i = 0; i < 10 && !feed.empty(); ++i) {
            recentTweets.push_back(feed.top().second);
            feed.pop();
        }
        return recentTweets;
    }

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

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

JavaScript

class Twitter {
    constructor() {
        this.timestamp = 0;
        this.tweets = new Map();
        this.following = new Map();
    }

    postTweet(userId, tweetId) {
        if (!this.tweets.has(userId)) this.tweets.set(userId, []);
        this.tweets.get(userId).push({ timestamp: this.timestamp++, tweetId });
    }

    getNewsFeed(userId) {
        let news = [];
        if (this.tweets.has(userId))
            news.push(...this.tweets.get(userId));

        const follows = this.following.get(userId) || new Set();
        follows.forEach(followeeId => {
            if (this.tweets.has(followeeId))
                news.push(...this.tweets.get(followeeId));
        });

        news.sort((a, b) => b.timestamp - a.timestamp); // descending order

        return news.slice(0, 10).map(tweet => tweet.tweetId);
    }

    follow(followerId, followeeId) {
        if (followerId === followeeId) return;
        if (!this.following.has(followerId)) this.following.set(followerId, new Set());
        this.following.get(followerId).add(followeeId);
    }

    unfollow(followerId, followeeId) {
        if (this.following.has(followerId))
            this.following.get(followerId).delete(followeeId);
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_USERS 501
#define MAX_TWEETS 10001

typedef struct Tweet {
    int tweetId;
    int timestamp;
    struct Tweet* next;
} Tweet;

typedef struct {
    Tweet* tweets[MAX_USERS];
    bool following[MAX_USERS][MAX_USERS];
    int timestamp;
} Twitter;

Twitter* twitterCreate() {
    Twitter* obj = (Twitter*)malloc(sizeof(Twitter));
    memset(obj->tweets, 0, sizeof(obj->tweets));
    memset(obj->following, false, sizeof(obj->following));
    obj->timestamp = 0;
    return obj;
}

void postTweet(Twitter* obj, int userId, int tweetId) {
    Tweet* newTweet = (Tweet*)malloc(sizeof(Tweet));
    newTweet->tweetId = tweetId;
    newTweet->timestamp = ++obj->timestamp;
    newTweet->next = obj->tweets[userId];
    obj->tweets[userId] = newTweet;
}

int* getNewsFeed(Twitter* obj, int userId, int* returnSize) {
    Tweet* minHeap[MAX_TWEETS];
    int heapSize = 0;

    Tweet* head = obj->tweets[userId];
    while (head) {
        minHeap[heapSize++] = head;
        head = head->next;
    }
    for (int i = 0; i < MAX_USERS; ++i) {
        if (obj->following[userId][i]) {
            head = obj->tweets[i];
            while (head) {
                minHeap[heapSize++] = head;
                head = head->next;
            }
        }
    }
    qsort(minHeap, heapSize, sizeof(Tweet*), [](const void* a, const void* b) {
        return ((*(Tweet**)b)->timestamp - (*(Tweet**)a)->timestamp);
    });
    int* newsFeed = (int*)malloc(10 * sizeof(int));
    *returnSize = heapSize < 10 ? heapSize : 10;
    for (int i = 0; i < *returnSize; ++i)
        newsFeed[i] = minHeap[i]->tweetId;
    return newsFeed;
}

void follow(Twitter* obj, int followerId, int followeeId) {
    if (followerId != followeeId)
        obj->following[followerId][followeeId] = true;
}

void unfollow(Twitter* obj, int followerId, int followeeId) {
    obj->following[followerId][followeeId] = false;
}

void twitterFree(Twitter* obj) {
    for (int i = 0; i < MAX_USERS; ++i) {
        Tweet* head = obj->tweets[i];
        while (head) {
            Tweet* toFree = head;
            head = head->next;
            free(toFree);
        }
    }
    free(obj);
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Twitter {
    private int timestamp;
    private Dictionary<int, List<Tweet>> tweets;
    private Dictionary<int, HashSet<int>> following;

    public Twitter() {
        timestamp = 0;
        tweets = new Dictionary<int, List<Tweet>>();
        following = new Dictionary<int, HashSet<int>>();
    }

    public void PostTweet(int userId, int tweetId) {
        if (!tweets.ContainsKey(userId)) {
            tweets[userId] = new List<Tweet>();
        }
        tweets[userId].Add(new Tweet(timestamp++, tweetId));
    }

    public IList<int> GetNewsFeed(int userId) {
        var news = new List<Tweet>();
        if (tweets.ContainsKey(userId))
            news.AddRange(tweets[userId]);

        if (following.ContainsKey(userId)) {
            foreach (var followeeId in following[userId]) {
                if (tweets.ContainsKey(followeeId))
                    news.AddRange(tweets[followeeId]);
            }
        }

        return news.OrderByDescending(t => t.Timestamp).Take(10).Select(t => t.TweetId).ToList();
    }

    public void Follow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        if (!following.ContainsKey(followerId))
            following[followerId] = new HashSet<int>();
        following[followerId].Add(followeeId);
    }

    public void Unfollow(int followerId, int followeeId) {
        if (following.ContainsKey(followerId))
            following[followerId].Remove(followeeId);
    }

    private class Tweet {
        public int Timestamp;
        public int TweetId;

        public Tweet(int timestamp, int tweetId) {
            Timestamp = timestamp;
            TweetId = tweetId;
        }
    }
}

This Python implementation uses two dictionaries: tweets and following. The tweets dictionary maps user IDs to a list of their tweets, where each tweet is a (timestamp, tweetId) tuple. The following dictionary maps user IDs to a set of user IDs they follow.

The postTweet method adds a tweet with a unique timestamp. The getNewsFeed method gathers all tweets from the user and users they follow, pushes them into a min-heap based on timestamps, and retrieves up to 10 tweets.

Complexity

Time Complexity for posting a tweet is O(1). For fetching the news feed, it's O(N + M log M) where N is the number of users, and M is the number of tweets. Space Complexity is O(U + T) where U is the number of users and T is the total number of tweets.

Try this approach in the editor

Approach 2: Approach 2: Multiset for Tweets and Followers

Here, we leverage the use of multisets or sorted lists to handle fetching of the 10 most recent tweets more efficiently.

Instead of managing the heap explicitly, some languages offer support for ordered collections, such as multisets, which can simplify the retrieval of the most recent items based on inserts.

Python

from collections import defaultdict
import heapq

class Twitter:
    def __init__(self):
        self.timestamp = 0
        self.user_tweets = defaultdict(list)
        self.user_follows = defaultdict(set)

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

    def getNewsFeed(self, userId: int):
        tweets = self.user_tweets[userId][:]
        for followeeId in self.user_follows[userId]:
            tweets.extend(self.user_tweets[followeeId])
        tweets.sort()  # max 10 sort
        return [tweetId for _, tweetId in tweets[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.user_follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.user_follows[followerId]:
            self.user_follows[followerId].remove(followeeId)

Java

import java.util.*;

class Twitter {
    private static int timeStamp = 0;
    private HashMap<Integer, List<Tweet>> tweetMap;
    private HashMap<Integer, Set<Integer>> followMap;

    public Twitter() {
        tweetMap = new HashMap<>();
        followMap = new HashMap<>();
    }

    public void postTweet(int userId, int tweetId) {
        tweetMap.putIfAbsent(userId, new ArrayList<>());
        tweetMap.get(userId).add(new Tweet(timeStamp++, tweetId));
    }

    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.time - a.time);
        List<Tweet> tweets = tweetMap.getOrDefault(userId, new ArrayList<>());
        pq.addAll(tweets);

        Set<Integer> followees = followMap.getOrDefault(userId, new HashSet<>());
        for (int user : followees) {
            tweets = tweetMap.getOrDefault(user, new ArrayList<>());
            pq.addAll(tweets);
        }

        List<Integer> recentFeeds = new ArrayList<>();
        while (!pq.isEmpty() && recentFeeds.size() < 10) {
            recentFeeds.add(pq.poll().id);
        }
        return recentFeeds;
    }

    public void follow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            followMap.putIfAbsent(followerId, new HashSet<>());
            followMap.get(followerId).add(followeeId);
        }
    }

    public void unfollow(int followerId, int followeeId) {
        Set<Integer> followees = followMap.get(followerId);
        if (followees != null) {
            followees.remove(followeeId);
        }
    }

    private static class Tweet {
        int time;
        int id;
        Tweet(int time, int id) {
            this.time = time;
            this.id = id;
        }
    }
}

This implementation uses a defaultdict for tweets and followers. Each tweet is stored with its negative timestamp to prioritize new tweets in sorting. The getNewsFeed function sorts these tweet entries to fetch the most recent ones efficiently.

Complexity

Time Complexity for posting is O(1). For newsfeed fetching: O(M log M). Space Complexity is O(U + T).

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: HashMap with Priority Queue	Time Complexity for posting a tweet is `O(1)`. For fetching the news feed, it's `O(N + M log M)` where `N` is the number of users, and `M` is the number of tweets. Space Complexity is `O(U + T)` where `U` is the number of users and `T` is the total number of tweets.
Approach 2: Multiset for Tweets and Followers	Time Complexity for posting is `O(1)`. For newsfeed fetching: `O(M log M)`. Space Complexity is `O(U + T)`.

Complexity analysis

Approach	Time	Space	When to Use
HashMap with Priority Queue	Post: O(1), Feed: O((F+10) log F)	O(T)	Best general solution. Efficient when users follow many accounts but only need the latest tweets.
Multiset for Tweets and Followers	Insert: O(log N), Feed: O(N)	O(N)	Simpler design for small datasets where tweet volume is limited.

Frequently asked questions

Is Design Twitter easy or hard?

Design Twitter is considered a medium difficulty problem. The API methods themselves are simple, but selecting the correct data structures to efficiently merge tweets from multiple users requires careful design thinking.

Design Twitter Python or Java solution

Python solutions typically use defaultdict with heapq for the priority queue, while Java implementations rely on HashMap, HashSet, and PriorityQueue. Both follow the same design: store tweets per user with timestamps and merge them using a heap during feed retrieval.

What is the best approach for Design Twitter?

The most efficient approach uses a HashMap to store follow relationships and tweet lists, combined with a Priority Queue (max heap) to merge recent tweets from followed users. This allows retrieving the 10 most recent tweets efficiently. Feed generation runs in O((F + 10) log F) time where F is the number of followed users.

What data structure is used in Design Twitter?

Typical implementations use HashMap for storing users and follow relationships, a list or linked structure for each user's tweets, and a Priority Queue (heap) to efficiently retrieve the most recent tweets across multiple users.

What is the time complexity of Design Twitter?

Posting a tweet and follow/unfollow operations run in O(1) time with hash maps. Retrieving the news feed using a heap-based merge costs O((F + 10) log F), where F is the number of users the person follows. Space complexity is O(T) for storing all tweets.

How to solve Design Twitter in O((F+10) log F)?

Store tweets per user with timestamps and track follow relationships using hash maps. When generating the feed, push the latest tweet from each followed user into a max heap ordered by timestamp. Pop the newest tweet, add it to the feed, and push the next tweet from that user until 10 tweets are collected.

Is Design Twitter asked at Google Amazon or Meta?

Design Twitter is a common object-oriented design problem asked in interviews at companies like Amazon, Meta, and Google. It tests data structure selection, API design, and efficient merging of sorted data streams.

Design Twitter solution and explanation

The problem

Approach overview

Approach 1: Approach 1: HashMap with Priority Queue

Approach 2: Approach 2: Multiset for Tweets and Followers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design Twitter solution and explanation

The problem

Approach overview

Approach 1: Approach 1: HashMap with Priority Queue

Approach 2: Approach 2: Multiset for Tweets and Followers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems