Last Updated: 21 Apr, 2021
Count Messages
Easy
Asked in company
You are given a task to do some analysis for a messaging service application.
You are given series of queries of two types :
1 'user' 'time', denoting that the query is of type-1, and a person named 'user' has received a message at the time 'time'.
2 ‘l’ ‘r’ 'user' ‘k’, denoting that the query is of type-2, and [l, r] being a range of time, 'user' is a name of a person, ‘k’ is the chunk size.
For query of type-2 you need to print a list of integers, representing the number of messages the person 'user' received in each of the time chunks of size ‘k’, in time period [l, r].
Example:
If [l, r] = [10, 100] and ‘k’ = 35, then the chunks of size ‘k’ for the range will be: [10, 44], [45, 79], [80, 100]. You need to return a list of size 3 here for each of these 3 chunks, where you tell the number of times a message is received by the person in that particular chunk (or sliced range).
Note :
Here you will implment function receiveMessage(user,time) for query of type-1, and implement function getMessageCount(l,r,user,k) for query fo type-2.
Input Format :
The first line contains an integer ‘q’, denoting the number of queries.
The next ‘q’ lines contain the queries of type-1 or type-2. The two types of queries are:
1 'user' 'time', denoting that the query is of type-1, and a person named 'user' has received a message at the time 'time'.
2 ‘l’ ‘r’ 'user' ‘k’, denoting that the query is of type-2, and [l, r] being a range of time, 'user' is a name of a person, ‘k’ is the chunk size.
Output Format :
For each query of type-2 return a list of integers, representing the number of messages the person in the time chunks.
Note:
Don't print anything it has already been taken care of. Just implement the given functions.
Constraints :
1 <= q <= 100
1 <= |user| <= 10
1 <= k <= 100
0 <= l, r , time <= 3000
|user| denotes the length of the string ‘user’
Time Limit: 1 sec
Approaches
For every user, you can create a multi-set for the timestamps of messages which are received.
In the type-1 query, what you need to do is just insert the timestamp into the multiset belonging to the user.
In the type-2 query, you will iterate over the multiset of the user and check if the current timestamp is between ‘l’ and ‘r’, if it is then it must belong to one of the chunks, find the chunk index, and increment its value.
To find the chunk index: if l = 10, r =100, and k = 35 then chunks will be [10, 44], [45, 79], [80, 100], chunk index of time ‘t’ will be floor( (t - l) / k).
Example: floor( (40 - 10) / 35 ) = 0, and floor( (45 - 10) / 35 ) = 1.
The number of chunks in the solution will be (r-l)/k + 1.
Algorithm:
Create a hashmap ‘mp’, mapping strings to multiset. This is done to create a multi-set for each user.
Function receiveMessage(user, time):
- Insert ‘time’ in the multiset for the ‘user’. mp[user].insert(time).
Function getMessageCount(l, r, user, k):
- Create a list ‘ans’ of size (r - l) / k +1, and initialize all indexes with ‘0’.
- Iterate over multiset of ‘user’, mp[user]. And check if the current timestamp is between [l, r], if it is then increment ans[chunkIndex], where chunkIndex = floor( (timestamp - l) / k ).
- Return ‘ans’.