Coding
I was doing coding for a while. It is lot of fine. Today I got stuck on a simple question.
Given a sequence of company names, output the company which mentioned most time in history. This is not that hard. However, I got stuck by trying to provide a more complicated solution which introduce using the priority queue. Actually it is not necessary at this stage. Reference code is below.
#include <iostream>
#include<map>
#include<unordered_map>
#include <climits>
using namespace std;
class MostMentionedCompany{
private:
unordered_map<string, int> cnt;
pair<string, int> max_company_;
public:
MostMentionedCompany(){
max_company_=make_pair("dummy", INT_MIN);
}
void update_company(string company){
cnt[company]++;
if(cnt[company]>max_company_.second || (cnt[company]==max_company_.second && company.compare(max_company_.first)<0)){
max_company_ = make_pair(company, cnt[company]);
}
}
string get_most_mentioned_company(){
return max_company_.first;
}
};int main()
{
MostMentionedCompany most_mentioned_company;
most_mentioned_company.update_company("google");
most_mentioned_company.update_company("google");
most_mentioned_company.update_company("facebook");
most_mentioned_company.update_company("facebook");
cout<<(most_mentioned_company.get_most_mentioned_company())<<endl;return 0;
}
The hard part is how to get top k most frequently mentioned company in real time. This is tricky. If we want to get the top K company names in real time. I don’t know how to solve the problem. There is a similar problem in leetcode. Top K words. By using priority queue, the complexity is O(nlogk).
Actually, we can use set to solve this top k frequency problem. By adjusting the code a little bit, we can do it on the fly. Detail can be found here.
