355. Design Twitter - cocoder39/coco39_LC GitHub Wiki

355. Design Twitter

tips:

  • unordered_map<int, unordered_set<int>> fallowees maps a user to a set of followees he follows
  • unordered_map<int, list<Tweet>> tweets maps a user to a list of Tweets.
  • time_stamp is increased by one when posting a new tweet, together with a max heap to generate the time line
class Cmp {
    public: 
        bool operator()(const Tweet& t1, const Tweet& t2) {
            return t1.time_stamp < t2.time_stamp;
        }
    };
  • a user should follow himself so that he can view his own tweets when feeding him tweets from his followees.
  • it is invalid to unfollow himself
class Twitter {
    class Tweet {
    public:    
        int tweetId;
        int time_stamp;
        Tweet(int id, int t) : tweetId(id), time_stamp(t) {}
    };
    unordered_map<int, unordered_set<int>> fallowees;
    unordered_map<int, list<Tweet>> tweets;
    int cnt;
    
    class Cmp {
    public: 
        bool operator()(const Tweet& t1, const Tweet& t2) {
            return t1.time_stamp < t2.time_stamp;
        }
    };
public:
    /** Initialize your data structure here. */
    Twitter() {
        cnt = 0;
    }
    
    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        if (fallowees.find(userId) == fallowees.end()) {
            fallowees[userId] = unordered_set<int>();
        }
        fallowees[userId].insert(userId);
        
        if (tweets.find(userId) == tweets.end()) {
            tweets[userId] = list<Tweet>();
        }
        tweets[userId].push_back(Tweet(tweetId, cnt++));
    }
    
    /** 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> feeds;
        if (fallowees.find(userId) == fallowees.end()) {
            return feeds;
        }
        priority_queue<Tweet, vector<Tweet>, Cmp> pq;
        for (auto &fallowee : fallowees[userId]) {
            for (auto &feed : tweets[fallowee]) {
                pq.push(feed);
            }
        }
        
        const int num = 10;
        while (! pq.empty() && feeds.size() < num) {
            feeds.push_back(pq.top().tweetId);
            pq.pop();
        }
        return feeds;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        if (fallowees.find(followerId) == fallowees.end()) {
            fallowees[followerId] = unordered_set<int>();
            fallowees[followerId].insert(followerId);
        }
        fallowees[followerId].insert(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        if (followerId == followeeId || fallowees.find(followerId) == fallowees.end()) {
            return;
        }
        auto it = fallowees[followerId].find(followeeId);
        if (it != fallowees[followerId].end()) {
            fallowees[followerId].erase(it);
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️