C++ 112ms solution, using HashMap + Lists & Maps, with very detailed comments and explanation


  • 0
    A

    The way I think of the design is the following:

    1. We need to have a "followers" dict, where we maintain the (user, user's followers) (k,v) pairs. This is handy because whenever anyone tweets, we look up his/her followers and update there news feed (details in below). You can regard this as a "listener pattern", if you will. Symmetric for "follow" and "unfollow", so one dict is enough

    2. We also need to keep a dictionary of each user's most recent top 10 tweets. Here, I used a hashmap of STL lists, as we can easily "emplace_front" and "pop_back" at const time (you can also easily implement a circular buffer, e.g. using a vector, if you want).

    3. The key part is to maintain the sequence of all tweets. This is necessary, for example, if one does "follow" and "getNewsFeed", the new "followee" could be some guy who tweets every minute, or someone who never tweets - this has quite different effect on your news feed. So, I "timestamped" each "tweet" using a simple int member, and increment it by one each time a "tweet function" is called. (Note: 2^31-1 is a huge number, which I doubt will overflow. If you are really concerned, use a "string", by all means).

    4. Finally, for each user, we keep a dict of (user, news feed) (k,v) pair using hashmap of BST (stl map). And we define a compare function where the larger the timestamp (int), the more priority it has.

    Hope it helps.

    class Twitter {
    private:
        struct cmp{
            bool operator()(const int& lhs, const int& rhs) const{
                return lhs > rhs;
            }
        };
        unordered_map<int, list<pair<int, int>>> tweets;
        unordered_map<int, map<int, int, cmp>> feeder;
        unordered_map<int, unordered_set<int>> followers;    
        int timeStamp;
        
    public:
        /** Initialize your data structure here. */
        Twitter() {
            timeStamp = 0;
        }
        
        /** Compose a new tweet. */
        void postTweet(int userId, int tweetId) {
            ++timeStamp;    // increment current timestamp
            // add to tweets
            unordered_map<int, list<pair<int, int>>> :: iterator it = tweets.find(userId);
            if (it == tweets.end()){
                tweets[userId] = list<pair<int, int>>({{timeStamp, tweetId}});
            }
            else{
                // here, we only keep the latest 10 tweets to save space
                if (tweets[userId].size() == 10) tweets[userId].pop_back();
                tweets[userId].emplace_front(timeStamp, tweetId);
            }
            // update news feed
            unordered_map<int, unordered_set<int>> :: iterator it2 = followers.find(userId);
            if (it2 == followers.end()){
                followers[userId] = unordered_set<int>({userId});
                unordered_map<int, map<int, int, cmp>> :: iterator iter = feeder.find(userId); 
                if (iter == feeder.end()){
                    feeder[userId] = map<int, int, cmp>({{timeStamp, tweetId}});
                }
                else{
                    feeder[userId].insert({timeStamp, tweetId});
                }
            }
            else {
                unordered_map<int, map<int, int, cmp>> :: iterator iter;            
                for (int follower : followers[userId]){
                    iter = feeder.find(follower);
                    if (iter == feeder.end()){
                        feeder[follower] = map<int, int, cmp>({{timeStamp, tweetId}});
                    }
                    else{
                        feeder[follower].insert({timeStamp, tweetId});
                    }
                }
            }
        }
    
        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        void follow(int followerId, int followeeId) {
            // add to followers dictionary
            unordered_map<int, unordered_set<int>> :: iterator it = followers.find(followeeId);
            if (it == followers.end()){
                followers[followeeId] = unordered_set<int>({followerId, followeeId});
            }
            else followers[followeeId].insert(followerId);
            // load in followee's tweets 
            unordered_map<int, map<int, int, cmp>> :: iterator iter = feeder.find(followerId);
            if (iter == feeder.end()){
                feeder[followerId] = map<int, int, cmp>();
                unordered_map<int, list<pair<int, int>>> :: iterator it = tweets.find(followeeId);
                if (it != tweets.end()){
                    for (pair<int, int> tweet : tweets[followeeId]){
                        feeder[followerId].insert(tweet);
                    }
                }
            }
            else{
                unordered_map<int, list<pair<int, int>>> :: iterator it = tweets.find(followeeId);
                if (it != tweets.end()){
                    for (pair<int, int> tweet : tweets[followeeId]){
                        feeder[followerId].insert(tweet);
                    }
                }            
            }
        }
        
        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        void unfollow(int followerId, int followeeId) {
            // Note: by definition, "unfollow self" is considered invalid action
            if (followerId != followeeId){
                // we do the reverse as in function "follow"
                unordered_map<int, unordered_set<int>> :: iterator it = followers.find(followeeId);
                if (it != followers.end()){
                    followers[followeeId].erase(followerId);
                }
                // load in followee's tweets 
                unordered_map<int, map<int, int, cmp>> :: iterator iter = feeder.find(followerId);
                if (iter != feeder.end()){
                    unordered_map<int, list<pair<int, int>>> :: iterator it = tweets.find(followeeId);
                    if (it != tweets.end()){
                        for (pair<int, int> tweet : tweets[followeeId]){
                            feeder[followerId].erase(tweet.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) {
            // we inorder traverse the top min(sizeofmap, 10) tweets for 'userId'
            unordered_map<int, map<int, int, cmp>> :: iterator iter = feeder.find(userId);
            if (iter == feeder.end()) return vector<int>();
            vector<int> news;
            int n = feeder[userId].size();
            int i = 0;
            for (map<int, int, cmp> :: iterator it = feeder[userId].begin(); it != feeder[userId].end() && i < 10; ++it){
                news.push_back(it->second);
                ++i;
            }
            return news;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.