355. Design TwitterMedium

355. Medium

Design Twitter🔗

MediumHash TableLinked ListDesignHeap (Priority Queue)·Amazon

Implement a simplified version of Twitter which allows users to post tweets, follow/unfollow each other, and view the 10 most recent tweets within their own news feed.

Implement the Twitter class:

Twitter() Initializes your twitter object.
postTweet(userId, tweetId) Publish a new tweet by the user userId.
getNewsFeed(userId) Fetches at most the 10 most recent tweet IDs in the user's feed. Each item must be posted by users who the user followed or by the user themself. ordered from most recent to least recent.
follow(followerId, followeeId) The user with followerId started following the user with followeeId.
unfollow(followerId, followeeId) The user with followerId started unfollowing the user with followeeId.

Constraints:

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10^4
All tweetIds are unique.
At most 3 * 10^4 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

1️⃣

Sorting Approach

🐢

Collect All & Sort

Time O(T log T)Space O(T)

Why do it this way? To generate a user's news feed, the most intuitive approach is to just grab all of the user's own tweets, plus all the tweets of everyone they follow. We dump them all into one giant list, sort the list by timestamp to get the most recent ones first, and return the top 10. It's incredibly simple, but pulling every single tweet just to get the top 10 is very inefficient for active users.

🌐 Real-World Analogy

Reading the Morning Newspaper

Imagine reading the news by ordering every single newspaper published in the entire world over the last decade, sorting them all by date in your living room, and then only reading the front page of the 10 newest ones.

Pseudocode

class Twitter:
    def getNewsFeed(self, userId):
        all_tweets = []
        
        # Add user's own tweets
        all_tweets.extend(self.tweets[userId])
        
        # Add followees' tweets
        for followeeId in self.follow_map[userId]:
            all_tweets.extend(self.tweets[followeeId])
            
        # Sort all by time (descending)
        all_tweets.sort(by=time)
        
        # Return top 10
        return [tweet.id for tweet in all_tweets[:10]]

Users & Tweets DB

Combined Feed (Sorting)

READYPress ▶ or step forward to begin.

✓

—

Executing Code

class Twitter:

    def __init__(self):

        self.time = 0

        self.followMap = defaultdict(set)

        self.tweetMap = defaultdict(list)

    def postTweet(self, userId: int, tweetId: int) -> None:

        self.tweetMap[userId].append((self.time, tweetId))

        self.time += 1

    def getNewsFeed(self, userId: int) -> List[int]:

        feed = self.tweetMap[userId][:]

        for followeeId in self.followMap[userId]:

            feed.extend(self.tweetMap[followeeId])

        feed.sort(key=lambda x: -x[0])

        return [tweetId for _, tweetId in feed[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:

        if followerId != followeeId:

            self.followMap[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:

        self.followMap[followerId].discard(followeeId)

🏆

Optimal Approach — Min-Heap

🔍

Merge K Sorted Lists

Time O(K log F)Space O(F)

Why do it this way? Because tweets for each user are naturally appended chronologically, each user's tweet list is already sorted by time! The problem of getting the 10 most recent tweets across `F` followees is exactly the "Merge K Sorted Lists" problem. We put the single most recent tweet of every followee into a Min-Heap. We pop the most recent one, add it to our feed, and push the next most recent tweet from that same user back into the heap. We only do this 10 times.

🌐 Real-World Analogy

News Anchor Desk

You have 5 reporters in the field. Instead of having them send you their entire life's work, you just ask each reporter for their single newest story. You look at the 5 stories, broadcast the newest one, and then ask that specific reporter for their next newest story. You do this 10 times and you're done.

Pseudocode

class Twitter:
    def getNewsFeed(self, userId):
        minHeap = []
        res = []
        
        # Add the newest tweet from user and followees to heap
        users = self.follow_map[userId] + [userId]
        for u in users:
            if self.tweets[u]:
                newest_tweet = self.tweets[u][-1]
                minHeap.push(newest_tweet)
                
        # Pop the 10 newest tweets overall
        while minHeap and len(res) < 10:
            tweet = minHeap.pop()
            res.append(tweet.id)
            
            # Push the next newest tweet from the SAME user
            if tweet.has_older_tweet():
                minHeap.push(tweet.get_older_tweet())
                
        return res

Users & Tweets DB

Min Heap (Next Tweet Candidates)

Result News Feed

READYPress ▶ or step forward to begin.

✓

—

Executing Code

class Twitter:

    def __init__(self):

        self.count = 0

        self.tweetMap = defaultdict(list)

        self.followMap = defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:

        self.tweetMap[userId].append([self.count, tweetId])

        self.count -= 1

    def getNewsFeed(self, userId: int) -> List[int]:

        res = []

        minHeap = []

        self.followMap[userId].add(userId)

        for followeeId in self.followMap[userId]:

            if followeeId in self.tweetMap:

                index = len(self.tweetMap[followeeId]) - 1

                count, tweetId = self.tweetMap[followeeId][index]

                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

        while minHeap and len(res) < 10:

            count, tweetId, followeeId, index = heapq.heappop(minHeap)

            res.append(tweetId)

            if index >= 0:

                count, tweetId = self.tweetMap[followeeId][index]

                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

        return res

    def follow(self, followerId: int, followeeId: int) -> None:

        self.followMap[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:

        self.followMap[followerId].discard(followeeId)

Discussion

…

Loading comments…

LeetMotion

class Twitter: def getNewsFeed(self, userId): all_tweets = [] # Add user's own tweets all_tweets.extend(self.tweets[userId]) # Add followees' tweets for followeeId in self.follow_map[userId]: all_tweets.extend(self.tweets[followeeId]) # Sort all by time (descending) all_tweets.sort(by=time) # Return top 10 return [tweet.id for tweet in all_tweets[:10]]

class Twitter: def getNewsFeed(self, userId): minHeap = [] res = [] # Add the newest tweet from user and followees to heap users = self.follow_map[userId] + [userId] for u in users: if self.tweets[u]: newest_tweet = self.tweets[u][-1] minHeap.push(newest_tweet) # Pop the 10 newest tweets overall while minHeap and len(res) < 10: tweet = minHeap.pop() res.append(tweet.id) # Push the next newest tweet from the SAME user if tweet.has_older_tweet(): minHeap.push(tweet.get_older_tweet()) return res