In Simple Words: - Post tweet: prepend (timestamp, tweetId) to user's tweet list. - Follow/unfollow: update user's followee Set. - Get news feed: Merge K sorted lists using Max-Heap of the 10 most recent tweets from followees and self. - Time...

Q70: Design Twitter. - DSA Patterns (Multi-Lang)

In Simple Words:

Post tweet: prepend (timestamp, tweetId) to user's tweet list.
Follow/unfollow: update user's followee Set.
Get news feed: Merge K sorted lists using Max-Heap of the 10 most recent tweets from followees and self.
Time: Post/Follow: $O(1)$, NewsFeed: $O(K \log U)$ | Space: $O(U + T)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

from collections import defaultdict
import heapq

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweet_map = defaultdict(list)  # userId -> list of [time, tweetId]
        self.follow_map = defaultdict(set)  # userId -> set of followeeIds

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time -= 1
        self.tweet_map[userId].append([self.time, tweetId])

    def getNewsFeed(self, userId: int) -> list[int]:
        res = []
        min_heap = []
        self.follow_map[userId].add(userId)
        for followee in self.follow_map[userId]:
            if followee in self.tweet_map:
                idx = len(self.tweet_map[followee]) - 1
                count, tweetId = self.tweet_map[followee][idx]
                min_heap.append([count, tweetId, followee, idx - 1])
        heapq.heapify(min_heap)
        while min_heap and len(res) < 10:
            count, tweetId, followee, idx = heapq.heappop(min_heap)
            res.append(tweetId)
            if idx >= 0:
                count, tweetId = self.tweet_map[followee][idx]
                heapq.heappush(min_heap, [count, tweetId, followee, idx - 1])
        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        self.follow_map[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follow_map[followerId].discard(followeeId)