{"id":6381,"date":"2020-02-29T17:14:15","date_gmt":"2020-03-01T01:14:15","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6381"},"modified":"2020-02-29T17:16:40","modified_gmt":"2020-03-01T01:16:40","slug":"leetcode-1348-tweet-counts-per-frequency","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1348-tweet-counts-per-frequency\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1348. Tweet Counts Per Frequency"},"content":{"rendered":"\n<p>Implement the class&nbsp;<code>TweetCounts<\/code>&nbsp;that supports two methods:<\/p>\n\n\n\n<p>1.<code>&nbsp;recordTweet(string tweetName, int time)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Stores the&nbsp;<code>tweetName<\/code>&nbsp;at the recorded&nbsp;<code>time<\/code>&nbsp;(in&nbsp;<strong>seconds<\/strong>).<\/li><\/ul>\n\n\n\n<p>2.<code>&nbsp;getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Returns the total number of occurrences for the given&nbsp;<code>tweetName<\/code>&nbsp;per&nbsp;<strong>minute<\/strong>,&nbsp;<strong>hour<\/strong>, or&nbsp;<strong>day<\/strong>&nbsp;(depending on&nbsp;<code>freq<\/code>) starting from the&nbsp;<code>startTime<\/code>&nbsp;(in&nbsp;<strong>seconds<\/strong>) and ending at the&nbsp;<code>endTime<\/code>&nbsp;(in&nbsp;<strong>seconds<\/strong>).<\/li><li><code>freq<\/code>&nbsp;is always&nbsp;<strong>minute<\/strong><em>,&nbsp;<\/em><strong>hour<\/strong><em>&nbsp;or&nbsp;<strong>day<\/strong><\/em>, representing the time interval to get the total number of occurrences for the given&nbsp;<code>tweetName<\/code>.<\/li><li>The first time interval always starts from the&nbsp;<code>startTime<\/code>, so the time intervals are&nbsp;<code>[startTime, startTime + delta*1&gt;, &nbsp;[startTime + delta*1, startTime + delta*2&gt;, [startTime + delta*2, startTime + delta*3&gt;, ... , [startTime + delta*i,&nbsp;<strong>min<\/strong>(startTime + delta*(i+1), endTime + 1)&gt;<\/code>&nbsp;for some non-negative number&nbsp;<code>i<\/code>&nbsp;and&nbsp;<code>delta<\/code>&nbsp;(which depends on&nbsp;<code>freq<\/code>).&nbsp;&nbsp;<\/li><\/ul>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"TweetCounts\",\"recordTweet\",\"recordTweet\",\"recordTweet\",\"getTweetCountsPerFrequency\",\"getTweetCountsPerFrequency\",\"recordTweet\",\"getTweetCountsPerFrequency\"]\n[[],[\"tweet3\",0],[\"tweet3\",60],[\"tweet3\",10],[\"minute\",\"tweet3\",0,59],[\"minute\",\"tweet3\",0,60],[\"tweet3\",120],[\"hour\",\"tweet3\",0,210]]\n\n<strong>Output<\/strong>\n[null,null,null,null,[2]\n[2,1],null,[4]]\n\n<strong>Explanation<\/strong>\nTweetCounts tweetCounts = new TweetCounts();\ntweetCounts.recordTweet(\"tweet3\", 0);\ntweetCounts.recordTweet(\"tweet3\", 60);\ntweetCounts.recordTweet(\"tweet3\", 10);                             \/\/ All tweets correspond to \"tweet3\" with recorded times at 0, 10 and 60.\ntweetCounts.getTweetCountsPerFrequency(\"minute\", \"tweet3\", 0, 59); \/\/ return [2]. The frequency is per minute (60 seconds), so there is one interval of time: 1) [0, 60&gt; - &gt; 2 tweets.\ntweetCounts.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&gt; - &gt; 2 tweets, and 2) [60,61&gt; - &gt; 1 tweet.\ntweetCounts.recordTweet(\"tweet3\", 120);                            \/\/ All tweets correspond to \"tweet3\" with recorded times at 0, 10, 60 and 120.\ntweetCounts.getTweetCountsPerFrequency(\"hour\", \"tweet3\", 0, 210);  \/\/ return [4]. The frequency is per hour (3600 seconds), so there is one interval of time: 1) [0, 211&gt; - &gt; 4 tweets.\n<\/p>\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>There will be at most\u00a0<code>10000<\/code>\u00a0operations considering both\u00a0<code>recordTweet<\/code>\u00a0and\u00a0<code>getTweetCountsPerFrequency<\/code>.<\/li><li><code>0 &lt;= time, startTime, endTime &lt;=\u00a010^9<\/code><br><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Hashtable + binary search<\/strong><\/h2>\n\n\n\n<p>Time complexity: <br>Record: O(logn)<br>getCount: O(logn + |entries|)<\/p>\n\n\n\n<p>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass TweetCounts {\npublic:\n  TweetCounts() {\n    m_.clear();\n  }\n\n  void recordTweet(string tweetName, int time) {\n    m_[tweetName].insert(time);\n  }\n\n  vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {\n    auto tit = m_.find(tweetName);\n    if (tit == m_.end()) return {};\n    const set<int>& s = tit->second;\n    int delta = 1;\n    if (freq == \"minute\") delta = 60;\n    else if (freq == \"hour\") delta = 60 * 60;\n    else if (freq == \"day\") delta = 60 * 60 * 24;\n    int slots = (endTime - startTime + delta - 1) \/ delta;\n    vector<int> ans(slots);\n    for (int i = startTime; i <= endTime; i += delta) {\n      auto it1 = s.lower_bound(i);\n      auto it2 = s.lower_bound(min(i + delta, endTime + 1));\n      ans.push_back(distance(it1, it2)); \/\/ O(|entries|)    \n    }\n    return ans;\n  }\nprivate:\n  unordered_map<string, set<int>> m_;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Implement the class&nbsp;TweetCounts&nbsp;that supports two methods: 1.&nbsp;recordTweet(string tweetName, int time) Stores the&nbsp;tweetName&nbsp;at the recorded&nbsp;time&nbsp;(in&nbsp;seconds). 2.&nbsp;getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) Returns the total&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,82,128,177,15],"class_list":["post-6381","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-hashtable","tag-interval","tag-medium","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6381","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6381"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6381\/revisions"}],"predecessor-version":[{"id":6383,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6381\/revisions\/6383"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6381"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6381"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}