501. Design Twitter

典型的一道看似很复杂，静下来钻进去看，就发现有思路的题目。

考察数据结构的运用，以及要定义一个新的node节点。

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?  

Example

Example 1:

Input:
  postTweet(1, "LintCode is Good!!!")
  getNewsFeed(1)
  getTimeline(1)
  follow(2, 1)
  getNewsFeed(2)
  unfollow(2, 1)
  getNewsFeed(2)
Output:
  1
  [1]
  [1]
  [1]
  []

Example 2:

Input:
  postTweet(1, "LintCode is Good!!!")
  getNewsFeed(1)
  getTimeline(1)
  follow(2, 1)
  postTweet(1, "LintCode is best!!!")
  getNewsFeed(2)
  unfollow(2, 1)
  getNewsFeed(2)
Output:
  1
  [1]
  [1]
  2
  [2,1]
  []

/**
 * Definition of Tweet:
 * class Tweet {
 * public:
 *     int id;
 *     int user_id;
 *     String text;
 *     static Tweet create(int user_id, string tweet_text) {
 *         // This will create a new tweet object,
 *         // and auto fill id
 *     }
 * }
 */
//缺少了时间信息，所以要定义一个node，加入时间信息。
struct node{
    int order; 
    Tweet tw; 
    node(int order, Tweet tw){
        this->order = order; 
        this->tw = tw; 
    }
    
    bool operator<(const node &o) const
    {
        return order > o.order;
    }
    
}; 

    //static const bool cmp(const node *n1, const node *n2){
    //    return n1->order > n2->order; 
    //} 这里没起作用，不知道为什么

class MiniTwitter {
private:
    unordered_map<int, unordered_set<int>> friends; 
    unordered_map<int, vector<node*>> userToTws;
    int order; 
public:

    MiniTwitter() {
        // do intialization if necessary
        order = 0; 
        friends.clear();
        userToTws.clear(); 
    }

    /*
     * @param user_id: An integer
     * @param tweet_text: a string
     * @return: a tweet
     */
     Tweet postTweet(int user_id, string &tweet_text) {
        // write your code here
        Tweet tw = Tweet::create(user_id, tweet_text); 
        node *nd = new node(order, tw); 
        userToTws[user_id].push_back(nd); 
        return tw; 
    }

    /*
     * @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
        // K路归并算法
        vector<Tweet> res; 
        vector<node*> nodes = getRecent10(user_id); 
        unordered_set<int> friendsId = friends[user_id];
        for(auto i : friendsId){
            nodes = merge2(nodes, getRecent10(i)); 
        }
        for(int i = 0; i < 10 && i < nodes.size(); i++){
                res.push_back(nodes[i]->tw); 
        }
        return res; 
    }
    
    
    vector<node*> merge2(vector<node*> v1, vector<node*> v2){
        vector<node *> res; 
        int len1 = v1.size();
        int len2 = v2.size(); 
        int i = 0, j = 0;
        int cnt = 0; 
        while(i < len1 && j < len2){
            if(v1[i]->order > v2[j]->order){
                res.push_back(v1[i]); 
                i++; 
            }
            else{
                res.push_back(v2[j]);
                j++; 
            }
            if(++cnt == 10){
                return res; 
            }
        }
        while(i < len1){
            res.push_back(v1[i++]); 
            if(++cnt == 10){
                return res; 
            }
        }
        while(j < len2){
            res.push_back(v2[j++]); 
            if(++cnt == 10){
                return res; 
            }
        }
        return res; 
    }
    
   vector<node*> getRecent10(int user_id) {
        // write your code here
        vector<node*> res;
        if(userToTws[user_id].size() > 0){
            vector<node*> nodes = userToTws[user_id]; 
            //sort(nodes.begin(), nodes.end(), cmp); 
            sort(nodes.begin(), nodes.end()); 
            for(int i = 0; i < 10 && i < nodes.size(); i++){
                res.push_back(nodes[i]); 
            }
        }
        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<Tweet> res;
        if(userToTws[user_id].size() > 0){
            vector<node*> nodes = userToTws[user_id]; 
            //sort(nodes.begin(), nodes.end(), cmp); 
            sort(nodes.begin(), nodes.end());
            for(int i = 0; i < 10 && i < nodes.size(); i++){
                res.push_back(nodes[i]->tw); 
            }
        }
        return res; 
    }

    /*
     * @param from_user_id: An integer
     * @param to_user_id: An integer
     * @return: nothing
     */
    void follow(int from_user_id, int to_user_id) {
        // write your code here
        //if(friends.find(from_user_id) != friends.end()){
            friends[from_user_id].insert(to_user_id); 
        //}
        return; 
    }

    /*
     * @param from_user_id: An integer
     * @param to_user_id: An integer
     * @return: nothing
     */
    void unfollow(int from_user_id, int to_user_id) {
        // write your code here
         if(friends.find(from_user_id) != friends.end()){
            friends[from_user_id].erase(to_user_id); 
        }
        return; 
    }
};