Watch 10 video solutions for Tweet Counts Per Frequency, a medium level problem involving Hash Table, Binary Search, Design. This walkthrough by Fraz has 5,674 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[10,69], [70,129], [130,189], ..., [9970,10000][10,3609], [3610,7209], [7210,10000][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 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.
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 <= 104104 calls in total to recordTweet and getTweetCountsPerFrequency.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 | 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 |