Krammer's blog

https://leetcode.com/problems/design-twitter/ from Amazon

Solutions:

1. Search all tweets

 1class Twitter {
 2public:
 3    vector<pair<int, int>> tweets;
 4    unordered_map<int, unordered_set<int>> followers;
 5    Twitter() {
 6    }
 7    
 8    void postTweet(int userId, int tweetId) {
 9        tweets.push_back({userId, tweetId});
10    }
11    
12    vector<int> getNewsFeed(int userId) {
13        int N = tweets.size();
14        vector<int> ret;
15        for (int i=N-1; i>=0 and ret.size()<10; i--) {
16            int ownerId = tweets[i].first;
17            if (ownerId == userId or followers[userId].count(ownerId)) {
18                ret.push_back(tweets[i].second);
19            }
20        }
21        return ret;
22    }
23    
24    void follow(int followerId, int followeeId) {
25        followers[followerId].insert(followeeId);
26    }
27    
28    void unfollow(int followerId, int followeeId) {
29        followers[followerId].erase(followeeId);
30    }
31};

Time complexity: O(N) when getNewsFeed. Space complexity: O(N).

2. Search followers only

In the above approach, we search all tweets when getNewsFeed gets called. If we don’t follow many users, then we might go through the whole tweets and can’t find 10 tweets, and thus the worst case time complexity is O(N).

We can just search all of our followers for the feed. In this way, assume that we have average K followers, then the time complexity of getNewsFeed becomes O(KlogK). We use a priority queue to get the latest tweet from K followers first, and then pop the latest tweets, then move on from the follower with the latest tweet.

 1class Twitter {
 2public:
 3    int time;
 4    unordered_map<int, vector<pair<int, int>>> tweets;
 5    unordered_map<int, unordered_set<int>> followers;
 6    Twitter() {
 7        time = 0;
 8    }
 9    
10    void postTweet(int userId, int tweetId) {
11        tweets[userId].push_back({time++, tweetId});
12    }
13    
14    vector<int> getNewsFeed(int userId) {
15        vector<int> ret;
16        followers[userId].insert(userId);
17        priority_queue<vector<int>> pq;
18        for (auto f : followers[userId]) {
19            if (tweets[f].size()) {
20                int index = tweets[f].size() - 1;
21                pq.push({tweets[f][index].first, f, index});
22            }
23        }
24        while (pq.size() and ret.size() < 10) {
25            auto v = pq.top(); pq.pop();
26            int uId = v[1], index = v[2];
27            ret.push_back(tweets[uId][index].second);
28            if (index) {
29                pq.push({tweets[uId][index-1].first, uId, index-1});
30            }
31        }
32        return ret;
33    }
34    
35    void follow(int followerId, int followeeId) {
36        followers[followerId].insert(followeeId);
37    }
38    
39    void unfollow(int followerId, int followeeId) {
40        followers[followerId].erase(followeeId);
41    }
42};

Time complexity: O(KlogK) for getNewsFeed. Space complexity: O(N).

Editorial: LeetCode 355 Design Twitter

1. Search all tweets

2. Search followers only