Approach
- PostTweet(): It takes two arguments, USERID, and TWEETID. It adds the pair of USERID and TWEETID into a vector. Now the tweet is available to view to the followers of this user.
- getNewsFeed(): It takes a single argument USERID and returns ten latest tweets for that user. The tweets are returned from the users whom this user follows. If there are less than 10 tweets available then we return them. We iterate from the end of the array and get the 10 most latest tweets of the user if available. Iterating from the end of the array guarantees that, we get the latest tweets. Simultaneously, we check if the user follows that user or not. If yes, then we add that tweet to the newsfeed else we continue.
- Follow(): It takes two arguments, FOLLOWERID and FOLLOWEEID, and makes the user with FOLLOWERID a follower of the user with FOLLOWEEID. Asymptotically, It takes constant time as we are inserting the follower in the map.
- UnFollow(): It takes two arguments, FOLLOWERID and FOLLOWEEID. Now the follower does not follow the followee. Now, we delete the FOLLOWERID from the unordered set of the FOLLOWEEID. Asymptotically, it takes constant time.
Program
#include <unordered_map>
#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;
class Twitter
{
private:
// Required data structures.
unordered_map<int, unordered_set<int> > following;
vector<pair<int, int> > tweets;
public:
// Constructor for initialising data structures.
Twitter()
{
following.clear();
tweets.clear();
}
// Function to compose a new tweet.
bool postTweet(int userId, int tweetId)
{
tweets.push_back({userId, tweetId});
return true;
}
/*
Function to retrieve the ten most recent tweet ids in the user's news feed.
Each item in the news feed must be posted by users.
followed or by the user themself. Tweets must be ordered from most.
recent to least recent.
*/
vector<int> getNewsFeed(int userId)
{
vector<int> ans;
for (int i = tweets.size() - 1; i >= 0 && ans.size() < 10; i--)
{
if (tweets[i].first == userId)
{
ans.push_back(tweets[i].second);
}
else
{
if (following.find(userId) != following.end())
{
if (following[userId].find(tweets[i].first) != following[userId].end())
{
ans.push_back(tweets[i].second);
}
}
}
}
return ans;
}
// Follower follows a followee.
bool follow(int followerId, int followeeId)
{
// If the follower already follows the followee, return false.
if (following[followerId].count(followeeId)) {
return false;
}
// Otherwise, follow and return true.
following[followerId].insert(followeeId);
return true;
}
// Follower unfollows a followee.
bool unfollow(int followerId, int followeeId)
{
// If follower already unfollows the followee, return false.
if (following[followerId].count(followeeId) == 0) {
return false;
}
// Otherwise, unfollow and return true.
following[followerId].erase(followeeId);
return true;
}
};
int main()
{
Twitter *twitter = new Twitter();
bool tweetPosted = false, followed = false, unfollowed = false;
vector<int> tweets;
tweetPosted = twitter->postTweet(1, 124);
cout << (tweetPosted ? "Success" : "Failure") << ": postTweet\n";
tweetPosted = twitter->postTweet(1, 23);
cout << (tweetPosted ? "Success" : "Failure") << ": postTweet\n";
tweetPosted = twitter->postTweet(1, 85);
cout << (tweetPosted ? "Success" : "Failure") << ": postTweet\n";
tweetPosted = twitter->postTweet(3, 769);
cout << (tweetPosted ? "Success" : "Failure") << ": postTweet\n";
tweets = twitter->getNewsFeed(1);
cout << (!tweets.empty() ? "Success" : "Failure") << ": getNewsFeed\n";
for (int i = 0; i < tweets.size(); i++)
{
cout << tweets[i] << " ";
}
cout << '\n';
followed = twitter->follow(1, 2);
cout << (followed ? "Success" : "Failure") << ": follow\n";
followed = twitter->follow(2, 3);
cout << (followed ? "Success" : "Failure") << ": follow\n";
tweetPosted = twitter->postTweet(2, 96);
cout << (tweetPosted ? "Success" : "Failure") << ": postTweet\n";
tweets = twitter->getNewsFeed(1);
cout << (!tweets.empty() ? "Success" : "Failure") << ": getNewsFeed\n";
for (int i = 0; i < tweets.size(); i++)
{
cout << tweets[i] << " ";
}
cout << '\n';
unfollowed = twitter->unfollow(1, 2);
cout << (unfollowed ? "Success" : "Failure") << ": unfollow\n";
unfollowed = twitter->unfollow(1, 3);
cout << (unfollowed ? "Success" : "Failure") << ": unfollow\n";
tweets = twitter->getNewsFeed(2);
cout << (!tweets.empty() ? "Success" : "Failure") << ": getNewsFeed\n";
for (int i = 0; i < tweets.size(); i++)
{
cout << tweets[i] << " ";
}
cout << '\n';
return 0;
}
You can also try this code with Online C++ Compiler
Output
Success: postTweet
Success: postTweet
Success: postTweet
Success: postTweet
Success: getNewsFeed
85 23 124
Success: follow
Success: follow
Success: postTweet
Success: getNewsFeed
96 85 23 124
Success: unfollow
Failure: unfollow
Success: getNewsFeed
96 769
Time Complexity
- getNewsFeed(): O(N), where ‘N’ is the total number of tweets. We iterate through the array of tweets to find the 10 most latest tweets for the user from his followees. In the worst case, we iterate through the entire array.
- follow(): O(1).As it just adds an entry to the unordered map. Asymptotically, an unordered map takes constant time for insertion.
- unfollow(): O(1).As it just deleted an entry from the unordered map. Asymptotically, an unordered map takes constant time for deletion.
- postTweet(): O(1). It adds a pair of USERID and TWEETID to the end of the vector. Asymptotically, adding an entry to the back of the array takes constant time.
Space Complexity
O(max(N, U)), where ‘N’ is the number of tweets and ‘U’ is the number of users.
We are adding every ‘TWEET_ID’ and ‘USER_ID’ in the tweets array. So it takes space equal to the number of tweets. Also, we are maintaining a map to store information about the followers of a user. So the overall space complexity is the maximum number of tweets and number of users.
Key Takeaways
In this blog, we discussed an exciting application, namely Design Twitter. We designed our own simplified version of Twitter in C++ where we implemented the functions like post tweet, follow a user, unfollow a user and get news feed. These functions are implemented based on the facilities offered by the actual Twitter. It was an application of Object-Oriented Programming and System Design.
Stay tuned for more such problems. To become a systems expert, please head over to Coding Ninjas Studio and practice more such exciting problems.
85+ registered