355.Desgin_Twitter(Medium).md

355. Design Twitter (Medium)

Date and Time: Aug 29, 2024, 22:34 (EST)

Link: https://leetcode.com/problems/design-twitter/

Question:

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

Implement the Twitter class:

• Twitter() Initializes your twitter object.

• void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.

• List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.

• void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.

• void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

Example 1:

Input:
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]

Output:
[null, null, [5], null, null, [6, 5], null, [5]]

Explanation: Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).
twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5]. return [5]
twitter.follow(1, 2); // User 1 follows user 2.
twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).
twitter.getNewsFeed(1); // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede > tweet id 5 because it is posted after tweet id 5.
twitter.unfollow(1, 2); // User 1 unfollows user 2.
twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

Constraints:

• 1 <= userId, followerId, followeeId <= 500

• 0 <= tweetId <= 10^4

• All the tweets have unique IDs.

• At most 3 * 10^4 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

Walk-through:

__init__():

1. we need count to store the priority for each tweet.
2. we need a tweetsMap to store all the tweetId associate with userId, a defaultdict(list) is the best option.
3. we need a followersMap to store all the followeeId associate with followerId, but if we also use defaultdict(list), it will take $O(n)$ time to remove a followeeId, a better way is to use defaultdict(set), which takes only $O(1)$ time to remove followeeId because of the hashcode().

postTweet(): Just saves the tweetId into the tweetsMap associated with the userId. We store [self.count, tweetId] into the tweetsMap, then we decrement the self.count by 1, so we can maintain the maxHeap.

getNewsFeed(): We create a maxHeap and res[] to store the tweetId. We can start by adding all followeeId from followersMap into maxHeap, don't forget to add the userId into the followersMap first. Remember to check if a followeeId has tweet in tweetsMap.

We can create index = len(tweetsMap[followeeId]) - 1 to find the latest tweet the followeeId created.

By accessing the index at tweetsMap, we can find the count, tweetId, then we append [count, tweetId, followeeId, index-1] into maxHeap. So we can go back to followeeId to check other tweets if its index >= 0

We then use a while loop for maxHeap to add tweetId to res until 10 tweets are met or all tweets are added. We can get count, tweetId, followeeId, index by popping maxHeap, then we add tweetId into res[], and we can use followeeId and index (if index >= 0) to get new count, tweetId from the same followeeId but just index-1 so we can access the next latest tweet. Then we heappush(minHeap, [count, tweetId, followeeId, index-1]) again into maxHeap.

follow: Add followeeId into followersMap assiociated with followerId.

unfollow: Remove followeeId from followersMap assiociated with followerId in $O(1)$. But we have to first check if followeeId in self.followersMap[followerId].

Python Solution:

class Twitter:

    def __init__(self):
        self.count = 0
        self.tweetsMap = defaultdict(list)  # userId -> list of [count, tweetIds]
        self.followersMap = collections.defaultdict(set)   # userId -> set of followeeId

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

    def getNewsFeed(self, userId: int) -> List[int]:
        res, maxHeap = [], []
        self.followersMap[userId].add(userId)
        for followeeId in self.followersMap[userId]:
            if followeeId in self.tweetsMap:
                index = len(self.tweetsMap[followeeId]) - 1
                count, tweetId = self.tweetsMap[followeeId][index]
                heapq.heappush(maxHeap, [count, tweetId, followeeId, index-1])
        while maxHeap and len(res) < 10:
            count, tweetId, followeeId, index = heapq.heappop(maxHeap)
            res.append(tweetId)
            if index >= 0:
                count, tweetId = self.tweetsMap[followeeId][index]
                heapq.heappush(maxHeap, [count, tweetId, followeeId, index-1])
        return res

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

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.followersMap[followerId]:
            self.followersMap[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)

Time Complexity: $O(nlog\ m)$, n is the total users, m is the total tweets. Because $O(n)$ to add into set, we use maxHeap to heappush, heappop m tweets.
Space Complexity: $O(n + m)$

Java Solution:

C++ Solution:

Runtime and Memory comparison

Language	Runtime	Memory
Python3	ms	MB
Java	ms	MB
C++	ms	MB