We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Tweet Counts Per Frequency

Number: 1470

Difficulty: Medium

Paid? No

Companies: Google, X

Problem Description

Design a TweetCounts class that supports recording tweet occurrences and retrieving the number of tweets in specified time intervals. Given a tweet name and its posting time (in seconds), the API should return the count of tweets within a time range partitioned into chunks based on a given frequency (minute, hour, or day).

Key Insights

  • Use a hashmap (or dictionary) to map tweet names to a list of their posting times.
  • Determine the chunk size based on frequency: 60 seconds for a minute, 3600 seconds for an hour, and 86400 seconds for a day.
  • Partition the time interval [startTime, endTime] into chunks and count the number of tweet timestamps falling into each chunk.
  • Efficiently process queries by iterating over the recorded timestamps, optionally leveraging binary search if the timestamps are maintained in a sorted order.

Space and Time Complexity

Time Complexity: O(T + log N) per query where T is the number of tweets in the time range and N is the total number of tweets for a given tweet name. Space Complexity: O(N) for storing all tweet timestamps.

Solution

We implement the TweetCounts class with two methods: recordTweet and getTweetCountsPerFrequency. The recordTweet method stores the tweet by appending its timestamp to a list corresponding to the tweet name in a hashmap. For the getTweetCountsPerFrequency method, we determine the appropriate time chunk based on the frequency, compute the number of chunks, then iterate over the tweet timestamps that fall within the given time range, mapping each timestamp to its respective chunk index. This approach uses a hashmap to group timestamps and simple arithmetic to partition the time range, ensuring correct and efficient counting.

Code Solutions

Below are code solutions with line-by-line comments for each language.

class TweetCounts:
    def __init__(self):
        # Dictionary to store tweet names and their list of timestamps.
        self.tweets = {}

    def recordTweet(self, tweetName: str, time: int) -> None:
        # Add the tweet's timestamp to the associated tweetName list.
        if tweetName not in self.tweets:
            self.tweets[tweetName] = []
        self.tweets[tweetName].append(time)

    def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> list:
        # Determine the chunk size based on frequency.
        if freq == "minute":
            interval = 60
        elif freq == "hour":
            interval = 3600
        else:  # "day"
            interval = 86400

        # Calculate the number of chunks.
        num_chunks = (endTime - startTime) // interval + 1
        counts = [0] * num_chunks

        # If tweetName is not present, return counts initialized with zeros.
        if tweetName not in self.tweets:
            return counts

        # Count each tweet if its time lies within [startTime, endTime].
        for time in self.tweets[tweetName]:
            if startTime <= time <= endTime:
                # Determine the chunk index for the current timestamp.
                index = (time - startTime) // interval
                counts[index] += 1
        return counts

# Example:
# tweetCounts = TweetCounts()
# tweetCounts.recordTweet("tweet3", 0)
# tweetCounts.recordTweet("tweet3", 60)
# tweetCounts.recordTweet("tweet3", 10)
# print(tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59))  # Output: [2]
← Back to All Questions