Implement the class TweetCounts
that supports two methods:
1. recordTweet(string tweetName, int time)
- Stores the
tweetName
at the recordedtime
(in seconds).
2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)
- Returns the total number of occurrences for the given
tweetName
per minute, hour, or day (depending onfreq
) starting from thestartTime
(in seconds) and ending at theendTime
(in seconds). freq
is always minute, hour or day, representing the time interval to get the total number of occurrences for the giventweetName
.- The first time interval always starts from the
startTime
, so the time intervals are[startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)>
for some non-negative numberi
anddelta
(which depends onfreq
).
Example:
Input ["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"] [[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]] Output [null,null,null,null,[2] [2,1],null,[4]] Explanation TweetCounts tweetCounts = new TweetCounts(); tweetCounts.recordTweet("tweet3", 0); tweetCounts.recordTweet("tweet3", 60); tweetCounts.recordTweet("tweet3", 10); // All tweets correspond to "tweet3" with recorded times at 0, 10 and 60. tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]. The frequency is per minute (60 seconds), so there is one interval of time: 1) [0, 60> - > 2 tweets. tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2, 1]. The frequency is per minute (60 seconds), so there are two intervals of time: 1) [0, 60> - > 2 tweets, and 2) [60,61> - > 1 tweet. tweetCounts.recordTweet("tweet3", 120); // All tweets correspond to "tweet3" with recorded times at 0, 10, 60 and 120. tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210); // return [4]. The frequency is per hour (3600 seconds), so there is one interval of time: 1) [0, 211> - > 4 tweets.
Constraints:
- There will be at most
10000
operations considering bothrecordTweet
andgetTweetCountsPerFrequency
. 0 <= time, startTime, endTime <= 10^9
Solution: Hashtable + binary search
Time complexity:
Record: O(logn)
getCount: O(logn + |entries|)
Space complexity: O(n)
C++
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 |
// Author: Huahua class TweetCounts { public: TweetCounts() { m_.clear(); } void recordTweet(string tweetName, int time) { m_[tweetName].insert(time); } vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) { auto tit = m_.find(tweetName); if (tit == m_.end()) return {}; const set<int>& s = tit->second; int delta = 1; if (freq == "minute") delta = 60; else if (freq == "hour") delta = 60 * 60; else if (freq == "day") delta = 60 * 60 * 24; int slots = (endTime - startTime + delta - 1) / delta; vector<int> ans(slots); for (int i = startTime; i <= endTime; i += delta) { auto it1 = s.lower_bound(i); auto it2 = s.lower_bound(min(i + delta, endTime + 1)); ans.push_back(distance(it1, it2)); // O(|entries|) } return ans; } private: unordered_map<string, set<int>> m_; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment