Problem statement

A social network wants activity charts: how many times a tweet was posted in each minute, hour or day of a time window.

The window [startTime, endTime] (in seconds, both ends included) is cut into consecutive chunks of the chosen frequency — 60 seconds for "minute", 3600 for "hour", 86400 for "day" — starting at startTime: [startTime, startTime + size - 1], [startTime + size, startTime + 2·size - 1], and so on. The last chunk stops at endTime and may be shorter than the others.

Write the class TweetCounts:

• TweetCounts() creates an empty record.
• void recordTweet(String tweetName, int time) records one posting of tweetName at second time.
• int[] getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) returns, for each chunk in order, how many recorded postings of tweetName fall inside it.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

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: [0,59] is one minute holding the postings at 0 and 10. [0,60] is two chunks, [0,59] and [60,60], with 2 and 1 postings. After a posting at 120, the hour window [0,210] is a single chunk holding all four.

Example 2

Input: ["TweetCounts","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency"]
[[],["news",5],["news",130],["minute","news",10,200],["day","sport",0,100]]
Output: [null,null,null,[0,0,1,0],[0]]
Explanation: The window [10,200] splits into [10,69], [70,129], [130,189] and [190,200]; only the posting at 130 is inside it. Nothing was recorded for sport, so its single day chunk counts 0.

Constraints

• 0 <= time, startTime, endTime <= 10^9
• 0 <= endTime - startTime <= 10^4
• freq is "minute", "hour" or "day"
• tweetName consists of lowercase English letters and digits
• At most 10^4 calls are made to recordTweet and getTweetCountsPerFrequency in total

Hints for Tweet Counts Per Frequency

1. Hint 1

   Keep the posting times of each tweet name together, in a map from name to a list of times.

2. Hint 2

   The number of chunks is (endTime - startTime) / size + 1 (integer division), and a posting at time t inside the window belongs to chunk (t - startTime) / size.

3. Hint 3

   So one pass over the tweet's times fills an array of counts: skip times outside [startTime, endTime] and increment the chunk each remaining time maps to. (With the times kept sorted, a binary search can jump straight to the window.)

How to solve Tweet Counts Per Frequency

Store each tweet's posting times; a query allocates one counter per chunk and drops every posting inside the window into its chunk with one division.

Approach

1. recordTweet(name, time): append time to times[name].
2. getTweetCountsPerFrequency(freq, name, start, end): let size be 60, 3600 or 86400 and make (end - start) / size + 1 counters, all 0.
3. For each recorded time t of name with start <= t <= end, increment counter (t - start) / size.
4. Return the counters.

Why it works

Chunk i covers [start + i·size, start + (i+1)·size - 1], so a time t >= start lies in chunk floor((t - start) / size); for t <= end that index is at most (end - start) / size, the last chunk — which is why the last chunk is automatically cut at end. Every posting inside the window is counted exactly once, in its own chunk.

Complexity

• Time — O(1) per record, O(p + c) per query for p postings of that tweet and c chunks
• Space — O(total postings)

Pitfalls

• The chunks start at startTime, not at multiples of 60 — [10,69] is a minute here.
• The last chunk may be shorter but must still be present: [0,60] in minutes is two chunks, [0,59] and [60,60].
• A tweet name never recorded still gets its full array of zeros.

Reference solution

Python

class TweetCounts:
    SIZE = {"minute": 60, "hour": 3600, "day": 86400}

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

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

    def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
        size = self.SIZE[freq]
        res = [0] * ((endTime - startTime) // size + 1)
        for t in self.times.get(tweetName, []):
            if startTime <= t <= endTime:
                res[(t - startTime) // size] += 1  # the chunk this posting falls in
        return res

Java

class TweetCounts {
    private HashMap<String, List<Integer>> times = new HashMap<>();

    public TweetCounts() {
    }

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

    public int[] getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
        int size = freq.equals("minute") ? 60 : freq.equals("hour") ? 3600 : 86400;
        int[] res = new int[(endTime - startTime) / size + 1];
        for (int t : times.getOrDefault(tweetName, new ArrayList<>()))
            if (t >= startTime && t <= endTime) res[(t - startTime) / size]++; // the chunk this posting falls in
        return res;
    }
}

C++

class TweetCounts {
    unordered_map<string, vector<int>> times;
public:
    TweetCounts() {}

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

    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int size = freq == "minute" ? 60 : freq == "hour" ? 3600 : 86400;
        vector<int> res((endTime - startTime) / size + 1, 0);
        auto it = times.find(tweetName);
        if (it != times.end())
            for (int t : it->second)
                if (t >= startTime && t <= endTime) res[(t - startTime) / size]++; // the chunk this posting falls in
        return res;
    }
};

JavaScript

var TweetCounts = function() {
    this.times = new Map();
};

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

TweetCounts.prototype.getTweetCountsPerFrequency = function(freq, tweetName, startTime, endTime) {
    var size = freq === "minute" ? 60 : freq === "hour" ? 3600 : 86400;
    var res = new Array(Math.floor((endTime - startTime) / size) + 1).fill(0);
    var list = this.times.get(tweetName) || [];
    for (var i = 0; i < list.length; i++) {
        var t = list[i];
        if (t >= startTime && t <= endTime) res[Math.floor((t - startTime) / size)]++; // the chunk this posting falls in
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium