Solve Leetcode Problems and Get Offers From Your Dream Companies||Tweets count per frequency

Problem 1348. Tweet Counts Per Frequency.

In this series, I am going to solve Leetcode medium problems live with my friend, which you can see on our youtube channel, Today we will do Problem Problem 1348. Tweet Counts Per Frequency.

A little bit about me, I have offers from Uber India and Amazon India in the past, and I am currently working for Booking.com in Amsterdam.

Problem Statement

Implement the class TweetCounts that supports two methods:

• recordTweet(string tweetName, int time)

  • Stores the tweetName at the recorded time (in seconds).

• getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)

  • Returns the total number of occurrences for the given tweetName per minute, hour, or day (depending on freq) starting from the startTime (in seconds) and ending at the endTime (in seconds).
  • freq is always minute, hour or day, representing the time interval to get the total number of occurrences for the given tweetName.
  • The first time interval always starts from the startTime, so the time intervals are [startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)> for some non-negative number i and delta (which depends on freq).

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);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10); // All tweets correspond to "tweet3" with recorded times at 0, 10 and 60.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]. The frequency is per minute (60 seconds), so there is one interval of time: 1) [0, 60> - > 2 tweets.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2, 1]. The frequency is per minute (60 seconds), so there are two intervals of time: 1) [0, 60> - > 2 tweets, and 2) [60,61> - > 1 tweet.
tweetCounts.recordTweet("tweet3", 120); // All tweets correspond to "tweet3" with recorded times at 0, 10, 60 and 120.
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210); // return [4]. The frequency is per hour (3600 seconds), so there is one interval of time: 1) [0, 211> - > 4 tweets.

Youtube Discussion

Solution

In this problem, we have to implement two methods. On is recordTweet which stores the tweet along with its timestamp and another one is getTweetsPerFrequenecy where we have to return no of tweets in some given frequency (minute, hour, day).

Here we will be using a HashMap to store the tweet data. The key is the title of the tweet and the value is a list which contains all the timestamps where this tweet is published.

In the recordTweet method, we store the tweet into the hashmap. This method runs in O(1) time complexity as the retrieval of the list from hashmap takes constant time.

The input frequency can be minute, hour and day. All the inputs are given in seconds. Therefore to calculate the frequency in a minute, hour and day terms we need to use different constants.

minute = 60 seconds

hour = 60 minutes = 3600 seconds

day = 24 hours = 24*3600 seconds

The getFreq method is used to calculate the occurrences of the tweet in different timeframes. We can visualize the problem as placing the tweets into different buckets. The bucket size depends on the frequency (minute, hour, day). We will find the unit timeframes in seconds depending upon the frequency.

eg : Start Time = 135 , End Time = 345 , freq = minutes

The bucket size will be 135-194 | 195-254 | 255-314 | 315-344

So we will place the tweets with different timestamps into these buckets. The index is found out by using the following formula :

index = (timestamp — startTime)/delta ; delta depends on the frequency

The final list is return in the method.

