Get K most frequent tokens from a token stream This is an interview problem:


  Given a token stream, find the K most frequent tokens in real time (the order of these k tokens does not matter).


My approach:


Use a hash table (unordered_map in c++) to maintain the frequency of tokens.
Use a min heap to maintain the k most frequent tokens.
Update the hash table and the min heap dynamically.


I feel my code is not concise enough and I am not experienced using some new features in C++11. I would be very appreciative if anyone could any suggestions on the algorithm, coding style, object-oriented design, etc.

    class TokenCounter{
    public:
    void MaxKFrequent(int k) {
      std::unordered_map&lt;std::string, TokenInfo::TokenInfoPtr&gt; hash_table;
      std::deque&lt;TokenInfo::TokenInfoPtr&gt; min_heap;

      string token;
      while(std::cin &gt;&gt; token) {
        // update hashtable
        if(hash_table.find(token) == hash_table.end()) {
          hash_table[token] = TokenInfo::TokenInfoPtr(new TokenInfo(token));
        } else {
          hash_table[token]-&gt;increase_cnt();
        }

        // update min-heap
        TokenInfo::TokenInfoPtr&amp; token_info = hash_table[token];
        // if already in the heap -&gt; heaplify directly
        if(token_info-&gt;get_in_heap()) {
          std::make_heap(min_heap.begin(), min_heap.end(), TokenInfoCmp());
        } else {
        // if not in the heap
          if(min_heap.size() &lt; k) {
          // if heap is not full -&gt; insert into heap directly
            token_info-&gt;set_in_heap(true);
            min_heap.push_back(token_info);
            std::push_heap(min_heap.begin(), min_heap.end(), TokenInfoCmp());
          } else {
          // if heap is full
              // if count &gt; heap top -&gt; delete heap top &amp; insert into heap
            if(token_info-&gt;get_cnt() &gt; min_heap.front()-&gt;get_cnt()) {
              token_info-&gt;set_in_heap(true);
              min_heap.push_back(token_info);

              min_heap[0]-&gt;set_in_heap(false);
              min_heap.pop_front();

              std::make_heap(min_heap.begin(), min_heap.end(), TokenInfoCmp());
            }
          }
        }

        for(auto&amp; token_ptr : min_heap) {
          std::cout &lt;&lt; token_ptr-&gt;get_token() &lt;&lt; " ";
        }
        std::cout &lt;&lt; std::endl;
      }
    }

    private:   
    class TokenInfo {
      public:
        using TokenInfoPtr = std::shared_ptr&lt;TokenInfo&gt;;
        TokenInfo(std::string token) : token_(token) {}

        int get_cnt() const {return cnt_;}
        void increase_cnt() {cnt_ += 1;}

        bool get_in_heap() const {return in_heap_;}
        void set_in_heap(bool in_heap) {in_heap_ = in_heap;}

        std::string get_token() const {return token_;}

      private:
        std::string token_;
        int cnt_ = 1;
        bool in_heap_ = false;
    };

    struct TokenInfoCmp {
      bool operator() (TokenInfo::TokenInfoPtr a, TokenInfo::TokenInfoPtr b) const {
        return a-&gt;get_cnt() &gt; b-&gt;get_cnt();
      }
    };
  };
I feel my code is not concise enough


The feeling is mutual.

I feel that this can be expressed much more succinctly.


  I am not experienced using some new features in C++11.


You seem to be using range based for so not bad in that regards.

But. You do "probably" have a memory leak.

hash_table[token] = TokenInfo::TokenInfoPtr(new TokenInfo(token))
                                            ^^^^


Don't see a delete anywhere in the code. To be honest I doubt you actually need that new at all. If you just made your container hold objects all these problems would go away.


  I would be very appreciative if anyone could any suggestions on the algorithm, coding style, object-oriented design, etc.


Not sure that heap is the correct structure.

Sure it does sound correct initially. But you can increase the count of items that are already in the heap (which means you have to rebuild it from scratch).

I would just keep a sorted list of the top n items. When a count increases you at most need to move one item in the list.

I can't really review more than that because your code snipet is missing the most important thing. TYPE information.