2
\$\begingroup\$

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:

  1. Use a hash table (unordered_map in c++) to maintain the frequency of tokens.
  2. Use a min heap to maintain the k most frequent tokens.
  3. 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<std::string, TokenInfo::TokenInfoPtr> hash_table;
      std::deque<TokenInfo::TokenInfoPtr> min_heap;

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

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

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

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

        for(auto& token_ptr : min_heap) {
          std::cout << token_ptr->get_token() << " ";
        }
        std::cout << std::endl;
      }
    }

    private:   
    class TokenInfo {
      public:
        using TokenInfoPtr = std::shared_ptr<TokenInfo>;
        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->get_cnt() > b->get_cnt();
      }
    };
  };
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the advice! TokenInfoPtr is actually a smart pointer and that's why I think I don't need the "delete" here. A sorted list does work but I suppose the worst case complexity is O(n^2), which is less efficient than maintaining a heap. Please correct me if I miss anything! \$\endgroup\$ – yvetterowe Aug 25 '15 at 14:32
  • \$\begingroup\$ @yvetterowe: Than rather than new I suggest you use make_shared() or make_unique() so that it is obvious. \$\endgroup\$ – Martin York Aug 25 '15 at 17:04
  • \$\begingroup\$ A sorted list is O(n.log(n)) to sort. But thats if you sort it from scratch each time. What you are going to be doing here is maintaining a sorted list. Which in reality is O(1) as in most cases you will be moving an item up one place in the sorted list after a token is retrieved. Worst case O(n) (if all tokens have the same count then you have to move 1 item from the bottom to the top of the list. Or worst case of O(n) if you implement it the brute force way. \$\endgroup\$ – Martin York Aug 25 '15 at 17:10
  • \$\begingroup\$ You would need to re-balance the tree after each item is added O(log n). But there are no standard functions to do that. So in reality you need to write your own or rebuild the heap each time a value in it changes. O(n.log(n)) \$\endgroup\$ – Martin York Aug 25 '15 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.