昨天下午去深信服参加了面试，只有两个面试官，一个是面软件开发的，一个是面算法的。
我去到的时候3点30分，一个华师的研究生师兄和一个华工的霸王面同学在等，就跟他们聊了一下。
4点45分才轮到我。
面试官先让我自我介绍，我从第三句起就开始说我喜欢算法，最后说到ACM。然后那个面试官就问我ACM比赛中印象最深的是哪几道题，我就说了那道11倍数还有打球的两道水题。然后他就根据笔试试题上面的问题来问我了。基本上都是先让我重新说一下我的思路，然后再根据我的思路来提问题。
1.假设路由器中有n条系统路由，每个路由条目由目标IP和子网掩码组成，现在需要转发网络的数据，请设计一个高效的路由寻找算法。
他另外提问的是：如何在路由器存储的那么多路由地址中查找到要转发的地址?最终我说的方法是用一个平衡二叉树进行查找，没办法，我对查找没研究，只是上午看哈希函数时不小心看到了平衡二叉树。
2.Web Cache(网页内容查找)，要把出现最多的网页的内容存在内存中，如果查不到内容，则放到磁盘里，如果磁盘满了，则把冷网页淘汰掉。请设计一个算法。
答案：设计一个计数器，每使用一次就自增1，当磁盘到达一定量时，把一定的计数器最小的网页从磁盘删去。
他另外提问的问题是：如何查找到某一个网页的Url?也还是类似上面的查找问题。不过看我没怎么主动回答，他也没有深问。
3.请设计一方案，尽可能短在10GB源串(数据保存在硬盘中)寻找某模式串(大小4KB)的最大匹配，在开始模式匹配前，可以对10GB数据进行分析处理，中间的分析数据可以存放在100MB左右的内存内。
他问我对这道题有没有什么想法(我试卷没做，因为只需要三道做2道就好)。这个我暂时想不出来，我就跟他说，暂时没有思路，除非让我多想一下。不过他还是问下一个问题了。
二：算法基础题
1.有a,b,c,d,e五个袋子里面装了26个玻璃球，没有空的也没有相同玻璃球数量的袋子，已知道a+e,b+c,c+d都超过了11个玻璃球，而 a+c小于11个玻璃球，请问有多少种可能的由小到大的组合?(例如1，3，5，7，10，但是1，5，3，7，10不是正确的组合)。解题空有6个空，但不一定都要填。
答：(1)1，3，4，8，10
(2)1，2，3，9，11
(3)2，3，4，8，9
(4)1，2，4，9，10
这道题他居然以为是我以前做过的，汗死，天大的耻辱啊。我再给他讲了一下我的思路，看他才有点相信我是真的第一次做的样子。
2.假设Hash函数是随机的，在n个桶中插入元素后平均占用多少个桶?(用数学表达式)
他跟我说了这道题的重大意义，他说这是一个评判该哈希函数好坏的一个依据，我自己讲了哈希函数的基本意义。
