数学类
数学类的解法一般泛用性低，但巧妙。
水库算法
有一个链表，我们不知道其长度，设计一个算法对其节点做均匀随机采样。要求最多做一次遍历。
水库算法：遍历这个链表，在遍历到第i个节点时，有 $\dfrac{1}{i}$ 的概率选择这个节点覆盖掉之前的节点选择。
(整个算法只需要遍历一次)
水库算法随机性的证明：
长度为n的链表，第i个节点被选中的充要条件是：第i个节点被选中，并且之后遍历第i+1到n个节点时，都未被替换。
这个概率就是 $\dfrac{1}{i}\times\dfrac{i}{i+1}\times\dfrac{i+1}{i+2}\times…\times\dfrac{n-1}{n}=\dfrac{1}{n}$
技巧类
最大回文
基础方法:遍历，第i到j是否是回文，遍历过程复杂度 $O(n^2)$，判断是否是回文复杂度是 O(n) ，全局复杂度 $O(n^3)$
改进1:遍历一次，每个值是回文的中心，复杂度是O(n)，判断回文的复杂度O(n)，全局复杂度是 $O(n^2)$
改进2:假设已经判断出n点左右各l距离是回文，那么右边n+l范围内是否是回文其实与左边n-l范围内的情况完全一样。那么n到n+l这个范围内的情况就不用判断了。
改进3:其实回文可以是奇数或偶数，只需要隔板插入一个字符串即可统一为一种算法。复杂度 O(n)
40亿个单词找某个单词，并且给定某个前缀，找到多少个单词的前缀是这个
其实就是 trie 树
不用1个节点对应1个字母，也可以1个节点对应一段字母。例如，in-intrest-intrested/interesting，这样。
40亿个数字找TOP1000
遍历40亿个数字，维护一个TOP1000的堆
如果允许多台机器，可以上分布式，每个 partition 求 top1000，最后合并
B+树基本知识
底层是mysql，redis是缓存；dao层操作mysql，cache层操作redis
- 如果某个sql查询比较慢，怎么办？
- 如果条件字段有索引，建立索引
- mysql底层是 B+ 树，查询复杂度 log(n)
- 如果用 hash，复杂度是 O(1)
