Skip to main content
Talentd

Design Twitter - Solution & Explanation

MediumHash TableLinked ListDesignHeap (Priority Queue)16 min readAsked at: Amazon, Microsoft, Apple +11
Practice this problem

Problem Statement

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 <= 104
  • All the tweets have unique IDs.
  • At most 3 * 104 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.

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.

Code

PythonC++JavaCJavaScriptC#

Python

C++

Java

C

JavaScript

C#

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.

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.

Code

PythonJava

Python

Java

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 →

Approach 3: Default Approach

Code

PythonJava

Python

Java

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap with Priority QueuePost: 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 FollowersInsert: O(log N), Feed: O(N)O(N)Simpler design for small datasets where tweet volume is limited.

Video Solution

Design Twitter - Leetcode 355 - Python • NeetCode • 154,539 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Design Twitter with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design a File Sharing System