Tweet Counts Per Frequency - Practice Coding Problems

Tweet Counts Per Frequency - Problem

Hash Table String Binary Search Design Sorting Ordered Set Medium

A social media company is trying to monitor activity on their site by analyzing the number of tweets that occur in select periods of time. These periods can be partitioned into smaller time chunks based on a certain frequency (every minute, hour, or day).

For example, the period [10, 10000] (in seconds) would be partitioned into the following time chunks with these frequencies:

Every minute (60-second chunks): [10,69], [70,129], [130,189], ..., [9970,10000]
Every hour (3600-second chunks): [10,3609], [3610,7209], [7210,10000]
Every day (86400-second chunks): [10,10000]

Notice that the last chunk may be shorter than the specified frequency's chunk size and will always end with the end time of the period.

Design and implement an API to help the company with their analysis.

Implement the TweetCounts class:

TweetCounts() Initializes the TweetCounts object.
void recordTweet(String tweetName, int time) Stores the tweetName at the recorded time (in seconds).
List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) Returns a list of integers representing the number of tweets with tweetName in each time chunk for the given period of time [startTime, endTime] (in seconds) and frequency freq.

freq is one of "minute", "hour", or "day" representing a frequency of every minute, hour, or day respectively.

Input & Output

Example 1 — Basic Tweet Recording and Querying

$ Input: operations = ["TweetCounts","recordTweet","recordTweet","getTweetCountsPerFrequency"], params = [[],["tweet3",0],["tweet3",60],["minute","tweet3",0,59]]

› Output: [null,null,null,[1]]

💡 Note: Initialize TweetCounts, record tweet3 at time 0, record tweet3 at time 60, then query minute frequency for tweet3 from 0 to 59. Only the tweet at time 0 falls in range [0,59].

Example 2 — Multiple Time Chunks

$ Input: operations = ["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency"], params = [[],["tweet3",0],["tweet3",60],["tweet3",120],["minute","tweet3",0,179]]

› Output: [null,null,null,null,[1,1,1]]

💡 Note: Record tweets at times 0, 60, 120. Query minute frequency from 0 to 179 creates chunks [0,59],[60,119],[120,179], each containing 1 tweet.

Example 3 — Hour Frequency with Multiple Tweets

$ Input: operations = ["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency"], params = [[],["tweet1",100],["tweet1",3700],["tweet1",7300],["hour","tweet1",0,7199]]

› Output: [null,null,null,null,[2]]

💡 Note: Record tweets at 100, 3700, 7300. Query hour frequency [0,7199] creates one chunk [0,3599] containing tweets at 100 and 3700 (7300 is outside range).

Constraints

0 ≤ time ≤ 10⁹
0 ≤ startTime ≤ endTime ≤ 10⁹
freq is one of "minute", "hour", or "day"
At most 10⁴ calls to recordTweet and getTweetCountsPerFrequency

Visualization

Tap to expand

Understanding the Visualization

Record Tweets

Store tweet timestamps grouped by name

Create Chunks

Divide time range into frequency-based chunks

Count Per Chunk

Return array of counts for each time chunk

Key Takeaway

🎯 Key Insight: Keep timestamps sorted per tweet name to enable fast binary search for range counting

Asked in

G Google 15 a Amazon 12 f Facebook 8 t Twitter 10

The key insight is to use a HashMap to group timestamps by tweet name, and maintain them in sorted order for efficient range queries. The optimized approach uses binary search to find timestamp ranges in O(log n) time per chunk. Best approach: Binary Search with Time: O(c × log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Linear Search	O(n × c)	O(n)	Store all tweets in a list and scan linearly for each query
Optimized - Binary Search	O(c × log n)	O(n)	Keep timestamps sorted and use binary search for range counting

Brute Force - Linear Search — Algorithm Steps

Store all tweet timestamps in lists grouped by name
For each query, scan all timestamps linearly
Count tweets falling in each time chunk

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Tweets

Add timestamps to lists by tweet name

Linear Search

For each chunk, scan all timestamps

Count Matches

Count timestamps within chunk range

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TWEETS 1000
#define MAX_NAME_LEN 100

typedef struct {
    char names[MAX_TWEETS][MAX_NAME_LEN];
    int times[MAX_TWEETS];
    int count;
} TweetCounts;

TweetCounts* tweetCountsCreate() {
    TweetCounts* obj = (TweetCounts*)malloc(sizeof(TweetCounts));
    obj->count = 0;
    return obj;
}

void tweetCountsRecordTweet(TweetCounts* obj, char* tweetName, int time) {
    strcpy(obj->names[obj->count], tweetName);
    obj->times[obj->count] = time;
    obj->count++;
}

int* tweetCountsGetTweetCountsPerFrequency(TweetCounts* obj, char* freq, char* tweetName, int startTime, int endTime, int* returnSize) {
    int interval;
    if (strcmp(freq, "minute") == 0) interval = 60;
    else if (strcmp(freq, "hour") == 0) interval = 3600;
    else interval = 86400;
    
    int* result = (int*)malloc(1000 * sizeof(int));
    *returnSize = 0;
    int current = startTime;
    
    while (current <= endTime) {
        int chunkEnd = (current + interval - 1 < endTime) ? current + interval - 1 : endTime;
        int count = 0;
        
        for (int i = 0; i < obj->count; i++) {
            if (strcmp(obj->names[i], tweetName) == 0 && obj->times[i] >= current && obj->times[i] <= chunkEnd) {
                count++;
            }
        }
        
        result[*returnSize] = count;
        (*returnSize)++;
        current += interval;
    }
    
    return result;
}

int main() {
    printf("[null,null,null,[0,2,1]]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × c)

n timestamps scanned × c time chunks per query

✓ Linear Growth

Space Complexity

O(n)

HashMap storing n tweet timestamps

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler