Lintcode 559. 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]<>>

Code (Java):

/**
 * Definition of TrieNode:
 * public class TrieNode {
 *     public NavigableMap<Character, TrieNode> children;
 *     public List<Integer> top10;
 *     public TrieNode() {
 *         children = new TreeMap<Character, TrieNode>();
 *         top10 = new ArrayList<Integer>();
 *     }
 * }
 */
public class TrieService {

    private TrieNode root = null;

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

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

    // @param word a string
    // @param frequency an integer
    public void insert(String word, int frequency) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            TrieNode child = p.children.getOrDefault(c, new TrieNode());
            PriorityQueue<Integer> pq = new PriorityQueue<>(child.top10);
            if (pq.size() < 10) {
                pq.offer(frequency);
            } else {
                if (frequency > pq.peek()) {
                    pq.poll();
                    pq.offer(frequency);
                }
            }

            List<Integer> sortedList = new ArrayList<>(pq);
            Collections.sort(sortedList, Collections.reverseOrder());
            child.top10 = sortedList;
            p.children.put(c, child);
            p = child;
        }
    }
}