Leetcode 355. Design Twitter

Problem

Leetcode 355 - Design Twitter

Example:

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.

Approach

From the given context, postTweet function needs some data structure that could save userId’s post where post consists of arrays

getNewsFeed retrieves 10 most recent tweet. Tweets must be ordered from most recent to least recent, and it should be consisting of user and user followed. Thus we need some other data structure that saves followers per user.

Using all the information given, we can use these:

• Hash Map (userPost): where key is userId and values are array consisting of (time posted, tweetId). This way we can use heap to get 10 most recent
• Integer (time): this is to indicate the time use posts the tweet. We have to decrement the time since in python we can get the most recent using heappop the minimum number
• Hash Map (follower): where key is userId and values are set consisting of followees. This way we don’t have to worry about duplicate follow.

Here is the Python code for the solution:

class Twitter:
    def __init__(self):
        self.userPost = {}
        self.time = 0
        self.follower = {}

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

    def getNewsFeed(self, userId: int) -> List[int]:
        arr = self.userPost.get(userId, []).copy()
        follow = self.follower.get(userId, set())
        
        for f in follow:
            arr += self.userPost.get(f, []).copy()
        
        heapq.heapify(arr)
        posts = []
        for i in range(10):
            if len(arr) == 0:
                return posts
            posts.append(heapq.heappop(arr)[1])
        
        return posts

    def follow(self, followerId: int, followeeId: int) -> None:
        arr = self.follower.get(followerId, set())
        arr.add(followeeId)
        self.follower[followerId] = arr

    def unfollow(self, followerId: int, followeeId: int) -> None:
        arr = self.follower.get(followerId, set())
        if followeeId in arr:
            arr.remove(followeeId)
        self.follower[followerId] = arr

Time Complexity and Space Complexity

Time Complexity:

• $O(1)$ for initializing, postTeet, follow, unfollow
• $O(n log n)$ for getNewsFeed

Space Complexity: $O(N * m + N * M + n)$ where $n$ is the total number of followeeIds associated with the userId, $m$ is the maximum number of tweets by any user (at most 10), $N$ is the total number of userIds and $M$ is the maximum number of followees for any user.