Problem Description

The "Tweet Counts Per Frequency" problem asks you to design a system that can:

• Record the time (in seconds) when a tweet was posted, for any given tweet name.
• Answer queries about how many times a tweet occurred in each interval of a specified frequency (minute, hour, or day) between a start and end time.

The system should implement three main methods:

• recordTweet(tweetName, time): Records that a tweet with name tweetName occurred at time seconds.
• getTweetCountsPerFrequency(freq, tweetName, startTime, endTime): Returns a list of counts of tweets with name tweetName for each interval of length specified by freq ("minute", "hour", "day") between startTime and endTime (inclusive).

Key Constraints:

• You may receive multiple tweets with the same name at different times.
• Queries may be called multiple times and in any order.
• All times are given in seconds, and are positive integers.
• You must not reuse tweet times for different intervals.
• You must return counts for all intervals between startTime and endTime, even if the count is zero.

Thought Process

The first step is to recognize that we need to efficiently store and retrieve tweet times for each tweet name. For each query, we need to quickly count how many tweets fall into each interval of the requested frequency.

A brute-force approach would be to scan through all recorded tweet times for every query and manually count which times fall into each interval. However, this would be very slow if there are many tweets or queries.

To optimize, we can:

• Store the tweet times in a way that allows fast range queries (e.g., a sorted list for each tweet name).
• When answering a query, use binary search to quickly find the relevant times between startTime and endTime.
• Then, for each interval, count how many tweet times fall into that interval.

Solution Approach

Here's how we can implement the solution step by step:

1. Data Structure:
   • Use a dictionary (hash map) where the key is the tweet name and the value is a list of times (integers) when the tweet was recorded.
   • Keep the list sorted for each tweet name to allow efficient range queries using binary search.
2. recordTweet(tweetName, time):
   • Append the time to the list for the given tweet name.
   • Keep the list sorted. (Either sort after every insertion or insert in order; for simplicity, sort before each query.)
3. getTweetCountsPerFrequency(freq, tweetName, startTime, endTime):
   • Determine the interval size based on the frequency:
     • "minute" → 60 seconds
     • "hour" → 3600 seconds
     • "day" → 86400 seconds
   • Calculate the number of intervals: ((endTime - startTime) // interval) + 1
   • For the tweet name, get the sorted list of times.
   • For each interval, use binary search to count how many tweet times fall within that interval.
   • Build and return a list of counts, one for each interval.

We use binary search (e.g., the bisect module in Python) because it allows us to efficiently find the start and end indices of tweet times within a range, making the count operation O(log n) per interval.

Example Walkthrough

Suppose we perform the following operations:

• recordTweet("tweet1", 10)
• recordTweet("tweet1", 20)
• recordTweet("tweet1", 120)
• getTweetCountsPerFrequency("minute", "tweet1", 0, 119)

1. We record tweet1 at times 10, 20, and 120.
2. We query for counts per "minute" (interval size 60) from time 0 to 119 (i.e., 0-59, 60-119).
3. For interval 0 (0-59): tweets at 10 and 20 fall here. Count = 2.
4. For interval 1 (60-119): no tweets fall here. Count = 0.
5. The result is [2, 0].

Time and Space Complexity

Brute-force Approach:

• For each query, scan all tweet times for the tweet name and check which interval each falls into.
• If there are n tweets and k intervals, time complexity is O(nk).

• Tweet times are kept sorted. For each query, we use binary search to find the relevant times in O(log n).
• For each interval, we use binary search to find the start and end indices, so total time is O(k log n), where k is the number of intervals.
• Space complexity is O(n) for storing all tweet times.

The optimized approach is much faster, especially when there are many tweets or queries.

Summary

In this problem, we designed a system to efficiently record tweet times and answer frequency-based queries. By storing tweet times in sorted lists and using binary search, we can quickly answer queries about how many tweets occurred in each interval of a given frequency. This approach balances fast insertions and efficient queries, making it suitable for large-scale use cases.

Code Implementation

from bisect import bisect_left, bisect_right
from collections import defaultdict

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):
        interval = {"minute": 60, "hour": 3600, "day": 86400}[freq]
        times = self.tweets[tweetName]
        times.sort()
        n_intervals = ((endTime - startTime) // interval) + 1
        res = [0] * n_intervals
        for t in times:
            if startTime <= t <= endTime:
                idx = (t - startTime) // interval
                res[idx] += 1
        return res
      

#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

class TweetCounts {
    map<string, vector<int>> tweets;
public:
    TweetCounts() {}

    void recordTweet(string tweetName, int time) {
        tweets[tweetName].push_back(time);
    }

    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int interval = freq == "minute" ? 60 : (freq == "hour" ? 3600 : 86400);
        vector<int>& times = tweets[tweetName];
        sort(times.begin(), times.end());
        int n_intervals = (endTime - startTime) / interval + 1;
        vector<int> res(n_intervals, 0);
        for (int t : times) {
            if (t >= startTime && t <= endTime) {
                int idx = (t - startTime) / interval;
                res[idx]++;
            }
        }
        return res;
    }
};
      

import java.util.*;

class TweetCounts {
    Map<String, List<Integer>> tweets;

    public TweetCounts() {
        tweets = new HashMap<>();
    }

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

    public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
        int interval = 0;
        if (freq.equals("minute")) interval = 60;
        else if (freq.equals("hour")) interval = 3600;
        else if (freq.equals("day")) interval = 86400;

        List<Integer> times = tweets.getOrDefault(tweetName, new ArrayList<>());
        Collections.sort(times);
        int n_intervals = (endTime - startTime) / interval + 1;
        List<Integer> res = new ArrayList<>(Collections.nCopies(n_intervals, 0));
        for (int t : times) {
            if (t >= startTime && t <= endTime) {
                int idx = (t - startTime) / interval;
                res.set(idx, res.get(idx) + 1);
            }
        }
        return res;
    }
}
      

class TweetCounts {
    constructor() {
        this.tweets = new Map();
    }
    recordTweet(tweetName, time) {
        if (!this.tweets.has(tweetName)) {
            this.tweets.set(tweetName, []);
        }
        this.tweets.get(tweetName).push(time);
    }
    getTweetCountsPerFrequency(freq, tweetName, startTime, endTime) {
        let interval = freq === "minute" ? 60 : (freq === "hour" ? 3600 : 86400);
        let times = this.tweets.get(tweetName) || [];
        times.sort((a, b) => a - b);
        let n_intervals = Math.floor((endTime - startTime) / interval) + 1;
        let res = Array(n_intervals).fill(0);
        for (let t of times) {
            if (t >= startTime && t <= endTime) {
                let idx = Math.floor((t - startTime) / interval);
                res[idx]++;
            }
        }
        return res;
    }
}