Build tries from a list of pairs. Save top 10 for each node.

Have you met this question in a real interview?

Yes

Example

Given a list of

<
"abc", 2
>
<
"ac", 4
>
<
"ab", 9
>

Return<a[9,4,2]<b[9,2]<c[2]<>>c[4]<>>>, and denote the following tree structure:

         Root
         / 
       a(9,4,2)
      /    \
    b(9,2) c(4)
   /
 c(2)

/**
 * Definition of TrieNode:
 * class TrieNode {
 * public:
 *     TrieNode() {}
 *     map<char, TrieNode*> children;
 *     vector<int> top10;
 * };
 */
class TrieService {
private:
    TrieNode* root;

public:
    TrieService() {
        root = new TrieNode();
    }

    TrieNode* getRoot() {
        // Return root of trie root, and 
        // lintcode will print the tree struct.
        return root;
    }

    void insert(string& word, int frequency) {
        // Write your code here
        TrieNode* node = root;
        for(auto ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children.insert(make_pair(ch, new TrieNode()));
            }
            node = node->children[ch];
            addFrequency(node->top10, frequency);
        }
    }

private:
    void addFrequency(vector<int>& top10, int frequency) {
        top10.push_back(frequency);
        for (int i = top10.size() - 1; i > 0; --i) {
            if (top10[i - 1] >= top10[i]) {
                break;
            }
            swap(top10[i - 1], top10[i]);
        }
        if (top10.size() > 10) {
            top10.pop_back();
        }
    }
};