K most frequent number in a stream

#1

i am not able to understand the input format. please help me understanding the output and input.

#2

I/p
1st line T : no of test cases
2nd line: n , k : size of input array , k top elements to be printed
3rd line: n array elements

O/P
for each element i in 1:n:
print top k elements keeping in mind if no. of elements read till now are less than k then print ’ i ’ elements
eg :
5 2
5 1 3 5 2
for 5 since only 1 element is read, top 1 elemnt is printed to console
for 5,1 acc to q it has to be o/p in increasing order & acc to increasing frequency so 1 5 is printed
similary 1 3 (k = 2)(taking top 2 from increasing order of 1 3 5 )
for 5 1 3 5 ( freq{5,2} freq{1,1} freq{3,1} ) so since 5 has highest frequency so 5 is printed first then other element with same freq in increasing order upto k elements.

Hope this provides clarity. :slight_smile:

#3

can you explain me with an another example?

#5

Given array is arr[] = {5, 2, 1, 3, 2} and k = 4

  1. After reading 5, there is only one element 5 whose frequency is max till now. so print 5.
    2:After reading 2, we will have two elements 2 and 5 with same frequency. As 2, is smaller than 5 but their frequency is same so we will print 2 5.
    3: After reading 1, we will have 3 elements 1,2 and 5 with same frequency, so print 1 2 5.
    4: Similarly after reading 3, print 1 2 3 5
    5: After reading last element 2, since 2 has already occurred so we have now frequency of 2 as 2. So we keep 2 at the top and then rest of element with same frequency in sorted order. So print, 2 1 3 5.