LeetCode Design Twitter
Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:
- postTweet(userId, tweetId): Compose a new tweet.
- getNewsFeed(userId): 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.
- follow(followerId, followeeId): Follower follows a followee.
- unfollow(followerId, followeeId): Follower unfollows a followee.
Twitter twitter = new Twitter(); // User 1 posts a new tweet (id = 5). twitter.postTweet(1, 5); // User 1's news feed should return a list with 1 tweet id -> [5]. twitter.getNewsFeed(1); // User 1 follows user 2. twitter.follow(1, 2); // User 2 posts a new tweet (id = 6). twitter.postTweet(2, 6); // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. // Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5. twitter.getNewsFeed(1); // User 1 unfollows user 2. twitter.unfollow(1, 2); // User 1's news feed should return a list with 1 tweet id -> [5], // since user 1 is no longer following user 2. twitter.getNewsFeed(1);
设计一个Twitter系统，实现三个接口，postTweet发文，follow某人，unfollow某人，getNewsFeed从自己以及follow的人中取出最近发表的三篇推文，按时间从近到远排序。比较麻烦的是getNewsFeed函数的实现。 先来个暴力版本，用unordered_map<int, unordered_set<int>>保存某个人follow的所有人，这样follow和unfollow的操作都可以在O(1)实现。 用vector<Tweet>保存所有推文，而且是最新postTweet的推文都push_back到末尾，所以该容器保存了全局从远到近的所有推文。那么getNewsFeed时，直接从容器末尾往前遍历所有推文，判断该推文是否是自己或者自己follow的用户发表的，如果是，则收集起来，直到收集到10篇推文。 思路和实现都非常简单，代码如下： [cpp] class Twitter { private: struct Tweet { int userId; int tweetId; Tweet(int u, int t) :userId(u), tweetId(t) {}; }; vector<Tweet> Tweets; unordered_map<int, unordered_set<int>> following; public: /** Initialize your data structure here. */ Twitter() { } /** Compose a new tweet. */ void postTweet(int userId, int tweetId) { Tweets.push_back({ userId,tweetId }); } /** 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> ans; for (int i = Tweets.size() – 1; i >= 0; –i) { int &uid = Tweets[i].userId; if (uid == userId || following[userId].find(uid) != following[userId].end()) { ans.push_back(Tweets[i].tweetId); if (ans.size() == 10)break; } } return ans; } /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ void follow(int followerId, int followeeId) { following[followerId].insert(followeeId); } /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ void unfollow(int followerId, int followeeId) { following[followerId].erase(followeeId); } }; [/cpp] 本代码提交AC，用时143MS。 上面的版本比较慢，主要是每次getNewsFeed时都要遍历全局所有的推文。讨论区有一种做法是把每个人发表的推文也保存到一个unordered_map<int, vector<Tweet>>中，那么在getNewsFeed时，只需要拿出自己或自己follow的用户发表的推文，放到一个优先队列中，优先队列自动按时间先后顺序排序了，从优先队列中取出10条推文即可。 为了按时间排序，需要一个全局时间戳，并且重载优先队列的比较运算符。 代码如下： [cpp] class Twitter { private: int timestamp; struct Tweet { int tweetId; int timestamp; Tweet(int tid, int ts) :tweetId(tid), timestamp(ts) {}; bool operator<(const Tweet& t)const { return timestamp < t.timestamp; } }; unordered_map<int, vector<Tweet>> Tweets; unordered_map<int, unordered_set<int>> following; public: /** Initialize your data structure here. */ Twitter() :timestamp(0) { } /** Compose a new tweet. */ void postTweet(int userId, int tweetId) { Tweets[userId].push_back({ tweetId,timestamp++ }); } /** 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) { priority_queue<Tweet> pq; for (const auto& uid : following[userId]) { for (const auto& t : Tweets[uid]) { pq.push(t); } } for (const auto& t : Tweets[userId]) { pq.push(t); } vector<int> ans; while (!pq.empty() && ans.size() < 10) { ans.push_back(pq.top().tweetId); pq.pop(); } return ans; } /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ void follow(int followerId, int followeeId) { if (followerId != followeeId)following[followerId].insert(followeeId); // map中不考虑自己follow自己，因为getNewsFeed单独考虑了 } /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ void unfollow(int followerId, int followeeId) { following[followerId].erase(followeeId); } }; [/cpp] 本代码提交AC，用时33MS，快了好几倍！]]>