1348. Tweet Counts Per Frequency

Tweet Counts Per Frequency (LeetCode 1348) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

How to solve Tweet Counts Per Frequency

Tweet Counts Per Frequency is a Data Structure Design problem, part of Design Patterns. Design and implement data structures: LRU cache, LFU cache, HashMap, and specialized structures.

Work towards the solution in these steps:

1. Consider how to efficiently store and organize tweets by their name and timestamp to support quick retrievals.
2. Think about mapping each tweet name to a sorted list of its tweet times to facilitate range queries.
3. To count tweets per frequency, partition the given time interval into chunks based on the frequency and count how many tweets fall into each chunk.

The reference solution runs in O(N log N + Q log N) time and O(N) space.

The Tweet Counts Per Frequency solution and editorial walks through the full approach with reference code.

Problem statement

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 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 <= 109

- 0 <= endTime - startTime <= 104

- There will be at most 104 calls in total to recordTweet and getTweetCountsPerFrequency.

Topics and companies

Topics: Hash Table, Binary Search, Design, Sorting, Ordered Set.

Reported in interviews at Twitter.

How to practise Tweet Counts Per Frequency on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N log N + Q log N) time and O(N) space.

Open Tweet Counts Per Frequency in the code editor, or read the Tweet Counts Per Frequency editorial for a worked solution with its approach and complexity analysis.

Where Tweet Counts Per Frequency sits in the DSA pattern sheet

• Design Patterns pattern guide
• Design (General/Specific) subpattern
• The full DSA patterns sheet

Problems related to Tweet Counts Per Frequency

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

• All O`one Data Structure — Hard, same subpattern
• Design a Stack With Increment Operation — Medium, same subpattern
• Design a Text Editor — Hard, same subpattern
• Design Circular Deque — Medium, same subpattern
• Design Circular Queue — Medium, same subpattern
• Design Compressed String Iterator — Easy, same subpattern

Tweet Counts Per Frequency FAQ