LintCode-559: Trie Service (System Design題)

1. Trie Service

Build tries from a list of <word, freq> pairs. Save top 10 for each node.

Example

Example1

Input:

<“abc”, 2>

<“ac”, 4>

<“ab”, 9>

Output:<a[9,4,2]<b[9,2]<c[2]<>>c[4]<>>>

Explanation:

Root

/

a(9,4,2)

/

b(9,2) c(4)

/

c(2)

Example2

Input:

<“a”, 10>

<“c”, 41>

<“b”, 50>

<“abc”, 5>

Output: <a[10,5]<b[5]<c[5]<>>>b[50]<>c[41]<>>

這個Trie的實作好像跟那種經典的每個節點分出26個分叉的Trie不太一樣。

insert()的代碼很重要。下次再學習。

/**
 * 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;
    }

    //important code    
    void insert(string& word, int frequency) {
        TrieNode *p = root;
        for (int i = 0; i < word.size(); ++i) {
            if (p->children.find(word[i]) == p->children.end()) {
                p->children[word[i]] = new TrieNode();
            }
            p = p->children[word[i]];
            helper(p->top10, frequency);
        }
    }
    
    
    //insert to the right place, top10 is sorted from large to small
    void helper(vector<int>& top10, int freq) {
        top10.push_back(freq);
        int top10Size = top10.size();
        if (top10Size == 1) return;
        
        //start from top10Size - 2 as top10Size - 1 is already freq
        for (int i = top10Size - 2; i >= 0; --i) {
            if (top10[i] < top10[i + 1]) {
                int temp = top10[i];
                top10[i] = top10[i + 1];
                top10[i + 1] = temp;
            } else {
                break;
            }
        }
        
        if (top10Size > 10) top10.pop_back();
    }
    
};