Tweet Counts Per Frequency
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach attempts to optimize the getTweetCountsPerFrequency method by avoiding a full scan of all timestamps. It maintains a list of timestamps for each tweet, similar to the brute-force method. However, to speed up queries, it sorts the list of timestamps on demand and then uses binary search to quickly find the start of the relevant time range [startTime, endTime]. After finding the starting point, it only iterates through the tweets within the specified range.
Algorithm
- Data Structure: Use a
HashMap<String, List<Integer>>to store tweet timestamps for eachtweetName, and aHashMap<String, Boolean>to track if a list is sorted. recordTweet(tweetName, time):- Add the
timeto the list corresponding totweetName. - Mark this list as unsorted.
- Add the
getTweetCountsPerFrequency(freq, tweetName, startTime, endTime):- Retrieve the list of timestamps for
tweetName. - If the list is marked as unsorted, sort it using
Collections.sort()and mark it as sorted. - Determine the time chunk
deltabased onfreq. - Calculate the number of chunks and initialize a result array/list with zeros.
- Use binary search (e.g.,
Collections.binarySearch) to find the index of the first timestamp that is greater than or equal tostartTime. - Iterate through the timestamps from this starting index.
- For each timestamp up to
endTime, calculate which time chunk it belongs to and increment the corresponding counter. - Stop iterating when a timestamp exceeds
endTime. - Return the list of counts.
- Retrieve the list of timestamps for
Walkthrough
The core idea is to trade a cheap recordTweet operation for a potentially expensive, but more targeted, getTweetCountsPerFrequency operation. We store timestamps in a List and use a separate flag to track whether the list is sorted.
When recordTweet is called, we simply append the new time to the list and set the isSorted flag for that tweetName to false. This makes recording a tweet an O(1) operation.
When getTweetCountsPerFrequency is called, we first check the isSorted flag. If it's false, we sort the entire list of timestamps, which takes O(N log N) time, where N is the number of tweets for that name. Once the list is sorted, we can efficiently find the first tweet in the [startTime, endTime] range using binary search in O(log N) time. From there, we iterate only through the relevant tweets until we pass endTime. This part of the process is efficient if the number of tweets in the range (M) is much smaller than the total number of tweets (N).
class TweetCounts { private Map<String, List<Integer>> tweets; private Map<String, Boolean> isSorted; public TweetCounts() { tweets = new HashMap<>(); isSorted = new HashMap<>(); } public void recordTweet(String tweetName, int time) { tweets.computeIfAbsent(tweetName, k -> new ArrayList<>()).add(time); isSorted.put(tweetName, false); } public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) { List<Integer> timestamps = tweets.get(tweetName); int delta = freq.equals("minute") ? 60 : freq.equals("hour") ? 3600 : 86400; int numChunks = (endTime - startTime) / delta + 1; int[] counts = new int[numChunks]; if (timestamps == null || timestamps.isEmpty()) { return new ArrayList<>(Collections.nCopies(numChunks, 0)); } if (!isSorted.getOrDefault(tweetName, false)) { Collections.sort(timestamps); isSorted.put(tweetName, true); } int startIdx = Collections.binarySearch(timestamps, startTime); if (startIdx < 0) { startIdx = -startIdx - 1; } else { // Handle duplicates, find the first occurrence while (startIdx > 0 && timestamps.get(startIdx - 1).equals(startTime)) { startIdx--; } } for (int i = startIdx; i < timestamps.size(); i++) { int time = timestamps.get(i); if (time > endTime) { break; } int index = (time - startTime) / delta; counts[index]++; } List<Integer> result = new ArrayList<>(numChunks); for (int count : counts) { result.add(count); } return result; }}Complexity
Time
- `recordTweet`: `O(1)` amortized time. - `getTweetCountsPerFrequency`: `O(N log N + M)` in the worst case for a single call if a sort is needed, where `N` is the number of tweets for the given name and `M` is the number of tweets in the query range. If the list is already sorted, it's `O(log N + M)`. The overall performance across many calls can be poor due to repeated sorting.
Space
O(T), where T is the total number of tweets recorded. We need to store every timestamp.
Trade-offs
Pros
recordTweetoperation is very fast, takingO(1)time.If
getTweetCountsPerFrequencyis called many times for the same set of tweets and the query ranges are small, subsequent calls after the initial sort are fast (O(log N + M)).
Cons
The sorting step (
O(N log N)) can be a significant performance bottleneck, especially ifgetTweetCountsPerFrequencyis called frequently after new tweets are recorded.The overall performance is unpredictable and highly dependent on the sequence of calls. In many common scenarios (like interleaved
recordTweetandgetcalls), it performs worse than the simpler brute-force approach.Standard
Collections.binarySearchmay not find the first occurrence of a timestamp if there are duplicates, requiring extra logic to find the true starting index.
This is a straightforward, brute-force approach. It uses a HashMap to associate each tweetName with an unsorted List of its recorded timestamps. When a tweet is recorded, its timestamp is simply appended to the corresponding list. When counts are requested, the method iterates through the entire list of timestamps for the given tweetName, checks if each timestamp falls within the [startTime, endTime] range, and if so, increments the count for the appropriate time chunk.
Algorithm
- Data Structure: Use a
HashMap<String, List<Integer>>where the key is thetweetNameand the value is a list of all timestamps for that tweet. The list is not kept in any specific order. recordTweet(tweetName, time):- Retrieve the list for the given
tweetName. If it doesn't exist, create a new one. - Add the
timeto the list.
- Retrieve the list for the given
getTweetCountsPerFrequency(freq, tweetName, startTime, endTime):- Determine the time chunk
delta(60 for minute, 3600 for hour, 86400 for day). - Calculate the number of chunks required for the interval
[startTime, endTime]and initialize a result array (or list) of that size with all zeros. - Retrieve the list of timestamps for the given
tweetName. - Iterate through every timestamp in the list.
- For each timestamp, check if it falls within the
[startTime, endTime]range. - If it does, calculate which time chunk it belongs to using the formula
index = (timestamp - startTime) / delta. - Increment the count for that chunk in the result array.
- After checking all timestamps, return the result array as a list.
- Determine the time chunk
Walkthrough
The implementation relies on a HashMap to store data, mapping tweet names to lists of integer timestamps. The recordTweet method is highly efficient, as adding an element to the end of an ArrayList is an amortized constant time operation.
The getTweetCountsPerFrequency method contains the main logic. First, it translates the frequency string ("minute", "hour", "day") into a chunk size in seconds. It then creates an integer array, counts, to hold the tweet counts for each chunk. The size of this array is determined by the total time span (endTime - startTime) and the chunk size. The method then performs a linear scan through all timestamps associated with the tweetName. For each timestamp, it verifies if it's within the query bounds. If it is, it computes the index of the chunk the tweet belongs to and increments the counter at that index. Finally, it converts the counts array into a List and returns it.
class TweetCounts { private 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 delta; if (freq.equals("minute")) { delta = 60; } else if (freq.equals("hour")) { delta = 3600; } else { // "day" delta = 86400; } int numChunks = (endTime - startTime) / delta + 1; int[] counts = new int[numChunks]; List<Integer> timestamps = tweets.get(tweetName); if (timestamps != null) { for (int time : timestamps) { if (time >= startTime && time <= endTime) { int index = (time - startTime) / delta; counts[index]++; } } } List<Integer> result = new ArrayList<>(numChunks); for (int count : counts) { result.add(count); } return result; }}Complexity
Time
- `recordTweet`: `O(1)` amortized time. - `getTweetCountsPerFrequency`: `O(N)`, where `N` is the number of tweets recorded for the given `tweetName`. This is because we must iterate through all of its timestamps.
Space
O(T), where T is the total number of tweets recorded across all names. Each timestamp is stored.
Trade-offs
Pros
Simple to understand and implement.
The
recordTweetoperation is very fast (O(1)amortized time).Performance is predictable, unlike approaches that involve conditional sorting.
Cons
getTweetCountsPerFrequencycan be inefficient if atweetNamehas a very large number of recorded tweets, as it must iterate through all of them, even those outside the query time range.
This is the most efficient and robust approach. It leverages a TreeMap, which is a sorted map implementation based on a Red-Black Tree. By storing timestamps as keys in a TreeMap, we get two key benefits: timestamps are automatically kept in sorted order, and we can efficiently query for a range of timestamps.
recordTweet involves an O(log N) insertion into the TreeMap. getTweetCountsPerFrequency becomes highly efficient because TreeMap provides a subMap method to get a view of the map for the range [startTime, endTime] in O(log N) time. We then only need to iterate over the M tweets that are actually in this range.
Algorithm
- Data Structure: Use a
HashMap<String, TreeMap<Integer, Integer>>. The outerHashMapmaps atweetNameto aTreeMap. TheTreeMapstores timestamps as keys and the count of tweets at that exact time as values.TreeMapautomatically keeps the keys (timestamps) sorted. recordTweet(tweetName, time):- Get the
TreeMapfor thetweetName. - Insert or update the entry for the given
time, incrementing its count. This operation is efficient due to the balanced binary search tree structure of theTreeMap.
- Get the
getTweetCountsPerFrequency(freq, String tweetName, int startTime, int endTime):- Get the
deltaand initialize thecountsarray as in other approaches. - Retrieve the
TreeMapfor thetweetName. - Use the
TreeMap.subMap(startTime, true, endTime, true)method to get a view of only the entries within the desired time range. This is a very efficient operation. - Iterate through the entries in this sub-map.
- For each entry (timestamp and its count), calculate the chunk index and add the count to the
countsarray. - Return the list of counts.
- Get the
Walkthrough
This approach uses a HashMap to map tweetName to a TreeMap. The TreeMap is the key to efficiency here. It stores timestamps as its keys and the number of tweets at that specific timestamp as its values. Since TreeMap is a balanced binary search tree, it maintains its keys in sorted order.
When recordTweet is called, we find the correct TreeMap for the tweetName and update the count for the given time. This put or merge operation on a TreeMap takes O(log N) time, where N is the number of distinct timestamps for that tweet name.
When getTweetCountsPerFrequency is called, we first get the TreeMap of timestamps. The crucial step is calling timestamps.subMap(startTime, true, endTime, true). This method returns a view of the portion of the map whose keys are in the specified range, without copying any data. The operation itself is fast (O(log N)). We then iterate only over this smaller sub-map. For each timestamp and its associated count in the sub-map, we calculate its chunk index and update our result array. This avoids scanning irrelevant timestamps, making the query very fast.
class TweetCounts { private Map<String, TreeMap<Integer, Integer>> tweets; public TweetCounts() { tweets = new HashMap<>(); } public void recordTweet(String tweetName, int time) { tweets.computeIfAbsent(tweetName, k -> new TreeMap<>()) .merge(time, 1, Integer::sum); } public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) { int delta; if (freq.equals("minute")) { delta = 60; } else if (freq.equals("hour")) { delta = 3600; } else { // "day" delta = 86400; } int numChunks = (endTime - startTime) / delta + 1; int[] counts = new int[numChunks]; TreeMap<Integer, Integer> timestamps = tweets.get(tweetName); if (timestamps != null) { Map<Integer, Integer> subMap = timestamps.subMap(startTime, true, endTime, true); for (Map.Entry<Integer, Integer> entry : subMap.entrySet()) { int time = entry.getKey(); int count = entry.getValue(); int index = (time - startTime) / delta; counts[index] += count; } } List<Integer> result = new ArrayList<>(numChunks); for (int count : counts) { result.add(count); } return result; }}Complexity
Time
- `recordTweet`: `O(log N)`, where `N` is the number of distinct timestamps for the `tweetName`. - `getTweetCountsPerFrequency`: `O(log N + M)`, where `N` is the number of distinct timestamps for the `tweetName` and `M` is the number of distinct timestamps within the `[startTime, endTime]` range.
Space
O(D), where D is the total number of *distinct* timestamps recorded. If many tweets occur at the same time, this can be more space-efficient than storing every single timestamp.
Trade-offs
Pros
Efficient for both
recordTweetandgetTweetCountsPerFrequencyoperations.Scales well as the number of tweets increases due to logarithmic time complexity.
Best approach for handling queries over small time ranges within a large dataset of tweets.
Cons
Slightly more complex to implement compared to list-based approaches.
TreeMaphas a higher memory overhead per entry than anArrayList.
Solutions
Solution
class TweetCounts { private Map < String , TreeMap < Integer , Integer >> data = new HashMap <>(); public TweetCounts () { } public void recordTweet ( String tweetName , int time ) { data . putIfAbsent ( tweetName , new TreeMap <>()); var tm = data . get ( tweetName ); tm . put ( time , tm . getOrDefault ( time , 0 ) + 1 ); } public List < Integer > getTweetCountsPerFrequency ( String freq , String tweetName , int startTime , int endTime ) { int f = 60 ; if ( "hour" . equals ( freq )) { f = 3600 ; } else if ( "day" . equals ( freq )) { f = 86400 ; } var tm = data . get ( tweetName ); List < Integer > ans = new ArrayList <>(); for ( int i = startTime ; i <= endTime ; i += f ) { int s = 0 ; int end = Math . min ( i + f , endTime + 1 ); for ( int v : tm . subMap ( i , end ). values ()) { s += v ; } ans . add ( s ); } return ans ; } } /** * Your TweetCounts object will be instantiated and called as such: * TweetCounts obj = new TweetCounts(); * obj.recordTweet(tweetName,time); * List<Integer> param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime); */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); */from sortedcontainers import SortedList class TweetCounts : def __init__ ( self ): self . d = { "minute" : 60 , "hour" : 3600 , "day" : 86400 } self . data = defaultdict ( SortedList ) def recordTweet ( self , tweetName : str , time : int ) -> None : self . data [ tweetName ]. add ( time ) def getTweetCountsPerFrequency ( self , freq : str , tweetName : str , startTime : int , endTime : int ) -> List [ int ]: f = self . d [ freq ] tweets = self . data [ tweetName ] t = startTime ans = [] while t <= endTime : l = tweets . bisect_left ( t ) r = tweets . bisect_left ( min ( t + f , endTime + 1 )) ans . append ( r - l ) t += f return ans # Your TweetCounts object will be instantiated and called as such: # obj = TweetCounts() # obj.recordTweet(tweetName,time) # param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.