Designing Twitter (basic)

this is actually a leetcode problem. 355. but, it is a good lld question.

note: the below discussion is only limited to the above problem description.

Requirements:

each user can follow another user.
each user can unfollow another user.
each user can post tweets.
each user can get news feed where the news feed contains 10 most recent tweets from self or it's followers.

Intuition:

we can maintain a set of followees for every user. whichever users a user follows will go into this set.
if followed, add the followee id to the follower id's followers set.
if unfollowed, remove the followee id from the follower id's followers set.
as there is no requirement to get each user's separate tweets, we can effectively maintain a large list of tweets along with the user ids.
to get the news feed, we will start from the last of the tweets list and check whether the current user follows the tweet owner or not or the tweet is of itself. if yes, we will add it to the news feed. we will do this till we have 10 tweets in the news feed or the tweets list is exhausted.

this works. and also this is accepted. but, we don't necessarily need to iterate over all the tweets right? we can just check only the recent tweets from the followees of the current user and also self. but, we need to get the 10 recent tweets only from the pool of the tweets from all the followees and self. how to do this?

priority queue. we can add pool of tweets from all the followees and self to a priority queue based on the timestamp (yes, we need to maintain timestamp along with the tweets) and if we get the tweets from top of the queue they come based on the timestamp.

approach:

everything is same but, we will maintain timestamp along with the tweets and we need to have a separate set of tweets for each user. we can maintain this in the same way we maintain the set of followees of each user.
to get the news feed for a specific user, we will add the tweets from that user and all the followees into the priority queue and get the top 10.

this is also good. but, should we need to add every tweet of the followees and itself to the priority queue? this isn't required if we have some way which directly points to the most recent tweet among all the followee's tweets. we can maintain a linked list which contains all the tweets.

approach:

instead of maintaining a list of tweets for every user, maintain a single linked list. if a new tweet comes, assign the previous tweet head to this new tweet and make the new tweet as the head.
to get the news feed for a specific user, we will add all the tweet heads and get the one head with recent timestamp. so on and so forth, if still tweets are there, we can update the priority queue again with the next tweet.
simple and brilliant.

Code:

class Tweet {
public:
    int tweetId;
    int timestamp;
    Tweet* nextTweet;
    Tweet (int tweetId, int timestamp) : tweetId(tweetId), timestamp(timestamp), nextTweet(nullptr) {};
    Tweet (int tweetId, int timestamp, Tweet* next) : tweetId(tweetId), timestamp(timestamp), nextTweet(next) {};
};

class Twitter {
    unordered_map<int, unordered_set<int>> followers;    // userId to set of followers
    unordered_map<int, Tweet*> tweets;                   // userId to tweets
    int timestamp;
public:
    Twitter () {
        timestamp = 0;
    }

    void postTweet(int userId, int tweetId) {
        Tweet* tweet = new Tweet(tweetId, timestamp++);
        // if user has no tweets yet
        if (!tweets.count(userId)) {
            tweets[userId] = tweet;
        // attach the previous tweets to current 
        // and make it as new head
        } else {
            tweet->nextTweet = tweets[userId];
            tweets[userId] = tweet;
        }
    }

    vector<int> getNewsFeed(int userId) {
        auto cmp = [](const Tweet* a, const Tweet* b) {
            return b->timestamp > a->timestamp;
        };

        priority_queue<Tweet*, vector<Tweet*>, decltype(cmp)> pq(cmp);
        // every user is follower to himself
        // this is a notion created because we need the personal tweets also coming in the user's news feed
        followers[userId].insert(userId);

        // push all the followers tweet heads into the pq
        for (auto followeeId : followers[userId]) {
            if (tweets.count(followeeId)) {
                pq.push(tweets[followeeId]);
            }
        }

        vector<int> newsFeed;
        while (newsFeed.size() < 10 && !pq.empty()) {
            Tweet* tweetHead = pq.top();    pq.pop();
            // take the most recent one
            newsFeed.push_back(tweetHead->tweetId);
            // if the user has still some more tweets, push back the new head
            if (tweetHead->nextTweet) {
                Tweet* tweet = tweetHead->nextTweet;
                pq.push(tweet);
            }
        }

        return newsFeed;
    }

    void follow(int followerId, int followeeId) {
        followers[followerId].insert(followeeId);
    }
    
    void unfollow(int followerId, int followeeId) {
        followers[followerId].erase(followeeId);
    }
};

good luck!