1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106 | struct Tweet {
int id;
int time;
Tweet* next = nullptr;
Tweet(int id, int time) : id(id), time(time) {}
};
struct User {
int id;
unordered_set<int> followeeIds;
Tweet* tweetHead = nullptr;
User() {}
User(int id) : id(id) {
follow(id);
}
void follow(int followeeId) {
followeeIds.insert(followeeId);
}
void unfollow(int followeeId) {
followeeIds.erase(followeeId);
}
void post(int tweetId, int time) {
Tweet* oldTweetHead = tweetHead;
tweetHead = new Tweet(tweetId, time);
tweetHead->next = oldTweetHead;
}
};
class Twitter {
public:
/** Compose a new tweet. */
void postTweet(int userId, int tweetId) {
if (!users.count(userId))
users[userId] = User(userId);
users[userId].post(tweetId, time++);
}
/**
* 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) {
if (!users.count(userId))
return {};
vector<int> newsFeed;
auto compare = [](const Tweet* a, const Tweet* b) {
return a->time < b->time;
};
priority_queue<Tweet*, vector<Tweet*>, decltype(compare)> maxHeap(compare);
for (const int followeeId : users[userId].followeeIds) {
Tweet* tweetHead = users[followeeId].tweetHead;
if (tweetHead != nullptr)
maxHeap.push(tweetHead);
}
int count = 0;
while (!maxHeap.empty() && count++ < 10) {
Tweet* tweet = maxHeap.top();
maxHeap.pop();
newsFeed.push_back(tweet->id);
if (tweet->next)
maxHeap.push(tweet->next);
}
return newsFeed;
}
/**
* Follower follows a followee.
* If the operation is invalid, it should be a no-op.
*/
void follow(int followerId, int followeeId) {
if (followerId == followeeId)
return;
if (!users.count(followerId))
users[followerId] = User(followerId);
if (!users.count(followeeId))
users[followeeId] = User(followeeId);
users[followerId].follow(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)
return;
if (const auto it = users.find(followerId);
it != users.cend() && users.count(followeeId))
it->second.unfollow(followeeId);
}
private:
int time = 0;
unordered_map<int, User> users; // {userId: User}
};
|