LeetCode Solutions Blog

Design Twitter

Difficulty: Medium

Problem Description

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

Key Insights

Each tweet must be linked to a user and has a unique ID.
Users can follow and unfollow other users.
A user's news feed should include tweets from users they follow, as well as their own tweets.
The news feed must display tweets in reverse chronological order (most recent first).

Space and Time Complexity

Time Complexity:

postTweet: O(1)
getNewsFeed: O(N log N) where N is the number of tweets to retrieve (up to 10).
follow/unfollow: O(1)

Space Complexity: O(U + T) where U is the number of users and T is the number of tweets.

Solution

To solve the problem, we will use the following data structures:

A hash table (dictionary) to store tweets for each user, where the key is the user ID and the value is a list of tweet IDs.
A hash table to maintain the follow relationship, where the key is the follower ID and the value is a set of followee IDs.

When a user posts a tweet, we append the tweet ID to their list of tweets. To retrieve a user's news feed, we collect tweets from the user and all users they follow, sorting them to get the 10 most recent tweets. Following and unfollowing users will update the follow relationship in constant time.

Code Solutions

class Twitter:
    def __init__(self):
        self.tweets = {}  # userId -> list of tweetIds
        self.following = {}  # followerId -> set of followeeIds
        self.time = 0  # to keep track of the order of tweets

    def postTweet(self, userId: int, tweetId: int) -> None:
        if userId not in self.tweets:
            self.tweets[userId] = []
        self.tweets[userId].append((self.time, tweetId))  # store time with tweetId
        self.time += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        tweets_to_show = []
        # Get tweets from the user and their followees
        if userId in self.tweets:
            tweets_to_show.extend(self.tweets[userId])
        if userId in self.following:
            for followee in self.following[userId]:
                if followee in self.tweets:
                    tweets_to_show.extend(self.tweets[followee])
        
        # Sort tweets by time and get the most recent 10
        tweets_to_show.sort(reverse=True, key=lambda x: x[0])
        return [tweetId for _, tweetId in tweets_to_show[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId not in self.following:
            self.following[followerId] = set()
        self.following[followerId].add(followeeId)

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