algoadvance

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 the given tweetId by the user with the given userId. Each call to this method will result in 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 themselves. Tweets must be ordered from most recent to least recent.
• void follow(int followerId, int followeeId): The user with the user ID followerId starts following the user with the user ID followeeId.
• void unfollow(int followerId, int followeeId): The user with the user ID followerId stops following the user with the user ID followeeId.

Clarifying Questions

1. Unique User IDs: Are user IDs guaranteed to be unique?
   • Yes, user IDs will be unique.
2. Tweets Limit: Is there a limit on the number of tweets a single user can post?
   • No, there is no explicit limit on the number of tweets.
3. Initial Followers: Are users following anyone when the system is initialized?
   • No, initially, users are not following anyone (except themselves, which we need to handle).
4. Operations Frequency: Which operations among posting a tweet, getting the news feed, and following/unfollowing are expected to be most frequent?
   • Typically, getting the news feed and posting tweets are expected to be the most frequent operations.

Strategy

• Data Structures:
  • Use a dictionary to keep track of users’ tweets: {userId: [List of tweets (with timestamp)]}.
  • Use a dictionary to keep track of users’ followers: {userId: {Set of followeeId}}.
  • Maintain a global timestamp to ensure each tweet’s order.
• Operations:
  • postTweet: Append the tweet with a timestamp to the user’s tweet list.
  • getNewsFeed:
    • Gather all tweets from the user and the users they follow.
    • Sort these tweets by timestamp (most recent) and return the top 10 tweet IDs.
  • follow: Add the followee to the follower’s followee set.
  • unfollow: Remove the followee from the follower’s followee set.

Code

Here’s the implementation:

class Twitter:

    def __init__(self):
        self.timestamp = 0
        self.user_tweets = {}  # {userId: [(tweetId, timestamp), ...]}
        self.user_follows = {} # {userId: {followeeId}}
        
    def postTweet(self, userId: int, tweetId: int) -> None:
        if userId not in self.user_tweets:
            self.user_tweets[userId] = []
        self.user_tweets[userId].append((tweetId, self.timestamp))
        self.timestamp += 1
        
    def getNewsFeed(self, userId: int) -> List[int]:
        import heapq
        
        tweets = []
        if userId in self.user_tweets:
            tweets.extend(self.user_ttweets[userId])
        if userId in self.user_follows:
            for followeeId in self.user_follows[userId]:
                if followeeId in self.user_tweets:
                    tweets.extend(self.user_tweets[followeeId])
        
        # Get the 10 most recent tweets using heaps
        most_recent_tweets = heapq.nlargest(10, tweets, key=lambda x: x[1])
        
        return [tweetId for tweetId, _ in most_recent_tweets]
    
    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId not in self.user_follows:
            self.user_follows[followerId] = set()
        self.user_follows[followerId].add(followeeId)
    
    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.user_follows:
            self.user_follows[followerId].discard(followeeId)

Time Complexity

• postTweet: O(1) - Append operation on a list is O(1).
• getNewsFeed: O(n log k) - n is the total number of tweets from the user and their followees, k is 10 (the number of tweets we want to return).
• follow: O(1) - Adding to a set is O(1).
• unfollow: O(1) - Removing from a set is O(1).

This design ensures efficient handling of frequent operations, leveraging dictionaries and heaps for optimal performance.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?