Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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:

  1. Posting a tweet: We need to store the tweets along with their timestamps.
  2. Following/Unfollowing a user: We need to maintain a data structure to track the followers and followees of each user.
  3. 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:

  1. Implement the User class to store the user's information, including their tweets and the users they follow.
  2. Use an unordered_map to store the user ID as the key and the corresponding User object as the value.
  3. Implement the Tweet class to store the tweet's information, including the tweet ID and the timestamp.
  4. Use a deque to store the tweets in the user's timeline, with the most recent tweet at the front.
  5. 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.
  1. 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.
  1. 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.
  1. 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)