Design Twitter

Problem Statement

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.

Users and tweets are uniquely identified by their IDs (integers).

Implement the following methods:

• Twitter() Initializes the twitter object.
• void postTweet(int userId, int tweetId) Publish a new tweet with ID tweetId by the user userId. You may assume that each tweetId is unique.
• List<Integer> getNewsFeed(int userId) Fetches at most the 10 most recent tweet IDs in the user’s news feed. Each item must be posted by users who the user is following or by the user themself. Tweets IDs should be ordered from most recent to least recent.
• void follow(int followerId, int followeeId) The user with ID followerId follows the user with ID followeeId.
• void unfollow(int followerId, int followeeId) The user with ID followerId unfollows the user with ID followeeId.

Example 1:

Input:
["Twitter", "postTweet", [1, 10], "postTweet", [2, 20], "getNewsFeed", [1], "getNewsFeed", [2], "follow", [1, 2], "getNewsFeed", [1], "getNewsFeed", [2], "unfollow", [1, 2], "getNewsFeed", [1]]

Output:
[null, null, null, [10], [20], null, [20, 10], [20], null, [10]]

Explanation:
Twitter twitter = new Twitter();
twitter.postTweet(1, 10); // User 1 posts a new tweet with id = 10.
twitter.postTweet(2, 20); // User 2 posts a new tweet with id = 20.
twitter.getNewsFeed(1);   // User 1's news feed should only contain their own tweets -> [10].
twitter.getNewsFeed(2);   // User 2's news feed should only contain their own tweets -> [20].
twitter.follow(1, 2);     // User 1 follows user 2.
twitter.getNewsFeed(1);   // User 1's news feed should contain both tweets from user 1 and user 2 -> [20, 10].
twitter.getNewsFeed(2);   // User 2's news feed should still only contain their own tweets -> [20].
twitter.unfollow(1, 2);   // User 1 follows user 2.
twitter.getNewsFeed(1);   // User 1's news feed should only contain their own tweets -> [10].

Constraints:

• 1 <= userId, followerId, followeeId <= 100
• 0 <= tweetId <= 1000

You should aim for a solution with O(nlogn) time for each getNewsFeed() function call, O(1) time for the remaining methods, and O((N * m) + (N * M) + n) space, where n is the number of followeeIds associated with the userId, m is the maximum number of tweets by any user, N is the total number of userIds, and M is the maximum number of followees for any user.

Recommended Time and Space Complexity

You should aim for a solution with O(n \log n) time for each get_news_feed() function call, O(1) time for the remaining methods, and O((N * m) + (N * M) + n) space, where n is the number of followee_ids associated with the user_id, m is the maximum number of tweets by any user, N is the total number of user_ids, and M is the maximum number of followees for any user.

Hint 1

Can you think of a data structure to store all the information, such as user_ids and corresponding followee_ids, or user_ids and their tweets? Maybe you should think of a hash data structure in terms of key-value pairs. Also, can you think of a way to determine that a tweet was posted before another tweet?

Hint 2

We use a hash map follow_map to store user_ids and their unique followee_ids as a hash set. Another hash map, tweet_map, stores user_ids and their tweets as a list of (count, tweet_id) pairs. A counter count, incremented with each tweet, tracks the order of tweets. The variable count is helpful in distinguishing the time of tweets from two users. This way of storing data makes the functions follow(), unfollow(), and post_tweet() run in O(1). Can you think of a way to implement get_news_feed()? Maybe consider a brute force approach and try to optimize it.

Hint 3

A naive solution would involve taking the tweets of the user_id and its followee_ids into a list, sorting them in descending order based on their count values, and returning the top 10 tweets as the most recent ones. Can you think of a more efficient approach that avoids collecting all tweets and sorting? Perhaps consider a data structure and leverage the fact that each user’s individual tweets list is already sorted.

Hint 4

We can use a Max-Heap to efficiently retrieve the top 10 most recent tweets. For each followee and the user_id, we insert their most recent tweet from the tweet_map into the heap, along with the tweet’s count and its index in the tweet list. This index is necessary because after processing a tweet, we can insert the next most recent tweet from the same user’s list. By always pushing and popping tweets from the heap, we ensure that the 10 most recent tweets are retrieved without sorting all tweets.

Solution

Sorting

from collections import defaultdict

class Twitter:

    def __init__(self):
        self.time = 0
        self.follow_map = defaultdict(set)
        self.tweet_map = defaultdict(list)

    def post_tweet(self, user_id: int, tweet_id: int) -> None:
        self.tweet_map[user_id].append((self.time, tweet_id))
        self.time += 1

    def get_news_feed(self, user_id: int) -> list[int]:
        feed = self.tweet_map[user_id][:]
        for followee_id in self.follow_map[user_id]:
            feed.extend(self.tweet_map[followee_id])

        feed.sort(key=lambda x: -x[0])
        return [tweet_id for _, tweet_id in feed[:10]]

    def follow(self, follower_id: int, followee_id: int) -> None:
        if follower_id != followee_id:
            self.follow_map[follower_id].add(followee_id)

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

Time complexity: O(n * m + t \log t) for each get_news_feed() call and O(1) for remaining methods. Space complexity: O(N * m + N * M)