Problem Statement

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.

Additional information

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

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].
• 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].
• 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.

Brute Force (Global Tweet Array)

Intuition

The simplest way to implement this is to mimic a real-world database log. We can store every single tweet from every single user in one giant, global tweets list. Since we always append new tweets to the end of the list, the list acts as a natural timeline, inherently sorted by time.

We can use a Hash Map to track who follows who. When getNewsFeed is called, we just loop backwards through the giant tweets list (starting from the most recent). If a tweet belongs to the user or someone the user follows, we add it to our results until we hit 10 tweets.

Algorithm

1. Initialize: Create a tweets list to store tuples of (userId, tweetId). Create a following dictionary mapping a followerId to a Set of followeeIds.
2. postTweet: Append (userId, tweetId) to self.tweets.
3. follow: Add followeeId to self.following[followerId].
4. unfollow: Remove followeeId from self.following[followerId].
5. getNewsFeed: * Retrieve the Set of people the user follows.
   • Loop backwards through self.tweets.
   • If the tweet's author is the user OR exists in the user's follow Set, append the tweetId to the result list.
   • Break the loop once the result list reaches length 10, and return it.

class Twitter:
    def __init__(self):
        # Global list of all tweets: stores (userId, tweetId)
        self.tweets = []
        # Maps user to a set of users they follow
        self.following = {}

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

    def getNewsFeed(self, userId: int) -> list[int]:
        res = []
        # Ensure the set exists for the user
        follows = self.following.get(userId, set())
        
        # Iterate backwards to get the most recent tweets first
        for i in range(len(self.tweets) - 1, -1, -1):
            author, tweetId = self.tweets[i]
            if author == userId or author in follows:
                res.append(tweetId)
            if len(res) == 10:
                break
        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId not in self.following:
            self.following[followerId] = set()
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.following and followeeId in self.following[followerId]:
            self.following[followerId].remove(followeeId)

Time & Space Complexity

• Time complexity: * postTweet, follow, unfollow: O(1) time.
  • getNewsFeed: O(N) where N is the total number of tweets ever posted globally. In the worst case, we might have to scan the entire history of Twitter to find 10 valid tweets, making it highly inefficient at scale.
• Space complexity: O(N + U) where N is the total number of tweets and U is the number of follow relationships.

Hash Maps & Max-Heap - Optimal

Intuition

Scanning a global list of tweets is too slow. Instead, every user should maintain their own private list of tweets.

When a user asks for their news feed, they are essentially asking to "merge" their own tweet list with the tweet lists of everyone they follow. Since we only want the top 10 most recent tweets across all these lists, this is an exact copy of the classic "Merge K Sorted Lists" problem!

We can use a global count variable as a timestamp. When getNewsFeed is called, we grab the single most recent tweet from the user and from each of their followees, and push them into a Max-Heap. We pop the most recent tweet (the maximum timestamp) from the heap, add it to our feed, and then push the next most recent tweet from that specific author back into the heap. We repeat this up to 10 times.

Algorithm

1. Initialize: Create a count variable initialized to 0. Create a tweetMap (maps userId to a list of [count, tweetId]). Create a followMap (maps userId to a Set of followeeIds).
2. postTweet: Append [self.count, tweetId] to the user's list in tweetMap. Decrement count by 1. (Note: We decrement instead of increment because Python only has Min-Heaps. Making the time negative simulates a Max-Heap!).
3. getNewsFeed:
   • Ensure the user follows themselves so their own tweets appear in the feed.
   • Gather the last index (the most recent tweet) for the user and everyone they follow. Push these [count, tweetId, followeeId, index] into a Min-Heap.
   • Loop while the heap is not empty and len(res) < 10:
     • heappop the top item. Append its tweetId to the results.
     • If that author has more tweets (i.e., index - 1 >= 0), fetch their next most recent tweet and heappush it into the heap.
   • Return results.
4. follow/unfollow: Add/Remove from the Hash Sets in followMap.

class Twitter:
    def __init__(self):
        # Time counter to keep tweets ordered
        self.count = 0
        self.tweetMap = {}  # userId -> list of [count, tweetId]
        self.followMap = {} # userId -> set of followeeIds

    def postTweet(self, userId: int, tweetId: int) -> None:
        if userId not in self.tweetMap:
            self.tweetMap[userId] = []
            
        self.tweetMap[userId].append([self.count, tweetId])
        # Decrement count so more negative numbers = more recent (for Python Min-Heap)
        self.count -= 1

    def getNewsFeed(self, userId: int) -> list[int]:
        res = []
        minHeap = []
        
        if userId not in self.followMap:
            self.followMap[userId] = set()
            
        # Temporarily follow self to include own tweets in the feed
        self.followMap[userId].add(userId)
        
        # Add the single most recent tweet from each followee to the heap
        for followeeId in self.followMap[userId]:
            if followeeId in self.tweetMap and len(self.tweetMap[followeeId]) > 0:
                index = len(self.tweetMap[followeeId]) - 1
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])
                
        # Pop the 10 most recent tweets, pushing older tweets from the same author as we go
        while minHeap and len(res) < 10:
            count, tweetId, followeeId, index = heapq.heappop(minHeap)
            res.append(tweetId)
            
            # If the author has older tweets, push the next one into the heap
            if index >= 0:
                next_count, next_tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [next_count, next_tweetId, followeeId, index - 1])
                
        # Clean up self-follow to prevent issues with strict unfollow tests
        self.followMap[userId].remove(userId)
        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId not in self.followMap:
            self.followMap[followerId] = set()
        self.followMap[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.followMap and followeeId in self.followMap[followerId]:
            self.followMap[followerId].remove(followeeId)

Time & Space Complexity

• Time complexity: * postTweet, follow, unfollow: O(1).
  • getNewsFeed: O(K) to build the initial heap where K is the number of followees. Then O(10 * log K) to pop/push from the heap. Overall time is strictly bounded by the number of people the user follows, completely ignoring the global volume of tweets.
• Space complexity: O(N + U) where N is the total number of tweets and U is the number of follow relationships.