Share my 70ms C++ code with "PULL" method.(dealing time-stamp with the idea in merge sort...)


  • 0

    There are two kind of ideas dealing with this problem:

    1. PUSH: Every user maintain a news pool of all his followings' tweets. Whenever a user post a tweet, push this tweet to all his followers.
    2. PULL: Every user maintain a tweets pool of all his OWN tweet.

    I implement the PULL method.But I wonder anyone implement the PUSH method....

    class Twitter {
    public:
        Twitter() {
            users.clear();
            tweetCounter=0;
        }
        void postTweet(int userId, int tweetId) {
            checkUserExist(userId);
            users[userId]->tweets.push_front(pair<int,int>(tweetId,tweetCounter++));
        }
        vector<int> getNewsFeed(int userId) {
            vector<int> res;
            if(users.find(userId)==users.end())
                return res;
            unordered_set<int> &following=users[userId]->following;
            list<pair<int,int>>::iterator tweets_its[following.size()];
            list<pair<int,int>> *tweets[following.size()];
            int pos=0;
            //init
            for(unordered_set<int>::iterator it=following.begin();it!=following.end();++it,++pos){
                tweets[pos]=&(users[*it]->tweets);
                tweets_its[pos]=tweets[pos]->begin();
            }
            //get most 10 recent tweet
            for(int i=0;i<10;++i){
                int mRecentIndex=-1;
                int mRecentTime=INT_MIN;
                for(int j=0;j<following.size();++j){
                    if(tweets_its[j]!=tweets[j]->end()){
                        if((tweets_its[j])->second>mRecentTime){
                            mRecentIndex=j;
                            mRecentTime=(tweets_its[j])->second;
                        }
                    }
                }
                if(mRecentIndex==-1)
                    break;
                else{
                    res.push_back(tweets_its[mRecentIndex]->first);
                    ++(tweets_its[mRecentIndex]);
                }
            }
            return res;
        }
        void follow(int followerId, int followeeId) {
            checkUserExist(followerId);
            checkUserExist(followeeId);
            users[followerId]->following.insert(followeeId);
        }
        void unfollow(int followerId, int followeeId) {
            if(followeeId==followerId)
                return;
            checkUserExist(followerId);
            checkUserExist(followeeId);
            users[followerId]->following.erase(followeeId);
        }
    private:
        void checkUserExist(int userId){
            if(users.find(userId)==users.end()){
                users[userId]=new User();
                this->follow(userId,userId);
            }
        }
        int tweetCounter;
        struct User{
            //  pair<int,int>: tweetID,counterVal
            list<pair<int,int>> tweets;
            unordered_set<int> following;
            User(){};
        };
        unordered_map<int,User*> users;
    };
    

Log in to reply
 

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