Design Twitter

Design Twitter

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

Implement the Twitter class:

• Twitter(): Initializes the Twitter object.
• postTweet(userId, tweetId): Composes a new tweet with ID tweetId by the user userId. Each call to this function will have a unique tweetId.
• getNewsFeed(userId): Retrieves the 10 most recent tweet IDs in the user's news feed. Each item must be posted by users the user follows or by the user themselves. Tweets should be ordered from most recent to least recent.
• follow(followerId, followeeId): The user with ID followerId starts following the user with ID followeeId.
• unfollow(followerId, followeeId): The user with ID followerId stops following the user with ID followeeId.

Examples

Example 1:

Input:
  twitter = Twitter()
  twitter.postTweet(1, 5)     // User 1 posts tweet 5
  twitter.getNewsFeed(1)      // returns [5]
  twitter.follow(1, 2)        // User 1 follows user 2
  twitter.postTweet(2, 6)     // User 2 posts tweet 6
  twitter.getNewsFeed(1)      // returns [6, 5]
  twitter.unfollow(1, 2)      // User 1 unfollows user 2
  twitter.getNewsFeed(1)      // returns [5]

Constraints

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

Expected Complexity

• Time: O(k log k) for getNewsFeed where k is the number of followed users; O(1) for other operations
• Space: O(N) where N is total number of tweets and follow relationships