Top k most frequent number in stream

#1

Can you explain this ques. to me? I also feel that sample input is wrong. Why is there a 2 followed by 5(n)?

#2

Hi @MadHawk
In this problem you are supposed to output atmost k integers on every iteration from the input you have taken so far.
Let us dry run the sample input given in the question for better understanding

Sample Input:
1
5 2
5 1 3 5 2
Sample Output:
5 1 5 1 3 5 1 5 1

Let us say store the input in an array named A

No of testcases = 1
Given n = 5 (We will get 5 integer elements in our array)
k = 2 (We have to output at max 2 integers on every iteration)

Iteration 1 :
Input : 5
A = {5}
Output : 5
Explanation : Since there is only one integer with frequency = 1 , we output it

Iteration 2 :
Input : 1
A = {1,5}
Output : 1 5
Explanation : Since there are two elements in A , we output them in sorted order

Iteration 3 :
Input : 3
A = {1,3,5}
Output : 1 3
Explanation : We output k = 2 elements from the array. Since frequency of all elements is the same , we output them in sorted order and 1 and 3 being the smallest gets printed

Iteration 4 :
Input : 5
A = {1,3,5,5}
Output : 5 1
Explanation : 5 has the highest frequency in the array so it gets printed first . Then the remaining elements having the same frequency get printed in the sorted order. Since we only have to print k=2 elements , only 5 and 1 get printed.

Iteration 5 :
Input : 2
A = {1,2,3,5,5}
Output : 5 1
Explanation : 5 still has the highest frequency and 1 being the smallest of the remaining elements gets to be printed .

Final Output : 5 1 5 1 3 5 1 5 1

I hope this clears your doubt and helps you understand the question.

2 Likes
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.