Implement a simple twitter. Support the following method:

1. postTweet(user_id, tweet_text) . Post a tweet.
2. getTimeline(user_id) . Get the given user's most recently 10 tweets posted by himself, order by timestamp from most recent to least recent.
3. getNewsFeed(user_id) . Get the given user's most recently 10 tweets in his news feed (posted by his friends and himself). Order by timestamp from most recent to least recent.
4. follow(from_user_id, to_user_id) . from_user_id followed to_user_id.
5. unfollow(from_user_id, to_user_id) . from_user_id unfollowed to to_user_id.

Have you met this question in a real interview?

Yes

Example

postTweet(1, "LintCode is Good!!!")

>
>
 1
getNewsFeed(1)

>
>
 [1]
getTimeline(1)

>
>
 [1]
follow(2, 1)
getNewsFeed(2)

>
>
 [1]
unfollow(2, 1)
getNewsFeed(2)

>
>
 []

/**
 * Definition of Tweet:
 * class Tweet {
 * public:
 *     int id;
 *     int user_id;
 *     String text;
 *     staontic Tweet create(int user_id, string tweet_text) {
 *         // This will create a new tweet object,
 *         // and auto fill id
 *     }
 * }
 */

 class Node{
   public:
   int order;
   Tweet tweet;
   Node(int o, Tweet t):order(o),tweet(t){}

   bool operator < (const Node& node) const {
       return order>node.order;
   }
 };

class MiniTwitter {
private:
    map<int,set<int>> friends;
    map<int,vector<Node>> user_tweets;
    int order;

public:
    MiniTwitter() {
        // initialize your data structure here.
        order=0;
    }

    // @param user_id an integer
    // @param tweet a string
    // return a tweet
    Tweet postTweet(int user_id, string tweet_text) {
        //  Write your code here
        Tweet tweet = Tweet::create(user_id,tweet_text);
        ++order;
        Node node(order,tweet);
        user_tweets[user_id].push_back(node);
        return tweet;
    }

    // @param user_id an integer
    // return a list of 10 new feeds recently
    // and sort by timeline
    vector<Tweet> getNewsFeed(int user_id) {
        // Write your code here
        vector<Tweet> res;
        vector<Node> nodes = getTop10Tweets(user_id);
        if(friends.find(user_id)!=friends.end()){
            for(auto& id:friends[user_id]){
                auto temp = getTop10Tweets(id);
                nodes.insert(nodes.end(),temp.begin(),temp.end());
            }
        }
        sort(nodes.begin(),nodes.end());
        int k = min(static_cast<int>(nodes.size()),10);
        for(int i=0;i<k;++i){
            res.push_back(nodes[i].tweet);
        }
        return res;
    }

    vector<Node> getTop10Tweets(int user_id){
        vector<Node> res;
        if(user_tweets.find(user_id)!=user_tweets.end()){
            auto it = user_tweets[user_id].crbegin();
            int k = min(static_cast<int>(user_tweets[user_id].size()),10);
            for(int i=0;i<k;++i,++it){
                res.push_back(*it);
            }
        }
        return res;
    }

    // @param user_id an integer
    // return a list of 10 new posts recently
    // and sort by timeline
    vector<Tweet>  getTimeline(int user_id) {
        // Write your code here
        vector<Node> temp = getTop10Tweets(user_id);
        vector<Tweet> res;
        for(auto& node:temp)
            res.push_back(node.tweet);
        return res;
    }

    // @param from_user_id an integer
    // @param to_user_id an integer
    // from user_id follows to_user_id
    void follow(int from_user_id, int to_user_id) {
        // Write your code here
        friends[from_user_id].insert(to_user_id);
    }

    // @param from_user_id an integer
    // @param to_user_id an integer
    // from user_id unfollows to_user_id
    void unfollow(int from_user_id, int to_user_id) {
        // Write your code here
        if(friends.find(from_user_id)!=friends.end()){
            if(friends[from_user_id].find(to_user_id)!=friends[from_user_id].end()){
                friends[from_user_id].erase(to_user_id);
            }
        }
    }
};