Leet Code: Problem: 355. Design Twitter

Problem Statement:

Design basic twitter which lets user follow and unfollow other users and show the latest new feed related to the current user and the user followers. Implement the following APIs

void postTweet(int userId, int tweetId):

    Stores the tweetId against the user ID.

void follow(int followerId, int followeeId):

    Marks that follower ID as following followee ID

void unfollow(int followerId, int followeeId):

    Marks that follower ID as unfollowing followee ID

vector<int> getNewsFeed(int userId):

    Returns the set of the latest 10 tweetIDs which include the current user tweetIDs and tweetIDs of the user that the follower if following.

Approach to the problem:

1. First we need to store the user IDs of the people a particular user is following
2. To store that we can use map. To optimize things instead of storing list of followers, it is better to store them in a set for quicker access.
3. So the followers data structure looks like unordered_map<int, unordered_set<int>>
4. Second data structure is to store the tweet ids against the user id.
5. Here the catch to get the latest tweets from the user we have to store a counter along with tweet ID to recognize how latest the tweet is.
6. Larger the count, latest is the tweet ID
7. After that we use priority queue to get the latest tweet IDs among current user and that user id followers.

Solution in C++:

class Twitter {

public:

    /** Initialize your data structure here. */

    Twitter() {

        time = 0;

    }

    /** Compose a new tweet. */

    void postTweet(int userId, int tweetId) {

        ++time;

        tweets[userId].push_back(make_pair(tweetId, time));

    }

    struct comp{

        bool operator()(const pair<int, int> &a, const pair<int, int> &b){

            return a.first < b.first;

        }

    };

    /** Retrieve 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 herself. Tweets must be ordered from most recent to least recent. */

    vector<int> getNewsFeed(int userId) {

        vector<int> res;

        priority_queue<pair<int,int>, vector<pair<int, int>>, comp> pq;

        auto user_tweets = tweets[userId];

        for(auto it = user_tweets.begin(); it != user_tweets.end(); ++it){

            pq.push(make_pair(it->second, it->first));

        }

        auto folowe = followers[userId];

        for(auto it = folowe.begin(); it != folowe.end(); ++it){

            if(*it == userId)

                continue;

            auto user_tweets = tweets[*it];

            for(auto iter = user_tweets.begin(); iter != user_tweets.end(); ++iter){

                pq.push(make_pair(iter->second, iter->first));

            }

        }

        int i = 0;

        while(!pq.empty() && i < 10){

            ++i;

            res.push_back(pq.top().second);

            pq.pop();

        }

        return res;

    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */

    void follow(int followerId, int followeeId) {

        followers[followerId].insert(followeeId);

    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */

    void unfollow(int followerId, int followeeId) {

        followers[followerId].erase(followeeId);

    }

private:

    long long time;

    unordered_map<int, unordered_set<int>> followers;

    unordered_map<int, vector<pair<int, int>>> tweets;

};