Tweet Counts Per Frequency solution and explanation
Google
9 more videos on this problem
Leetcode 1348. Tweet Counts Per FrequencyFraz · 6:34 · 5K views
Twitter Coding Interview Question | Leetcode 1348 | Tweet Counts Per FrequencyWorkWithGoogler · 7:12 · 1K views
Tweet Counts Per Frequency(Leetcode 1348)Coding Interviews · 14:50 · 704 views
Leetcode [1348] Tweet Counts Per FrequencySDE Skills · 33:00 · 601 views
Leetcode [1348] Tweet Counts Per FrequencySDE Skills · 26:35 · 297 views
Problem 1348. Tweet Counts Per FrequencyMySixPack · 1:13:34 · 274 views
小飞羊 LeetCode 1348. Tweet Counts Per Frequency [套路得人薪C++]Willy小飞羊 DJ · 6:47 · 253 views
Leetcode Problem 1348Leetcode Solver · 9:46 · 233 views
1348. Tweet Counts Per FrequencyMuerde un zombie · 14:19 · 166 views
[LeetCode] 1348. Tweet Counts Per Frequency (medium)개발자영맨(bluedawnstar) · 16:15 · 149 views
The problem
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 (10000 in the above example).
Design and implement an API to help the company with their analysis.
Implement the TweetCounts class:
TweetCounts()Initializes theTweetCountsobject.void recordTweet(String tweetName, int time)Stores thetweetNameat the recordedtime(in seconds).List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime)Returns a list of integers representing the number of tweets withtweetNamein each time chunk for the given period of time[startTime, endTime](in seconds) and frequencyfreq.freqis one of"minute","hour", or"day"representing a frequency of every minute, hour, or day respectively.
Example:
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
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0); // New tweet "tweet3" at time 0
tweetCounts.recordTweet("tweet3", 60); // New tweet "tweet3" at time 60
tweetCounts.recordTweet("tweet3", 10); // New tweet "tweet3" at time 10
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]; chunk [0,59] had 2 tweets
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2,1]; chunk [0,59] had 2 tweets, chunk [60,60] had 1 tweet
tweetCounts.recordTweet("tweet3", 120); // New tweet "tweet3" at time 120
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210); // return [4]; chunk [0,210] had 4 tweets
Constraints:
0 <= time, startTime, endTime <= 1090 <= endTime - startTime <= 104- There will be at most
104calls in total torecordTweetandgetTweetCountsPerFrequency.
Approach overview
Problem Overview: Design a data structure that records tweet timestamps and returns how many tweets occurred in each time bucket (minute, hour, or day) within a given range. The main challenge is efficiently storing timestamps and answering repeated range queries.
Approach 1: Brute Force with Unsorted List (O(n) query, O(1) insert)
Store every timestamp for a tweet in a plain list inside a hash table keyed by tweet name. When getTweetCountsPerFrequency is called, iterate through all stored timestamps and count how many fall into each interval bucket. This approach works because insertion is trivial, but every query scans the entire list. Time complexity is O(n) per query and space complexity is O(n). It works for small inputs but becomes slow when tweets accumulate.
Approach 2: Sorted List with Binary Search (O(log n + k) query, O(log n) insert)
Maintain a sorted list of timestamps for each tweet. When recording a tweet, insert the timestamp while keeping the list sorted (or append and sort lazily). During a query, use binary search to find the first timestamp within the requested range, then iterate through relevant timestamps to count them per bucket. Each bucket corresponds to a fixed interval (60 seconds for minute, 3600 for hour, 86400 for day). This reduces unnecessary scanning because timestamps before the range are skipped. Query complexity becomes O(log n + k) where k is the number of timestamps inside the range, and space complexity remains O(n).
Approach 3: TreeMap for Efficient Range Queries (O(log n + k) query, O(log n) insert)
Use a TreeMap (or any ordered set structure) to keep timestamps sorted automatically. Each tweet name maps to a TreeMap where keys are timestamps and values are occurrence counts. Recording a tweet inserts into the TreeMap in O(log n). For queries, use subMap(startTime, endTime) to retrieve only timestamps in the range, then distribute them into frequency buckets. This avoids scanning unrelated timestamps and keeps operations efficient even with large datasets.
Recommended for interviews: The sorted structure approach (Sorted List or TreeMap) is what interviewers typically expect. The brute force version demonstrates understanding of the problem, but the optimized design shows you know how to combine ordered data structures with range queries. TreeMap is especially clean in Java because subMap directly provides the required time slice.
Approach 1: Using Sorted List
This approach uses a sorted list to maintain tweet times for each tweet name. When querying, it computes the number of time chunks based on frequency and counts tweets within each chunk.
class TweetCounts:
def __init__(self):
self.tweets = {}
def recordTweet(self, tweetName: str, time: int) -> None:
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[int]:
if tweetName not in self.tweets:
return []
freq_map = {'minute': 60, 'hour': 3600, 'day': 86400}
interval = freq_map[freq]
num_chunks = (endTime - startTime) // interval + 1
counts = [0] * num_chunks
for time in self.tweets[tweetName]:
if startTime <= time <= endTime:
index = (time - startTime) // interval
counts[index] += 1
return countsimport java.util.*;
class TweetCounts {
private Map<String, List<Integer>> tweetMap;
public TweetCounts() {
tweetMap = new HashMap<>();
}
public void recordTweet(String tweetName, int time) {
tweetMap.computeIfAbsent(tweetName, k -> new ArrayList<>()).add(time);
}
public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
List<Integer> result = new ArrayList<>();
if (!tweetMap.containsKey(tweetName)) {
return result;
}
int interval = 0;
switch (freq) {
case "minute":
interval = 60;
break;
case "hour":
interval = 3600;
break;
case "day":
interval = 86400;
break;
default:
throw new IllegalArgumentException("Invalid frequency");
}
List<Integer> times = tweetMap.get(tweetName);
int chunks = ((endTime - startTime) / interval) + 1;
int[] countChunks = new int[chunks];
for (int time : times) {
if (time >= startTime && time <= endTime) {
int index = (time - startTime) / interval;
countChunks[index]++;
}
}
for (int count : countChunks) {
result.add(count);
}
return result;
}
}This solution uses a dictionary to store lists of tweet times, indexed by tweet name. For each call to getTweetCountsPerFrequency, it calculates the appropriate interval for the given frequency, and uses a loop to count the number of tweets in each time chunk. The counts are stored in a list, which is returned. The use of direct indexing ensures that we obtain count results efficiently.
Time Complexity: O(n), where n is the number of tweets of the specified tweet name. We iterate through each relevant time once.
Space Complexity: O(m), where m is the number of recorded times, as we store them in a dictionary.
Approach 2: Using TreeMap for Efficient Range Querying
The second approach makes use of a TreeMap, which allows us to efficiently manage and query a sorted set of elements. This is particularly useful for efficiently accessing the times that fall within the specific chunks, taking advantage of logarithmic time complexity for lookups.
import java.util.*;
class TweetCounts {
private Map<String, TreeMap<Integer, Integer>> tweetMap;
public TweetCounts() {
tweetMap = new HashMap<>();
}
public void recordTweet(String tweetName, int time) {
tweetMap.putIfAbsent(tweetName, new TreeMap<>());
TreeMap<Integer, Integer> timeMap = tweetMap.get(tweetName);
timeMap.put(time, timeMap.getOrDefault(time, 0) + 1);
}
public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
List<Integer> result = new ArrayList<>();
if (!tweetMap.containsKey(tweetName)) {
return result;
}
int interval = 0;
switch (freq) {
case "minute":
interval = 60;
break;
case "hour":
interval = 3600;
break;
case "day":
interval = 86400;
break;
default:
throw new IllegalArgumentException("Invalid frequency");
}
TreeMap<Integer, Integer> timeMap = tweetMap.get(tweetName);
int start = startTime;
while (start <= endTime) {
int end = Math.min(start + interval - 1, endTime);
int count = 0;
for (Map.Entry<Integer, Integer> entry : timeMap.subMap(start, true, end, true).entrySet()) {
count += entry.getValue();
}
result.add(count);
start += interval;
}
return result;
}
}This Java solution employs a more sophisticated data structure, a TreeMap, which keeps entries sorted by their keys. For each tweet, the TreeMap records the count of tweets at exact times. The range query to obtain counts in a given chunk is efficiently handled by TreeMaps' subMap method, which provides a view of the portion of the map whose keys range from start (inclusive) to end (inclusive).
Time Complexity: O((n + k) log m) per query, where n is the number of timestamps in the range query, k is the number of chunks, and m is the size of the timestamp map.
Space Complexity: O(m), where m is the number of unique timestamps stored in the TreeMap.
Approach 3: Default Approach
class TweetCounts {
public:
TweetCounts() {
}
void recordTweet(string tweetName, int time) {
data[tweetName].insert(time);
}
vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
int f = 60;
if (freq == "hour")
f = 3600;
else if (freq == "day")
f = 86400;
vector<int> ans((endTime - startTime) / f + 1);
auto l = data[tweetName].lower_bound(startTime);
auto r = data[tweetName].upper_bound(endTime);
for (; l != r; ++l) {
++ans[(*l - startTime) / f];
}
return ans;
}
private:
unordered_map<string, multiset<int>> data;
};
/**
* Your TweetCounts object will be instantiated and called as such:
* TweetCounts* obj = new TweetCounts();
* obj->recordTweet(tweetName,time);
* vector<int> param_2 = obj->getTweetCountsPerFrequency(freq,tweetName,startTime,endTime);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Using Sorted List | Time Complexity: O(n), where n is the number of tweets of the specified tweet name. We iterate through each relevant time once. |
| Using TreeMap for Efficient Range Querying | Time Complexity: O((n + k) log m) per query, where n is the number of timestamps in the range query, k is the number of chunks, and m is the size of the timestamp map. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Unsorted List | Insert: O(1), Query: O(n) | O(n) | Simple implementation when number of tweets per user is small |
| Sorted List + Binary Search | Insert: O(log n), Query: O(log n + k) | O(n) | General solution when many range queries are expected |
| TreeMap / Ordered Map | Insert: O(log n), Query: O(log n + k) | O(n) | Best choice in Java for clean range queries using subMap |
Frequently asked questions
Is Tweet Counts Per Frequency easy or hard?
Tweet Counts Per Frequency is a medium-level design problem. The logic is straightforward, but choosing the right data structure for efficient range queries and frequency bucketing makes it slightly more challenging than standard array problems.
Tweet Counts Per Frequency Python/Java solution
Python implementations usually maintain a sorted list of timestamps and use the bisect module for binary search. Java solutions often use TreeMap so timestamps remain ordered and subMap can quickly return the relevant range for counting.
How to solve Tweet Counts Per Frequency in O(log n + k)?
Store timestamps for each tweet in a sorted data structure. Use binary search (or TreeMap.subMap in Java) to quickly find the first timestamp within the range. Then iterate only through timestamps in that range and place them into frequency buckets based on the interval size.
What is the best approach for Tweet Counts Per Frequency?
The most practical solution stores timestamps in a sorted structure and performs range queries. A sorted list with binary search or a TreeMap allows efficient retrieval of timestamps between startTime and endTime. Query complexity becomes O(log n + k), where k is the number of tweets in the requested interval.
Is Tweet Counts Per Frequency asked at Google/Amazon/Meta?
Design-style problems involving time-based counters and range queries frequently appear at companies like Google, Amazon, and Meta. This problem tests understanding of ordered data structures, efficient querying, and system-style API design.
What data structure is used in Tweet Counts Per Frequency?
Common implementations use a hash table to map tweet names to timestamp collections, combined with a sorted data structure. Options include a sorted list with binary search or a TreeMap (ordered map) for efficient range queries.
What is the time complexity of Tweet Counts Per Frequency?
Recording a tweet takes O(log n) time when using a sorted structure like a TreeMap or a sorted list insertion. Retrieving tweet counts takes O(log n + k) time because the algorithm first locates the range using binary search or ordered map operations, then iterates over timestamps within that range.