Design:
class TopK {
void insert(String s);
List getTop(int k);
}
[Solution]
三种solution: quick select, priority queue, bst.
[Solution #1] – quick select.
O(1) insert
O(n) query (worst case O(n^2))
[Solution #2] – priority queue.
O(logn) insert
O(klogn) query
注意这个解法就是维护一个priority queue来存所有insert的string，而不是另外维护一个size为k的priority queue，因为每次call getTop时k是不一样的。
另外在query的时候，本来想的是用iterator去遍历，这样就避免了poll出来又要offer进去的情况。但是查了java doc之后发现priority queue的iterator不保证任何顺序，所以只能poll出来再offer进去。
这个解法Insert和query time都不是很理想。所以一般不会考虑。面试的时候提一下就好了。
[Solution #3] – BST
BST绝对是练习活学活用，举一反三最好的方法，因为很多看似跟bst没有半毛钱关系的题目，都能用bst来解。
bst的思路就是每个TreeNode存3个variables: string本身，freqCount以及rightSize。
class TNode {
String s;
int freq;
int rightSize;
TNode left;
TNode right;
}
Query的方法有2种:
1. 当query的时候，从right most node开始中序遍历k个。
- 另一种query方法是利用rightSize，从root开始：
(1) if root.rightSize == k, then return 整个right subtree
(2) if root.rightSize > k, then return getK(root.right, k)
(3) if root.rightSize < k, then Add the whole right subtree to result List first.
3.1 if root.freq + root.rightSize >= k, then Add root.val to result List until result.size() == k
3.2 if root.freq + root.rightSize < k, then Add all root.val to result List, then Add getK(root.left, k – root.rightSize – root.freq) to result List.
两种方法的复杂度一样
O(logn) insert
O(n) query
但是这题实现起来难度略大。因为bst结构是根据freqency来构建的，在insert过程中如果某个node的freq变化了，很可能tree的结构也要跟着变。而且存在frequency一样的情况。当然可以把freq一样的node放在right child上，但是维护这个bst实在太麻烦了。
但是query的复杂度可以guarantee O(n)
Read full article from Google – TopK
