Top k most frequent number in a stream...near to the soln

#1

plz tell me how to define functor in this question

#2

Hello @ynikhil1999,

Can you please give a clear description of you doubt?

#3

have just tried to make a custom comparator…
which will first see if there frequency are same …then it will sort them normally…
and if one’s frequency is greater that that element would be on top…
but i am not getting desored results…
so plzz tell me how to make a custom comparator of the above given configuration

#4

Hello @ynikhil1999

I unable to understand the input and output format of your question as it doesn’t match with the one specified in the question.
Can you explain your approach?

In case you have understood the question wrong, please refer to the following:

Let’s understand this problem with the help of two examples:
1.
arr[] = {5, 2, 1, 3, 2}
k = 4
Output :
5 2 5 1 2 5 1 2 3 5 2 1 3 5
Explanation:
Given array is arr[] = {5, 2, 1, 3, 2} and k = 4
Step 1:After reading 5, there is only one element 5 whose frequency is max till now. so print 5.
Step 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.
Step 3: After reading 1, we will have 3 elements 1,2 and 5 with same frequency, so print 1 2 5.
Step 4: Similarly after reading 3, print 1 2 3 5
Step 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.

arr[] = {5, 2, 1, 3, 4}
k = 4
Output :
5 2 5 1 2 5 1 2 3 5 1 2 3 4
Explanation:
Given array is arr[] = {5, 2, 1, 3, 4} and k = 4
Step 1:After reading 5, there is only one element 5 whose frequency is max till now. so print 5.
Step 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.
Step 3: After reading 1, we will have 3 elements 1,2 and 5 with same frequency, so print 1 2 5.
Step 4: Similarly after reading 3, print 1 2 3 5
Step 5: After reading last element 4, since 4 is smaller than 5. So we keep 4 at the top and then rest of element with same frequency in sorted order and will discard 5 as k=4. So print, 2 1 3 4.

Approach:

  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.
2 Likes
#5

see here in my code…i am not trying to solve the question directly …but just want to make a custom comparator that would just order the heap in the way…the question demads provided we are manually inputing the numbers and their frequencies…
so in a nut shell i am just experimenting with the custom comparator as i haven’t understood it fully

#6

Hello @ynikhil1999,

As per what I have understood:

  1. There is a problem with the order in which the priority queue has been popped.
    It should print the pairs in the order:
    5 8
    2 5
    1 2
    Your Output is:
    2 5
    5 8
    1 2
    Reason:
    Because the inbuilt comparator looks for the condition (a<b) :
    a. return true if ab

    But in your comparator, you are returning a>b for the second case, which will return true indicating the priority queue that the first element is greater though it is not.
    if(a.second>b.second)
    {
    // cout<<a.second<<" “<<b.second<<” : "<<endl;
    return a>b;
    }
    Solution:
    return a<b;

You can check it here:

Hope, this would help.
If you still have any doubts, feel free to ask.

1 Like
#7

5 8
2 5
1 2

even this is also sorting upon the basis of first element…
but i want that…if the second no is greater…then sort acc to that…but if second number is same…then sort acoording to the first no…

so bro can u plzz…code such a comparator…plzzzz

#8

Sure @ynikhil1999,

You have created a similar comparator before in the question, string sort.
Try to recall that.
Same would work here also.

BTW, i have modified your code as per your requirement, you can check:

This would surely solve your problem.
Give a like, if you are satisfied.

1 Like
#9

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.