- Define the priority key and whether the smallest or largest item should lead.
- Push each candidate when it becomes eligible.
- Discard stale entries when necessary and process the best live candidate.
Code notes
- 106 lines of C++ from the credited upstream file 355.cpp.
- The implementation visibly relies on sequence storage, hash lookup, work queue.
- 2 loop blocks detected.
Complexity
Count heap pushes and pops; each normally contributes a logarithmic factor in the heap size.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1struct Tweet {2 int id;3 int time;4 Tweet* next = nullptr;5};6 7struct User {8 int id;9 unordered_set<int> followeeIds;10 Tweet* tweetHead = nullptr;11 12 User() {}13 14 User(int id) : id(id) {15 follow(id);16 }17 18 void follow(int followeeId) {19 followeeIds.insert(followeeId);20 }21 22 void unfollow(int followeeId) {23 followeeIds.erase(followeeId);24 }25 26 void post(int tweetId, int time) {27 Tweet* oldTweetHead = tweetHead;28 tweetHead = new Tweet(tweetId, time);29 tweetHead->next = oldTweetHead;30 }31};32 33class Twitter {34 public:35 36 void postTweet(int userId, int tweetId) {37 if (!users.contains(userId))38 users[userId] = User(userId);39 users[userId].post(tweetId, time++);40 }41 42 /**43 * Retrieve the 10 most recent tweet ids in the user's news feed. Each item in44 * the news feed must be posted by users who the user followed or by the user45 * herself. Tweets must be ordered from most recent to least recent.46 */47 vector<int> getNewsFeed(int userId) {48 if (!users.contains(userId))49 return {};50 51 vector<int> newsFeed;52 53 auto compare = [](const Tweet* a, const Tweet* b) {54 return a->time < b->time;55 };56 priority_queue<Tweet*, vector<Tweet*>, decltype(compare)> maxHeap(compare);57 58 for (const int followeeId : users[userId].followeeIds) {59 Tweet* tweetHead = users[followeeId].tweetHead;60 if (tweetHead != nullptr)61 maxHeap.push(tweetHead);62 }63 64 int count = 0;65 while (!maxHeap.empty() && count++ < 10) {66 Tweet* tweet = maxHeap.top();67 maxHeap.pop();68 newsFeed.push_back(tweet->id);69 if (tweet->next)70 maxHeap.push(tweet->next);71 }72 73 return newsFeed;74 }75 76 /**77 * Follower follows a followee.78 * If the operation is invalid, it should be a no-op.79 */80 void follow(int followerId, int followeeId) {81 if (followerId == followeeId)82 return;83 if (!users.contains(followerId))84 users[followerId] = User(followerId);85 if (!users.contains(followeeId))86 users[followeeId] = User(followeeId);87 users[followerId].follow(followeeId);88 }89 90 /**91 * Follower unfollows a followee.92 * If the operation is invalid, it should be a no-op.93 */94 void unfollow(int followerId, int followeeId) {95 if (followerId == followeeId)96 return;97 if (const auto it = users.find(followerId);98 it != users.cend() && users.contains(followeeId))99 it->second.unfollow(followeeId);100 }101 102 private:103 int time = 0;104 unordered_map<int, User> users; 105};106