Design Twitter 🧠
LeetCode Link: Design Twitter
Difficulty: Medium
Problem Explanation 📝
Problem: LeetCode 355 - Design Twitter
Description: Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and see the 10 most recent tweets in the user's news feed.
Intuition: To design Twitter, we need to efficiently handle the following operations:
- Posting a tweet: We need to store the tweets along with their timestamps.
- Following/Unfollowing a user: We need to maintain a data structure to track the followers and followees of each user.
- Retrieving the news feed: We need to combine the tweets from the user's own timeline along with the tweets from the users they follow.
Approach:
- Implement the
User
class to store the user's information, including their tweets and the users they follow. - Use an unordered_map to store the user ID as the key and the corresponding
User
object as the value. - Implement the
Tweet
class to store the tweet's information, including the tweet ID and the timestamp. - Use a deque to store the tweets in the user's timeline, with the most recent tweet at the front.
- To post a tweet:
- Get the
User
object corresponding to the user ID. - Create a new
Tweet
object with the tweet ID and the current timestamp. - Add the tweet to the user's timeline and update the timestamp.
- To follow a user:
- Get the
User
objects corresponding to the follower and followee IDs. - Add the followee ID to the follower's list of followees.
- To unfollow a user:
- Get the
User
objects corresponding to the follower and followee IDs. - Remove the followee ID from the follower's list of followees.
- To retrieve the news feed:
- Get the
User
object corresponding to the user ID. - Create a priority_queue to store the tweets from the user's timeline and the timelines of the users they follow.
- Iterate over the tweets in the user's timeline and add them to the priority queue.
- Iterate over the followees of the user and add their tweets to the priority queue.
- Pop the top 10 tweets from the priority queue and return them in reverse order.
⌛ Time Complexity: The time complexity of posting a tweet, following/unfollowing a user, and retrieving the news feed is O(log n), where n is the number of tweets. This is because we use a priority queue to retrieve the top 10 tweets in the news feed.
💾 Space Complexity: The space complexity is O(m + n), where m is the number of users and n is the number of tweets. We store the user information in the unordered_map and the tweets in the deque.
Solutions 💡
Cpp 💻
class Twitter {
private:
struct Tweet {
int tweetId;
int timestamp;
Tweet(int id, int time) : tweetId(id), timestamp(time) {}
};
unordered_map<int, vector<Tweet>> userTweets; // Store tweets of each user
unordered_map<int, unordered_set<int>> userFollowees; // Store followees of each user
int time; // Keep track of the timestamp
public:
Twitter() {
time = 0;
}
void postTweet(int userId, int tweetId) {
userTweets[userId].emplace_back(tweetId, time++); // Add the tweet with the current timestamp
}
void follow(int followerId, int followeeId) {
userFollowees[followerId].insert(followeeId); // Add followee to the follower's set of followees
}
void unfollow(int followerId, int followeeId) {
userFollowees[followerId].erase(followeeId); // Remove followee from the follower's set of followees
}
vector<int> getNewsFeed(int userId) {
vector<int> newsFeed;
priority_queue<pair<int, int>> pq; // Use a priority queue to sort tweets by timestamp (max-heap)
// Add the user's own tweets to the priority queue
for (const auto &tweet : userTweets[userId]) {
pq.push({ tweet.timestamp, tweet.tweetId });
}
// Add tweets from the user's followees to the priority queue
for (int followeeId : userFollowees[userId]) {
for (const auto &tweet : userTweets[followeeId]) {
pq.push({ tweet.timestamp, tweet.tweetId });
}
}
// Retrieve the top 10 tweets from the priority queue
while (!pq.empty() && newsFeed.size() < 10) {
newsFeed.push_back(pq.top().second); // Add the tweet ID to the news feed
pq.pop();
}
return newsFeed;
}
};
Python 🐍
import heapq
class Tweet:
def __init__(self, tweet_id, timestamp):
self.tweet_id = tweet_id
self.timestamp = timestamp
class Twitter:
def __init__(self):
self.user_tweets = {} # User ID -> List of Tweet objects
self.user_followees = {} # User ID -> Set of followees
self.timestamp = 0
def postTweet(self, userId: int, tweetId: int) -> None:
self.timestamp += 1
if userId not in self.user_tweets:
self.user_tweets[userId] = []
self.user_tweets[userId].append(Tweet(tweetId, self.timestamp))
def getNewsFeed(self, userId: int) -> List[int]:
tweets = []
if userId in self.user_tweets:
tweets.extend(self.user_tweets[userId])
if userId in self.user_followees:
for followee in self.user_followees[userId]:
if followee in self.user_tweets:
tweets.extend(self.user_tweets[followee])
tweets.sort(key=lambda x: x.timestamp, reverse=True)
return [tweet.tweet_id for tweet in tweets[:10]]
def follow(self, followerId: int, followeeId: int) -> None:
if followerId != followeeId:
if followerId not in self.user_followees:
self.user_followees[followerId] = set()
self.user_followees[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
if (
followerId in self.user_followees
and followeeId in self.user_followees[followerId]
):
self.user_followees[followerId].remove(followeeId)
# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)