A social media company is trying to monitor activity on their site by analyzing the number of tweets that occur in select periods of time. These periods can be partitioned into smaller time chunks based on a certain frequency (every minute, hour, or day).

For example, the period [10, 10000] (in seconds) would be partitioned into the following time chunks with these frequencies:


	Every minute (60-second chunks): [10,69], [70,129], [130,189], ..., [9970,10000]
	Every hour (3600-second chunks): [10,3609], [3610,7209], [7210,10000]
	Every day (86400-second chunks): [10,10000]


Notice that the last chunk may be shorter than the specified frequency's chunk size and will always end with the end time of the period (10000 in the above example).

Design and implement an API to help the company with their analysis.

Implement the TweetCounts class:


	TweetCounts() Initializes the TweetCounts object.
	void recordTweet(String tweetName, int time) Stores the tweetName at the recorded time (in seconds).
	List&lt;Integer&gt; getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) Returns a list of integers representing the number of tweets with tweetName in each time chunk for the given period of time [startTime, endTime] (in seconds) and frequency freq.
	
		freq is one of "minute", "hour", or "day" representing a frequency of every minute, hour, or day respectively.
	
	


&nbsp;
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);                              // New tweet "tweet3" at time 0
tweetCounts.recordTweet("tweet3", 60);                             // New tweet "tweet3" at time 60
tweetCounts.recordTweet("tweet3", 10);                             // New tweet "tweet3" at time 10
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]; chunk [0,59] had 2 tweets
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2,1]; chunk [0,59] had 2 tweets, chunk [60,60] had 1 tweet
tweetCounts.recordTweet("tweet3", 120);                            // New tweet "tweet3" at time 120
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // return [4]; chunk [0,210] had 4 tweets


&nbsp;
Constraints:


	0 &lt;= time, startTime, endTime &lt;= 109
	0 &lt;= endTime - startTime &lt;= 104
	There will be at most 104 calls in total to recordTweet and getTweetCountsPerFrequency.


import bisect
class TweetCounts:

    def __init__(self):
        self.tweets = {}
        

    def recordTweet(self, tweetName: str, time: int) -> None:
        if not tweetName in self.tweets:
            self.tweets[tweetName] = []
        index = bisect.bisect_left(self.tweets[tweetName], time)
        self.tweets[tweetName].insert(index, time)
        
    
    def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
        
        def find(step):
            nonlocal tweet
            result = []
            for i in range(startTime, endTime+1, step):
                result.append(bisect.bisect_right(tweet, min(endTime, i + step - 1)) - bisect.bisect_left(tweet, i))
            return result
                
                
        tweet = self.tweets[tweetName]
        if freq == "minute":
            return find(60)
        elif freq == "hour":
            return find(3600)
        else:
            return find(86400)
class TweetCounts {
    Map<String, List<Integer>> map;
    public TweetCounts() {
        map = new HashMap<>();
    }

    public void recordTweet(String tweetName, int time) {
        map.computeIfAbsent(tweetName, v->new ArrayList<>()).add(time);
    }

    public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
        List<Integer> res = new ArrayList<>();
        if(map.containsKey(tweetName)) {
            Collections.sort(map.get(tweetName));
            while(startTime<=endTime) {
                int interval = Freq.valueOf(freq).getVal();
                int end = Math.min(startTime+interval-1, endTime); // need this to handle the last interval
                res.add(getFreq(map.get(tweetName), startTime, end));
                startTime=end+1; // ex: for minute, the interval is 60 so our end is 59. The next startTime is end+1
            }
        }
        return res;
    }

    public int getFreq(List<Integer> list, int start, int end) {
        int st = Collections.binarySearch(list, start);
        if(st<0) {
            st = (st+1)*-1; // our exact start time might not be in the list, to get the 1st timestamp greater than start
        }
        int en = Collections.binarySearch(list, end);
        if(en<0) {
            en = (en+2)*-1; // our exact end time might not be in the list, to get the last timestamp just smaller than end
        }

        return en-st+1; // the freq count
    }
}

 enum Freq {
    minute(60), hour(3600), day(86400);
    Map<Freq, Integer> map = new HashMap<>();
    Freq(int val) {
        map.put(this, val);
    }

    public int getVal() {
         return map.get(this);
     }

}

/**
 * Your TweetCounts object will be instantiated and called as such:
 * TweetCounts obj = new TweetCounts();
 * obj.recordTweet(tweetName,time);
 * List<Integer> param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime);
 */
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

//less_equal to use it as a multiset
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

class TweetCounts {
public:
    unordered_map<string, pbds> tweet;
    TweetCounts() {
        tweet.clear();
    }
    
    void recordTweet(string tweetName, int time) {
        tweet[tweetName].insert(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int interval;
        if(freq == "minute") interval = 60;
        else if(freq == "hour") interval = 3600;
        else interval = 86400;
        
        vector<int> ans;
		
        for(int i=startTime; i<=endTime; i+=interval)
        {
            int start = i, end = min(endTime, i+interval-1);
            
            //[start - end] or [start - end+1)
            auto low = tweet[tweetName].order_of_key(start);
            auto high = tweet[tweetName].order_of_key(end+1);
            
            ans.push_back(high-low);
        }
        return ans;
    }
};
var TweetCounts = function() {
    this.map = new Map();
};

TweetCounts.prototype.recordTweet = function(tweetName, time) {
    if (!this.map.has(tweetName)) this.map.set(tweetName, []);
    this.map.get(tweetName).push(time);
};

TweetCounts.prototype.getTweetCountsPerFrequency = function(freq, tweetName, startTime, endTime) {
    if (!this.map.has(tweetName)) return [];

    const tweets = this.map.get(tweetName);
    const buckets = createBuckets(freq, startTime, endTime);

    for (let i = 0; i < tweets.length; i++) {
        const tweetTime = tweets[i];

        let left = 0;
        let right = buckets.length - 1;

        while (left <= right) {
            const mid = (left + right) >> 1;
            const [startTime, endTime, count] = buckets[mid];

            if (startTime <= tweetTime && tweetTime <= endTime) {
                buckets[mid][2] = count + 1;
                break;
            }

            if (endTime < tweetTime) left = mid + 1;
            else right = mid - 1;
        }
    }

    const res = [];

    for (let i = 0; i < buckets.length; i++) {
        res.push(buckets[i][2]);
    }

    return res;

    function createBuckets(freq, startTime, endTime) {
        const chunks = { "minute": 60, "hour": 3600, "day": 86400 };
        const buckets = [];

        let start = startTime;

        while (start <= endTime) {
            const end = Math.min(start + chunks[freq] - 1, endTime);
            buckets.push([start, end, 0])
            start = end + 1;
        }

        return buckets;
    }
};
Tweet Counts Per Frequency