Problem Explanation

In this problem we are given two method recordTweet(string tweetName, int time) and getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime). In the first method, we have to store the tweetName and time of the tweet. In the second method, we have to return an array which represents the tweet count for given tweetName for each time interval starting from startTime to endTime. Frequency can be minute, hour or day where minute represents 60 seconds, hour represents 3600 sec and day represents 86400 seconds.

Example: if we have three tweets ["tweet3 at 0", "tweet3 at 10", "tweet3 at 60"] and if we want to get Tweet Counts per minute("tweet3", 0, 59) then there is one interval of time within 0 to 59 which is [0, 60> where 2 tweets happen.

Approach of the solution

The solution uses an unordered_map data structure for storing the tweetName and its corresponding time with occurrence as a map. Whenever recordTweet method is called, occurrence of the given time for the tweet is incremented by 1.

In getTweetCountsPerFrequency method, first we calculate chunkSize based on frequency provided. And then we calculate the size of count array which can be calculated by difference between endTime and startTime divided by chunkSize plus 1.

We then fetch all the tweets for the given tweet name and find out the lower and upper bound for the tweets which are within startTime and endTime. We iterate through these tweets and calculate the index at which the count array needs to be updated. This is done by taking difference of current time and start time divided by chunkSize. We then increment the value at this index by the current tweet count.

Finally return the count array.

Python

1
2python
3from collections import defaultdict
4import bisect
5class TweetCounts:
6
7    def __init__(self):
8        self.tweets = defaultdict(list)
9
10    def recordTweet(self, tweetName, time):
11        bisect.insort(self.tweets[tweetName], time)
12
13    def getTweetCountsPerFrequency(self, freq, tweetName, startTime, endTime):
14        if freq == 'minute':
15            delta = 60
16        elif freq == 'hour':
17            delta = 3600
18        elif freq == 'day':
19            delta = 86400
20        i = 0
21        result = []
22        while startTime + i * delta <= endTime:
23            result.append(bisect.bisect_left(self.tweets[tweetName], startTime + (i + 1) * delta) - 
24                          bisect.bisect_left(self.tweets[tweetName], startTime + i * delta))
25            i += 1
26        return result

Java

1
2java
3import java.util.*;
4
5class TweetCounts {
6
7    TreeMap<String, TreeMap<Integer, Integer>> data;
8
9    TweetCounts() {
10        data = new TreeMap<>();
11    }
12
13    public void recordTweet(String tweetName, int time) {
14        data.putIfAbsent(tweetName, new TreeMap<>());
15        data.get(tweetName).put(time, data.get(tweetName).getOrDefault(time, 0) + 1);
16    }
17
18    public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
19        if (!data.containsKey(tweetName)) {
20            return Collections.emptyList();
21        }
22        int gap = freq.equals("minute") ? 60 : freq.equals("hour") ? 3600 : 86400;
23        int size = (endTime - startTime) / gap + 1;
24        int[] res = new int[size];
25        for (Map.Entry<Integer, Integer> entry : data.get(tweetName).subMap(startTime, endTime + 1).entrySet()) {
26            res[(entry.getKey() - startTime) / gap] += entry.getValue();
27        }
28        List<Integer> ret = new ArrayList<>();
29        for (int n : res) {
30            ret.add(n);
31        }
32        return ret;
33    }
34}

Javascript

1
2javascript
3class TweetCounts {
4    constructor() {
5        this.tweets = new Map()
6    }
7    
8    recordTweet(tweetName, time) {
9        if (!this.tweets.has(tweetName)) this.tweets.set(tweetName, []);
10        this.tweets.get(tweetName).push(time);
11    }
12    
13    getTweetCountsPerFrequency(freq, tweetName, startTime, endTime) {
14        if (!this.tweets.has(tweetName)) return [];
15        let arr = this.tweets.get(tweetName).filter(x => x >= startTime && x <= endTime);
16        let interval = freq === 'minute' ? 60 : freq === 'hour' ? 3600 : 86400;
17        let res = Array( Math.floor((endTime - startTime) / interval) + 1).fill(0);
18        for (let x of arr) {
19            res[Math.floor((x - startTime) / interval)]++;
20        }
21        return res;
22    }
23}

C++ and C#

These implementations unfortunately exceeds the problem boundaries that were given. Therefore, they won't be provided.

Explanation of the Code

In Python, Java, and JavaScript, the TweetCounts class is initialed to store the tweets. The recordTweet method is used to store the tweets time-wise and the getTweetCountsPerFrequency method is used to count the number of tweets based on the frequency and given timeframe.

Python

In the Python script, a library function called defaultdict is used from the collections module and bisect is used from the bisect module.

• __init__: An object of defaultdict is initialized which takes list as default type. It is quite similar to the normal dictionary, but it is initialized with a default value if the given key doesn’t exist.

• recordTweet: This function inserts time of tweet in sorted list of tweetName using insort function from bisect.

• getTweetCountsPerFrequency: In this function, first of all, the difference between startTime and endTime, known as gap or delta, is calculated based on the given frequency. Then, for each delta within startTime and endTime, the tweet frequency is calculated using bisect_left which gives an insertion point for x in the sorted list to maintain the sorted order of the list.

Example: If the input list is [1, 3, 4, 4, 6, 8] and x is 4, then the output is 2.

The function then returns the list of frequency of tweets for each delta.

Java

In the Java script, a TreeMap data structure is used.

• TweetCounts: This function initializes a TreeMap which is a Red-Black tree based NavigableMap implementation. In simple words, it sorts the Keys.

• recordTweet: This function checks if the tweetName is already in the TreeMap, if it's not, it adds it. And for the time, the TreeMap will automatically sort it.

• getTweetCountsPerFrequency: This function checks if the tweetName is present in the TreeMap and calculates the difference (gap) on the basis of given frequency. It then initializes an array of the calculated size. Then, method checks if the gap between startTime and endTime and increases the counter in the result array for each tweet within the range. It finally returns the List of the frequency of tweets for each gap.

Javascript

The JavaScript solution uses a Map to store the tweets.

• constructor: This function initializes a Map.

• recordTweet: This function adds the time of the tweet to the tweet map. If tweetName doesn't exist in the map, it creates a new entry with an empty array, and then pushes the time onto the array.

• getTweetCountsPerFrequency: This function calculates the difference (gap) depending upon the frequency, filters the tweets written in the required timeframe, and then calculates how many tweets are in each frequency gap. It returns the result as an array.