Not able to understand question

#1

Please explain question and given test case
not able to understand.

#2

We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency.

eg:
{5, 2, 1, 3, 2} k = 2
5 is added
ans : 5
add 2 { array has 2 & 5 both with feq 1 print in increasing order} print 2 5

add 1 { array had 1 & 2 & 5 all with freq 1 so print in increasing order} print 1 2
add 3 { array had 1 & 2 & 5 & 3 all with freq 1 so print in increasing order} print 1 2 [ smalles k elements]
add 2 { array has 2-twos 1 => ( 1 3 5 ) ) first print 2[highest freq] , then 1 [smalles no]

so final o/p
5 2 5 1 2 1 2 2 1

1 Like
#3

How to solve this using Heaps?

#4

1.Iterate through the array which contains stream of numbers.
2.To keep track of top k elements, make a top vector of size k+1.
3.For every element in the stream increase its frequency and store it in the last position of top vector. We can use hashing for efficiently fetching frequency of an element and increasing it.
4.Now find the position of element in top vector and iterate from that position to zero. For finding position we can make use of the find() function in C++ STL, it returns an iterator pointing to element if found in the vector.
5.And make that list of k+1 numbers sorted according to frequency and their value.
6.Print top k elements form top vector.
7.Repeat the above steps for every element in the stream.

u could use a vector & map to keep sorted
but using a heap with customised sort function could help u [ priority queue]

#5

@shivansh.sm1 do you have any further doubts?

#6

pls share the code using heaps.

#7

@shivansh.sm1 we have shared the logic for solving the question using heaps, have you tried writing the code on your own? I would suggest doing that since it is the best way to learn. I can help if you are stuck.

#8

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.