Tweet Counts Per Frequency - Leetcode Solution

Description: The task is to implement a system, which given several tweets and a list of queries, returns the number of tweets that match the queried interval. The queried interval can be specified by start and end epoch times, and the frequency can be every minute, every hour, or every day.

Solution: The solution to this problem requires us to store the tweet data, and then perform queries on this data. A hash table can be used to store the tweet data. The hash table can be indexed by the timestamp of each tweet. Furthermore, a set can be used to store the set of tweet ids corresponding to each timestamp.

To perform the queries, we first initialize an empty result vector. Next, for each query interval, we compute a list of timestamps that fall within the interval, based on the frequency of the query. For example, if the query is for every hour between timestamps start and end, then we compute a list of timestamps where each is an hour apart starting from the start timestamp, up to the end timestamp. Finally, for each timestamp in the list, we retrieve the corresponding set of tweet ids from the hash table, and count the size of the set. This count is then appended to the result vector.

Time Complexity: The time complexity of the solution is O(Nlog(N)), where N is the number of tweets. The space complexity is also O(N).

Here's the Python implementation of the solution:

from collections import defaultdict


class TweetCounts:

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

    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 == 'minute':
            delta = 60
        elif freq == 'hour':
            delta = 3600
        elif freq == 'day':
            delta = 86400

        result = []
        timestamp = startTime
        while timestamp <= endTime:
            tweet_times = self.tweets[tweetName]
            count = sum(time >= timestamp and time < timestamp + delta for time in tweet_times)
            result.append(count)
            timestamp += delta

        return result

Note that we use the defaultdict to default to an empty set for any tweetName that hasn't been seen before. We then use a standard Python list comprehension to count the number of tweets within a given interval. We simply sum the boolean values obtained from the comparison of each tweet time to the current timestamp range. Finally, we append this count to the result vector.

1