题目描述
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.
Example:
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(userId, tweetId)
: 创建一条新的推文
getNewsFeed(userId)
: 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
follow(followerId, followeeId)
: 关注一个用户
unfollow(followerId, followeeId)
: 取消关注一个用户
算法1
(堆)
题解:首先我们建立一个用户的结构体,属性包括用户id
,他关注的所有人(用set表示),他发的所有推特(使用pair数组表示,pair<全局推特UUID,tweetId>)我们使用全局UUID来为了获得最近的十条推特。再使用一个哈希表来记录userId
到user
信息的映射。
postTweet
:我们只需要在对应的用户的推特列表末尾将推特插入就可以了,因为没有涉及到删除,所以我们推特列表中的推特肯定是越在末尾越新的。
follow
和unfollow
:只需要在对应的用户关注的人集合中插入或者删除即可,注意一下不合法的情况。如关注自己或者取关一个没有关注的人。
getNewsFeed
:这是最难设计与实现的一个方法了。首先我们需要获得当前用户自己以及关注的所有的人的userId
和对应的每个人发了多少条推特,这两个数组我们分别用f
和g
数组来表示。我们现在需要利用发推特的时候我们的一个特点,每个人发的所有推特都是越在末尾越新的。因此,我们可以使用类似合并K
个有序链表的方法,依次选出每个人最后一条推特放入大顶堆,然后堆顶元素就是最新的推特,我们将堆顶推特删除,并加入这个人的上一条推特,直至选到10条或者堆为空(关注的所有人加在一起没有发到10条)。
C++ 代码
class Twitter {
public:
int uuid = 0;
struct user
{
int id;
unordered_set<int> follow;
vector<pair<int,int>> tweets;
user(){}
};
unordered_map<int,user> hash;
/** Initialize your data structure here. */
Twitter() {
}
/** Compose a new tweet. */
void postTweet(int userId, int tweetId) {
hash[userId].tweets.push_back(make_pair(uuid ++,tweetId));
hash[userId].id = 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. */
vector<int> getNewsFeed(int userId) {
int n = hash[userId].follow.size(),i = 0,cnt = 0;
vector<int> res;
vector<int> f(n + 1),g(n + 1);
f[0] = userId,g[0] = hash[userId].tweets.size() - 1;
for(auto it : hash[userId].follow)
f[i + 1] = it,g[++ i] = hash[it].tweets.size() - 1;
priority_queue<pair<int,int>> q;
for(int i = 0 ; i <= n ; i ++)
if(g[i] >= 0) q.push(make_pair(hash[f[i]].tweets[g[i]].first,i));
while(cnt < 10 && !q.empty())
{
int cur = q.top().second;
q.pop();
res.push_back(hash[f[cur]].tweets[g[cur]].second);
g[cur] --;
if(g[cur] >= 0)
q.push(make_pair(hash[f[cur]].tweets[g[cur]].first,cur));
cnt ++;
}
return res;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
void follow(int followerId, int followeeId) {
if(followerId != followeeId)
hash[followerId].follow.insert(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
void unfollow(int followerId, int followeeId) {
if(hash[followerId].follow.find(followeeId) != hash[followerId].follow.end())
hash[followerId].follow.erase(followeeId);
}
};