// Time: O(klogu), k is most recently number of tweets, // u is the number of the user's following. // Space: O(t + f), t is the total number of tweets, // f is the total number of followings. /** * Definition of Tweet: * class Tweet { * public: * int id; * int user_id; * String text; * static Tweet create(int user_id, string tweet_text) { * // This will create a new tweet object, * // and auto fill id * } * } */ class MiniTwitter { public: MiniTwitter() : time_(0) { } // @param user_id an integer // @param tweet a string // return a tweet Tweet postTweet(int user_id, string tweet_text) { const auto& tweet = Tweet::create(user_id, tweet_text); messages_[user_id].emplace_back(make_pair(++time_, tweet)); return tweet; } // @param user_id an integer // return a list of 10 new feeds recently // and sort by timeline vector getNewsFeed(int user_id) { using RIT = deque>::reverse_iterator; priority_queue> heap; if (messages_[user_id].size()) { heap.emplace(make_tuple(messages_[user_id].rbegin()->first, messages_[user_id].rbegin(), messages_[user_id].rend())); } for (const auto& id : followings_[user_id]) { if (messages_[id].size()) { heap.emplace(make_tuple(messages_[id].rbegin()->first, messages_[id].rbegin(), messages_[id].rend())); } } vector res; while (!heap.empty() && res.size() < number_of_most_recent_tweets_) { const auto& top = heap.top(); size_t t; RIT begin, end; tie(t, begin, end) = top; heap.pop(); auto next = begin + 1; if (next != end) { heap.emplace(make_tuple(next->first, next, end)); } res.emplace_back(begin->second); } return res; } // @param user_id an integer // return a list of 10 new posts recently // and sort by timeline vector getTimeline(int user_id) { vector res; for (auto it = messages_[user_id].rbegin(); it != messages_[user_id].rend() && res.size() < number_of_most_recent_tweets_; ++it) { res.emplace_back(it->second); } return res; } // @param from_user_id an integer // @param to_user_id an integer // from user_id follows to_user_id void follow(int from_user_id, int to_user_id) { if (from_user_id != to_user_id && !followings_[from_user_id].count(to_user_id)) { followings_[from_user_id].emplace(to_user_id); } } // @param from_user_id an integer // @param to_user_id an integer // from user_id unfollows to_user_id void unfollow(int from_user_id, int to_user_id) { if (followings_[from_user_id].count(to_user_id)) { followings_[from_user_id].erase(to_user_id); } } private: const size_t number_of_most_recent_tweets_ = 10; unordered_map> followings_; unordered_map>> messages_; size_t time_; };

Problem