The java code along with a dry run of the example is given below. Also, the code is properly documented.

	class TweetCounts {
	// "TweetCounts", [] Initilize the hashMap
	// "recordTweet", ["tweet3",0] <"tweet3", [0]>
	// "recordTweet", ["tweet3",60] <"tweet3", [0,60]>
	// "recordTweet", ["tweet3",10] <"tweet3", [0,60,10]>
	// "getTweetCountsPerFrequency", ["minute","tweet3",0,59] no of buckets = (59-0)/60 + 1 = 1
	// count the tweet3 from 0-59 seconds,
	// i.e. 0 , 10 seconds . return [2]
	// "getTweetCountsPerFrequency", ["minute","tweet3",0,60] no of buckets = (60-0)/60 + 1 = 2
	// count the tweet3 from 0-59 seconds, 60-61 seconds
	// i.e. 0,10 | 60 seconds . return [2,1]
	// "recordTweet", ["tweet3",120] <"tweet3", [0,60,10,120]>
	// "getTweetCountsPerFrequency" ["hour","tweet3",0,210] as freq = hour,buckets = 210/3600 + 1 = 1
	// Count tweets from 0-3599 seconds and put them into the list
	//This hashmap contains all the tweets and their timestamps.
	HashMap<String,List<Integer>> hashMap;
	public TweetCounts() {
	//initilize the hashmap in the constructor
	hashMap = new HashMap<>();
	}
	//This method inserts a tweet into the hashmap.
	public void recordTweet(String tweetName, int time) {
	//If that tweet is present, we have to append the new time in the exisiting list.
	if (hashMap.containsKey(tweetName)){
	List<Integer> list = hashMap.get(tweetName);
	list.add(time);
	hashMap.put(tweetName,list);
	}
	else{
	//If the tweet is not present, then we have to create a new list and put the timestamp in that .
	List<Integer> list = new ArrayList<>();
	list.add(time);
	hashMap.put(tweetName,list);
	}
	}
	//This method acts as an utility method. We pass different parameters to the getFreq method depending upon the frequency.
	public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
	//delta value is set as 60 if the freq is minute. 1 minute = 60 seconds
	//delta value is set as 3600 if the freq is hour, 1 hour = 60*60 seconds
	//delta value is set as 3600*24 if the freq is day . 1 day = 24 hours = 24*3600 seconds
	if (freq.equals("minute"))
	return getFreq(60,startTime,endTime,tweetName);
	if (freq.equals("hour"))
	return getFreq(3600,startTime,endTime,tweetName);
	if (freq.equals("day"))
	return getFreq(3600*24,startTime,endTime,tweetName);
	else
	return null;
	}
	// This is the method where all the logic of this problem resides.
	//Here we can treat the timeframes as some buckets, and we will put those into their respective buckets with this method. eg : Suppose we are given a time frame we will find the total no of required buckets and place the tweets to their respective suppose.
	// eg : time frame : 0-210 seconds, frequency = minutes . Therefore we will divide it in buckets of 60 seconds.
	// 0-59 | 60-119 | 120-179 | 180-209
	// (210-0)/60 + 1 = 4 . So 4 should be the no of buckets .
	public List<Integer> getFreq(int delta,int startTime,int endTime,String tweetName){
	//length is the total no of buckets.
	int length = (endTime-startTime)/delta + 1;
	//This is the list which needs to be returned. It will contain the frequency of tweet .
	List<Integer> ans = new ArrayList<>();
	//We make a list of size length and initialize it with 0. As our timestamps are not sorted , we have to do this step. We don't know at what sequence our inputs are given.
	for (int i=0;i<length;i++)
	ans.add(0);
	//This gets the all the timestamps where this tweetName was made. We have to return total no of occurances for the given tweetName depending upon the frequency .
	List<Integer> timestamps = hashMap.get(tweetName);
	//SO we run a loop for each integer in the timestamps list and place them into their respective buckets. We have to count the no of tweets per bucket , therefore we are incrementing the value from that index.
	for (int timestamp : timestamps){
	//We check this condition so that the timestamp is in range of our timeframe.
	if(timestamp>=startTime && timestamp<=endTime){
	//Also the index of the bucket needs to be found out by using this . Because if the startTime is not zero , the range of the bucket will be different .
	// eg ::: startTime = 135 , endTime = 345 . freq = minutes
	//So the buckets should be 135-194| 195-254| 255-314 | 315- 344
	// So the respective indexs 0 | 1 | 2 | 3
	// Therefore the startTime needs to be substracted from the timeStamp.
	int index = (timestamp-startTime)/delta;
	ans.set(index,ans.get(index)+1);
	}
	}
	return ans;
	}

view raw TweetCounts.java hosted with ❤ by GitHub

The code for this problem can be found in the following repository.

webtutsplus / LeetCode

Thank You for reading and Follow this publication for more LeetCode problems!😃
Leetcode simplified

Sign up for Leetcode Simplified
By LeetCode Simplified

Get latest leetcode solution with youtube breakdown Take a look
You're an editor of Leetcode Simplified