Top K Most Frequent elements in a stream

#1

Pls help find the mistake in my code https://ide.codingblocks.com/s/104717

#2

@ratik_puri
Try this testcase
Input :
2
5 3
5 1 5 2 1
8 3
5 1 3 5 2 1 1 3

Expected Output :
5 1 5 5 1 5 1 2 1 5 2
5 1 5 1 3 5 5 1 3 5 1 2 1 5 2 1 5 2 1 3 5

Your Output :
5 5 1 5 5 2 1
5 3 1 5 5 3 1 5 5 3 2 1 5 1 5 3 2 1 1 5 1 5 3 2 1

Note that you are also missing an endl statement for each testcase so this output was in a single line. It was still wrong after the endl though so make the according changes and let me know if you are not able to figure out the problem with this.

#3

Still not able to solve

#4

@ratik_puri
You are printing the contents of entire heap in the loop which starts at Line No. 64. You are only supposed to print atmost k elements in each iteration. I don’t think you grasped the question properly. Let me explain the problem.

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.

#5

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.