Implement the class TweetCounts that supports two methods:
1. recordTweet(string tweetName, int time)

Stores the tweetName at the recorded time (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 on freq) starting from the startTime (in seconds) and ending at the endTime (in seconds).
freq is always minute, hour or day, representing the time interval to get the total number of occurrences for the given tweetName.
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 number i and delta (which depends on freq).  

 
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 both recordTweet and getTweetCountsPerFrequency.
0 <= time, startTime, endTime <= 10^9
0 <= endTime - startTime <= 10^4

Difficulty: MEDIUM
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:
class TweetCounts:
    def __init__(self):
    def recordTweet(self, tweetName: str, time: int) -> None:
    def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
# Your TweetCounts object will be instantiated and called as such:
# obj = TweetCounts()
# obj.recordTweet(tweetName,time)
# param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime)

Solutions:
from bisect import insort, bisect_left, bisect_right
from math import ceil

class TweetCounts:

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName not in self.tweets:
			self.tweets[tweetName] = []
		insort(self.tweets[tweetName], time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		entry = self.tweets[tweetName]
		diff = endTime - startTime
		factor = 86400
		if freq == 'minute':
			factor = 60
		elif freq == 'hour':
			factor = 3600
		buckets = math.ceil((diff + 1) / factor)
		ans = [0] * buckets
		start = bisect_left(entry, startTime)
		end = bisect_right(entry, endTime)
		for i in range(start, end):
			time = entry[i]
			d = (time - startTime) // factor
			ans[d] += 1
		return ans


class TweetCounts:
	FREQUENCE = {'minute': 60, 'hour': 3600, 'day': 24 * 3600}

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName not in self.tweets_dict:
			self.tweets_dict[tweetName] = []
		bisect.insort(self.tweets_dict.get(tweetName), time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if tweetName not in self.tweets_dict:
			return []
		delta = TweetCounts.FREQUENCE[freq]
		num_intervals = (endTime - startTime) // delta + 1
		result = [0] * num_intervals
		start = bisect.bisect_left(self.tweets_dict.get(tweetName), startTime)
		end = bisect.bisect_right(self.tweets_dict.get(tweetName), endTime)
		for t1 in range(start - 1, end + 1):
			if t1 < 0:
				continue
			if t1 >= len(self.tweets_dict.get(tweetName)):
				continue
			t = self.tweets_dict.get(tweetName)[t1]
			if t < startTime or t > endTime:
				continue
			index = (t - startTime) // delta
			result[index] += 1
		return result


class TweetCounts:

	def __init__(self):
		from bisect import bisect_left, bisect_right
		from functools import lru_cache
		self.tweets = {}
		self.cache = {}
		return

	def recordTweet(self, tweetName: str, time: int) -> None:
		(tn, seconds) = (tweetName, time)
		if tn not in self.tweets:
			self.tweets[tn] = Counter()
		self.tweets[tn] += Counter(dict([(seconds, 1)]))
		return

	def quantize(self, per_second_tweet_counter, valid_times, scale):
		t = [((timekey - self.st) // scale, per_second_tweet_counter[timekey]) for timekey in valid_times]
		(qcnts, qkeys) = ({}, [])
		for (tk, tc) in t:
			if tk not in qcnts:
				qcnts[tk] = 0
				qkeys.append(tk)
			qcnts[tk] += tc
		n = (self.et - self.st + 1) // scale
		if (self.et - self.st + 1) % scale:
			n += 1
		res = [0] * n
		for tk in qkeys:
			res[tk] = qcnts[tk]
		return res

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		(M, H, D) = (60, 60 * 60, 60 * 60 * 24)
		(self.tn, self.st, self.et) = (tweetName, startTime, endTime)
		if self.tn not in self.tweets:
			return [0]
		per_second_tweet_counter = self.tweets[self.tn]
		key = (self.tn, self.st, self.et)
		if key in self.cache:
			valid_times = self.cache[key]
		else:
			valid_times = [timekey for timekey in per_second_tweet_counter if self.st <= timekey <= self.et]
			self.cache[key] = valid_times
		if freq == 'minute':
			return self.quantize(per_second_tweet_counter, valid_times, M)
		if freq == 'hour':
			return self.quantize(per_second_tweet_counter, valid_times, H)
		if freq == 'day':
			return self.quantize(per_second_tweet_counter, valid_times, D)
		return [0]


class TweetCounts:

	def __init__(self):
		self.a = collections.defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		heapq.heappush(self.a[tweetName], time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if tweetName not in self.a:
			return []
		temp = list(self.a[tweetName])
		q = []
		while temp:
			q.append(heapq.heappop(temp))
		if freq == 'minute':
			f = 60
		elif freq == 'hour':
			f = 3600
		else:
			f = 3600 * 24
		bucket_size = (endTime - startTime) // f + 1
		ans = [0] * bucket_size
		cur = 0
		end = f + startTime
		for t in q:
			if t < startTime:
				continue
			if t > endTime:
				break
			i = (t - startTime) // f
			ans[i] += 1
		return ans


from collections import defaultdict

class TweetCounts:

	def __init__(self):
		self.data = defaultdict(list)

	def recordTweet(self, tweetName, time):
		self.data[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq, tweetName, startTime, endTime):
		delta = 60 if freq == 'minute' else 3600 if freq == 'hour' else 86400
		start = startTime
		res = []
		self.data[tweetName].sort()
		while start <= endTime:
			end = min(start + delta, endTime + 1)
			res.append(len([x for x in self.data[tweetName] if start <= x < end]))
			start += delta
		return res


class TweetCounts:
	FREQUENCE = {'minute': 60, 'hour': 3600, 'day': 24 * 3600}

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName not in self.tweets_dict:
			self.tweets_dict[tweetName] = []
		bisect.insort(self.tweets_dict.get(tweetName), time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if tweetName not in self.tweets_dict:
			return []
		delta = TweetCounts.FREQUENCE[freq]
		num_intervals = (endTime - startTime) // delta + 1
		result = [0] * num_intervals
		for t in self.tweets_dict[tweetName]:
			if t < startTime:
				continue
			if t > endTime:
				break
			index = (t - startTime) // delta
			result[index] += 1
		return result


class TweetCounts:

	def __init__(self):
		self.tweets = defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		insort(self.tweets[tweetName], time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		delta = 60
		if freq == 'hour':
			delta = 3600
		elif freq == 'day':
			delta = 86400
		pre = bisect_left(self.tweets[tweetName], startTime)
		n = (endTime + 1 - startTime) // delta + (1 if (endTime + 1 - startTime) % delta != 0 else 0)
		(end, res) = (startTime, [])
		for _ in range(n):
			end = min(end + delta, endTime + 1)
			i = bisect_left(self.tweets[tweetName], end)
			res.append(i - pre)
			pre = i
		return res


class TweetCounts:
	FREQUENCE = {'minute': 60, 'hour': 3600, 'day': 24 * 3600}

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName not in self.tweets_dict:
			self.tweets_dict[tweetName] = []
		(left, right) = (0, len(self.tweets_dict[tweetName]))
		while left < right:
			mid = left + (right - left) // 2
			if self.tweets_dict[tweetName][mid] == time:
				right = mid
			elif self.tweets_dict[tweetName][mid] > time:
				right = mid
			elif self.tweets_dict[tweetName][mid] < time:
				left = mid + 1
		self.tweets_dict[tweetName].insert(left, time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if tweetName not in self.tweets_dict:
			return []
		delta = TweetCounts.FREQUENCE[freq]
		num_intervals = (endTime - startTime) // delta + 1
		result = [0] * num_intervals
		for t in self.tweets_dict[tweetName]:
			if t < startTime:
				continue
			if t > endTime:
				break
			index = (t - startTime) // delta
			result[index] += 1
		return result


class TweetCounts:

	def __init__(self):
		self.store = defaultdict(list)
		self.delta = {'hour': 3600, 'minute': 60, 'day': 24 * 3600}

	def recordTweet(self, tn: str, time: int) -> None:
		insort(self.store[tn], time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		d = self.delta[freq]
		ans = []
		arr = self.store[tweetName]
		for st_time in range(startTime, endTime + 1, d):
			left = bisect_left(arr, st_time)
			right = bisect_right(arr, min(endTime, st_time + d - 1))
			ans.append(right - left)
		return ans


from collections import defaultdict
from enum import Enum
from math import ceil
frequency = Enum(value='frequency', names=[('minute', 60), ('hour', 3600), ('day', 86400)])

class TweetManager:

	def __init__(self):
		self.tweets = defaultdict(list)

	def __str__(self):
		return str(self.tweets)

	def add_tweet(self, tweet_name, time):
		self.tweets[tweet_name].append(time)
		self.tweets[tweet_name].sort()

	def _find_start_index(self, history: List[int], start_time, min_index=None, max_index=None):
		if min_index is None:
			min_index = 0
		if max_index is None:
			max_index = len(history) - 1
		if min_index > max_index:
			return None
		middle_index = int((max_index + min_index) / 2)
		if history[middle_index] == start_time:
			return middle_index
		if history[middle_index] > start_time:
			result = self._find_start_index(history, start_time, min_index, middle_index - 1)
			if result is None:
				return middle_index
			return result
		if history[middle_index] < start_time:
			return self._find_start_index(history, start_time, middle_index + 1, max_index)

	def _find_end_index(self, history: List[int], end_time, min_index=None, max_index=None):
		if min_index is None:
			min_index = 0
		if max_index is None:
			max_index = len(history) - 1
		if min_index > max_index:
			return None
		middle_index = int((max_index + min_index) / 2)
		if history[middle_index] == end_time:
			return middle_index
		if history[middle_index] > end_time:
			return self._find_end_index(history, end_time, min_index, middle_index - 1)
		if history[middle_index] < end_time:
			result = self._find_end_index(history, end_time, middle_index + 1, max_index)
			if result is None:
				return middle_index
			return result

	def _calculate_frequency(self, history: List[int], start_index, end_index, freq, end_time, start_time):
		if start_index is None or end_index is None:
			history = []
		else:
			history = history[start_index:end_index + 1]
		previous_bucket = None
		result = []
		bucket = None
		for time_seconds in history:
			bucket = 0 if (time_seconds + 1 - start_time) / frequency[freq].value <= 1 else int((time_seconds + 1 - start_time) / frequency[freq].value)
			empty_buckets = bucket - (previous_bucket if previous_bucket else 0)
			if previous_bucket is None:
				empty_buckets += 1
			if empty_buckets > 1:
				for a in range(empty_buckets):
					result.append(0)
			if len(result) == bucket:
				result.append(1)
			else:
				result[bucket] += 1
			previous_bucket = bucket
		max_bucket = 0 if (end_time - start_time) / frequency[freq].value < 1 else int((end_time - start_time) / frequency[freq].value)
		if bucket is None:
			while max_bucket >= 0:
				result.append(0)
				max_bucket -= 1
		else:
			while max_bucket > bucket:
				result.append(0)
				max_bucket -= 1
		return result

	def get_tweet_frequency(self, tweet_name: str, start_time: int, end_time: int, freq) -> List[int]:
		start_index = self._find_start_index(self.tweets.get(tweet_name), start_time)
		end_index = self._find_end_index(self.tweets.get(tweet_name), end_time)
		result_frequency = self._calculate_frequency(self.tweets.get(tweet_name), start_index, end_index, freq, end_time, start_time)
		return result_frequency

class TweetCounts:

	def __init__(self):
		self.tweets = TweetManager()

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.tweets.add_tweet(tweetName, time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		return self.tweets.get_tweet_frequency(tweetName, startTime, endTime, freq)


from collections import defaultdict
from bisect import bisect_left, insort

class TweetCounts:

	def __init__(self):
		self.history = defaultdict(list)

	def recordTweet(self, tweet, t):
		insort(self.history[tweet], t)

	def getTweetCountsPerFrequency(self, freq, tweet, s, e):
		if freq == 'minute':
			delta = 60
		elif freq == 'hour':
			delta = 3600
		else:
			delta = 86400
		(A, cur) = (self.history[tweet], s)
		res = []
		while cur <= e:
			nxt = min(cur + delta, e + 1)
			occurence = bisect_left(A, nxt) - bisect_left(A, cur)
			res.append(occurence)
			cur += delta
		return res


class TweetCounts:

	def __init__(self):
		self.recorder = collections.defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		bisect.insort(self.recorder[tweetName], time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		delta = 60 if freq == 'minute' else 3600 if freq == 'hour' else 86400
		(res, i, start) = ([], 1, startTime)
		while start <= endTime:
			end = min(startTime + delta * i, endTime + 1)
			res.append(bisect_left(self.recorder[tweetName], end) - bisect_left(self.recorder[tweetName], start))
			(start, i) = (end, i + 1)
		return res


class TweetCounts:
	FREQUENCEY_TO_SECONDS = {'minute': 60, 'hour': 3600, 'day': 86400}

	def __init__(self):
		self._data = collections.defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		bisect.insort(self._data[tweetName], time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		delta = self.FREQUENCEY_TO_SECONDS.get(freq.lower(), None)
		if not delta:
			return []
		(i, result) = (startTime, [])
		while i <= endTime:
			j = min(i + delta, endTime + 1)
			left = bisect.bisect_left(self._data[tweetName], j)
			right = bisect.bisect_left(self._data[tweetName], i)
			result.append(left - right)
			i += delta
		return result


import bisect
from collections import defaultdict

class TweetCounts:

	def __init__(self):
		self._tweets = defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		self._tweets[tweetName].insert(bisect.bisect_right(self._tweets[tweetName], time), time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		delta = 60 if freq == 'minute' else 3600 if freq == 'hour' else 86400
		result = []
		while startTime <= endTime:
			end = min(startTime + delta, endTime + 1)
			result.append(bisect.bisect_left(self._tweets[tweetName], end) - bisect.bisect_left(self._tweets[tweetName], startTime))
			startTime += delta
		return result


class TweetCounts:

	def __init__(self):
		self.a = defaultdict(list)

	def recordTweet(self, tn: str, time: int) -> None:
		bisect.insort(self.a[tn], time)

	def getTweetCountsPerFrequency(self, freq: str, tn: str, startTime: int, endTime: int) -> List[int]:
		delta = 60 if freq == 'minute' else 3600 if freq == 'hour' else 86400
		i = startTime
		res = []
		while i <= endTime:
			j = min(i + delta, endTime + 1)
			res.append(bisect_left(self.a[tn], j) - bisect_left(self.a[tn], i))
			i += delta
		return res


class TweetCounts:

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName in list(self.tweets.keys()):
			bisect.insort(self.tweets[tweetName], time)
		else:
			self.tweets[tweetName] = [time]

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if tweetName not in self.tweets:
			return []
		delta = 60 if freq == 'minute' else 3600 if freq == 'hour' else 86400
		time_list = self.tweets[tweetName]
		size = int((endTime - startTime) // delta) + 1
		res = [0] * size
		for t in time_list:
			if startTime <= t <= endTime:
				index = int((t - startTime) // delta)
				res[index] += 1
		return res


from collections import defaultdict
from bisect import insort, bisect_left

class TweetCounts:

	def __init__(self):
		self.tweets = defaultdict(list)
		self.d = {'minute': 60, 'hour': 3600, 'day': 86400}

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.tweets[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		record = self.tweets[tweetName]
		delta = self.d[freq]
		res = [0] * ((endTime - startTime) // delta + 1)
		for time in record:
			if time < startTime or time > endTime:
				continue
			res[(time - startTime) // delta] += 1
		return res


class TweetCounts:

	def __init__(self):
		self.memo = collections.defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.memo[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		lst = self.memo[tweetName]
		lst = [t - startTime for t in lst if t >= startTime and t <= endTime]
		if freq == 'minute':
			freq = 60
		elif freq == 'hour':
			freq = 60 * 60
		elif freq == 'day':
			freq = 24 * 60 * 60
		(length, remainder) = divmod(endTime - startTime + 1, freq)
		if remainder > 0:
			length += 1
		res = [0 for _ in range(length)]
		for t in lst:
			res[t // freq] += 1
		return res


class TweetCounts:

	def __init__(self):
		self.tweets = collections.defaultdict(list)
		self.convert = {'minute': 60, 'hour': 3600, 'day': 86400}

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.tweets[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		seconds = self.convert[freq]
		ans = [0] * ((endTime - startTime) // seconds + 1)
		for time in self.tweets[tweetName]:
			if startTime <= time <= endTime:
				ans[(time - startTime) // seconds] += 1
		return ans


from collections import defaultdict
import bisect

class TweetCounts:

	def __init__(self):
		self.T = defaultdict(lambda : [False, []])

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.T[tweetName][0] = False
		self.T[tweetName][1].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		delta = 60 if freq == 'minute' else 3600 if freq == 'hour' else 86400
		if not self.T[tweetName][0]:
			self.T[tweetName][1].sort()
		ans = []
		s = startTime
		i = bisect.bisect_left(self.T[tweetName][1], s)
		while s <= endTime:
			e = min(s + delta, endTime + 1)
			j = bisect.bisect_left(self.T[tweetName][1], e)
			ans.append(j - i)
			(s, i) = (e, j)
		return ans


class TweetCounts:
	deltaDic = {'minute': 60, 'hour': 3600, 'day': 24 * 3600}

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		if not tweetName in self.tweetDic:
			self.tweetDic[tweetName] = []
		self.tweetDic[tweetName].append(time)
		self.tweetDic[tweetName].sort()

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if not tweetName in self.tweetDic:
			return []
		delta = self.deltaDic[freq]
		output = [0] * ((endTime - startTime) // delta + 1)
		for t in self.tweetDic[tweetName]:
			if t < startTime:
				continue
			elif t > endTime:
				continue
			else:
				idx = (t - startTime) // delta
				output[idx] += 1
		return output


class TweetCounts:

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName not in self.d:
			self.d[tweetName] = [time]
		else:
			self.d[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if freq == 'minute':
			s = 60
		elif freq == 'hour':
			s = 3600
		else:
			s = 3600 * 24
		intervals = (endTime - startTime) // s + 1
		res = [0] * intervals
		times = self.d[tweetName]
		for t in times:
			if startTime <= t <= endTime:
				i = (t - startTime) // s
				res[i] += 1
		return res


class TweetCounts:

	def __init__(self):
		self.tweets = defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.tweets[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		count = 0
		den = 0
		size = 0
		if freq == 'minute':
			den = 60
			size = (endTime - startTime) // 60 + 1
		elif freq == 'hour':
			den = 3600
			size = (endTime - startTime) // 3600 + 1
		else:
			den = 86400
			size = (endTime - startTime) // 86400 + 1
		op = [0] * size
		for t in self.tweets[tweetName]:
			if startTime <= t and t <= endTime:
				idx = (t - startTime) // den
				op[idx] += 1
		return op


class TweetCounts:

	def __init__(self):
		self.log = defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.log[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		ret = []
		events = sorted([t for t in self.log[tweetName] if startTime <= t <= endTime])
		ei = 0
		time = startTime
		delta = {'minute': 60, 'hour': 3600, 'day': 24 * 3600}[freq]
		cur = 0
		while time <= endTime:
			if ei == len(events):
				ret.append(cur)
				cur = 0
				time += delta
				continue
			if events[ei] < time:
				ei += 1
			elif time + delta <= events[ei]:
				ret.append(cur)
				time += delta
				cur = 0
			else:
				assert time <= events[ei] < time + delta
				cur += 1
				ei += 1
		return ret


class TweetCounts:

	def __init__(self):
		self.tw = collections.defaultdict(list)
		self.duration = {'minute': 60, 'hour': 3600, 'day': 86400}

	def recordTweet(self, tweetName: str, time: int) -> None:
		if not self.tw[tweetName]:
			self.tw[tweetName].append(time)
		else:
			ind = bisect.bisect(self.tw[tweetName], time)
			self.tw[tweetName] = self.tw[tweetName][:ind] + [time] + self.tw[tweetName][ind:]

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		res = []
		q = self.tw[tweetName]
		s = startTime
		while s <= endTime:
			e = min(endTime, s + self.duration[freq] - 1)
			ind1 = bisect.bisect_left(q, s)
			ind2 = bisect.bisect_right(q, e, lo=ind1)
			res.append(ind2 - ind1)
			s = e + 1
		return res


from collections import defaultdict

class TweetCounts:

	def __init__(self):
		self.data = defaultdict(list)

	def recordTweet(self, tweetName, time):
		self.data[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq, tweetName, startTime, endTime):
		delta = 60 if freq == 'minute' else 3600 if freq == 'hour' else 86400
		new_data = [x for x in self.data[tweetName] if startTime <= x <= endTime]
		delta_data = [(x - startTime) // delta for x in new_data]
		n = (endTime - startTime) // delta + 1
		res = [len([x for x in delta_data if x == i]) for i in range(n)]
		return res


class TweetCounts:

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.tweets.setdefault(tweetName, {}).setdefault(time, 0)
		self.tweets[tweetName][time] += 1

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		eligible = []
		for (time, count) in list(self.tweets.get(tweetName, {}).items()):
			if startTime <= time <= endTime:
				eligible.append((time, count))
		if 'minute' == freq:
			samples = 60
		elif 'hour' == freq:
			samples = 3600
		elif 'day' == freq:
			samples = 86400
		else:
			raise RuntimeError(freq)
		num_results = 1 + (endTime - startTime) // samples
		results = [0] * num_results
		for (time, count) in eligible:
			offset = time - startTime
			if 'minute' == freq:
				offset //= 60
			elif 'hour' == freq:
				offset //= 3600
			elif 'day' == freq:
				offset //= 86400
			results[offset] += count
		return results


class TweetCounts:

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName not in self.dict:
			self.dict[tweetName] = [time]
		else:
			self.dict[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		times = self.dict[tweetName]
		size = 0
		secs = 0
		if freq == 'minute':
			secs = 60
			size = (endTime - startTime) / 60 + 1
		if freq == 'hour':
			secs = 3600
			size = (endTime - startTime) / 3600 + 1
		if freq == 'day':
			secs = 86400
			size = (endTime - startTime) / 86400 + 1
		r = [0] * int(size)
		for i in times:
			if startTime <= i and i <= endTime:
				index = int((i - startTime) / secs)
				r[index] += 1
		return r


class TweetCounts:
	MAP = {'minute': 60, 'hour': 60 * 60, 'day': 24 * 60 * 60}

	def __init__(self):
		self.data = defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.data[tweetName].append(time)
		self.data[tweetName].sort()

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		data = self.data[tweetName]
		index = 0
		while index < len(data) and data[index] < startTime:
			index += 1
		ans = []
		tmp = 0
		k = 0
		delta = self.MAP[freq]
		while startTime + k * delta <= endTime:
			end = min(startTime + delta * (k + 1), endTime + 1)
			if index >= len(data) or data[index] >= end:
				ans.append(tmp)
				tmp = 0
				k += 1
			else:
				tmp += 1
				index += 1
		return ans


from sortedcontainers import SortedList

class TweetCounts:
	freq_seconds = {'minute': 60, 'hour': 3600, 'day': 86400}

	def __init__(self):
		self.tweets: Dict[str, List[int]] = {}

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName not in self.tweets:
			self.tweets[tweetName] = SortedList()
		self.tweets[tweetName].add(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		interval = self.freq_seconds[freq]
		counts = []
		times = self.tweets.get(tweetName, [])
		bucket_start = startTime
		index_start = times.bisect_left(bucket_start)
		while bucket_start <= endTime:
			bucket_end = min(bucket_start + interval, endTime + 1)
			index_end = times.bisect_left(bucket_end)
			counts.append(index_end - index_start)
			bucket_start = bucket_end
			index_start = index_end
		return counts


from typing import List
from sortedcontainers import SortedList
from collections import defaultdict
SECONDS_PER_MINUTE = 60
SECONDS_PER_HOUR = 60 * SECONDS_PER_MINUTE
SECONDS_PER_DAY = 24 * SECONDS_PER_HOUR
INTERVAL_LENGTH = {'minute': SECONDS_PER_MINUTE, 'hour': SECONDS_PER_HOUR, 'day': SECONDS_PER_DAY}

class TweetCounts:

	def __init__(self):
		self.tweets = defaultdict(SortedList)

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.tweets[tweetName].add(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if freq not in INTERVAL_LENGTH:
			raise Exception(f'Expected freq to be one of {INTERVAL_LENGTH.keys()}, got {freq} instead')
		if tweetName not in self.tweets:
			raise Exception(f'Unknown tweet: {tweetName}')
		intervalLength = INTERVAL_LENGTH[freq]
		numIntervals = (endTime - startTime + intervalLength) // intervalLength
		counts = []
		for i in range(numIntervals):
			intervalStart = startTime + i * intervalLength
			intervalEnd = min(intervalStart + intervalLength, endTime + 1)
			matchingTimes = self.tweets[tweetName].irange(minimum=intervalStart, maximum=intervalEnd, inclusive=(True, False))
			counts.append(len(list(matchingTimes)))
		return counts


import bisect

class TweetCounts:

	def __init__(self):
		self.td = dict()
		self.incrDict = {'minute': 60, 'hour': 60 * 60, 'day': 24 * 60 * 60}

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.td[tweetName] = self.td.get(tweetName, list())
		self.td[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if tweetName not in self.td:
			return []
		tl = sorted(self.td.get(tweetName, list()))
		si = bisect.bisect_left(tl, startTime)
		ei = bisect.bisect_right(tl, endTime)
		incr = self.incrDict[freq]
		res = []
		for i in range(math.ceil((endTime - startTime + 1) / incr)):
			et = startTime + (i + 1) * incr
			ind = bisect.bisect_right(tl, et - 1, si, ei)
			res.append(ind - si)
			si = ind
		return res


from collections import defaultdict, deque
import bisect

class TweetCounts:

	def __init__(self):
		self._deltas = {'minute': 60, 'hour': 60 * 60, 'day': 60 * 60 * 24}
		self._tweets = defaultdict(deque)

	def recordTweet(self, tweetName: str, time: int) -> None:
		bisect.insort_left(self._tweets[tweetName], time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		tweet_times = self._tweets[tweetName]
		left = 0
		right = len(tweet_times)
		while left < right:
			mid = (left + right) // 2
			if tweet_times[mid] >= startTime:
				right = mid
			else:
				left = mid + 1
		output = [0]
		interval = self._deltas[freq]
		period_start = startTime
		while left < len(tweet_times) and tweet_times[left] <= endTime:
			if tweet_times[left] < period_start + interval:
				output[-1] += 1
				left += 1
			else:
				period_start += interval
				output.append(0)
		for _ in range((endTime - period_start) // interval):
			output.append(0)
		return output


class TweetCounts:

	def __init__(self):
		self.tweets = collections.defaultdict(list)

	def __bs(self, arr, val):
		(lo, hi) = (0, len(arr))
		while lo < hi:
			mid = (lo + hi) // 2
			if arr[mid] >= val:
				hi = mid
			else:
				lo = mid + 1
		return lo

	def recordTweet(self, tweetName: str, time: int) -> None:
		idx = self.__bs(self.tweets[tweetName], time)
		self.tweets[tweetName].insert(idx, time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		delta = 60 if freq == 'minute' else 3600 if freq == 'hour' else 86400
		i = startTime
		arr = self.tweets[tweetName]
		result = []
		while i <= endTime:
			j = min(i + delta, endTime + 1)
			result.append(self.__bs(arr, j) - self.__bs(arr, i))
			i += delta
		return result


class TweetCounts:

	def __init__(self):
		self.data = defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.data[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if freq[0] == 'm':
			ans = [0] * ((endTime - startTime) // 60 + 1)
			for x in self.data[tweetName]:
				if startTime <= x <= endTime:
					a = (x - startTime) // 60
					ans[a] += 1
			return ans
		elif freq[0] == 'h':
			ans = [0] * ((endTime - startTime) // 3600 + 1)
			for x in self.data[tweetName]:
				if startTime <= x <= endTime:
					a = (x - startTime) // 3600
					ans[a] += 1
			return ans
		else:
			ans = [0] * ((endTime - startTime) // 86400 + 1)
			for x in self.data[tweetName]:
				if startTime <= x <= endTime:
					a = (x - startTime) // 86400
					ans[a] += 1
			return ans


from collections import defaultdict
import bisect

class TweetCounts:
	freq_map = {'minute': 60, 'hour': 3600, 'day': 3600 * 24}

	def __init__(self):
		self.tweet_map = defaultdict(list)

	def recordTweet(self, tweetName: str, time: int) -> None:
		bisect.insort(self.tweet_map[tweetName], time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		interval_length = TweetCounts.freq_map[freq]
		starting_index = bisect.bisect_left(self.tweet_map[tweetName], startTime)
		res = []
		curr_index = starting_index
		current_interval_start = startTime
		current_interval_end = min(current_interval_start + interval_length - 1, endTime)
		current_interval_count = 0
		while current_interval_end <= endTime:
			if curr_index < len(self.tweet_map[tweetName]):
				if self.tweet_map[tweetName][curr_index] <= current_interval_end:
					current_interval_count += 1
					curr_index += 1
				elif current_interval_end != endTime:
					current_interval_start += interval_length
					current_interval_end = min(current_interval_end + interval_length, endTime)
					res.append(current_interval_count)
					current_interval_count = 0
				else:
					res.append(current_interval_count)
					break
			elif current_interval_end != endTime:
				current_interval_start += interval_length
				current_interval_end = min(current_interval_end + interval_length, endTime)
				res.append(current_interval_count)
				current_interval_count = 0
			else:
				res.append(current_interval_count)
				break
		return res


class TweetCounts:

	def __init__(self):
		self.data = collections.defaultdict(dict)

	def recordTweet(self, tweetName: str, time: int) -> None:
		if time not in self.data[tweetName]:
			self.data[tweetName][time] = 1
		else:
			self.data[tweetName][time] += 1

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		delta = [60, 60 * 60, 60 * 60 * 24]
		if freq == 'minute':
			t = delta[0]
		elif freq == 'hour':
			t = delta[1]
		else:
			t = delta[2]
		res = [0] * ((endTime - startTime) // t + 1)
		i = 0
		data = self.data[tweetName]
		for time in sorted(data.keys()):
			if startTime <= time <= endTime:
				res[(time - startTime) // t] += data[time]
		return res


class TweetCounts:

	def __init__(self):
		self.tweets = defaultdict(list)
		self.mapping = {'minute': 60, 'hour': 3600, 'day': 86400}

	def binary_search(self, left, right, key, array, type):
		while left <= right:
			mid = left + (right - left) // 2
			if array[mid] >= key:
				right = mid - 1
			else:
				left = mid + 1
		return left if type == 'S' else right

	def recordTweet(self, tweetName: str, time: int) -> None:
		self.tweets[tweetName].append(time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		self.tweets[tweetName].sort()
		tweetcounts = self.tweets[tweetName]
		intervals = []
		while startTime < endTime + 1:
			startindex = self.binary_search(0, len(tweetcounts) - 1, startTime, tweetcounts, 'S')
			findval = min(startTime + self.mapping[freq], endTime + 1)
			endindex = self.binary_search(0, len(tweetcounts) - 1, findval, tweetcounts, 'E')
			intervals.append(endindex - startindex + 1)
			startTime += self.mapping[freq]
		return intervals


class TweetCounts:

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

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName not in self.tweet2time:
			self.tweet2time[tweetName] = [time]
		else:
			arr = self.tweet2time[tweetName]
			index = self.binary_search(arr, time)
			arr.insert(index, time)

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		if tweetName not in self.tweet2time:
			return []
		arr = self.tweet2time[tweetName]
		if freq == 'minute':
			interval = 60
		elif freq == 'hour':
			interval = 3600
		else:
			interval = 3600 * 60
		time = startTime
		result = []
		while time <= endTime:
			end_time = time + interval
			start_index = self.binary_search(arr, time)
			end_index = self.binary_search(arr, min(end_time, endTime + 1))
			result.append(end_index - start_index)
			time = end_time
		return result

	def binary_search(self, arr, num):
		left = 0
		right = len(arr)
		while left < right:
			mid = left + (right - left) // 2
			if arr[mid] > num:
				right = mid
			elif arr[mid] < num:
				left = mid + 1
			else:
				return mid
		return left


class TweetCounts:

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

	def insertAt(self, tN, x):
		l = 0
		r = len(self.tweetDict[tN]) - 1
		if x < self.tweetDict[tN][l]:
			return 0
		if x > self.tweetDict[tN][r]:
			return r + 1
		while r > l:
			m = (r + l) // 2
			if self.tweetDict[tN][m] < x:
				l = m + 1
			else:
				r = m
		return l

	def recordTweet(self, tweetName: str, time: int) -> None:
		if tweetName in self.tweetDict:
			self.tweetDict[tweetName].insert(self.insertAt(tweetName, time), time)
		else:
			self.tweetDict[tweetName] = [time]

	def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
		ans = []
		if freq == 'minute':
			delta = 60
		elif freq == 'hour':
			delta = 3600
		else:
			delta = 86400
		total = (endTime - startTime) // delta
		if (endTime - startTime) % delta > 0:
			total += 1
		n = 0
		for t in range(startTime, endTime + 1, delta):
			t0 = t
			t1 = min(t + delta, endTime + 1)
			i0 = self.insertAt(tweetName, t0)
			if i0 == len(self.tweetDict[tweetName]):
				ans += [0] * (total - n)
				return ans
			i1 = self.insertAt(tweetName, t1)
			if i1 == len(self.tweetDict[tweetName]):
				ans.append(i1 - i0)
				ans += [0] * (total - n - 1)
				return ans
			n += 1
			ans.append(i1 - i0)
		return ans