fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void increase(int contentId, unordered_map<int, int> &contentIdToPop, map<int, set<int>> &popToContentIdList) {
  5.  
  6.         if(contentIdToPop.find(contentId) != contentIdToPop.end()) {
  7.  
  8.             int oldPop = contentIdToPop[contentId];
  9.             popToContentIdList[oldPop].erase(contentId);
  10.             if (popToContentIdList[oldPop].empty()) {
  11.                 popToContentIdList.erase(oldPop);
  12.             }
  13.  
  14.             int newPop = oldPop + 1;
  15.             contentIdToPop[contentId] = newPop;
  16.             popToContentIdList[newPop].insert(contentId);
  17.         } else {
  18.             int newPop = 1;
  19.             contentIdToPop[contentId] = newPop;
  20.             popToContentIdList[newPop].insert(contentId);
  21.         }
  22. }
  23.  
  24. void decrease(int contentId, unordered_map<int, int> &contentIdToPop, map<int, set<int>> &popToContentIdList) {
  25.  
  26.         if(contentIdToPop.find(contentId) != contentIdToPop.end()) {
  27.  
  28.             int oldPop = contentIdToPop[contentId];
  29.             popToContentIdList[oldPop].erase(contentId);
  30.             if (popToContentIdList[oldPop].empty()) {
  31.                 popToContentIdList.erase(oldPop);
  32.             }
  33.  
  34.             int newPop = oldPop - 1;
  35.             if(newPop == 0) {
  36.                 contentIdToPop.erase(contentId);
  37.             } else {
  38.                 contentIdToPop[contentId] = newPop;
  39.                 popToContentIdList[newPop].insert(contentId);
  40.             }
  41.  
  42.         } else {
  43.             cout<<"Content Id not found"<<endl;
  44.         }
  45. }
  46.  
  47. int getMostPopular(map<int, set<int>> popToContentIdList) {
  48.     if(popToContentIdList.empty()) {
  49.         return -1;
  50.     }
  51.     set<int> mostPopularContent = popToContentIdList.rbegin()->second; 
  52.  
  53.     // all content Ids are most popular in this set, so return any one, for tie breaking , can return first element or last element
  54.     return *mostPopularContent.begin();
  55. }
  56.  
  57. int main() {
  58.  
  59.  
  60.     unordered_map<int, int> contentIdToPop;
  61.     map<int, set<int>> popToContentIdList;
  62.  
  63.     increase(7, contentIdToPop, popToContentIdList);  //  7->1                   1->(7,)
  64.     increase(7, contentIdToPop, popToContentIdList);  //  7->2                   2->(7,)
  65.     increase(8, contentIdToPop, popToContentIdList);  //  7->2, 8->1             1->(8,) , 2->(7,)
  66.     cout<<getMostPopular(popToContentIdList)<<endl;  // Ans = 7               
  67.  
  68.  
  69.     increase(8, contentIdToPop, popToContentIdList);   // 7->2, 8->2               2->(7,8,)
  70.     increase(8, contentIdToPop, popToContentIdList);   // 7->2, 8->3               2->(7,) , 3->(8,)
  71.     cout<<getMostPopular(popToContentIdList)<<endl;   // Ans = 8
  72.  
  73.     decrease(8, contentIdToPop, popToContentIdList);   // 7->2, 8->2               2->(7,8,)
  74.     decrease(8, contentIdToPop, popToContentIdList);   // 7->2, 8->1               1->(8,) , 2->(7,)
  75.     cout<<getMostPopular(popToContentIdList)<<endl;   // Ans = 7
  76.  
  77.     decrease(7, contentIdToPop, popToContentIdList);  // 7->1, 8->1                1->(7,8,)
  78.     decrease(7, contentIdToPop, popToContentIdList);  // 8->1                      1->(8,)
  79.     decrease(8, contentIdToPop, popToContentIdList);   // empty                     empty
  80.     cout<<getMostPopular(popToContentIdList)<<endl;   // Ans = -1
  81.  
  82.     increase(7, contentIdToPop, popToContentIdList);  //  7->1                     1->(7,)
  83.     cout<<getMostPopular(popToContentIdList)<<endl;  // Ans = 7 
  84.  
  85.  
  86.  
  87.     return 0;
  88.  
  89. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7
8
7
-1
7
https://ideone.com/chY84R
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!