LeetCode Solutions Blog

Design Twitter

Number: 355

Difficulty: Medium

Paid? No

Problem Description

Design a simplified version of Twitter that supports posting tweets, following/unfollowing other users, and retrieving the 10 most recent tweet IDs in a user's news feed. The news feed should include tweets posted by the user themself and by users they follow, ordered from most recent to least recent.

Key Insights

Use a global timestamp to order tweets as they are posted.
Maintain a mapping of each user to the list of tweets they posted.
Maintain a mapping of each user to the set of users they follow.
For getNewsFeed, merge tweets from the user and their followees using a heap to efficiently retrieve the 10 most recent tweets.
Ensure that a user always follows themself to simplify retrieving their own tweets.

Space and Time Complexity

Time Complexity:

postTweet: O(1)
follow / unfollow: O(1)
getNewsFeed: O(N log K) where N is the number of followees and K is the average number of tweets considered (capped at 10 tweets per merge iteration) Space Complexity:
O(U + T) where U is the number of users (for follow mappings) and T is the total number of tweets stored.

Solution

We use two main data structures: a hash table to store tweets for each user and another hash table for follow relationships. Each tweet is stored as a tuple of (timestamp, tweetId). A global timestamp counter provides a unique ordering. A min-heap (or max-heap using negative timestamp values) is used to merge the tweets from different users efficiently. When retrieving the news feed, we look up the tweet lists for the given user's followees (including self) and use the heap to extract the 10 most recent tweets.

Code Solutions

# Python implementation of the Twitter design problem
import heapq

class Twitter:
    def __init__(self):
        # Mapping from userId to a set of followeeIds
        self.follows = {}
        # Mapping from userId to list of (timestamp, tweetId)
        self.tweets = {}
        # Global timestamp to order tweets
        self.timestamp = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        # Ensure the user follows itself for easier news feed retrieval
        if userId not in self.follows:
            self.follows[userId] = set()
        self.follows[userId].add(userId)
        
        # Append the tweet with the current timestamp, then increment timestamp
        if userId not in self.tweets:
            self.tweets[userId] = []
        self.tweets[userId].append((self.timestamp, tweetId))
        self.timestamp += 1
        
    def getNewsFeed(self, userId: int) -> list:
        # If the user does not exist in follows mapping, return empty feed
        if userId not in self.follows:
            return []
        
        # Use a heap (as a max-heap using negative timestamp)
        heap = []
        # Iterate over all followees of the user
        for followeeId in self.follows[userId]:
            if followeeId in self.tweets and self.tweets[followeeId]:
                # Start from the most recent tweet of the followee
                index = len(self.tweets[followeeId]) - 1
                ts, tid = self.tweets[followeeId][index]
                # Push the tweet along with followeeId and the index of the tweet in the list
                heapq.heappush(heap, (-ts, tid, followeeId, index))
        
        result = []
        # Retrieve up to 10 tweets
        while heap and len(result) < 10:
            neg_ts, tweetId, followeeId, idx = heapq.heappop(heap)
            result.append(tweetId)
            # If there is an older tweet from this followee, push it onto the heap
            if idx - 1 >= 0:
                ts, tid = self.tweets[followeeId][idx - 1]
                heapq.heappush(heap, (-ts, tid, followeeId, idx - 1))
        return result

    def follow(self, followerId: int, followeeId: int) -> None:
        # A user should always follow itself
        if followerId not in self.follows:
            self.follows[followerId] = set()
        self.follows[followerId].add(followerId)
        # Add followeeId to follower's follow set if not self-follow
        if followerId != followeeId:
            self.follows[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        # A user cannot unfollow itself
        if followerId in self.follows and followeeId != followerId:
            self.follows[followerId].discard(followeeId)