Design Twitter
Problem Description
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 IDtweetIdby the useruserId. Each call to this function will be made with a uniquetweetId.List<Integer> getNewsFeed(int userId)Retrieves the10most 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 IDfollowerIdstarted following the user with IDfolloweeId.void unfollow(int followerId, int followeeId)The user with IDfollowerIdstarted unfollowing the user with IDfolloweeId.
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
Constraints:
1 <= userId, followerId, followeeId <= 500- 0 <= tweetId <= 104
- All the tweets have unique IDs.
- At most
3 * 104calls will be made topostTweet,getNewsFeed,follow, andunfollow. - A user cannot follow himself.
Solve it on LeetCode
Approaches
1. Naive Approach
Intuition:
This naive approach involves maintaining three main data structures:
- Map of Tweets: A HashMap to store all tweets for each user.
- Follow Graph: A HashMap to store follow relationships.
- Global Tweet List: A list of all tweets in the order they were posted.
Using these data structures, we can retrieve the latest tweets for any user by filtering the global tweet list according to the follow relationships.
Code:
- Time Complexity:
- Posting a tweet: O(1).
- Getting the news feed: O(n) where n is the number of tweets (limited to the recent ones, i.e., last 10).
- Follow and unfollow: O(1).
- Space Complexity: O(u + t) where u is the number of users and t is the number of tweets.
2. Optimized Approach using Min-Heap
Intuition:
To improve the retrieval of the latest tweets for a user, we utilize a Min-Heap to efficiently manage the fetching of the top 10 most recent tweets. We maintain similar data structures for storing tweets and follow relationships, but enhance the retrieval by using the current timestamp to prioritize recent tweets.
Code:
- Time Complexity:
- Posting a tweet: O(1).
- Getting the news feed: O(n log 10) where n is the number of tweets by followers but it is limited to 10 recent tweets.
- Follow and unfollow: O(1).
- Space Complexity: O(u + t) where u is the number of users and t is the number of tweets. The additional overhead is due to the priority queue holding at most 10 elements.